Bra12同态加密方案初步学习

基于LWE，采用了最大比特编码，把消息编码到了高位，无需模交换，模数可以任意形式（只要满足大小，可以设置为2的幂次来简化运算），密钥分布没有限制。
由于所有运算都是在整数上面，所以运算速度会比BGV慢，但是又因为更优秀的噪声控制，会使得电路深度更深。

Regev的公钥加密方案

本方案是基于这个搭建的，故在此介绍一下，和Regev09里的基本一致，只是表达形式不同。

注意这里没有限制$q$一定是奇数或者素数，另外加密的时候对消息$m$采用了最大比特编码，也就是消息放到了高位上避免与噪声混淆。

向量分解以及密钥交换

向量分解

这里的向量分解也就是利用到以前文章提过的BitDecomp和Powersof2函数，故不再解释，可以参看前面BGV和GSW方案中的描述。

下标$q$经常被省略。

密钥交换

这里的密钥交换函数也和BGV方案中的很类似，功能都是把一个密钥下的密文转换成另一个密钥下的密文。值得注意的是，这里的噪声不是$2e$，而是$e$。
另外第一个$\mathrm{SwitchKeyGen}$函数中的${\mathbf{P}}_{\mathbf{s}:\mathbf{t}}$就是BGV中同一个函数诞生的矩阵${\tau }_{{\mathbf{s}}_1\to {\mathbf{s}}_2}=\mathbf{B}$，不同的是，没有把$\mathrm{P}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{f}2\left(\mathrm{s}\right)$叠加到第一列，而是类似加密明文一样的加密它。（好吧，其实基本上一样的）

验证一下正确性：
⟨ c t , ( 1 , t ) ⟩ = BitDecomp ⁡ ( c s ) ⋅ P s : t T ⋅ ( 1 , t ) = BitDecomp ⁡ ( c s ) ⋅ [ b s : t , − A s : t ] ⋅ [ 1 , t ] = BitDecomp ⁡ ( c s ) ⋅ ( A s : t ⋅ t + e s : t + Powersof2 ⁡ ( s ) − A s : t ⋅ t ) = ⟨ BitDecomp ⁡ ( c s ) , e s : t ⟩ + ⟨ BitDecomp ⁡ ( c s ) , Powersof2 ⁡ ( s ) ⟩ = ⟨ BitDecomp ⁡ ( c s ) , e s : t ⟩ + ⟨ c s , s ⟩

⟨ct​,(1,t)⟩​=BitDecomp(cs​)⋅Ps:tT​⋅(1,t)=BitDecomp(cs​)⋅[bs:t​,−As:t​]⋅[1,t]=BitDecomp(cs​)⋅(As:t​⋅t+es:t​+Powersof2(s)−As:t​⋅t)=⟨BitDecomp(cs​),es:t​⟩+⟨BitDecomp(cs​),Powersof2(s)⟩=⟨BitDecomp(cs​),es:t​⟩+⟨cs​,s⟩​

同态加密方案

$q=q(n)$为一个整数函数，$L=L(n)$为多项式，$\chi =\chi (n)$为$\mathbb{Z}$上的分布

• $\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{K}\mathrm{e}\mathrm{y}\mathrm{g}\mathrm{e}\mathrm{n}(1^L,1^n):$
  
  密钥生成过程就是先生成$L+1$个私钥链，生成初始的公钥，计算出每一轮私钥的乘积作备用，接着生成每一轮密钥交换的交换密钥作为评估密钥集合。这样通过密钥生成算法就获得了初始加密公钥$pk=P_0$、评估密钥链（用于密钥交换）$evk$和最终解密的私钥$sk=s_L$

• ${\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{E}\mathrm{n}\mathrm{c}}_{pk}(m):$直接使用$\mathbf{c}\leftarrow {\mathrm{R}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{v}.\mathrm{E}\mathrm{n}\mathrm{c}}_{pk}(m)$

• ${\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{E}\mathrm{v}\mathrm{a}\mathrm{l}}_{evk}(\cdot ):$同态运算包含有限域$GF(2)$上的加法和乘法，这里有个显然的约定就是电路第$i$级输入（同态运算输入的当然是上一级的密文形式）可以用${\mathbf{s}}_{i-1}$来解密，同态运算输入结果自然就可以用${\mathbf{s}}_i$来解密了。

  1. ${\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{A}\mathrm{d}\mathrm{d}}_{evk}({\mathbf{c}}_1,{\mathbf{c}}_2):$
     
     首先来看看加法，这里加法和以往的加法不太一样，采用了先相加再与一个特殊向量求张积，显然能这个乘法张积不会改变加法的大小，前面提到了，作者想让同态运算的结果用${\mathbf{s}}_i$来解密，但是这里显然如果只单纯把密文相加的话，解密的密钥就是${\mathbf{s}}_{i-1}$而不是${\mathbf{s}}_i$。所以这里加了一个不会改变加法和密文的乘法运算生成一个“中间密文”来达成目的。

  2. ${\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{M}\mathrm{u}\mathrm{l}\mathrm{t}}_{evk}({\mathbf{c}}_1,{\mathbf{c}}_2):$
     
     首先假定两个密文都是密钥${\mathbf{s}}_{i-1}$加密的密文，这里对密文张积的处理是直接乘了一个$\frac{2}{q}$，等于是把BGV中模交换过程近似的（这里没有$\mathrm{Scale}()$取最近整数向量过程）放到了乘法运算里面（BGV中是先做乘法运算然后进行一个内嵌模交换的$\mathrm{Refresh}()$过程），最后输出密钥交换后的密文。

• ${\mathrm{S}\mathrm{I}-\mathrm{H}\mathrm{E}.\mathrm{D}\mathrm{e}\mathrm{c}}_{sk}(\mathbf{c}):$直接使用$m\leftarrow {\mathrm{R}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{v}.\mathrm{D}\mathrm{e}\mathrm{c}}_{sk}(\mathbf{c})$

噪声分析

大致如图

对Regev的加密方案，有$<\mathbf{c},\mathbf{s}>=q/2\cdot m+e+qI$这里$I$是一个整数（没有模运算），密钥向量也是整数。现在考虑一下小数密文$\tilde{\mathbf{c}}=\mathbf{c}/q$，得到解密结果$<\tilde{\mathbf{c}},s>=1/2\cdot m+\tilde{e}+I$，由于除以了一个$q$，那么当前密文元素的取值范围应该是$(-1/2,1/2)$。此外这里的$I$有一个界限就是$||s|{|}_1=l_1(s)$（一阶范数）这个界限来源于除法过后取整所诞生的误差，也就是BGV中模交换的误差。
证明如下，（其实就是把BGV中的模$p$变成了模1）（下面的${\mathbf{c}}^{\prime }$就是$\tilde{\mathbf{c}}$）
[ ⟨ c ′ , s ⟩ ] 1 = ⟨ c ′ , s ⟩ − k = ⟨ c ′ , s ⟩ − k q ⋅ 1 q = ⟨ c ′ , s ⟩ + 1 q ⋅ ( [ ⟨ c , s ⟩ ] q − ⟨ c , s ⟩ ) = ⟨ c ′ , s ⟩ − 1 q ⟨ c , s ⟩ + 1 q [ ⟨ c , s ⟩ ] q = 1 q ⋅ [ ⟨ c , s ⟩ ] q + ⟨ c ′ − ( 1 q ) c , s ⟩ < ( 1 q ) ⋅ ∣ [ ⟨ c , s ⟩ ] q ∣ + ℓ 1 ( s )

[⟨c′,s⟩]1​=⟨c′,s⟩−k​=⟨c′,s⟩−kq⋅q1​=⟨c′,s⟩+q1​⋅([⟨c,s⟩]q​−⟨c,s⟩)=⟨c′,s⟩−q1​⟨c,s⟩+q1​[⟨c,s⟩]q​=q1​⋅[⟨c,s⟩]q​+⟨c′−(q1​)c,s⟩<(q1​)⋅∣[⟨c,s⟩]q​∣+ℓ1​(s)​

现在来看看乘法${\mathbf{c}}_{mult}=2\cdot {\mathbf{c}}_1\otimes {\mathbf{c}}_2$，使用张量密钥解密后，
< 2 c 1 ⊗ c 2 , s ⊗ s > = 2 < c 1 , s > ⋅ < c 2 , s > = 2 ⋅ ( 1 2 m 1 + e 1 + I 1 ) ⋅ ( 1 2 m 2 + e 2 + I 2 ) = 1 2 m 1 m 2 + 2 ( e 1 I 2 + e 2 I 1 ) + 2 e 1 e 2 + e 1 m 2 + e 2 m 1 + ( m 1 I 2 + m 2 I 1 + 2 I 1 I 2 ) ∈ Z

<2c1​⊗c2​,s⊗s>​=2<c1​,s>⋅<c2​,s>=2⋅(21​m1​+e1​+I1​)⋅(21​m2​+e2​+I2​)=21​m1​m2​+2(e1​I2​+e2​I1​)+2e1​e2​+e1​m2​+e2​m1​+(m1​I2​+m2​I1​+2I1​I2​)∈Z​
以前的噪声增长主要是看两个噪声乘积，现在对于两个小密文$e_1{e}_2$的噪声乘积自然是非常小的，主要的噪声误差在于后面。假定$ϵ=B/q$，$B$为噪声上限，那么$e_1{e}_2={ϵ}^2\ll ϵ$、$e_1{m}_2+e_2{m}_1\le 2ϵ$，那么主要的误差就在$2(e_1{I}_2+e_2{I}_1)$，然而$I$的界限是$||s|{|}_1$，所以需要减小私钥的范数们也就是二进制化。二进制化后，私钥的范数至多就是它的维度们也就是$O(n\cdot \log q)=O(poly(n))$。

参考

同态加密（十）：Bra12：经典GapSVP无模切换全同态加密

Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. IACR Cryptology ePrint Archive, 2012:78, 2012.
全同态加密：BFV