参考资料：

1. Micciancio D, Peikert C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[C]//Eurocrypt. 2012, 7237: 700-718.
2. Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error[C]//Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34. Springer Berlin Heidelberg, 2014: 297-314.
3. Ducas L, Micciancio D. FHEW: bootstrapping homomorphic encryption in less than a second[C]//Advances in Cryptology–EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I 34. Springer Berlin Heidelberg, 2015: 617-640.

文章目录

• HEPerm
• • Embedding
  • GSW
  • HEPerm
  • Bootstrapping
• FHEW
• • Notation
  • LWE Symmetric Encryption
  • NAND Gate
  • Homomorphic Accumulator

HEPerm

2014 年，Alperin 和 Peikert 提出了一种快速 Bootstrapping 方案。他们将加法群 ZqZ_qZq​ 嵌入到对称群 SqS_qSq​ （置换矩阵 {0,1}q×q\{0,1\}^{q \times q}{0,1}q×q 的乘法群）上。利用 GSW 乘法噪声增长的非对称性，采用右结合的乘法链其噪声增长是拟加性的（quasi-additive）。另外，他们给出了 GSW 的更简单的变体，可以证明两者是等价的。

本文重点关注如何快速自举，它可以兼容所有的基于 LWE 的 FHE。由于解密算法是：
Dec(s,c):=⌊⟨s,c⟩⌉2Dec(s,c) := \lfloor \langle s,c \rangle \rceil_2 Dec(s,c):=⌊⟨s,c⟩⌉2​

这里 ⌊x⌉2:=⌊2/q⋅x⌉\lfloor x \rceil_2 := \lfloor 2/q \cdot x \rceil⌊x⌉2​:=⌊2/q⋅x⌉ 是从 ZqZ_qZq​ 到 Z2Z_2Z2​ 的模切换，或者说是 MSB 的提取。那么，自举的关键就是：

• 对于固定的秘密 sss，对于任意密文 ccc，在 GSW 下同态地计算出内积 ⟨s,c⟩\langle s,c \rangle⟨s,c⟩（这是 subset-sum，只需要同态加法）。
• 对于计算出的 ⟨s,c⟩\langle s,c \rangle⟨s,c⟩ 的密文，提取出 MSB 对应的 LWE 密文（关键步骤）。

Embedding

根据 Cayley’s Theorem，任意的有限群 GGG 都可以嵌入（injective homomorphism）到对称群 S∣G∣S_{|G|}S∣G∣​ 中。而这个对称群同构于 ∣G∣|G|∣G∣ 阶的置换矩阵乘法群，置换 π\piπ 对应的置换矩阵为：
Pπ:=[eπ(1),eπ(2),⋯,eπ(∣G∣)]P_\pi := [e_{\pi(1)},e_{\pi(2)},\cdots,e_{\pi(|G|)}] Pπ​:=[eπ(1)​,eπ(2)​,⋯,eπ(∣G∣)​]

因此，任意的加法群 (Zr,+)(Z_r,+)(Zr​,+) 都可以嵌入到对称群 SrS_rSr​ 中，也就是 r×rr \times rr×r 的置换矩阵的乘法群。嵌入映射为：将元素 x∈Zrx \in Z_rx∈Zr​ 映射到位移 xxx 的循环置换（the permutation that cyclically rotates by x positions）。

我们定义 π:i→i+1(modr)\pi:i \to i+1 \pmod rπ:i→i+1(modr) 为循环位移置换，将 xxx 次置换的复合 π∘⋯∘π\pi \circ \cdots \circ \piπ∘⋯∘π 简记为 πx\pi^xπx。容易看出，循环置换 PπxP_{\pi^x}Pπx​ 可以被简化表示为一个 {0,1}r\{0,1\}^r{0,1}r 的指示向量 exe_xex​（indicator vector），其第 xxx 个分量是 111，其他分量都为 000，而对应的置换矩阵就是将 exe_xex​ 作为第一列，其他列依次是 exe_xex​ 的循环移位（cyclic shift）。

此时，ZrZ_rZr​ 与 SrS_rSr​ 上的运算对应关系为：

1. ZrZ_rZr​ 中的加法 x+y(modr)x+y \pmod rx+y(modr)，同构于 SrS_rSr​ 中的置换复合，或者说置换矩阵乘法 Pπx⋅PπyP_{\pi^x} \cdot P_{\pi^y}Pπx​⋅Pπy​，可以简化为 Pπx⋅eyP_{\pi^x} \cdot e_yPπx​⋅ey​（等价于多项式 ex,eye_x,e_yex​,ey​ 的在 Z2[x]/(xr−1)Z_2[x]/(x^r-1)Z2​[x]/(xr−1) 上的多项式乘积）
2. ZrZ_rZr​ 中的相等判定 x=v(modr)x = v \pmod rx=v(modr)，同构于 SrS_rSr​ 中的置换相等判定 Pπx=PπvP_{\pi^x} = P_{\pi^v}Pπx​=Pπv​，可以简化为 ex(v)e_x^{(v)}ex(v)​
3. ZrZ_rZr​ 中的提取 MSB ⌊x⌉2\lfloor x \rceil_2⌊x⌉2​，同构于 SrS_rSr​ 中的一些相等判定的加和，即 ∑v∈[r]s.t.⌊v⌉2=1ex(v)\sum_{v \in [r]\,s.t.\,\lfloor v \rceil_2=1} e_x^{(v)}∑v∈[r]s.t.⌊v⌉2​=1​ex(v)​

对于一个较大的模数 qqq，直接将 ZqZ_qZq​ 嵌入到 SqS_qSq​ 效率很低。优化思路是利用 CRT，如果让 q=∏iriq = \prod_i r_iq=∏i​ri​，其中 rir_iri​ 是规模 O~(1)\tilde O(1)O~(1) 的素数幂，那么有
Zq≅∏iZri⊆∏iSriZ_q \cong \prod_i Z_{r_i} \subseteq \prod_i S_{r_i} Zq​≅i∏​Zri​​⊆i∏​Sri​​

对应的嵌入映射为：
ϕ:x∈Zq↦(ex(modri))i∈∏iSri\phi: x \in Z_q \mapsto \left(e_{x \pmod{r_i}}\right)_i \in \prod_i S_{r_i} ϕ:x∈Zq​↦(ex(modri​)​)i​∈i∏​Sri​​

这样就可以在多个小规模的对称群 SriS_{r_i}Sri​​ 上执行计算。此时，

1. ZqZ_qZq​ 上的加法，同构于 ∏iSri\prod_i S_{r_i}∏i​Sri​​ 上的各个分量的置换各自复合，即
   (x+y):=(Pπx(modri)⋅ey(modri))i(x+y) := \left(P_{\pi^{x \pmod{r_i}}} \cdot e_{y \pmod{r_i}}\right)_i (x+y):=(Pπx(modri​)​⋅ey(modri​)​)i​

2. ZqZ_qZq​ 上的相等判定，同构于 ∏iSri\prod_i S_{r_i}∏i​Sri​​ 上的各个分量的相等判定的乘积（逻辑 AND），即
   [x=v]:=∏iex(modri)(v(modri))[x=v] := \prod_i e_{x \pmod{r_i}}^{(v \pmod{r_i})} [x=v]:=i∏​ex(modri​)(v(modri​))​

3. ZqZ_qZq​ 上的提取 MSB，同构于 ∏iSri\prod_i S_{r_i}∏i​Sri​​ 上的一些相等判定的加和（逻辑 OR），即
   ⌊x⌉2:=∑v∈[q]s.t.⌊v⌉2=1[x=v]\lfloor x \rceil_2 := \sum_{v \in [q]\,s.t.\,\lfloor v \rceil_2=1} [x=v] ⌊x⌉2​:=v∈[q]s.t.⌊v⌉2​=1∑​[x=v]

为了加速，文章选择让 qqq 是 max⁡iri\max_i r_imaxi​ri​ 的指数级大。根据 second Chebyshev function，
ψ(x):=∑pk≤xlog⁡p=log⁡(∏p≤xp⌊log⁡px⌋)\psi(x) := \sum_{p^k \le x} \log p = \log\left(\prod_{p \le x} p^{\lfloor \log_p x \rfloor}\right) ψ(x):=pk≤x∑​logp=log(p≤x∏​p⌊logp​x⌋)

因此，所有的小于 xxx 的最大素数幂 ri=p⌊log⁡px⌋r_i = p^{\lfloor \log_p x \rfloor}ri​=p⌊logp​x⌋ 的乘积 q=∏iriq=\prod_i r_iq=∏i​ri​ 大小为 exp⁡(ψ(x))\exp(\psi(x))exp(ψ(x))。已知 ψ(x)=x+O(x/log⁡x)\psi(x)=x+O(x/\log x)ψ(x)=x+O(x/logx)，并且对于所有的 x≥7x \ge 7x≥7 都有一个非渐进界 ψ(x)≥3x/4\psi(x)\ge 3x/4ψ(x)≥3x/4，所以有
q≥exp⁡(3x/4)≥exp⁡(3/4⋅max⁡iri)q \ge \exp(3x/4) \ge \exp(3/4 \cdot \max_i r_i) q≥exp(3x/4)≥exp(3/4⋅imax​ri​)

选取很小的界 xxx，就可以用一些最大素数幂 ri≤xr_i \le xri​≤x 合成出一个指数级大的模数 qqq。

GSW

本文给出了 GSW 的一个对称版本的更简单变体。

给定模数 qqq，令 l=⌈log⁡q⌉l = \lceil \log q \rceill=⌈logq⌉，定义 gadget column vector g=(1,2,4,⋯,2l−1)∈Zlg = (1,2,4,\cdots,2^{l-1}) \in Z^lg=(1,2,4,⋯,2l−1)∈Zl，它的倒数第二个分量为 2l−2∈[q/4,q/2)2^{l-2} \in [q/4,q/2)2l−2∈[q/4,q/2) 就是 GSW 中所谓 “big coefficient”。

根据 MP12，存在一个随机的可有效计算的函数 g−1:Zq→Zlg^{-1}:Z_q \to Z^lg−1:Zq​→Zl，使得 x←g−1(a)x \leftarrow g^{-1}(a)x←g−1(a) 是一个满足 a=⟨g,x⟩a=\langle g,x \ranglea=⟨g,x⟩ 的参数 O(1)O(1)O(1) 的亚高斯随机变量。具体地，就是使用随机版本的 Babai nearest-plane 算法，给定格 Λ⊥(gt):={z∈Zl:⟨g,x⟩≡0∈Zq}\Lambda^\perp(g^t) := \{z \in Z^l: \langle g,x \rangle \equiv 0 \in Z_q\}Λ⊥(gt):={z∈Zl:⟨g,x⟩≡0∈Zq​} 的一组 “好” 的基底 SSS，每次迭代中第 iii 次个基向量对应的系数服从中心零的 {ci−1,ci},ci∈1qZ∩[0,1)\{c_i-1,c_i\},\,c_i \in \frac{1}{q} Z \cap [0,1){ci​−1,ci​},ci​∈q1​Z∩[0,1) 上二值分布。

对于向量和矩阵，定义 gadget matrix G=gt⊗In∈Zqn×nlG = g^t \otimes I_n \in Z_q^{n \times nl}G=gt⊗In​∈Zqn×nl​，对应的 G−1:Zqn×m→Zqnl×mG^{-1}: Z_q^{n \times m} \to Z_q^{nl \times m}G−1:Zqn×m​→Zqnl×m​ 就是对于每个 entry 独立的使用 g−1g^{-1}g−1 算法。那么给定 A=G⋅XA = G \cdot XA=G⋅X，X←G−1(A)X \leftarrow G^{-1}(A)X←G−1(A) 是一个参数 O(1)O(1)O(1) 的亚高斯随机向量（与任意的固定单位向量的内积是亚高斯的）。

在 GSW 中，密文 C∈{0,1}nl×nlC \in \{0,1\}^{nl \times nl}C∈{0,1}nl×nl 是二元方阵，秘密 s∈Zqnls \in Z_q^{nl}s∈Zqnl​ 是结构化向量（有个 “big coefficient”），它是个近似特征向量 stC≈μst(modq)s^tC \approx \mu s^t \pmod qstC≈μst(modq)。本文中的 GSW 变体，密文 C∈Zqn×nlC \in Z_q^{n \times nl}C∈Zqn×nl​ 是长矩阵，秘密 s∈Zns \in Z^{n}s∈Zn 是非结构化的短向量，关系为 stC≈μ⋅stG(modq)s^tC \approx \mu \cdot s^tG \pmod qstC≈μ⋅stG(modq)。两者是等价的。

对称的 GSW 变体：

1. GSW.Gen(1n)GSW.Gen(1^n)GSW.Gen(1n)：采样 sˉ←Rχn−1\bar s \leftarrow_R \chi^{n-1}sˉ←R​χn−1，输出 s:=(sˉ,1)s := (\bar s,1)s:=(sˉ,1)
2. GSW.Enc(s,μ∈Z)GSW.Enc(s,\mu \in \mathbb Z)GSW.Enc(s,μ∈Z)：采样 Cˉ←RZq(n−1)×nl\bar C \leftarrow_R Z_q^{(n-1)\times nl}Cˉ←R​Zq(n−1)×nl​ 和 e←χme \leftarrow \chi^me←χm，计算 bt=et−stCˉb^t = e^t - s^t \bar Cbt=et−stCˉ，输出 C=(Cˉ,bt)t+μG∈CC = (\bar C,b^t)^t + \mu G \in \mathcal CC=(Cˉ,bt)t+μG∈C（而原始 GSW 中是 Flatten(μInl+G−1(RA))=G−1(μG+RA)Flatten(\mu I_{nl}+G^{-1}(RA)) = G^{-1}(\mu G+RA)Flatten(μInl​+G−1(RA))=G−1(μG+RA)，两者等价）
3. GSW.Dec(s,C∈C)GSW.Dec(s,C \in \mathcal C)GSW.Dec(s,C∈C)：由于 stC=et+μ⋅stGs^tC = e^t + \mu \cdot s^t GstC=et+μ⋅stG，因此取出倒数第二列 ccc（GGG 的倒数第二列是 [0,⋯,0,2l−2][0,\cdots,0,2^{l-2}][0,⋯,0,2l−2]），计算出 2l−2⋅μ≈⟨s,c⟩2^{l-2} \cdot \mu \approx \langle s,c \rangle2l−2⋅μ≈⟨s,c⟩，输出 μ\muμ

在 LWEn−1,q,χLWE_{n-1,q,\chi}LWEn−1,q,χ​ 假设下，上述方案是 IND-CPA 安全的。

• 同态加法 C1⊞C2:=C1+C2C_1 \boxplus C_2:= C_1 + C_2C1​⊞C2​:=C1​+C2​，噪声 e1t+e2te_1^t+e_2^te1t​+e2t​
• 同态乘法 C1⊡C2:=C1⋅XC_1 \boxdot C_2:= C_1 \cdot XC1​⊡C2​:=C1​⋅X，噪声 e1tX+μ1e2te_1^t X + \mu_1 e_2^te1t​X+μ1​e2t​，其中 X←G−1(C2)X \leftarrow G^{-1}(C_2)X←G−1(C2​)

由于同态乘法的非对称噪声增长，我们令算符 ⊡\boxdot⊡ 是右结合的（ right associative）。对于一个关于密文 Ci,i=1,⋯,kC_i, i=1,\cdots,kCi​,i=1,⋯,k 的乘法链，
C←(⊡i∈[k]Ci)⊡G=C1⊡(⋯(Ck⊡G))∈CC \leftarrow \left(\boxdot_{i \in [k]} C_i\right) \boxdot G = C_1 \boxdot(\cdots(C_k \boxdot G)) \in \mathcal C C←(⊡i∈[k]​Ci​)⊡G=C1​⊡(⋯(Ck​⊡G))∈C

这里的 G=0+1⋅G∈CG = \textbf{0}+1 \cdot G \in \mathcal CG=0+1⋅G∈C 是个零噪声的 111 的密文。由于 μ∈{0,1}\mu \in \{0,1\}μ∈{0,1}，因此 CCC 的噪声为 ∑i∈[k]eitXi\sum_{i \in [k]} e_i^t X_i∑i∈[k]​eit​Xi​，这是参数 O(∥ei∥)O(\|e_i\|)O(∥ei​∥) 的亚高斯随机变量（拟加性）。

HEPerm

现在，我们基于上述的对称 GSW 方案，构造关于对称群 SrS_rSr​ 的同态方案（不是 FHE）：

1. HEPerm.Gen(1n)HEPerm.Gen(1^n)HEPerm.Gen(1n)：输出 sk:=GSW.Gen(1n)sk := GSW.Gen(1^n)sk:=GSW.Gen(1n)
2. HEPerm.Enc(sk,π∈Sr)HEPerm.Enc(sk, \pi \in S_r)HEPerm.Enc(sk,π∈Sr​)：找到对应的置换阵 Pπ=(pij)∈{0,1}r×rP_\pi = (p_{ij}) \in \{0,1\}^{r \times r}Pπ​=(pij​)∈{0,1}r×r，输出 C=(GSW.Enc(sk,pij))∈Cr×rC = (GSW.Enc(sk,p_{ij})) \in \mathcal C^{r \times r}C=(GSW.Enc(sk,pij​))∈Cr×r
3. HEPerm.Enc(sk,C∈Cr×r)HEPerm.Enc(sk, C \in \mathcal C^{r \times r})HEPerm.Enc(sk,C∈Cr×r)：计算出 Pπ=(GSW.Dec(sk,cij))∈{0,1}r×rP_\pi = (GSW.Dec(sk,c_{ij})) \in \{0,1\}^{r \times r}Pπ​=(GSW.Dec(sk,cij​))∈{0,1}r×r，输出对应的置换 π\piπ

这个方案有如下的同态运算（对于任意的 π,σ∈Sr\pi,\sigma \in S_rπ,σ∈Sr​，而不仅仅那 rrr 个循环置换）：

• 同态的映射复合 Cπ∘Cσ:=(⊞k∈[r](cikπ⊡ckjσ))ij∈Cr×rC^\pi \circ C^\sigma := \left(\boxplus_{k \in [r]} \left(c_{ik}^\pi \boxdot c_{kj}^\sigma\right)\right)_{ij} \in \mathcal C^{r \times r}Cπ∘Cσ:=(⊞k∈[r]​(cikπ​⊡ckjσ​))ij​∈Cr×r，就是一般的矩阵乘法（在同态运算下），噪声 E+Pπ⋅EσE+P^\pi \cdot E^\sigmaE+Pπ⋅Eσ，其中 EEE 的第 iii 行服从参数 O(∥eiπ∥)O(\|e_i^\pi\|)O(∥eiπ​∥) 的亚高斯分布，这里 eiπe_i^\pieiπ​ 是指 EπE^\piEπ 的第 iii 行。
• 同态的相等判定 Eq(Cπ,σ):=(⊡i∈[r]cσ(i),iπ)⊡G∈CEq(C^\pi,\sigma) := \left(\boxdot_{i \in [r]} c_{\sigma(i),i}^\pi\right) \boxdot G \in \mathcal CEq(Cπ,σ):=(⊡i∈[r]​cσ(i),iπ​)⊡G∈C，因为置换阵 PπP_\piPπ​ 的 pπ(i),ip_{\pi(i),i}pπ(i),i​ 都是 111，而其他的 entry 都是 000

对于同构于 Zr\mathbb Z_rZr​ 的循环置换子群 Cr⊆SrC_r \subseteq S_rCr​⊆Sr​，可以只对指示向量对应的那一列加密。对于 x,y∈Zrx,y \in \mathbb Z_rx,y∈Zr​，密文 Cx,Cy∈CrC^x,C^y \in \mathcal C^rCx,Cy∈Cr，此时的计算复杂度降低了 rrr 因子：

• 同态加法 Cx∘Cy:=(⊞k∈[r](cr+i−kx⊡cky))i∈CrC^x \circ C^y := \left(\boxplus_{k \in [r]} \left(c_{r+i-k}^x \boxdot c_{k}^y \right)\right)_{i} \in \mathcal C^{r }Cx∘Cy:=(⊞k∈[r]​(cr+i−kx​⊡cky​))i​∈Cr，计算复杂度从 O(r3)O(r^3)O(r3) 降低到了 O(r2)O(r^2)O(r2)
• 同态的相等判定 Eq(Cx,v):=cvx∈CEq(C^x,v) := c_{v}^x \in \mathcal CEq(Cx,v):=cvx​∈C，计算复杂度从 O(r)O(r)O(r) 降低到了 O(1)O(1)O(1)

类似的，由于同态乘法的非对称噪声增长，我们令算符 ∘\circ∘ 也是右结合的（ right associative）。对于一个关于密文 Ci,i=1,⋯,kC_i, i=1,\cdots,kCi​,i=1,⋯,k 的复合链，
C←(◯i∈[k]Ci)∘J=C1∘(⋯(Ck∘J))∈CrC \leftarrow \left(\bigcirc _{i \in [k]} C_{i}\right) \circ J = C_1 \circ(\cdots(C_k \circ J)) \in \mathcal C^{r} C←(◯i∈[k]​Ci​)∘J=C1​∘(⋯(Ck​∘J))∈Cr

这里 J∈CrJ \in \mathcal C^{r}J∈Cr 是零噪声的恒等置换 IrI_{r}Ir​ 的 HEPerm 密文（对角线 entry 是 1⋅G1 \cdot G1⋅G，其他的 entry 都是 0⋅G0 \cdot G0⋅G，将第一列作为指示向量的密文）。由于 PσP^\sigmaPσ 是置换阵，因此 CCC 的噪声矩阵的第 iii 行服从参数 O(∥ei∥)O(\|e_i\|)O(∥ei​∥) 的亚高斯分布，其中 ei∈Ekre_i \in \mathcal E^{kr}ei​∈Ekr 是 [E1∣⋯∣Ek][E_1|\cdots|E_k][E1​∣⋯∣Ek​] 的第 iii 行。

Bootstrapping

现在，我们可以使用 HEPerm 来对任意的 LWE 方案 执行自举了！

定义群嵌入（group embedding），
ϕ:(Zq,+)→(S:=∏i=1tSri,∘)\phi: (\mathbb Z_q,+) \to (S:=\prod_{i=1}^t S_{r_i}, \circ) ϕ:(Zq​,+)→(S:=i=1∏t​Sri​​,∘)

令 ϕi\phi_iϕi​ 是它的第 iii 分量。我们为 HEPerm（或者说它的部件 GSW）选取一个足够大的模数 Q≫qQ \gg qQ≫q，以保证 Bootstrapping 之后的噪声比率很小。

令 LWE 的私钥是 s∈Zqds \in \mathbb Z_q^ds∈Zqd​，密文是二元向量 c∈{0,1}dc \in \{0,1\}^dc∈{0,1}d，解密函数为
Dec(s,c):=f(⟨s,c⟩)Dec(s,c) := f(\langle s,c \rangle) Dec(s,c):=f(⟨s,c⟩)

其中 f:Zq→{0,1}f:\mathbb Z_q \to \{0,1\}f:Zq​→{0,1} 是某种解码函数。

令 sk←χnsk \leftarrow \chi^nsk←χn 是 HEPerm 的对称秘钥，自举方案如下：

1. BootGen(s,sk)BootGen(s,sk)BootGen(s,sk)：将 sss 的每个分量 sjs_jsj​ 嵌入到 SSS 中，然后对每个 SriS_{r_i}Sri​​ 上的置换 ϕi(sj)\phi_i(s_j)ϕi​(sj​) 用 HEPerm 加密，作为 bootstrapping key，
   bk:={Cij←HEPerm.Enc(sk,ϕi(sj))∈Cri:i∈[t],j∈[d]}bk := \{ C_{ij} \leftarrow HEPerm.Enc(sk,\phi_i(s_j)) \in \mathcal C^{r_i}: i \in [t], j \in [d] \} bk:={Cij​←HEPerm.Enc(sk,ϕi​(sj​))∈Cri​:i∈[t],j∈[d]}

   由于 t,ri=O(log⁡λ)t,r_i = O(\log \lambda)t,ri​=O(logλ) 且 d=O~(λ)d = \tilde O(\lambda)d=O~(λ)，因此 bk∈(∏i=1tCri)dbk \in \left(\prod_{i=1}^t \mathcal C^{r_i}\right)^dbk∈(∏i=1t​Cri​)d 包含 O~(λ)\tilde O(\lambda)O~(λ) 个 GSW 密文。

2. Bootstrap(bk,c∈{0,1}d)Bootstrap(bk,c \in \{0,1\}^d)Bootstrap(bk,c∈{0,1}d)：

   • 内积运算，转化为 subset-sum，即 ⟨s,c⟩=∑j:cj=1sj∈Zq\langle s,c \rangle = \sum_{j:c_j=1} s_j \in \mathbb Z_q⟨s,c⟩=∑j:cj​=1​sj​∈Zq​，在对称群 S:=∏i=1tSriS:=\prod_{i=1}^t S_{r_i}S:=∏i=1t​Sri​​ 下的复合链为
     Ci←(◯j∈[d]s.t.cj=1Cij)∘J∈CriC_i \leftarrow \left(\bigcirc _{j \in [d]\, s.t.\, c_j=1} C_{ij}\right) \circ J \in \mathcal C^{r_i} Ci​←(◯j∈[d]s.t.cj​=1​Cij​)∘J∈Cri​

     回顾下算符 ∘\circ∘ 是右结合的，其中 J∈CriJ \in \mathcal C^{r_i}J∈Cri​ 是恒等置换 IriI_{r_i}Iri​​ 的无噪声 HEPerm 密文。

   • 解码运算，转化为 equality test，即 f(x)=∑v:f(v)=1[x=v]∈{0,1}f(x) = \sum_{v:f(v)=1} [x=v] \in \{0,1\}f(x)=∑v:f(v)=1​[x=v]∈{0,1}，在对称群 S:=∏i=1tSriS:=\prod_{i=1}^t S_{r_i}S:=∏i=1t​Sri​​ 下的相等判定为
     C←⊞v∈[q]s.t.f(v)=1((⊡i∈[t]Eq(Ci,ϕi(v)))⊡G)∈CC \leftarrow \boxplus_{v \in [q]\, s.t.\, f(v)=1} \left(\left(\boxdot_{i \in [t]} Eq(C_i, \phi_i(v))\right) \boxdot G\right) \in \mathcal C C←⊞v∈[q]s.t.f(v)=1​((⊡i∈[t]​Eq(Ci​,ϕi​(v)))⊡G)∈C

     回顾下 Eq(Cπ,σ)∈CEq(C^\pi, \sigma) \in \mathcal CEq(Cπ,σ)∈C，算符 ⊡\boxdot⊡ 是右结合的，而 GGG 是整数 111 的无噪声 GSW 密文。

在自举之前，由于我们的 GSW 对密文格式有要求，因此需要对 LWE 密文做一些预处理，包括：维度约减、模约减、二进制分解。在自举结束后，选取 GSW 密文的倒数第二列作为 LWE 密文（GSW 密文就是由 LWE 密文组成的向量），并做密钥切换，从 sksksk 下的 LWE 密文回到 sss 下的 LWE 密文。

FHEW

2015 年，Ducas 等人提出了 FHEW 方案。与上述的 HEPerm 相似，FHEW 采用一个与原始 LWE 方案不同的加密方案，构造出一个同态累加器（Homomorphic Accumulator），然后用它来 refresh 密文。另外，FHEW 还提出了一种新的 NAND 门，只需要用到加法同态，而不需要乘法同态，噪声增长率较低。

Notation

FHEW 定义了一个 randomized rounding 函数 χ:R→Z\chi:\mathbb R \to \mathbb Zχ:R→Z，对于任意的 x∈Rx \in \mathbb Rx∈R 和任意的 n∈Zn \in \mathbb Zn∈Z，都有 χ(x+n)=χ(x)+n\chi(x+n) = \chi(x)+nχ(x+n)=χ(x)+n，其中 χ(x)−x\chi(x)-xχ(x)−x 叫做 χ(x)\chi(x)χ(x) 的 rounding error。不知道本人理解的对不对，χ(x)\chi(x)χ(x) 是一族关于实数 xxx 的噪声分布，对于每个固定的 xxx 都有一个固定的分布 χ(x(mod1))\chi(x \pmod 1)χ(x(mod1))；特别当 x∈Zx \in \mathbb Zx∈Z 时，对应于 χ(0)\chi(0)χ(0)。

我们说实数域 R\mathbb RR 上的随机变量 XXX 是参数 α>0\alpha>0α>0 的亚高斯（subgaussian），如果对于任意的 t∈Rt \in \mathbb Rt∈R 都满足
E[exp⁡(2πtX)]≤exp(πα2t2)E[\exp(2\pi tX)] \le exp(\pi \alpha^2 t^2) E[exp(2πtX)]≤exp(πα2t2)

进一步地，它的尾部（tail）满足
Pr[∣X∣≥t]≤2exp⁡(−πt2/α2),∀t≥0Pr[|X| \ge t] \le 2\exp(-\pi t^2/\alpha^2),\forall t \ge 0 Pr[∣X∣≥t]≤2exp(−πt2/α2),∀t≥0

所有的 B-B\text{ -}B - bounded 对称随机变量 XXX 都是参数 B2πB \sqrt{2\pi}B2π​ 的亚高斯。扩展到随机向量 x\bf xx，如果它的所有 one-dimensional marginals ⟨u,x⟩\bf \langle u,x \rangle⟨u,x⟩（其中 u\bf uu 是单位向量）是参数 α\alphaα 的亚高斯。扩展到随机矩阵 X\bf XX，如果它的所有 one-dimensional marginals utXv\bf u^tXvutXv（其中 u,v\bf u,vu,v 是单位向量）是参数 α\alphaα 的亚高斯。

对于 222 的幂次 NNN，Φ2N(X)=XN+1\Phi_{2N}(X)=X^N+1Φ2N​(X)=XN+1 是分园多项式（cyclotomic

polynomial）。令 R=Z[X]/(XN+1)R = \mathbb Z[X]/(X^N+1)R=Z[X]/(XN+1) 是分园环（cyclotomic ring），对应的商环 Rq=R/qRR_q=R/qRRq​=R/qR。对于 a=a0+a1x+⋯+aN−1xN−1∈Ra=a_0 + a_1x + \cdots + a_{N-1}x^{N-1} \in Ra=a0​+a1​x+⋯+aN−1​xN−1∈R，简记
a⃗:=[a0a1⋮aN−1]∈ZN,a⇒:=[a0−aN−1⋯−a1a1a0⋯−a2⋮⋮⋯⋮aN−1aN−2⋯a0]∈ZN×N\vec a := \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{N-1} \end{bmatrix} \in \mathbb Z^N,\, \mathop{a}\limits^{\Rightarrow} := \begin{bmatrix} a_0 & -a_{N-1} & \cdots & -a_1\\ a_1 & a_0 & \cdots & -a_2\\ \vdots & \vdots & \cdots & \vdots\\ a_{N-1} & a_{N-2} & \cdots & a_{0} \end{bmatrix} \in \mathbb Z^{N \times N} a:=​a0​a1​⋮aN−1​​​∈ZN,a⇒:=​a0​a1​⋮aN−1​​−aN−1​a0​⋮aN−2​​⋯⋯⋯⋯​−a1​−a2​⋮a0​​​∈ZN×N

其实 a⇒⋅b⃗=a⋅b→\mathop{a}\limits^{\Rightarrow} \cdot \vec b = \overrightarrow{a \cdot b}a⇒⋅b=a⋅b，这就是环 RRR 上的多项式乘积罢了（文章中使用的全是矩阵乘，却不使用多项式乘积）。扩展到向量和矩阵，对于 A∈Rw×kA \in R^{w \times k}A∈Rw×k，令 A⇒∈ZwN×kN\mathop{A}\limits^{\Rightarrow} \in \mathbb Z^{wN \times kN}A⇒​∈ZwN×kN 就是对于每个 entry 单独地应用 ⋅⇒\mathop{\cdot}\limits^{\Rightarrow}⋅⇒ 算符。我们说一个随机多项式 a∈Ra \in Ra∈R 是亚高斯的，如果 a⃗\vec aa 是亚高斯的随机向量。

LWE Symmetric Encryption

我们描述一个基于 LWE 的对称加密方案，它可以用标准的转化技术得到非对称加密。秘钥 $ s \in \mathbb Z_q^n,q=n{O(1)}$，消息 m∈Zt,t≥2m \in \mathbb Z_t,t \ge 2m∈Zt​,t≥2，随机园整函数满足 ∣χ(x)−x∣

对称加密方案：

1. 加密，LWEst/q(m):=(a,χ(as+mq/t)(modq))∈Zqn+1LWE_s^{t/q}(m) := (a,\chi(as+mq/t) \pmod q) \in \mathbb Z_q^{n+1}LWEst/q​(m):=(a,χ(as+mq/t)(modq))∈Zqn+1​，其中 a∈Zqna \in \mathbb Z_q^na∈Zqn​ 是均匀随机的
2. 解密，输入密文 (a,b)(a,b)(a,b)，输出 m′←⌊t(b−as)/q⌉(modt)∈Ztm' \leftarrow \lfloor t(b-as)/q \rceil \pmod t \in \mathbb Z_tm′←⌊t(b−as)/q⌉(modt)∈Zt​

Modulus Switching，从模数 QQQ 到模数 qqq 的 (scaled) randomized rounding function [⋅]Q:q:ZQ→Zq[\cdot]_{Q:q}:\mathbb Z_Q \to \mathbb Z_q[⋅]Q:q​:ZQ​→Zq​ 定义为
[x]Q:q:=⌊qx/Q⌋+B[x]_{Q:q} := \lfloor qx/Q \rfloor + B [x]Q:q​:=⌊qx/Q⌋+B

其中 B∈{0,1}B \in \{0,1\}B∈{0,1} 是服从 Pr[B=1]=qx/Q−⌊qx/Q⌋Pr[B=1]=qx/Q-\lfloor qx/Q \rfloorPr[B=1]=qx/Q−⌊qx/Q⌋ 的二值分布，容易看出 E([x]Q:q)=qx/QE([x]_{Q:q})=qx/QE([x]Q:q​)=qx/Q，并且园整错误 [x]Q:q−qx/Q[x]_{Q:q}-qx/Q[x]Q:q​−qx/Q 是参数 2π\sqrt{2\pi}2π​ 的亚高斯。对于 (a,b)∈LWEzt/q(m)(a,b) \in LWE_z^{t/q}(m)(a,b)∈LWEzt/q​(m)，计算模 qqq 下的新密文
ModSwitch(a,b):=(([ai]Q:q)i,[b]Q:q)ModSwitch(a,b) := (\left([a_i]_{Q:q}\right)_i,[b]_{Q:q}) ModSwitch(a,b):=(([ai​]Q:q​)i​,[b]Q:q​)

Key Switching，设置 base 为 BksB_{ks}Bks​，从密钥 z∈ZqNz \in \mathbb Z_q^Nz∈ZqN​ 到密钥 s∈ZqNs \in \mathbb Z_q^Ns∈ZqN​ 的 switching key R:={kijv}\mathfrak R := \{k_{ijv}\}R:={kijv​} 定义为
kijv←LWEsq/q(vziBksj),i=1,⋯,N,j=0,⋯,dks−1,v=0,⋯,Bks−1k_{ijv} \leftarrow LWE_s^{q/q}(vz_iB_{ks}^j),\, i = 1,\cdots,N,\, j=0,\cdots,d_{ks}-1,\, v =0,\cdots,B_{ks}-1 kijv​←LWEsq/q​(vzi​Bksj​),i=1,⋯,N,j=0,⋯,dks​−1,v=0,⋯,Bks​−1

其中 dks=⌈log⁡Bksq⌉d_{ks} = \lceil \log_{B_{ks}}q \rceildks​=⌈logBks​​q⌉，并且 t=qt=qt=q 使得 kijvk_{ijv}kijv​ 是噪声比率为 1/21/21/2 的 not typically decryptable 的密文。对于 (a,b)∈LWEzt/q(m)(a,b) \in LWE_z^{t/q}(m)(a,b)∈LWEzt/q​(m)，首先做分解 ai=∑jaijBksja_i = \sum_j a_{ij} B_{ks}^jai​=∑j​aij​Bksj​，然后计算 sss 下的新密文
KeySwitch((a,b),R):=(0,b)−∑i,jki,j,aijKeySwitch\left((a,b),\mathfrak R\right) := (0,b) - \sum_{i,j} k_{i,j,a_{ij}} KeySwitch((a,b),R):=(0,b)−i,j∑​ki,j,aij​​

可以验证 b′=b−az+a′s−Eb'=b-az+a's-Eb′=b−az+a′s−E，从而 b′−a′s≈b−az≈mq/tb'-a's \approx b-az \approx mq/tb′−a′s≈b−az≈mq/t，前后两者加密了同一个明文。

NAND Gate

本文提出了一种新的 NAND 计算方式。思路是，用 Z\mathbb ZZ 上的仿射变换来拟合 NAND 运算：

只需要在就近取整，就可以得到 m0∧ˉm1m_0 \bar\wedge m_1m0​∧ˉm1​ 的结果了。将明文空间 Zt\mathbb Z_tZt​ 设置为 t=4t=4t=4，并设置一个更小的错误界 E=q/16E = q/16E=q/16，那么对于 mi∈{0,1}m_i \in \{0,1\}mi​∈{0,1}，计算密文 ci∈LWEs4/q(mi,q/16)c_i \in LWE_s^{4/q}(m_i,q/16)ci​∈LWEs4/q​(mi​,q/16)，另外计算无噪声密文 (0,5q8)∈LWEs2/q(54,0)(0,\dfrac{5q}{8}) \in LWE_s^{2/q}(\dfrac{5}{4},0)(0,85q​)∈LWEs2/q​(45​,0)，并将 LWEs4/q(mi,q/16)LWE_s^{4/q}(m_i,q/16)LWEs4/q​(mi​,q/16) 视为 LWEs2/q(12mi,q/16)LWE_s^{2/q}(\dfrac{1}{2}m_i,q/16)LWEs2/q​(21​mi​,q/16)

计算 m0∧ˉm1=1−m0m1=⌊54−12(m0+m1)⌉m_0 \bar\wedge m_1 = 1-m_0m_1 = \left\lfloor \dfrac{5}{4}-\dfrac{1}{2}(m_0+m_1) \right\rceilm0​∧ˉm1​=1−m0​m1​=⌊45​−21​(m0​+m1​)⌉ 的同态与非门：
HomNAND:LWEs4/q(m0,q/16)×LWEs4/q(m1,q/16)→LWEs2/q(m0∧ˉm1,q/4)(a,b)←HomNAND((a0,b0),(a1,b1)):=(−a0−a1,5q8−b0−b1)HomNAND: LWE_s^{4/q}(m_0,q/16) \times LWE_s^{4/q}(m_1,q/16) \to LWE_s^{2/q}(m_0 \bar\wedge m_1,q/4)\\ (a,b) \leftarrow HomNAND((a_0,b_0),\, (a_1,b_1)) := (-a_0-a_1,\, \dfrac{5q}{8}-b_0-b_1) HomNAND:LWEs4/q​(m0​,q/16)×LWEs4/q​(m1​,q/16)→LWEs2/q​(m0​∧ˉm1​,q/4)(a,b)←HomNAND((a0​,b0​),(a1​,b1​)):=(−a0​−a1​,85q​−b0​−b1​)

于是 NAND 门只需要同态加法，不需要采用同态乘法，因此输入密文的噪声界从以前的 O(q)O(\sqrt q)O(q​) 扩大到了 O(q)O(q)O(q)。可以验证，
b−as=5q8−(b0−a0s)−(b1−a1s)=q2(54−12(m0+m1))−(e0+e1)=q2(m0∧ˉm1±14)−(e0+e1)=q2(m0∧ˉm1)±q8−(e0+e1)\begin{aligned} b-as &= \dfrac{5q}{8} - (b_0-a_0s) - (b_1-a_1s)\\ &= \dfrac{q}{2}\left(\dfrac{5}{4}-\dfrac{1}{2}(m_0+m_1)\right) - (e_0+e_1)\\ &= \dfrac{q}{2}\left(m_0 \bar\wedge m_1 \pm \dfrac{1}{4}\right) - (e_0+e_1)\\ &= \dfrac{q}{2}\left(m_0 \bar\wedge m_1\right) \pm \dfrac{q}{8} - (e_0+e_1)\\ \end{aligned} b−as​=85q​−(b0​−a0​s)−(b1​−a1​s)=2q​(45​−21​(m0​+m1​))−(e0​+e1​)=2q​(m0​∧ˉm1​±41​)−(e0​+e1​)=2q​(m0​∧ˉm1​)±8q​−(e0​+e1​)​

噪声 ∣q8−(e0+e1)∣

为了继续进行 NAND 运算，我们需要一个刷新函数：
Refresh:LWEs2/q(m,q/4)→LWEs4/q(m,q/16)Refresh:\, LWE_s^{2/q}(m,q/4) \to LWE_s^{4/q}(m,q/16) Refresh:LWEs2/q​(m,q/4)→LWEs4/q​(m,q/16)

这个函数就是 Bootstrapping 的作用，每次 NAND 计算后都立刻刷新密文，因此计算瓶颈在 Refresh 上。

Homomorphic Accumulator

FHEW 选取一个可以与 LWE 加密方案不同的另一个加密方案 E(⋅)E(\cdot)E(⋅)，要求它对于 (a,b)∈LWEs2/q(m)(a,b) \in LWE_s^{2/q}(m)(a,b)∈LWEs2/q​(m) 满足如下运算关系
⌊2q(b−a⋅E(s))⌉(mod2)=E(m)\left\lfloor \dfrac{2}{q}(b-a \cdot E(s))\right\rceil \pmod 2 = E(m) ⌊q2​(b−a⋅E(s))⌉(mod2)=E(m)

关键是计算 b−a⋅E(s)=E(b−a⋅s)b-a \cdot E(s) = E(b-a \cdot s)b−a⋅E(s)=E(b−a⋅s)，这只是密文的同态数乘，可以被视为一些密文的加法。方案 EEE 被用来构造同态累加器（Homomorphic Accumulator），它是一个算法四元组 (E,Init,Incr,msbExtract)(E,Init,Incr,msbExtract)(E,Init,Incr,msbExtract)，

• EEE：加密算法，密文空间 C\mathcal CC 可以与 LWEst/qLWE_s^{t/q}LWEst/q​ 不同。
• InitInitInit：初始化，ACC←Init(v0)ACC \leftarrow Init(v_0)ACC←Init(v0​) 简记为 ACC←v0ACC \leftarrow v_0ACC←v0​
• IncrIncrIncr：同态累加（Increment），ACC←Incr(ACC,E(vi))ACC \leftarrow Incr(ACC,E(v_i))ACC←Incr(ACC,E(vi​)) 简记为 ACC←+E(vi)ACC \overset{+}{\leftarrow} E(v_i)ACC←+E(vi​)，其中 i=1,⋯,li=1,\cdots,li=1,⋯,l
• msbExtractmsbExtractmsbExtract：提取 MSB，c←msbExtract(ACC)c \leftarrow msbExtract(ACC)c←msbExtract(ACC)

我们说这个同态累加器是 E- correct\mathcal E\text{ - correct}E - correct 的，如果 c∉LWEst/q(∑ivi,E(l))c \notin LWE_s^{t/q}(\sum_i v_i, \mathcal E(l))c∈/LWEst/q​(∑i​vi​,E(l)) 的概率可忽略。对于 t=4t=4t=4，要求 E(l)≤q/16\mathcal E(l) \le q/16E(l)≤q/16

然后利用上述的同态累加器，可以实现 refresh 函数。首先预计算 refreshing key K:={Kijc}\mathcal K := \{K_{ijc}\}K:={Kijc​}，
Kijc:=E(csiBrj(modq)),i=1,⋯,n,j=0,⋯,dr−1,c=0,⋯,Br−1K_{ijc} := E(cs_iB_r^j \pmod q),\, i = 1,\cdots,n,\, j=0,\cdots,d_{r}-1,\, c =0,\cdots,B_{r}-1 Kijc​:=E(csi​Brj​(modq)),i=1,⋯,n,j=0,⋯,dr​−1,c=0,⋯,Br​−1

其中 dr=⌈log⁡Brq⌉d_{r} = \lceil \log_{B_{r}}q \rceildr​=⌈logBr​​q⌉，这儿的 LWE 密钥 s∈Zqns \in \mathbb Z_q^ns∈Zqn​ 的各个系数被 power 为 (siBrj)j(s_i B_r^j)_j(si​Brj​)j​，然后枚举了所有的 BrB_rBr​ 进制下的所有取值。由于 Decompose(ai)⋅Power(si)=ai⋅siDecompose(a_i) \cdot Power(s_i) = a_i \cdot s_iDecompose(ai​)⋅Power(si​)=ai​⋅si​，因此可以根据 ai=∑jaijBrja_i = \sum_j a_{ij} B_r^jai​=∑j​aij​Brj​ 挑选出对应的 Ki,j,aijK_{i,j,a_{ij}}Ki,j,aij​​ 计算同态加法。

初始化 b+q/4b+q/4b+q/4，这使得循环末尾
v=q/4+b−a⋅s=mq/2+(e+q/4)v = q/4 + b-a \cdot s = mq/2 + (e+q/4) v=q/4+b−a⋅s=mq/2+(e+q/4)

由于 ∣e∣提取 b−asb-asb−as 的 MSB 转化为了测试 vvv 的范围（与 HEPerm 类似）。

FHEW 使用 Ring-GSW 来实例化同态累加器。LWE 的模数 q=2kq=2^kq=2k，消息域大小 t=4t=4t=4。GSW 的模数 QQQ 满足 Q=BgdgQ=B_g^{d_g}Q=Bgdg​​，其中 base BgB_gBg​ 是 333 的幂次（这使得 ∀K≥3,N=2K,XN+1=(XN/2+XN/4−1)(XN/2−XN/4−1)\forall K \ge 3,N=2^K,X^N+1 = (X^{N/2}+X^{N/4}-1) (X^{N/2}-X^{N/4}-1)∀K≥3,N=2K,XN+1=(XN/2+XN/4−1)(XN/2−XN/4−1)，从而 RQR_QRQ​ 几乎是一个域）。额外设置一个参数 u=⌊Q/2t⌋u = \lfloor Q/2t \rflooru=⌊Q/2t⌋ 或者 u=⌈Q/2t⌉u = \lceil Q/2t \rceilu=⌈Q/2t⌉，它们在 ZQ\mathbb Z_QZQ​ 中是可逆的，且误差 ∣u−Q/2t∣<1|u-Q/2t|<1∣u−Q/2t∣<1。

设置环 R=Z[X]/(XN+1)R = \mathbb Z[X]/(X^N+1)R=Z[X]/(XN+1)，使得 q∣2Nq\mid 2Nq∣2N，那么它有 qqq 次本原单位根 Y:=X2N/qY := X^{2N/q}Y:=X2N/q，因此 Zq≅⟨Y⟩\mathbb Z_q \cong \langle Y \rangleZq​≅⟨Y⟩ 是单位根循环群 G=⟨X⟩≅Z2NG = \langle X \rangle \cong \mathbb Z_{2N}G=⟨X⟩≅Z2N​ 的子循环群。消息 m∈Zqm \in \mathbb Z_qm∈Zq​ 可以直接编码到指数上为 Ym∈RY^m \in RYm∈R，其向量表示为 {−1,0,1}N\{-1,0,1\}^N{−1,0,1}N 上的 one-hot 向量。为了提取 mmm 的 MSB，我们构造一个 testing vector
t:=−∑v=1q/2−1Y⃗v∈{−1,0,1}Nt := - \sum_{v=1}^{q/2-1} \vec Y^v \in \{-1,0,1\}^N t:=−v=1∑q/2−1​Yv∈{−1,0,1}N

如果 0≤mm=−1，如果 N≤m<2NN \le m < 2NN≤m<2N 那么 t⋅Y⃗m=+1t \cdot \vec Y^m = +1t⋅Ym=+1，这其实就是挨个测试了 Eq(m,v),∀MSB(v)=0Eq(m,v),\forall MSB(v)=0Eq(m,v),∀MSB(v)=0

FHEW 的基于 RGSW 的同态累加器：

由于 GSW 密文就是由 LWE 密文组成的向量，因此提取 MSB 对应的 LWE 密文，就是挑选出对应的列向量：

Refresh 的主要的计算量集中在累加阶段，可以用 FFT/NTT 来加速：