Chimera全同态加密加密转换方案学习

admin • 2021-11-24 21:10 • 区块链

全同态加密

众所周知，对同态加密的数据进行计算再解密，所得到的的结果与解密再计算是相同的。那么，同态加密中对计算（即同态评估）会有什么样的限制呢？

目前已知可以进行的同态加密计算类型大致有三种：

整数计算
近似计算（定点数计算）
二进制计算（电路计算）

整数计算

给定两个明文

∈

m_1, m_2 in mathbb{Z}

$m_{1}, m_{2} \in Z$ 的加密，可以计算：

整数计算是可以使用 SIMD 进行加速的，给定两个明文

∈

m_1, m_2 in mathbb{Z}

$m_{1}, m_{2} \in Z$ 的加密，我们可以计算：

元素之间的加法： $m_1 + m_2 m1+m2$
元素之间的乘法： $m_1 times m_2 m1×m2$
置换操作： $(m_1) σ(m1)$

这里的 SIMD 加速的思想早在 BV 方案中就已经被提出和使用：（在多项式环上使用中国剩余定理）让密文上有很多槽 (slots) ，就可以把明文数组插进槽中，对两个密文进行同态加操作的时候，可以对数组向量按分量进行同态加操作，来提高计算的效率与降低密文转换率。

然而，单例的加法和乘法都是完备的，但是如果我们把数据看成数组形式的话，加法和乘法就不是完备的了，例如同一个数组中不同的元素之间无法进行运算。因此，需要引入同态置换操作

(

)

sigma (m_1)

$σ (m_{1})$ 才能在加密数组上实现完备的操作。

通常来说，取任意精度的整数对同态加密来说并不是很友好。例如在 C 语言中，取模

p = 2^{32}

$p = 2^{32}$ ，则有可能在计算时发生溢出，如

−

2^{30} + 2^{30} = -2^{31}

$2^{30} + 2^{30} = - 2^{31}$ 。

近似计算

与浮点数相比，定点数对同态加密更友好（CKKS 方案中选择了定点数）。

将定点数表示为：

⋅

x = m sdot 2^{tau}

$x = m \cdot 2^{τ}$ ，其中

∈

−

⋅

m in 2^{-rho} sdot mathbb{Z}

$m \in 2^{- ρ} \cdot Z$ 并且

≤

∣

0 leq | m | < 1

$0 \leq ∣ m ∣ < 1$

明文参数有：

其中

tau

$τ$ 是公开的，因此对于同态加密来说较为友好。但这也增加了计算时数据上溢和下溢的风险。

如果在这里也希望能够使用 SIMD 的思想加速，即实现以下三种运算：

（也许是 SIMD）定点数加法
（也许是 SIMD）定点数乘法
置换操作

然而实际的操作可能比你想象的要复杂很多。例如给定

(

)

(

)

(m_1, tau_1), (m_2, tau_2)

$(m_{1}, τ_{1}), (m_{2}, τ_{2})$ 和

tau

$τ$ ，需要计算

rho

$ρ$ bits 精度的

⋅

m sdot 2^{tau} = m_1 sdot 2^{tau_1} + m_2 sdot 2^{tau_2}

$m \cdot 2^{τ} = m_{1} \cdot 2^{τ_{1}} + m_{2} \cdot 2^{τ_{2}}$ ，除了需要加法运算之外，则需要非线性函数：右移和舍入。

电路计算

给定

∈

{

}

b_1, b_2 in { 0, 1 }

$b_{1}, b_{2} \in {0, 1}$ ，同态运算为：

在这里考虑三种电路：

布尔电路（完全二进制的电路）：由各种门电路组成，有 NAND，AND，OR，NOT，XOR，MUX
查找表（混合）：给定 $(v_0, ..., v_n) (v0,...,vn) 和 i i i ，返回 v i v_i vi$
决策图/自动机（混合）：每次读入一个 bit ，更新内部状态。返回最终状态的一些信息或者整个路径。

环面上的LWE困难问题

多项式环

首先给出整数多项式、实数多项式和复数多项式的定义：

整数多项式 $mathbb{Z}_N[X] = mathbb{Z}[X] / (X^N + 1) ZN[X]=Z[X]/(XN+1) ，是系数是整数的多项式模 X N + 1 X^N + 1 XN+1 的环$
实数多项式 $mathbb{R}_N[X] = mathbb{R}[X] / (X^N + 1) RN[X]=R[X]/(XN+1) ，是系数是实数的多项式模 X N + 1 X^N + 1 XN+1 的环$
复数多项式 $mathbb{C}_N[X] = mathbb{C}[X] / (X^N + 1) CN[X]=C[X]/(XN+1) ，是系数是复数的多项式模 X N + 1 X^N + 1 XN+1 的环$

举个例子说明，当

N = 2

$N = 2$ 时，实数多项式上的运算可以为：

(

1.2

2.3

)

⋅

(

3.2

4.1

)

3.84

12.28

9.42

12.28

−

5.59

(

)

(1.2 + 2.3X) sdot (3.2 + 4.1X) = 3.84 + 12.28X + 9.42X^2 = 12.28X - 5.59 , mod , (X^2 + 1)

$(1.2 + 2.3 X) \cdot (3.2 + 4.1 X) = 3.84 + 12.28 X + 9.42 X^{2} = 12.28 X - 5.59 m o d (X^{2} + 1)$

可以观察到，实数多项式

(

[

]

)

(mathbb{R}_N[X], +, times)

$(R_{N} [X], +, \times)$ 和复数多项式

(

[

]

)

(mathbb{C}_N[X], +, times)

$(C_{N} [X], +, \times)$ 都是环：

$(mathbb{R}_N[X], +) (RN[X],+) 和 ( C N [ X ] , + ) (mathbb{C}_N[X], +) (CN[X],+) 都是群$

为了继续在槽上进行操作，我们需要使用系数打包(Coefficient packing) 和槽打包 (Slot packing) 的技术，将这两个环同构到

mathbb{R}

$R$ -向量空间上：

Coefficient packing ：使用系数提取
Slot packing：使用 $X^N + 1 XN+1 的本原根$

环面与环面上的LWE加密在TFHE：环面上全同态加密方案学习笔记1中：https://blog.csdn.net/qq_38076131/article/details/107896239

Chimera的框架

那么我们如何选择同态加密方案呢？

每种类型的方案有不同的优势：

BGV/Helib 方案：善于使用 SIMD 在有限域上进行计算
B/FV 方案：善于使用 SIMD 在向量模
HEAAN(CKKS) 方案：善于使用 SIMD 进行定点数运算
TFHE 方案：善于按位评估、计算布尔逻辑、比较、阈值计算、计算复杂电路等……

有没有什么方法能够使用这些方案的优势，同时避免它们的劣势呢？

Mariya Georgieva 等人给出了一个解决方案：Chimera

在环面上定义明文空间
在密文表达之间转换
在 TFHE 、B/FV 、HEAAN 之间建立桥梁

在上述方案中，明文种类有：电路的布尔值、整数摸

(

)

(mathbb{Z}/pmathbb{Z})^n

$(Z / p Z)^{n}$ 、定点数

mathbb{C}

$C$ 。那么，我们怎么用

[

]

mathbb{T}_N[X]

$T_{N} [X]$ 来表示所有的明文呢？

电路转换为 $mathbb{T}_N[X] TN[X]$

在 TFHE 的层次同态中，作者使用 CMux 门与 0，1 这个图灵完备的门电路组合构造了层次 TFHE ，原因是它可以几乎没有消耗的做二进制选择(噪声呈线性增长)。CMux 门的密文类型如下图所示：

该门的噪声增长如下图所示：

其中 CMux 门的表达式为：

(

)

⊡

(

−

)

CMux(C, d_1, d_0) = C boxdot (d_1 - d_0) + d_0

$C M u x (C, d_{1}, d_{0}) = C ⊡ (d_{1} - d_{0}) + d_{0}$

使用很多这样的 CMux 门可以构造和评估任意的查找表/布尔函数，进而评估任意函数

→

f:mathbb{B}^d rightarrow mathbb{T}^s

$f : B^{d} \to T^{s}$

可以对该查找表进行横向/纵向打包（与TFHE方案中相同）。

整数转换为 $mathbb{T}_N[X] TN[X]$

我们知道整数多项式模

$p$ ：即

[

]

mathbb{Z}_N[x] , mod , p

$Z_{N} [x] m o d p$ 是系数是模

$p$ 整数的多项式环模

X^N + 1

$X^{N} + 1$ 。

如果

X^N + 1

$X^{N} + 1$ 有

$N$ 个根，则

mathbb{Z}/pmathbb{Z}

$Z / p Z$ 是和

[

]

mathbb{Z}_N[X] , mod , p

$Z_{N} [X] m o d p$ 同构的（可以用模

$p$ 的槽来模拟）。

举个栗子：

关于

$p$ 的限制：

在 BFV 方案中，
在 BGV 方案中，任意

我们知道有同构：

(

)

≃

[

]

≃

[

]

(mathbb{Z} / pmathbb{Z})^N simeq mathbb{Z}_N [X] , mod , p simeq frac{1}{p} mathbb{Z}_N[X] , mod , 1

$(Z / p Z)^{N} ≃ Z_{N} [X] m o d p ≃ \frac{1}{p} Z_{N} [X] m o d 1$

于是我们可以使用

frac{1}{p}

$\frac{1}{p}$ 的整数倍构造明文空间

mathcal{M}

$M$ ：

于是明文上的加法

(

)

(

)

addition(mu_1(X), mu_2(X))

$a d d i t i o n (μ_{1} (X), μ_{2} (X))$ ：

(

)

(

)

(

)

(

)

mu_1(X) + mu_2(X) := mu_1(X) + mu_2(X) , mod , 1

$μ_{1} (X) + μ_{2} (X) : = μ_{1} (X) + μ_{2} (X) m o d 1$

明文上的蒙哥马利乘法

(

)

(

)

(

)

product(Montgomery) (mu_1(X), mu_2(X))

$p r o d u c t (M o n t g o m e r y) (μ_{1} (X), μ_{2} (X))$ ：

(

)

⊠

(

)

⋅

(

)

⋅

(

)

mu_1(X) boxtimes_p mu_2(X) := p sdotmu_1(X) sdot mu_2(X) , mod , 1

$μ_{1} (X) ⊠_{p} μ_{2} (X) : = p \cdot μ_{1} (X) \cdot μ_{2} (X) m o d 1$

这个方案看似很简单，但是在实际操作过程中会遇到一些问题。

例如选取参数

p = 3, mu_1 = 1/3, mu_2 = 2/3

$p = 3, μ_{1} = 1 / 3, μ_{2} = 2 / 3$ 时

对于所有整数 $I_1, I_2 I1,I2 ，计算外积 3 ( I 1 + 1 / 3 ) ( I 2 + 2 / 3 ) = I + 2 / 3 = 2 / 3 m o d 1 3(I_1 + 1/3)(I_2 + 2/3) = I + 2/3 = 2/3 , mod , 1 3(I1+1/3)(I2+2/3)=I+2/3=2/3mod1$
当我们在噪声下计算小元素时：
当我们在噪声下计算大元素时：

因此，我们需要明文的小表达式来保证结果的正确性；即我们需要将密文限制为

[

]

mathbb{R}[X]

$R [X]$ 上的小的表达式；以及保证

≫

frac{1}{p} gg noise

$\frac{1}{p} ≫ n o i s e$

在这种情况下，同态操作的定义为：

同态加法

c

1

=

(

a

1

,

b

1

)

,

c

2

=

(

a

2

,

b

2

)

c_1 = (a_1, b_1), c_2 = (a_2, b_2)

$c_{1} = (a_{1}, b_{1}), c_{2} = (a_{2}, b_{2})$

(

a

,

b

)

=

(

a

1

+

a

2

,

b

1

+

b

2

)

(a, b) = (a_1 + a_2, b_1 + b_2)

$(a, b) = (a_{1} + a_{2}, b_{1} + b_{2})$
同态积

c

1

=

(

a

1

,

b

1

)

,

c

2

=

(

a

2

,

b

2

)

c_1 = (a_1, b_1), c_2 = (a_2, b_2)

$c_{1} = (a_{1}, b_{1}), c_{2} = (a_{2}, b_{2})$

定点数转换为 $mathbb{T}_N[X] TN[X]$

通过添加以下三个标签/参数可以对 HEAAN 密文进行表示，下面定义这些标签：

$2^{tau} z=m⋅2τ，其中 τ tau τ 是公开的， m ∈ 2 − ρ ⋅ ( Z + i Z ) m in 2^{- rho} sdot (mathbb{Z} + i mathbb{Z}) m∈2−ρ⋅(Z+iZ) ，其中 0 ≤ ∣ m ∣ < 1 0 leq |m| < 1 0≤∣m∣<1 。$

下图表示了如何使用前面定义的标签定义 (带噪声的) 明文空间：

如果使用连续的方法来表示明文：

(

)

∗

(

)

x times y = Lift(x) * Lift(y) , mod , 1

$x \times y = L i f t (x) * L i f t (y) m o d 1$

优势1：这种方法可以保留 (或减少) 间隔 $frac{1}{2^L}, frac{1}{2^L}] [−2L1,2L1]$
优势2：
不足：但是

如果使用离散的方法来表示明文：舍入

a, b

$a, b$ (进而舍入

$μ$ ) 到确切的

frac{1}{q}

$\frac{1}{q}$ 的倍数，其中

≈

q approx 2^{L + rho}

$q \approx 2^{L + ρ}$

优势1：这是一个环 $mathbb{Z}_N[X] , mod , 1 q1ZN[X]mod1 ，可以避免使用 L i f t Lift Lift$
优势2：可以进行蒙哥马利乘法 $q(b_1 - s sdot a_1)(b_2 - s sdot a_2) q(b1−s⋅a1)(b2−s⋅a2)$
不足：会扩大区间 $frac{1}{2^L}, frac{1}{2^L}] rightarrow [- frac{1}{2^{L - rho}}, frac{1}{2^{L - rho}}] [−2L1,2L1]→[−2L−ρ1,2L−ρ1] ，只能进行 L L L 次乘法$

小结

挂两张论文中的图片，讲的很清楚：

参考文献

参考论文：Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316-338.(2018与2020两个版本)

参考视频：https://www.youtube.com/watch?v=nn2fFpO4p9Q

参考PPT：http://nutmic2019.imj-prg.fr/slides/Chimera.pdf

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c++信息安全密码学

二维码

)">

周鸿祎的“花房上市”执念

< <上一篇

区块链笔记5-共识算法

下一篇>>

搜索内容

Chimera全同态加密加密转换方案学习

全同态加密

整数计算

近似计算

电路计算

环面上的LWE困难问题

多项式环

Chimera的框架

电路转换为 $mathbb{T}_N[X] TN[X]$

整数转换为 $mathbb{T}_N[X] TN[X]$

定点数转换为 $mathbb{T}_N[X] TN[X]$

小结

参考文献

最新文章

分类

标签云

Chimera全同态加密加密转换方案学习

全同态加密

整数计算

近似计算

电路计算

环面上的LWE困难问题

多项式环

Chimera的框架

电路转换为 T N [ X ] mathbb{T}_N[X] TN​[X]

整数转换为 T N [ X ] mathbb{T}_N[X] TN​[X]

定点数转换为 T N [ X ] mathbb{T}_N[X] TN​[X]

小结

参考文献

最新文章

分类

标签云

电路转换为 $mathbb{T}_N[X] TN[X]$

整数转换为 $mathbb{T}_N[X] TN[X]$

定点数转换为 $mathbb{T}_N[X] TN[X]$