全同态加密

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

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

1. 整数计算
2. 近似计算（定点数计算）
3. 二进制计算（电路计算）

整数计算

给定两个明文 m 1 , m 2 ∈ Z m_1, m_2 \in \mathbb{Z} m1​,m2​∈Z 的加密，可以计算：

整数计算是可以使用 SIMD 进行加速的，给定两个明文 m 1 , m 2 ∈ Z m_1, m_2 \in \mathbb{Z} m1​,m2​∈Z 的加密，我们可以计算：

• 元素之间的加法： m 1 + m 2 m_1 + m_2 m1​+m2​
• 元素之间的乘法： m 1 × m 2 m_1 \times m_2 m1​×m2​
• 置换操作： σ ( m 1 ) \sigma (m_1) σ(m1​)

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

然而，单例的加法和乘法都是完备的，但是如果我们把数据看成数组形式的话，加法和乘法就不是完备的了，例如同一个数组中不同的元素之间无法进行运算。因此，需要引入同态置换操作 σ ( m 1 ) \sigma (m_1) σ(m1​) 才能在加密数组上实现完备的操作。

通常来说，取任意精度的整数对同态加密来说并不是很友好。例如在 C 语言中，取模 p = 2 32 p = 2^{32} p=232 ，则有可能在计算时发生溢出，如 2 30 + 2 30 = − 2 31 2^{30} + 2^{30} = -2^{31} 230+230=−231 。

近似计算

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

将定点数表示为： x = m ⋅ 2 τ x = m \sdot 2^{\tau} x=m⋅2τ ，其中 m ∈ 2 − ρ ⋅ Z m \in 2^{-\rho} \sdot \mathbb{Z} m∈2−ρ⋅Z 并且 0 ≤ ∣ m ∣ < 1 0 \leq | m | < 1 0≤∣m∣<1

明文参数有：

• ρ ∈ N \rho \in \mathbb{N} ρ∈N ：明文精度的比特数（约为15）
• τ ∈ Z \tau \in \mathbb{Z} τ∈Z ：槽指数（每个槽内复数值的数量级的阶）

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

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

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

然而实际的操作可能比你想象的要复杂很多。例如给定 ( m 1 , τ 1 ) , ( m 2 , τ 2 ) (m_1, \tau_1), (m_2, \tau_2) (m1​,τ1​),(m2​,τ2​) 和 τ \tau τ ，需要计算 ρ \rho ρ bits 精度的 m ⋅ 2 τ = m 1 ⋅ 2 τ 1 + m 2 ⋅ 2 τ 2 m \sdot 2^{\tau} = m_1 \sdot 2^{\tau_1} + m_2 \sdot 2^{\tau_2} m⋅2τ=m1​⋅2τ1​+m2​⋅2τ2​ ，除了需要加法运算之外，则需要非线性函数：右移 和 舍入。

电路计算

给定 b 1 , b 2 ∈ { 0 , 1 } b_1, b_2 \in \{ 0, 1 \} b1​,b2​∈{0,1} ，同态运算为：

在这里考虑三种电路：

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

环面上的LWE困难问题

多项式环

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

• 整数多项式 Z N [ X ] = Z [ X ] / ( X N + 1 ) \mathbb{Z}_N[X] = \mathbb{Z}[X] / (X^N + 1) ZN​[X]=Z[X]/(XN+1) ，是系数是整数的多项式模 X N + 1 X^N + 1 XN+1 的环
• 实数多项式 R N [ X ] = R [ X ] / ( X N + 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 的环
• 复数多项式 C N [ X ] = C [ X ] / ( X N + 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 N=2 时，实数多项式上的运算可以为：

( 1.2 + 2.3 X ) ⋅ ( 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 ) (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.3X)⋅(3.2+4.1X)=3.84+12.28X+9.42X2=12.28X−5.59mod(X2+1)

可以观察到，实数多项式 ( R N [ X ] , + , × ) (\mathbb{R}_N[X], +, \times) (RN​[X],+,×) 和复数多项式 ( C N [ X ] , + , × ) (\mathbb{C}_N[X], +, \times) (CN​[X],+,×) 都是环：

• ( R N [ X ] , + ) (\mathbb{R}_N[X], +) (RN​[X],+) 和 ( C N [ X ] , + ) (\mathbb{C}_N[X], +) (CN​[X],+) 都是群
• x × y x \times y x×y 有定义

为了继续在槽上进行操作，我们需要使用 系数打包(Coefficient packing) 和 槽打包 (Slot packing) 的技术，将这两个环同构到 R \mathbb{R} R-向量空间上：

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

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

Chimera的框架

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

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

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

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

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

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

在上述方案中，明文种类有：电路的布尔值、整数摸 ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n (Z/pZ)n 、定点数 C \mathbb{C} C 。那么，我们怎么用 T N [ X ] \mathbb{T}_N[X] TN​[X] 来表示所有的明文呢？

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

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

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

其中 CMux 门的表达式为： C M u x ( C , d 1 , d 0 ) = C ⊡ ( d 1 − d 0 ) + d 0 CMux(C, d_1, d_0) = C \boxdot (d_1 - d_0) + d_0 CMux(C,d1​,d0​)=C⊡(d1​−d0​)+d0​

使用很多这样的 CMux 门可以构造和评估任意的 查找表/布尔函数 ，进而评估任意函数 f : B d → T s f:\mathbb{B}^d \rightarrow \mathbb{T}^s f:Bd→Ts

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

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

我们知道整数多项式模 p p p ：即 Z N [ x ]   m o d   p \mathbb{Z}_N[x] \, mod \, p ZN​[x]modp 是系数是模 p p p 整数的多项式环模 X N + 1 X^N + 1 XN+1 。

如果 X N + 1 X^N + 1 XN+1 有 N N N 个根，则 Z / p Z \mathbb{Z}/p\mathbb{Z} Z/pZ 是和 Z N [ X ]   m o d   p \mathbb{Z}_N[X] \, mod \, p ZN​[X]modp 同构的（可以用模 p p p 的槽来模拟）。

举个栗子：

关于 p p p 的限制：

• 在 BFV 方案中， p p p 需要满足一些条件
• 在 BGV 方案中，任意 p p p 都可以（在扩域中进行运算）

我们知道有同构： ( Z / p Z ) N ≃ Z N [ X ]   m o d   p ≃ 1 p Z N [ X ]   m o d   1 (\mathbb{Z} / p\mathbb{Z})^N \simeq \mathbb{Z}_N [X] \, mod \, p \simeq \frac{1}{p} \mathbb{Z}_N[X] \, mod \, 1 (Z/pZ)N≃ZN​[X]modp≃p1​ZN​[X]mod1

于是我们可以使用 1 p \frac{1}{p} p1​ 的整数倍构造明文空间 M \mathcal{M} M ：

于是明文上的加法 a d d i t i o n ( μ 1 ( X ) , μ 2 ( X ) ) addition(\mu_1(X), \mu_2(X)) addition(μ1​(X),μ2​(X)) ：

μ 1 ( X ) + μ 2 ( X ) : = μ 1 ( X ) + μ 2 ( X )   m o d   1 \mu_1(X) + \mu_2(X) := \mu_1(X) + \mu_2(X) \, mod \, 1 μ1​(X)+μ2​(X):=μ1​(X)+μ2​(X)mod1

明文上的蒙哥马利乘法 p r o d u c t ( M o n t g o m e r y ) ( μ 1 ( X ) , μ 2 ( X ) ) product(Montgomery) (\mu_1(X), \mu_2(X)) product(Montgomery)(μ1​(X),μ2​(X)) ：

μ 1 ( X ) ⊠ p μ 2 ( X ) : = p ⋅ μ 1 ( X ) ⋅ μ 2 ( X )   m o d   1 \mu_1(X) \boxtimes_p \mu_2(X) := p \sdot\mu_1(X) \sdot \mu_2(X) \, mod \, 1 μ1​(X)⊠p​μ2​(X):=p⋅μ1​(X)⋅μ2​(X)mod1

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

例如选取参数 p = 3 , μ 1 = 1 / 3 , μ 2 = 2 / 3 p = 3, \mu_1 = 1/3, \mu_2 = 2/3 p=3,μ1​=1/3,μ2​=2/3 时

• 对于所有整数 I 1 , I 2 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
• 当我们在噪声下计算小元素时： 3 × 5.33333 × 10.66665 = 170.6662 3 \times 5.33333 \times 10.66665 = 170.6662 3×5.33333×10.66665=170.6662 正确
• 当我们在噪声下计算大元素时： 3 × 12345678.33333 × 7654321.66665 = − . 839...   m o d   1 3 \times 12345678.33333 \times 7654321.66665 = -.839... \, mod \, 1 3×12345678.33333×7654321.66665=−.839...mod1 错误

因此，我们需要明文的小表达式来保证结果的正确性；即我们需要将密文限制为 R [ X ] \mathbb{R}[X] R[X] 上的小的表达式；以及保证 1 p ≫ n o i s e \frac{1}{p} \gg noise p1​≫noise

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

• 同态加法 c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) c_1 = (a_1, b_1), c_2 = (a_2, b_2) c1​=(a1​,b1​),c2​=(a2​,b2​)

  ( a , b ) = ( a 1 + a 2 , b 1 + b 2 ) (a, b) = (a_1 + a_2, b_1 + b_2) (a,b)=(a1​+a2​,b1​+b2​)

• 同态积 c 1 = ( a 1 , b 1 ) , c 2 = ( a 2 , b 2 ) c_1 = (a_1, b_1), c_2 = (a_2, b_2) c1​=(a1​,b1​),c2​=(a2​,b2​)

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

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

• L ∈ N L \in \mathbb{N} L∈N ：表示密文的级的指数，它量化了在执行自举之前同态操作的最大数量。
• ρ ∈ N \rho \in \mathbb{N} ρ∈N ：明文精度的比特值，即尾数的位数。由于它是一个全局常量，我们一般省略它。
• τ ∈ Z \tau \in \mathbb{Z} τ∈Z ：槽指数(每个槽中复数值的数量级)。这里使用浮点表示，其指数是公开的，并且在向量的所有坐标上都是固定的，只有尾数是保密的。更准确地说，一个复数 z z z 被表示为 z = m ⋅ 2 τ z = m \sdot 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 × y = L i f t ( x ) ∗ L i f t ( y )   m o d   1 x \times y = Lift(x) * Lift(y) \, mod \, 1 x×y=Lift(x)∗Lift(y)mod1

• 优势1：这种方法可以保留 (或减少) 间隔 [ − 1 2 L , 1 2 L ] [- \frac{1}{2^L}, \frac{1}{2^L}] [−2L1​,2L1​]
• 优势2： L i f t Lift Lift 是一个周期函数：它可以通过 s i n sin sin 函数（或者其他傅里叶序列）来近似
• 不足：但是 s i n sin sin 函数只能近似于多项式，而多项式需要递归地乘积

如果使用离散的方法来表示明文：舍入 a , b a, b a,b (进而舍入 μ \mu μ) 到确切的 1 q \frac{1}{q} q1​ 的倍数，其中 q ≈ 2 L + ρ q \approx 2^{L + \rho} q≈2L+ρ

• 优势1：这是一个环 1 q Z N [ X ]   m o d   1 \frac{1}{q} \mathbb{Z}_N[X] \, mod \, 1 q1​ZN​[X]mod1 ，可以避免使用 L i f t Lift Lift
• 优势2：可以进行蒙哥马利乘法 q ( b 1 − s ⋅ a 1 ) ( b 2 − s ⋅ a 2 ) q(b_1 - s \sdot a_1)(b_2 - s \sdot a_2) q(b1​−s⋅a1​)(b2​−s⋅a2​)
• 不足：会扩大区间 [ − 1 2 L , 1 2 L ] → [ − 1 2 L − ρ , 1 2 L − ρ ] [- \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