帮助理解

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

第一阶段

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

密钥生成算法KenGen

这里随机选取一个向量s⃗\vec ss作为加密密钥

“加密”算法Enc

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

解密算法Dec

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

运算算法Eval

从FHE定义中不难看到，EvalEvalEval算法满足加法和乘法任意次计算，这个体系就是全同态。
假定有两个密文C1,C2C_1,C_2C1​,C2​和对应明文μ1,μ2\mu_1,\mu2μ1​,μ2。
加法验证Eval(+,C1,C2)Eval(+,C_1,C_2)Eval(+,C1​,C2​)：
(C1±C2)⋅s⃗=C1⋅s⃗±C2⋅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(×,C1,C2)Eval(\times,C_1,C_2)Eval(×,C1​,C2​)：
(C1⋅C2)⋅s⃗=C1⋅(C2⋅s⃗)=C1⋅μ2⋅s⃗=μ2⋅C1⋅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​

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

存在的问题

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

第二阶段

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

密钥生成算法KenGen

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

加密算法Enc

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

解密算法Dec

Dec(s⃗,C)Dec(\vec s,C)Dec(s,C):和第一阶段一样，计算出C⋅s⃗C \cdot \vec sC⋅s，然后通过观察得到大致倍数，就可以还原出明文了。
C⋅s⃗=((A,A⋅s~+e⃗)+μ⋅In)⋅s⃗=(A,A⋅s~+e⃗)⋅s⃗+μ⋅In⋅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⋅s~+e⃗)(A, A \cdot \tilde{s}+\vec{e})(A,A⋅s~+e)和s⃗\vec{s}s分别看作拼装的1×21 \times 21×2和2×12 \times 12×1矩阵，那乘法就等于是把把LWE的问题矩阵AAA与未知向量s~\tilde{s}s~相乘，再减去A⋅s~+e⃗A \cdot \tilde{s}+\vec{e}A⋅s~+e，最后就只剩一项噪音向量。
解密结果和在特征向量等式中加入噪音是一样的，另外噪音的绝对值只需要符合一个上限BBB就行了，所以正负号没有什么区别。
然后由于解密得到的关系式和之前的特征向量关系式大概一致，我们可以称这里的私密向量为矩阵CCC的近似特征向量（approximate eigenvector）。

运算算法Eval

在安全性得到保证之后呢，再来验证一下是否满足全同态。
加法Eval(+,C1,C2)Eval(+,C_1,C_2)Eval(+,C1​,C2​)：对结果进行解密
(C1+C2)⋅s⃗=C1⋅s⃗+C2⋅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+e1​+μ2​⋅s+e2​=(μ1​+μ2​)⋅s+small error term (e1​+e2​)​​​
可以看到结果是比较好看的，能有效得到明文之和，而这里同样的会使得两个随机噪音进行叠加，但是规定的噪音取值上限BBB一般来说很小，所以即便是叠加起来也只是2B2B2B的容错率，考虑到B<

乘法Eval(×,C1,C2)Eval(\times,C_1,C_2)Eval(×,C1​,C2​)：
(C1⋅C2)⋅s⃗=C1⋅(C2⋅s⃗)=C1⋅(μ2⋅s⃗+e⃗2)=μ2⋅C1⋅s⃗+C1⋅e⃗2=μ1⋅μ2⋅s⃗⏟Result +μ2⋅e⃗1⏟ok error term +C1⋅e⃗2⏟large error term! (modq)\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+e2​)=μ2​⋅C1​⋅s+C1​⋅e2​=Result μ1​⋅μ2​⋅s​​+ok error term μ2​⋅e1​​​+large error term! C1​⋅e2​​​(modq)​
可以看到，这里比想要的μ1⋅μ2⋅s⃗\mu_1 \cdot \mu_2 \cdot \vec sμ1​⋅μ2​⋅s多出了一个μ2⋅e⃗1\mu_{2} \cdot \vec{e}_{1}μ2​⋅e1​和一个C1⋅e⃗2C_{1} \cdot \vec{e}_{2}C1​⋅e2​。
来看看多出的两个会不会对结果有很大的影响.

第一个噪音μ2⋅e⃗1\mu_{2} \cdot \vec{e}_{1}μ2​⋅e1​似乎就有不小的影响，如果这个μ2\mu_{2}μ2​比较大的话，那就会超出噪音上限从而丢失精度。

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

第三阶段

解决大噪音问题

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

而对于第二个噪音C1⋅e⃗2C_{1} \cdot \vec{e}_{2}C1​⋅e2​上，也就是C1C_1C1​这个矩阵上，因为矩阵的无穷范数是∥C∥∞≤q/2\|C\|_{\infty} \leq q / 2∥C∥∞​≤q/2，矩阵中的数字取值是毫无约束的随机数。接下来的目标是把这个取值范围调整到能控制的小范围内，同时还要保证数字是随机取的。

二进制拆分（也叫扁平化）
将数字用二进制的一串比特表示，可以使得这个数字的范数降低。
x^=(x0,x1,…,xlog⁡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)\log_{2} (q)log2​(q)个比特，每个比特取值范围都是{0,1}\{0,1\}{0,1}，这样便可以使得其无穷范数大大降低。
∥x^∥∞≤1\|\hat{x}\|_{\infty} \leq 1 ∥x^∥∞​≤1
同理可以对一个向量的每一个元素进行二进制拆分，然后连在一起就可以了，假如有向量v=(v0,v1,…,vn−1):v=\left(v_{0}, v_{1}, \ldots, v_{n-1}\right):v=(v0​,v1​,…,vn−1​):
v^=(v0,0,…,v0,log⁡2(q)−1⏟log⁡(q)−1elements ,v1,0,…,v1,log⁡2(q)−1,…,vn−1,0,…,vn−1,log⁡2(q)−1)\hat{v}=(\underbrace{v_{0,0}, \ldots, v_{0, \log_{2} (q)-1}}_{\log (\mathrm{q})-1 \text { elements }}, v_{1,0}, \ldots, v_{1, \log_{2} (q)-1}, \ldots, v_{n-1,0}, \ldots, v_{n-1, \log_{2} (q)-1}) v^=(log(q)−1 elements v0,0​,…,v0,log2​(q)−1​​​,v1,0​,…,v1,log2​(q)−1​,…,vn−1,0​,…,vn−1,log2​(q)−1​)
分解后得到一共n×log⁡2(q)n \times \log_{2} (q)n×log2​(q)个元素，每个元素都是一个二进制比特。
接着，假如对一个矩阵进行二进制拆分，即把每一行当作一个单独的向量分解，假如有一个m×nm \times nm×n的矩阵，通过分解就将得到维度为m×n×log⁡2(q)m \times n \times \log_{2} (q)m×n×log2​(q)。
此外，二进制拆分还有一个好处即，如果想把二进制分解态进行还原的话，整个过程是一个线性变换的过程，例如把上面的x^\hat xx^还原：
x=∑i=0log⁡2(q)−1xi⋅2ix=\sum_{i=0}^{\log_{2} (q)-1} x_{i} \cdot 2^{i} x=i=0∑log2​(q)−1​xi​⋅2i
同理，对矩阵进行二进制还原，通过一个二进制重组矩阵GGG来变换。
C=C^⋅G=[C^1⋮C^m]⋅G=[C0,0,0⋯C0,0,log⁡2(q)−1…C0,n−1,0…C0,n−1,log⁡2(q)−1⋮⋱⋮⋱⋮⋱⋮Cm−1,0,0…Cm−1,0,log⁡2(q)−1…Cm−1,n−1,0…Cm−1,n−1,log(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​
重组矩阵GGG
G=[200⋯0210⋯0⋮⋮⋱⋮2log⁡2(q)−10⋯0020⋯0⋮⋮⋱⋮00⋯2log⁡2(q)−1]G=\left[\begin{array}{cccc} 2^{0} & 0 & \cdots & 0 \\ 2^{1} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 2^{\log_{2} (q)-1} & 0 & \cdots & 0 \\ 0 & 2^{0} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 2^{\log_{2} (q)-1} \end{array}\right] G=⎣⎡​2021⋮2log2​(q)−10⋮0​00⋮020⋮0​⋯⋯⋱⋯⋯⋱⋯​00⋮00⋮2log2​(q)−1​⎦⎤​
矩阵GGG中，每一列系数对应C^\hat CC^中的每一行的每log⁡2(q)\log_{2} (q)log2​(q)个bits的线性重组，也就是C^\hat CC^为m×(n×log⁡2(q))m \times (n \times \log_{2} (q))m×(n×log2​(q))的矩阵，GGG为(n×log⁡2(q))×m(n \times \log_{2} (q)) \times m(n×log2​(q))×m的矩阵，这样最后相乘就可以还原出最初的CCC，同时二进制分解矩阵就可以用G−1(⋅)G^{-1}(\cdot)G−1(⋅)来表示。

密钥生成算法KenGen

KeyGen(1λ)KeyGen(1^\lambda)KeyGen(1λ)：和第二阶段一样，密钥向量s⃗∈Zqn\vec s \in \mathbb{Z}_q^{n}s∈Zqn​
s⃗←(s~−1)\vec s \leftarrow \left(\begin{array}{c} \tilde{s} \\ -1 \end{array}\right) s←(s~−1​)

加密算法Enc

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

解密算法Dec

Dec(s⃗,C)Dec(\vec s,C)Dec(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​
这里GGG为m×nm \times nm×n，s⃗\vec ss为n×1n \times 1n×1 ，最后乘法结果得到mmm元素的向量作为结果的乘积，而这个向量中则蕴含了加密的原文的信息。

注意观察前面的二进制重组矩阵GGG的第一行，它是G1=[10⋯0]G1 = \left[\begin{array}{llll} 1 & 0 & \cdots & 0 \end{array}\right]G1=[1​0​⋯​0​]，于是最后得到的表达式μ⋅G⋅s⃗\mu \cdot G \cdot \vec{s}μ⋅G⋅s的第一项的第一个元素为
(μ⋅G⋅s⃗)1=μ⋅(G⃗)1⋅s⃗=μ⋅[10⋯0]⋅[s1⋮sn−1−1]=μ⋅s1(\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} \\ \vdots \\ s_{n-1} \\ -1 \end{array}\right]=\mu \cdot s_{1} (μ⋅G⋅s)1​=μ⋅(G)1​⋅s=μ⋅[1​0​⋯​0​]⋅⎣⎡​s1​⋮sn−1​−1​⎦⎤​=μ⋅s1​
想要的原文是μ\muμ，这里的s1s_1s1​是密钥生成阶段随机选取的一个数字，而它是随机分布于Zq\mathbb{Z}_qZq​的，也就是说很大概率上会是一个远大于噪音上限的数字，那么就可以只计算+观察得到的第一项结果(μ⋅G⋅s⃗)1−e⃗1(\mu \cdot G \cdot \vec{s})_{1}-\vec e_1(μ⋅G⋅s)1​−e1​，这里知道这个等式的第一项中μ\muμ为0 or 1，如果为0，那么0乘以一个大数还是为0，再减去一个随机噪音小数那么结果将是较小的（在可以接受的噪音范围之内，比如q/4q/4q/4），这就可以输出μ=0\mu=0μ=0，反之，若为1的话，那么等式结果应该是一个大数来减去一个随机噪音小数，结果必然是很大的，这时就可以输出μ=1\mu=1μ=1。

运算算法Eval

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

GSW上的bootstrapping操作

Bootstrapping参考
这里回顾一下GSW的解密
C^\hat CC^是密文的二进制矩阵，GGG为二进制重组矩阵用户还原C^\hat CC^为密文CCC。解密过程如下
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μ的值了。

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

GSW原文学习

前置知识

LWE实例

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

Flattening（扁平化）

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

几个参数ℓ=⌊log⁡2q⌋+1\ell = \left\lfloor\log _{2} q\right\rfloor + 1ℓ=⌊log2​q⌋+1、N=k⋅ℓN = k \cdot \ellN=k⋅ℓ

几个主要函数

• BitDecomp(a)=(a1,0,…,a1,ℓ−1,…,ak,0,…,ak,ℓ−1)=a′BitDecomp(\bm{a}) = \left(a_{1,0}, \ldots, a_{1, \ell-1}, \ldots, a_{k, 0}, \ldots, a_{k, \ell-1}\right) = \bm{a'}BitDecomp(a)=(a1,0​,…,a1,ℓ−1​,…,ak,0​,…,ak,ℓ−1​)=a′
  这个函数把向量转换为二进制。

• BitDecomp−1(a′)=(∑2j⋅a1,j,…,∑2j⋅ak,j)=aBitDecomp^{-1}(\bm{a'})=\left(\sum 2^{j} \cdot a_{1, j}, \ldots, \sum 2^{j} \cdot a_{k, j}\right)=\bm{a}BitDecomp−1(a′)=(∑2j⋅a1,j​,…,∑2j⋅ak,j​)=a
  前一个的逆运算。

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

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

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

• ==<\bm{a},\bm{b}>=
  一个二进制化，一个对应幂化，乘起来自然结果不变。
• 对任意N维的a′\bm{a'}a′向量，有==<\bm{a'},Powersof2(\bm{b})>====

基本方案

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

• Setup(1λ,1L)Setup(1^\lambda,1^L)Setup(1λ,1L)：
  输入安全参数λ\lambdaλ和电路深度LLL，输出kkk bits的模数qqq、噪音分布χ\chiχ（是Z\mathbb{Z}Z上的噪音高斯分布）、维数nnn，向量数量mmm（一般大于2nlog⁡q2n\log q2nlogq）
  参数集params=(n,q,χ,m)params = (n,q,\chi,m)params=(n,q,χ,m)
  另外几个参数ℓ=⌊log⁡2q⌋+1\ell = \left\lfloor\log _{2} q\right\rfloor + 1ℓ=⌊log2​q⌋+1、N=(n+1)⋅ℓN = (n+1) \cdot \ellN=(n+1)⋅ℓ

• SecretKeyGen(params)SecretKeyGen(params)SecretKeyGen(params)：
  随机选取向量t←Zqn\bm{t} \leftarrow \mathbb{Z}_q^nt←Zqn​（n列矩阵），计算私钥sk=s←(1−t)∈Zqn+1sk = \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列矩阵），再让v=Powersof2(s)\bm{v} = Powersof2(\bm{s})v=Powersof2(s)。

• PublicKenGen(params,sk)PublicKenGen(params,sk)PublicKenGen(params,sk)：
  随机均匀选取矩阵B←Zqm×nB \leftarrow \mathbb{Z}_q^{m \times n}B←Zqm×n​，噪音向量e←χm\bm{e} \leftarrow \chi^me←χm
  设b=B⋅t+e\bm{b}=B \cdot \bm{t} + \bm{e}b=B⋅t+e（计算出来是1列矩阵）
  再设矩阵AAA是由b\bm{b}b和BBB拼接乘的n+1n+1n+1列矩阵，即，A=[b∣B]=(b,B)∈Zqm×(n+1)A = [\bm{b}|B] = (\bm{b},B)\in \mathbb{Z}_q^{m \times (n+1)}A=[b∣B]=(b,B)∈Zqm×(n+1)​，其中A⋅s=(b,B)⋅(1−t)=b−B⋅t=eA \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=Apk = Apk=A。

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

DecDecDec（解密算法）：
Dec(params,pk,C)Dec(params,pk,C)Dec(params,pk,C)
C⋅v=μ⋅v+BitDecomp(R⋅A)⋅v=μ⋅v+R⋅A⋅s=μ⋅v+R⋅e=μ⋅v+small\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​
由于向量vvv的系数是乘以了2的幂，就是(1,2,⋯,2ℓ−1)(1,2,\cdots,2^{\ell -1})(1,2,⋯,2ℓ−1)，则这里面一定有一个足够大的系数来还原出明文μ\muμ。
另外这里的μ\muμ貌似不是0或1，而是一个未知整数。这里给的解密法是，选取一个位于(q/4,q/2](q/4,q/2](q/4,q/2]的大数viv_ivi​（其实就是随便选一列在范围内），再取密文的第iii行CiC_iCi​，计算明文μ′=⌊xi/vi⌉\mu' = \lfloor x_i/v_i \rceilμ′=⌊xi​/vi​⌉（最近整数，也就是四舍五入）。

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

同态操作就和前文的类似了，这里列举一个乘法
Mult(C1,C2)Mult(C_1,C_2)Mult(C1​,C2​)输入两个密文，输出二进制结果
Mult(C1,C2)⋅v=C1⋅C2⋅v=C1⋅(μ2⋅v+e2)=μ2⋅(μ1⋅v+e1)+C1⋅e2=μ1⋅μ2⋅v+μ2⋅e1+C1⋅e2\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​​
这里C1C_1C1​，是二进制化的，所以噪声还是比较小。

参考

初探全同态加密之三：构建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.