GSW同态加密方案学习_gsw加密方案

帮助理解

第三代全同态加密方案，对比之前的方案来说，概念上更加简单，渐进更快，基于身份和属性。
核心思想是近似特征向量技术。
一开始看Gentry的文章很不适应，所以先看的Yue佬的文章帮助理解后再去看原文。

第一阶段

由线代中的特征值与特征向量的关系$Ax=\lambda x$

密钥生成算法KenGen

这里随机选取一个向量$\vec{s}$作为加密密钥

“加密”算法Enc

$Enc(\vec{s},\mu )\to C$：待加密的明文为$\mu$，$C$是密文
$$C\cdot \vec{s}=\mu \cdot \vec{s}$$
这个加密过程中，$\mu$ 类似特征值，$C$是特征矩阵。整个过程只需要找到一个符合要求的特征矩阵$C$即为密文。

解密算法Dec

$Dec(\vec{s},C)$:同样只需要知道$\vec{s}$就能用$C\cdot \vec{s}$得到$\vec{s}$的倍数，从而推导出明文$\mu$。

运算算法Eval

从FHE定义中不难看到，$Eval$算法满足加法和乘法任意次计算，这个体系就是全同态。
假定有两个密文$C_1,C_2$和对应明文${\mu }_1,\mu 2$。
加法验证$Eval(+,C_1,C_2)$：
( C 1 ± C 2 ) ⋅ s ⃗ = C 1 ⋅ s ⃗ ± C 2 ⋅ s ⃗ = μ 1 ⋅ s ⃗ ± μ 2 ⋅ s ⃗ = ( μ 1 ± μ 2 ) ⋅ s ⃗

$$\begin{aligned} (C_1 \pm C_2)\cdot\vec s &= C_1\cdot \vec s \pm C_2\cdot\vec s \\ &= \mu_1\cdot \vec s \pm \mu_2\cdot \vec s \\ &= (\mu_1 \pm \mu_2)\cdot \vec s \end{aligned}$$ (C1​±C2​)⋅s ​=C1​⋅s ±C2​⋅s =μ1​⋅s ±μ2​⋅s =(μ1​±μ2​)⋅s ​
解密结果正好是原文相加，所以加法同态成立。

乘法验证$Eval(\times ,C_1,C_2)$：
( C 1 ⋅ C 2 ) ⋅ s ⃗ = C 1 ⋅ ( C 2 ⋅ s ⃗ ) = C 1 ⋅ μ 2 ⋅ s ⃗ = μ 2 ⋅ C 1 ⋅ s ⃗ = ( μ 1 ⋅ μ 2 ) ⋅ s ⃗

$$\begin{aligned} (C_1 \cdot C_2)\cdot\vec s &= C_1\cdot (C_2\cdot\vec s) \\ &= C_1\cdot \mu_2 \cdot \vec s \\ &= \mu_2 \cdot C_1 \cdot \vec s \\ &= (\mu_1 \cdot \mu_2) \cdot \vec s \end{aligned}$$ (C1​⋅C2​)⋅s ​=C1​⋅(C2​⋅s )=C1​⋅μ2​⋅s =μ2​⋅C1​⋅s =(μ1​⋅μ2​)⋅s ​

解密结果也正好是原文相乘，所以乘法同态也成立。

存在的问题

这个算法看似完美满足了加法和乘法的同态而且还没有噪音，但是有一个致命弱点，加密太容易破解了！
密文$C$其实就是一个正常的矩阵，所以通过线性代数的方法能直接找到$C$的特征值和特征向量，这就直接破解了，甚至连密钥$\vec{s}$都不需要。

第二阶段

第一阶段的问题是满足了全同态但是没有加密，所以缺啥补啥，第二阶段加入了一个随机噪音$\vec{e}$，类似LWE那样，这就直接变成了一个困难的LWE问题。
$$C\cdot \vec{s}=\mu \cdot \vec{s}+\vec{e}$$

密钥生成算法KenGen

$KeyGen(1^{\lambda })$：$\lambda$为难度系数，这里随机生成一个私密向量$\tilde{s}\in {\mathbb{Z}}_q^{n-1}$，然后再在这个向量最下面加上以恶个$-1$，构成密钥向量
s ⃗ ← ( s ~ − 1 ) \vec s \leftarrow \left(

$$\begin{array}{c} \tilde{s} \\ -1 \end{array}$$ \right) s ←(s~−1​)
最后输出$\vec{s}\in {\mathbb{Z}}_q^n$作为密钥。

加密算法Enc

$Enc(\vec{s},\mu \in {\mathbb{Z}}_q)$:这里构建一个LWE问题实例，也就是随机生成一个矩阵$A\stackrel{R}{\leftarrow }{\mathbb{Z}}_q^{n\times (n-1)}$和对应的随机噪音$\vec{e}\stackrel{R}{\leftarrow }{x}_B^n$，则生成的密文如下：
$$C=\underset{\text{LWE Instance }}{\underbrace{(A,A\cdot \tilde{s}+\vec{e})}}+\stackrel{\text{message }}{\overbrace{\mu \cdot I_n}}\in {\mathbb{Z}}_q^{n\times n}$$
这里的$I_n$是个$n\times n$的单位矩阵，同时这里可以把$(A,A\cdot \tilde{s}+\vec{e})$两个矩阵拼接起来变成$n\times n$的矩阵，从而能够叠加在要加密的信息$\mu \cdot I_n$上面。由于DLWE假设，整个过程可以看作是OTP（One-Time Pad）的，即类同于密文是安全的。

解密算法Dec

$Dec(\vec{s},C)$:和第一阶段一样，计算出$C\cdot \vec{s}$，然后通过观察得到大致倍数，就可以还原出明文了。
C ⋅ s ⃗ = ( ( A , A ⋅ s ~ + e ⃗ ) + μ ⋅ I n ) ⋅ s ⃗ = ( A , A ⋅ s ~ + e ⃗ ) ⋅ s ⃗ + μ ⋅ I n ⋅ s ⃗ = A ⋅ s ~ − ( A ⋅ s ~ + e ⃗ ) + μ ⋅ s ⃗ = μ ⋅ s ⃗ − e ⃗

$$\begin{aligned} C \cdot \vec{s} &=\left((A, A \cdot \tilde{s}+\vec{e})+\mu \cdot I_{n}\right) \cdot \vec{s} \\ &=(A, A \cdot \tilde{s}+\vec{e}) \cdot \vec{s}+\mu \cdot I_{n} \cdot \vec{s} \\ &=A \cdot \tilde{s}-(A \cdot \tilde{s}+\vec{e})+\mu \cdot \vec{s} \\ &=\mu \cdot \vec{s}-\vec{e} \end{aligned}$$ C⋅s ​=((A,A⋅s~+e )+μ⋅In​)⋅s =(A,A⋅s~+e )⋅s +μ⋅In​⋅s =A⋅s~−(A⋅s~+e )+μ⋅s =μ⋅s −e ​
第二步看作矩阵乘法，因此计算矩阵相乘的时候，把$(A,A\cdot \tilde{s}+\vec{e})$和$\vec{s}$分别看作拼装的$1\times 2$和$2\times 1$矩阵，那乘法就等于是把把LWE的问题矩阵$A$与未知向量$\tilde{s}$相乘，再减去$A\cdot \tilde{s}+\vec{e}$，最后就只剩一项噪音向量。
解密结果和在特征向量等式中加入噪音是一样的，另外噪音的绝对值只需要符合一个上限$B$就行了，所以正负号没有什么区别。
然后由于解密得到的关系式和之前的特征向量关系式大概一致，我们可以称这里的私密向量为矩阵$C$的近似特征向量（approximate eigenvector）。

运算算法Eval

在安全性得到保证之后呢，再来验证一下是否满足全同态。
加法$Eval(+,C_1,C_2)$：对结果进行解密
( C 1 + C 2 ) ⋅ s ⃗ = C 1 ⋅ s ⃗ + C 2 ⋅ s ⃗ = μ 1 ⋅ s ⃗ + e ⃗ 1 + μ 2 ⋅ s ⃗ + e ⃗ 2 = ( μ 1 + μ 2 ) ⋅ s ⃗ + ( e ⃗ 1 + e ⃗ 2 ) ⏟ small error term 

$$\begin{aligned} \left(C_{1}+C_{2}\right) \cdot \vec{s} &=C_{1} \cdot \vec{s}+C_{2} \cdot \vec{s} \\ &=\mu_{1} \cdot \vec{s}+\vec{e}_{1}+\mu_{2} \cdot \vec{s}+\vec{e}_{2} \\ &=\left(\mu_{1}+\mu_{2}\right) \cdot \vec{s}+\underbrace{\left(\vec{e}_{1}+\vec{e}_{2}\right)}_{\text {small error term }} \end{aligned}$$ (C1​+C2​)⋅s ​=C1​⋅s +C2​⋅s =μ1​⋅s +e 1​+μ2​⋅s +e 2​=(μ1​+μ2​)⋅s +small error term  (e 1​+e 2​)​​​
可以看到结果是比较好看的，能有效得到明文之和，而这里同样的会使得两个随机噪音进行叠加，但是规定的噪音取值上限$B$一般来说很小，所以即便是叠加起来也只是$2B$的容错率，考虑到$B<<q$的情况下，这个叠加是能接受的。

乘法$Eval(\times ,C_1,C_2)$：
( C 1 ⋅ C 2 ) ⋅ s ⃗ = C 1 ⋅ ( C 2 ⋅ s ⃗ ) = C 1 ⋅ ( μ 2 ⋅ s ⃗ + e ⃗ 2 ) = μ 2 ⋅ C 1 ⋅ s ⃗ + C 1 ⋅ e ⃗ 2 = μ 1 ⋅ μ 2 ⋅ s ⃗ ⏟ Result  + μ 2 ⋅ e ⃗ 1 ⏟ ok error term  + C 1 ⋅ e ⃗ 2 ⏟ large error term!  ( m o d    q )

$$\begin{aligned} \left(C_{1} \cdot C_{2}\right) \cdot \vec{s} &=C_{1} \cdot\left(C_{2} \cdot \vec{s}\right) \\ &=C_{1} \cdot\left(\mu_{2} \cdot \vec{s}+\vec{e}_{2}\right) \\ &=\mu_{2} \cdot C_{1} \cdot \vec{s}+C_{1} \cdot \vec{e}_{2} \\ &=\underbrace{\mu_{1} \cdot \mu_{2} \cdot \vec{s}}_{\text {Result }}+\underbrace{\mu_{2} \cdot \vec{e}_{1}}_{\text {ok error term }}+\underbrace{C_{1} \cdot \vec{e}_{2}}_{\text {large error term! }}(\mod q) \end{aligned}$$ (C1​⋅C2​)⋅s ​=C1​⋅(C2​⋅s )=C1​⋅(μ2​⋅s +e 2​)=μ2​⋅C1​⋅s +C1​⋅e 2​=Result  μ1​⋅μ2​⋅s ​​+ok error term  μ2​⋅e 1​​​+large error term!  C1​⋅e 2​​​(modq)​
可以看到，这里比想要的${\mu }_1\cdot {\mu }_2\cdot \vec{s}$多出了一个${\mu }_2\cdot {\vec{e}}_1$和一个$C_1\cdot {\vec{e}}_2$。
来看看多出的两个会不会对结果有很大的影响.

第一个噪音${\mu }_2\cdot {\vec{e}}_1$似乎就有不小的影响，如果这个${\mu }_2$比较大的话，那就会超出噪音上限从而丢失精度。

第二个噪音$C_1\cdot {\vec{e}}_2$，由于$C_1$是随机取值于${\mathbb{Z}}_q$的矩阵，即它的每个值最大上限是$q/2$，那么就算${\vec{e}}_2$的取值很小，这项的乘积也会很大，极有可能超过噪音上限$q/4$，直接导致无法区分从而解密失败。
所以这里加法同态能实现，但是乘法同态却失效了，失败的原因是乘法运算会加入过大的噪音，缺啥补啥，所以接下来的问题是如果处理这个过大的噪音。

第三阶段

解决大噪音问题

对于第一个噪音，如果我们使用与非门（NAND gates），也就是规定一次只加密一个比特，这样$\mu$的取值范围就是 { 0 , 1 } \{0,1\} {0,1}，那这一项的噪音上限还是$B$。

而对于第二个噪音$C_1\cdot {\vec{e}}_2$上，也就是$C_1$这个矩阵上，因为矩阵的无穷范数是$\Vert C{\Vert }_{\infty }\le q/2$，矩阵中的数字取值是毫无约束的随机数。接下来的目标是把这个取值范围调整到能控制的小范围内，同时还要保证数字是随机取的。

二进制拆分（也叫扁平化）
将数字用二进制的一串比特表示，可以使得这个数字的范数降低。
x ^ = ( x 0 , x 1 , … , x log ⁡ 2 ( q ) − 1 ) ∈ { 0 , 1 } log ⁡ 2 ( q ) \hat{x}=\left(x_{0}, x_{1}, \ldots, x_{\log_{2} (q)-1}\right) \in\{0,1\}^{\log_{2} (q)} x^=(x0​,x1​,…,xlog2​(q)−1​)∈{0,1}log2​(q)
分解过后，最多得到${\log }_2(q)$个比特，每个比特取值范围都是 { 0 , 1 } \{0,1\} {0,1}，这样便可以使得其无穷范数大大降低。
$$\Vert \hat{x}{\Vert }_{\infty }\le 1$$
同理可以对一个向量的每一个元素进行二进制拆分，然后连在一起就可以了，假如有向量$v=\left(v_0,v_1,\dots ,v_{n-1}\right):$
$$\hat{v}=(\underset{\log (\mathrm{q})-1\text{ elements }}{\underbrace{v_{0,0},\dots ,v_{0,{\log }_2(q)-1}}},v_{1,0},\dots ,v_{1,{\log }_2(q)-1},\dots ,v_{n-1,0},\dots ,v_{n-1,{\log }_2(q)-1})$$
分解后得到一共$n\times {\log }_2(q)$个元素，每个元素都是一个二进制比特。
接着，假如对一个矩阵进行二进制拆分，即把每一行当作一个单独的向量分解，假如有一个$m\times n$的矩阵，通过分解就将得到维度为$m\times n\times {\log }_2(q)$。
此外，二进制拆分还有一个好处即，如果想把二进制分解态进行还原的话，整个过程是一个线性变换的过程，例如把上面的$\hat{x}$还原：
$$x=\sum _{i=0}^{{\log }_2(q)-1}{x}_i\cdot 2^i$$
同理，对矩阵进行二进制还原，通过一个二进制重组矩阵$G$来变换。
C = C ^ ⋅ G = [ C ^ 1 ⋮ C ^ m ] ⋅ G = [ C 0 , 0 , 0 ⋯ C 0 , 0 , log ⁡ 2 ( q ) − 1 … C 0 , n − 1 , 0 … C 0 , n − 1 , log ⁡ 2 ( q ) − 1 ⋮ ⋱ ⋮ ⋱ ⋮ ⋱ ⋮ C m − 1 , 0 , 0 … C m − 1 , 0 , log ⁡ 2 ( q ) − 1 … C m − 1 , n − 1 , 0 … C m − 1 , n − 1 , l o g ( q ) − 1 ] ⋅ G

$$\begin{array}{l} \begin{aligned} C &=\hat{C} \cdot G \\ &=\left[\begin{array}{c} \hat{C}_{1} \\ \vdots \\ \hat{C}_{m} \end{array}$$ \right] \cdot G \end{aligned}\\ =\left[ $$\begin{array}{ccccccc} C_{0,0,0} & \cdots & C_{0,0, \log_{2} (q)-1} & \ldots & C_{0, n-1,0} & \ldots & C_{0, n-1, \log_{2} (q)-1} \\ \vdots & \ddots & \vdots & \ddots & \vdots & \ddots & \vdots \\ C_{m-1,0,0} & \ldots & C_{m-1,0, \log_{2} (q)-1} & \ldots & C_{m-1, n-1,0} & \ldots & C_{m-1, n-1, l o g}(q)-1 \end{array}$$ \right] \cdot G \end{array} C​=C^⋅G=⎣ ⎡​C^1​⋮C^m​​⎦ ⎤​⋅G​=⎣ ⎡​C0,0,0​⋮Cm−1,0,0​​⋯⋱…​C0,0,log2​(q)−1​⋮Cm−1,0,log2​(q)−1​​…⋱…​C0,n−1,0​⋮Cm−1,n−1,0​​…⋱…​C0,n−1,log2​(q)−1​⋮Cm−1,n−1,log​(q)−1​⎦ ⎤​⋅G​
重组矩阵$G$
$$G=\left[\begin{array}{cccc}{2}^0& 0& \cdots & 0\\ 2^1& 0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 2^{{\log }_2(q)-1}& 0& \cdots & 0\\ 0& 2^0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 2^{{\log }_2(q)-1}\end{array}\right]$$
矩阵$G$中，每一列系数对应$\hat{C}$中的每一行的每${\log }_2(q)$个bits的线性重组，也就是$\hat{C}$为$m\times (n\times {\log }_2(q))$的矩阵，$G$为$(n\times {\log }_2(q))\times m$的矩阵，这样最后相乘就可以还原出最初的$C$，同时二进制分解矩阵就可以用$G^{-1}(\cdot )$来表示。

密钥生成算法KenGen

$KeyGen(1^{\lambda })$：和第二阶段一样，密钥向量$\vec{s}\in {\mathbb{Z}}_q^n$
s ⃗ ← ( s ~ − 1 ) \vec s \leftarrow \left(

$$\begin{array}{c} \tilde{s} \\ -1 \end{array}$$ \right) s ←(s~−1​)

加密算法Enc

E n c ( s ⃗ , μ ∈ { 0 , 1 } ) Enc(\vec s, \mu \in \{0,1\}) Enc(s ,μ∈{0,1})：前文说过如果$\mu$过大将导致噪音${\mu }_2\cdot {\vec{e}}_1$过大，所以这里设置为每次只加密一个比特。
加密过程类似， 但是为了使得各项系数的维度相符合，在构造LWE问题实例的时候，选择将参数$m=n\cdot {\log }_2(q)$，然后随机生成一个矩阵$A\stackrel{R}{\leftarrow }{\mathbb{Z}}_q^{m\times (n-1)}$和对应的随机噪音$\vec{e}\stackrel{R}{\leftarrow }{x}_B^m$，接着计算到密文$C$
$$C=(A,A\cdot \tilde{s}+\vec{e})+\mu \cdot G\in {\mathbb{Z}}_q^{m\times n}$$
在算出$C$之后不直接输出，而是输出它的二进制分解态$\hat{C}\leftarrow G^{-1}(C)$作为密文。

解密算法Dec

$Dec(\vec{s},C)$:首先对二进制状态的密文进行二进制重组再进行正常解密。
C ^ ⋅ G ⋅ s ⃗ = C ⋅ s ⃗ = ( A , A ⋅ s ~ + e ⃗ ) ( s ~ − 1 ) + μ ⋅ G ⋅ s ⃗ = A ⋅ s ~ − A ⋅ s ~ − e ⃗ + μ ⋅ G ⋅ s ⃗ = μ ⋅ G ⋅ s ⃗ − e ⃗

$$\begin{aligned} \hat{C} \cdot G \cdot \vec{s} &=C \cdot \vec{s} \\ &=(A, A \cdot \tilde{s}+\vec{e})\left(\begin{array}{c} \tilde{s} \\ -1 \end{array}\right)+\mu \cdot G \cdot \vec{s} \\ &=A \cdot \tilde{s}-A \cdot \tilde{s}-\vec{e}+\mu \cdot G \cdot \vec{s} \\ &=\mu \cdot G \cdot \vec{s}-\vec{e} \end{aligned}$$ C^⋅G⋅s ​=C⋅s =(A,A⋅s~+e )(s~−1​)+μ⋅G⋅s =A⋅s~−A⋅s~−e +μ⋅G⋅s =μ⋅G⋅s −e ​
这里$G$为$m\times n$，$\vec{s}$为$n\times 1$ ，最后乘法结果得到$m$元素的向量作为结果的乘积，而这个向量中则蕴含了加密的原文的信息。

注意观察前面的二进制重组矩阵$G$的第一行，它是 G 1 = [ 1 0 ⋯ 0 ] G1 = \left[

$$\begin{array}{llll} 1 & 0 & \cdots & 0 \end{array}$$ \right] G1=[1​0​⋯​0​]，于是最后得到的表达式$\mu \cdot G\cdot \vec{s}$的第一项的第一个元素为
$$(\mu \cdot G\cdot \vec{s}{)}_1=\mu \cdot (\vec{G}{)}_1\cdot \vec{s}=\mu \cdot \left[\begin{array}{llll}1& 0& \cdots & 0\end{array}\right]\cdot \left[\begin{array}{c}{s}_1\\ ⋮\\ s_{n-1}\\ -1\end{array}\right]=\mu \cdot s_1$$
想要的原文是$\mu$，这里的$s_1$是密钥生成阶段随机选取的一个数字，而它是随机分布于${\mathbb{Z}}_q$的，也就是说很大概率上会是一个远大于噪音上限的数字，那么就可以只计算+观察得到的第一项结果$(\mu \cdot G\cdot \vec{s}{)}_1-{\vec{e}}_1$，这里知道这个等式的第一项中$\mu$为0 or 1，如果为0，那么0乘以一个大数还是为0，再减去一个随机噪音小数那么结果将是较小的（在可以接受的噪音范围之内，比如$q/4$），这就可以输出$\mu =0$，反之，若为1的话，那么等式结果应该是一个大数来减去一个随机噪音小数，结果必然是很大的，这时就可以输出$\mu =1$。

运算算法Eval

加法$Eval(+,C_1,C_2)$：
( C ^ 1 + C ^ 2 ) ⋅ G ⋅ s ⃗ = C ^ 1 ⋅ G ⋅ s ⃗ + C ^ 2 ⋅ G ⋅ s ⃗ = μ 1 ⋅ G ⋅ s ⃗ − e ⃗ 1 + μ 2 ⋅ G ⋅ s ⃗ − e ⃗ 2 = ( μ 1 + μ 2 ) ⋅ G ⋅ s ⃗ ⏟ addition of plaintext  − ( e ⃗ 1 + e ⃗ 2 ) ⏟ small error term 

$$\begin{aligned} \left(\hat{C}_{1}+\hat{C}_{2}\right) \cdot G \cdot \vec{s} &=\hat{C}_{1} \cdot G \cdot \vec{s}+\hat{C}_{2} \cdot G \cdot \vec{s} \\ &=\mu_{1} \cdot G \cdot \vec{s}-\vec{e}_{1}+\mu_{2} \cdot G \cdot \vec{s}-\vec{e}_{2} \\ &=\underbrace{\left(\mu_{1}+\mu_{2}\right) \cdot G \cdot \vec{s}}_{\text {addition of plaintext }}-\underbrace{\left(\vec{e}_{1}+\vec{e}_{2}\right)}_{\text {small error term }} \end{aligned}$$ (C^1​+C^2​)⋅G⋅s ​=C^1​⋅G⋅s +C^2​⋅G⋅s =μ1​⋅G⋅s −e 1​+μ2​⋅G⋅s −e 2​=addition of plaintext  (μ1​+μ2​)⋅G⋅s ​​−small error term  (e 1​+e 2​)​​​
可以看到噪音只是${\vec{e}}_1+{\vec{e}}_2$，很小。
乘法$Eval(\times ,C_1,C_2)$：
$$\begin{array}{rl}\left({\hat{C}}_1\cdot {\hat{C}}_2\right)\cdot G\cdot \vec{s}& ={\hat{C}}_1\cdot \left({\hat{C}}_2\cdot G\right)\cdot \vec{s}\\ & ={\hat{C}}_1\cdot C_2\cdot \vec{s}\\ & ={\hat{C}}_1\cdot \left({\mu }_2\cdot G\cdot \vec{s}+{\vec{e}}_2\right)\\ & ={\mu }_2\cdot {\hat{C}}_1\cdot G\cdot \vec{s}+{\hat{C}}_1\cdot {\vec{e}}_2\\ & ={\mu }_2\cdot \left({\mu }_1\cdot G\cdot \vec{s}+{\vec{e}}_1\right)+{\hat{C}}_1\cdot {\vec{e}}_2\\ & =\underset{\text{multiplication of pt }}{\underbrace{\left({\mu }_1\cdot {\mu }_2\right)\cdot G\cdot \vec{s}}}+\underset{\text{small error term }}{\underbrace{{\mu }_2\cdot {\vec{e}}_1}}+\underset{\text{relatively small }}{\underbrace{{\hat{C}}_1\cdot {\vec{e}}_2}}(\mathrm{mod}q)\end{array}$$
还是分三项，由于第二项已经约束$\mu$为一个比特，所以噪音很小。
在看第三项，在两个矩阵相乘的结果是一个二进制矩阵，它的无穷范数很小，最大的噪音上限也就是$n\times {\log }_2(q)\times B$，是远小于$m\times q\times B$，而且由于$n$和$q$增大，这一项的噪音也会增大，但噪音上限是可控的，这足够做很多次加法和乘法了。而乘法会有一个上限，这就是GSW所描述的LFHE的系统。

GSW上的bootstrapping操作

Bootstrapping参考
这里回顾一下GSW的解密
$\hat{C}$是密文的二进制矩阵，$G$为二进制重组矩阵用户还原$\hat{C}$为密文$C$。解密过程如下
C ^ ⋅ G ⋅ s ⃗ = C ⋅ s ⃗ = ( A , A ⋅ s ~ + e ⃗ ) ( s ~ − 1 ) + μ ⋅ G ⋅ s ⃗ = A ⋅ s ~ − A ⋅ s ~ − e ⃗ + μ ⋅ G ⋅ s ⃗ = μ ⋅ G ⋅ s ⃗ − e ⃗

$$\begin{aligned} \hat{C} \cdot G \cdot \vec{s} &=C \cdot \vec{s} \\ &=(A, A \cdot \tilde{s}+\vec{e})\left(\begin{array}{c} \tilde{s} \\ -1 \end{array}\right)+\mu \cdot G \cdot \vec{s} \\ &=A \cdot \tilde{s}-A \cdot \tilde{s}-\vec{e}+\mu \cdot G \cdot \vec{s} \\ &=\mu \cdot G \cdot \vec{s}-\vec{e} \end{aligned}$$ C^⋅G⋅s ​=C⋅s =(A,A⋅s~+e )(s~−1​)+μ⋅G⋅s =A⋅s~−A⋅s~−e +μ⋅G⋅s =μ⋅G⋅s −e ​
只需要取这个结果的第一项，看它的值是大还是小，就可以判定明文$\mu$的值了。

即同态的运算一下解密过程，将密文还原为原文，并将噪声值还原为初始值。
第一步首先完成解密，需要一个加密过后的密钥$c{t}_{\vec{s}}\in {\mathbb{Z}}_q^n$。由于加密是针对比特加密的，所以需要将向量$\vec{s}$的每一个比特进行加密得到$n\times lo{g}_2(q)个密文$。
接着进行线性乘积计算，也就是基于$C$的第一行$C_1$值（只需要看解密之后的第一项即可），构造一个解密的线性函数$De{c}_{Lin}$，该函数的效果是把$\vec{s}$中的每一项都乘以$C_1$系数然后相加。
$$c{t}_{De{c}_{Lin}}=Eval(De{c}_{Lin},c{t}_{\vec{s}},C_1)$$
这样将会得到一个结果。
接下来第二步要做的是根据这个结果来判定原明文是0还是1。这是个难点，很难判断，不能用简单的加法或者乘法来让一个${\mathbb{Z}}_q$中的数字映射到${\mathbb{Z}}_2$中的一个比特值。
整个解密电路的复杂度会变得非常高，甚至高于我们真正想要进行同态计算的电路。为了使得Bootstrapping之后的密文的噪音值会“降低”到一个比原来更低的值，就需要被迫扩大GSW的模组和其他参数，使得能够成功的在噪音区间内同态解密，这会使得大部分算力都花在计算Bootstrapping上面，显得效率太低了。
为了提升Bootstrapping的效率，后续15和16年相继提出了FHEW和THEW方案。

GSW原文学习

前置知识

LWE实例

生成一个$LW{E}_{n,q,\chi }$实例需要三个参数，也就是维数，模数和概率分布，这三个一般由输入一个安全参数$\lambda$和电路深度$L$的函数生成，还需要一个参数m，它代表向量的个数或者方程的组数。
$$A\stackrel{R}{\leftarrow }{\mathbb{Z}}_q^{m\times n},s\stackrel{R}{⟵}{\mathbb{Z}}_q^n,e\stackrel{R}{\leftarrow }{\chi }^m$$
$(A,As+e)$叫做一个LWE实例，它是一个由向量拼成的一个m行，n+1列的矩阵。

Flattening（扁平化）

也就是前面所说的二进制分解。
$<\mathbf{a},\mathbf{b}>$，是两个向量$\mathbf{a},\mathbf{b}$(都$\in {\mathbb{Z}}_q^k$)的内积，目的就是为了减少同态操作出现的噪声。

几个参数$\ell =\lfloor {\log }_{2}q\rfloor +1$、$N=k\cdot \ell$

几个主要函数

• $BitDecomp(\mathbf{a})=\left(a_{1,0},\dots ,a_{1,\ell -1},\dots ,a_{k,0},\dots ,a_{k,\ell -1}\right)={\mathbf{a}}^{\prime }$
  这个函数把向量转换为二进制。

• $BitDecom{p}^{-1}({\mathbf{a}}^{\prime })=\left(\sum 2^j\cdot a_{1,j},\dots ,\sum 2^j\cdot a_{k,j}\right)=\mathbf{a}$
  前一个的逆运算。

• $Flatten({\mathbf{a}}^{\prime })=BitDecomp(BitDecom{p}^{-1}({\mathbf{a}}^{\prime }))$
  先二进制逆运算再二进制化，可以保证无论输入的是二进制向量还是一般向量输出结果都是二进制的，也就是把向量变为二进制的。

• $Powersof2(\mathbf{b})=\left(b_1,2b_1,\dots ,2^{\ell -1}{b}_1,\dots ,b_k,2b_k,\dots ,2^{\ell -1}{b}_k\right)$
  相当于把向量的每一项都拆成了二进制，但是对应进制位上的不是0或1，而是原来的项，并且要乘以对应的2的幂。这个操作主要是为了使得两个向量的内积结果不会因为运算而变化。

这样可以得出几个常用的计算

• $<BitDecomp(\mathbf{a}),Powersof2(\mathbf{b})>=<\mathbf{a},\mathbf{b}>$
  一个二进制化，一个对应幂化，乘起来自然结果不变。
• 对任意N维的${\mathbf{a}}^{\prime }$向量，有$<{\mathbf{a}}^{\prime },Powersof2(\mathbf{b})>=<BitDecom{p}^{-1}({\mathbf{a}}^{\prime }),\mathbf{b}>=<Flatten({\mathbf{a}}^{\prime }),Powersof2(\mathbf{b})>$

基本方案

$KeyGen$（密钥生成）：分为三个阶段。

• $Setup(1^{\lambda },1^L)$：
  输入安全参数$\lambda$和电路深度$L$，输出$k$ bits的模数$q$、噪音分布$\chi$（是$\mathbb{Z}$上的噪音高斯分布）、维数$n$，向量数量$m$（一般大于$2n\log q$）
  参数集$params=(n,q,\chi ,m)$
  另外几个参数$\ell =\lfloor {\log }_{2}q\rfloor +1$、$N=(n+1)\cdot \ell$

• $SecretKeyGen(params)$：
  随机选取向量$\mathbf{t}\leftarrow {\mathbb{Z}}_q^n$（n列矩阵），计算私钥 s k = s ← ( 1 − t ) ∈ Z q n + 1 sk = \bm{s} \leftarrow \left(

  $$\begin{array}{c} 1 \\ -\bm{t} \end{array}$$ \right) \in \mathbb{Z}_q^{n+1} sk=s←(1−t​)∈Zqn+1​（n+1列矩阵），再让$\mathbf{v}=Powersof2(\mathbf{s})$。

• $PublicKenGen(params,sk)$：
  随机均匀选取矩阵$B\leftarrow {\mathbb{Z}}_q^{m\times n}$，噪音向量$\mathbf{e}\leftarrow {\chi }^m$
  设$\mathbf{b}=B\cdot \mathbf{t}+\mathbf{e}$（计算出来是1列矩阵）
  再设矩阵$A$是由$\mathbf{b}$和$B$拼接乘的$n+1$列矩阵，即，$A=[\mathbf{b}|B]=(\mathbf{b},B)\in {\mathbb{Z}}_q^{m\times (n+1)}$，其中 A ⋅ s = ( b , B ) ⋅ ( 1 − t ) = b − B ⋅ t = e A \cdot \bm{s} = (\bm{b},B) \cdot \left(

  $$\begin{array}{c} 1 \\ -\bm{t} \end{array}$$ \right) =\bm{b} - B \cdot \bm{t}=\bm{e} A⋅s=(b,B)⋅(1−t​)=b−B⋅t=e
  输出$pk=A$。

$Enc$（加密算法）：
$Enc(params,pk,\mu )$
设明文$\mu \in {\mathbb{Z}}_q$，随机均匀取一个矩阵 R ∈ { 0 , 1 } N × m R \in \{0,1\}^{N \times m} R∈{0,1}N×m，输出密文$C$如下
$$C=Flatten(\mu \cdot I_N+BitDecomp(R\cdot A))\in {\mathbb{Z}}_q^{N\times N}$$
$I_N$是一个单位矩阵，加密就是将明文和LWE实例叠加，然后输出二进制的密文。

$Dec$（解密算法）：
$Dec(params,pk,C)$
C ⋅ v = μ ⋅ v + B i t D e c o m p ( R ⋅ A ) ⋅ v = μ ⋅ v + R ⋅ A ⋅ s = μ ⋅ v + R ⋅ e = μ ⋅ v + s m a l l

$$\begin{aligned} C \cdot \bm{v} &= \mu \cdot \bm{v} +BitDecomp(R \cdot A) \cdot \bm{v} \\ &= \mu \cdot \bm{v} + R \cdot A \cdot \bm{s} \\ & = \mu \cdot \bm{v} + R \cdot \bm{e} \\ & = \mu \cdot \bm{v} + small \end{aligned}$$ C⋅v​=μ⋅v+BitDecomp(R⋅A)⋅v=μ⋅v+R⋅A⋅s=μ⋅v+R⋅e=μ⋅v+small​
由于向量$v$的系数是乘以了2的幂，就是$(1,2,\cdots ,2^{\ell -1})$，则这里面一定有一个足够大的系数来还原出明文$\mu$。
另外这里的$\mu$貌似不是0或1，而是一个未知整数。这里给的解密法是，选取一个位于$(q/4,q/2]$的大数$v_i$（其实就是随便选一列在范围内），再取密文的第$i$行$C_i$，计算明文${\mu }^{\prime }=\lfloor x_i/v_i\rceil$（最近整数，也就是四舍五入）。

可以算出，若噪音$e^{\prime }$的最大限度为$q/8$，而$v_i\in (q/4,q/2]$，那么结果$x_i/v_i=(\mu \cdot v_i+e^{\prime })/vi=\mu +1/2$，经过四舍五入是能够正确解密的。

同态操作就和前文的类似了，这里列举一个乘法
$Mult(C_1,C_2)$输入两个密文，输出二进制结果
M u l t ( C 1 , C 2 ) ⋅ v = C 1 ⋅ C 2 ⋅ v = C 1 ⋅ ( μ 2 ⋅ v + e 2 ) = μ 2 ⋅ ( μ 1 ⋅ v + e 1 ) + C 1 ⋅ e 2 = μ 1 ⋅ μ 2 ⋅ v + μ 2 ⋅ e 1 + C 1 ⋅ e 2

$$\begin{aligned} Mult(C_1,C_2) \cdot \bm{v} &= C_1 \cdot C_2 \cdot \bm{v} \\ & = C_1 \cdot (\mu_2 \cdot \bm{v}+e_2) \\ & = \mu_2 \cdot (\mu_1 \cdot \bm{v}+e_1) + C_1 \cdot e_2 \\ & = \mu_1 \cdot \mu_2 \cdot \bm{v} + \mu_2 \cdot e_1+C_1 \cdot e_2 \end{aligned}$$ Mult(C1​,C2​)⋅v​=C1​⋅C2​⋅v=C1​⋅(μ2​⋅v+e2​)=μ2​⋅(μ1​⋅v+e1​)+C1​⋅e2​=μ1​⋅μ2​⋅v+μ2​⋅e1​+C1​⋅e2​​
这里$C_1$，是二进制化的，所以噪声还是比较小。

参考

初探全同态加密之三：构建GSW全同态加密系统
同态加密GSW方案学习笔记1-GSW最初方案概述

C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler,asymptotically-faster, attribute-based. In R. Canetti and J. A. Garay, editors, CRYPTO 2013, Part I, volume8042 of LNCS, pages 75–92. Springer, Aug. 2013.