文章目录

• FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second
• • 个人总结
  • 摘要
  • 引言
  • • 我们的工作
    • 技术
    • • 同态NAND门
      • Bootstrapping
  • LWE对称加密
  • • 加密形式
    • 模数替换
    • 密钥替换
  • 本文的FHE：高层结构
  • • 一种新的同态NAND门
    • 通过同态累加器进行噪声刷新
    • • 思想（通过ACC进行Refresh）
      • 定义（同态累加器）
      • 算法（Refresh）
  • 由RGSW构造同态累加器
  • • • 基于RGSW的累加器的构造
      • 正确性
      • • **ACC的正确性没有给出证明，而是直接作为一个结果。**
        • **Extract正确性**
    • 方案总览
  • 总结
• 小尾巴

FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second

作者: Leo Ducas¹, Daniele Micciancio².

个人总结

FHEW总结：
其实FHEW的主要贡献就在于使用了累加器的方法来做Bootstrapping，思路是在幂次上计算Xb+as=XmX^{b+as}=X^{m}Xb+as=Xm，通过与一个test vector $v(X)$相乘就可以用来提取最高位，对于{0,1}的密文来说，提取了最高位就相当于做了刷新。

后续工作：

之后TFHE将FHEW中使用$\mathsf{RGSW}$与$\mathsf{RGSW}$内乘来做算v(x)⋅Xb+asv(x)\cdot X^{b+as}v(x)⋅Xb+as改为了$\mathsf{RGSW}$与$\mathsf{RLWE}$的外乘，从而极大地提高了效率。

且FHEW中的testvector就是v(X)=1+X+X2+…+XN−1v(X)=1+X+X^2+…+X^{N-1}v(X)=1+X+X2+…+XN−1。后续文章会有将$v(X)$改为v(X)=f(0)+f(1)X+…+f(N−1)XN−1v(X)=f(0)+f(1)X+…+f(N-1)X^{N-1}v(X)=f(0)+f(1)X+…+f(N−1)XN−1，就可以在做Bootstrapping的同时执行某个函数。详情可以看TFHE作者写的PBS这篇以及我们写的TOTA这篇文章。

摘要

目前所有FHE方案主要的瓶颈在于Gentry的Bootstrapping操作。在之前2014年HElib of Halevi and Shoup中，一次Bootstrapping操作需要6分钟³。我们发现了一种新的方法来刷新密文的噪声，在个人机器上只要半秒。

引言

我们的工作

这篇文章考虑了1bit密文的刷新究竟能有多快，具体来说，考虑两个加密一比特的密文E(b1)E(b_1)E(b1​)和E(b2)E(b_2)E(b2​)，我们想要同态地运算一个与非门（NAND），来得到E(b1∧ˉb2)E(b_1 \bar{\wedge} b_2)E(b1​∧ˉb2​)的结果。这里考虑的门电路是带bootstrapping的门电路，也就是在执行一次同态的与非门之后，要跟上一个bootstrapping，也就是对E(b1∧ˉb2)E(b_1 \bar{\wedge} b_2)E(b1​∧ˉb2​)运行一次同态地解密电路，使得E(b1∧ˉb2)E(b_1 \bar{\wedge} b_2)E(b1​∧ˉb2​)的噪声大小与E(bi),i∈{0,1}E(b_i),i\in \{0,1\}E(bi​),i∈{0,1}​一致。这样的一次同态的NAND门加上一次Bootstrapping操作在个人电脑上的耗时为半秒。

与HElib中的bootstrapping比起来，这篇文章中在每次bootstrapping之前只允许一次NAND操作，而HElib支持更加复杂的操作，而且HElib还考虑了SIMD技术，因此平均每个比特刷新的速度和本文是一个量级的。

技术

这篇文章的提升主要基于两个技术，第一个是在两个LWE密文上计算NAND门的新算法。另一个是一种进行Bootstrapping的方法。

同态NAND门

具体来说，考虑两个密文E(m1)E(m_1)E(m1​)​​​和E(m2)E(m_2)E(m2​)​​​，同态加密运行进行同态加法得到一个噪声更大的密文E(m1+m2)E(m_1+m_2)E(m1​+m2​)​​。​当在模2下考虑时，就能够同态地两个比特的异或。实现NAND门的方法就是将模2扩展到模4。考虑以下的真值表：

m1m_1m1​​​​	m2m_2m2​​​​	m1∧ˉm2m_1 \bar\wedge m_2m1​∧ˉm2​​​​	[m1+m2]4[m_1 + m_2]_4[m1​+m2​]4​​​
0	0	1	0
0	1	1	1
1	0	1	1
1	1	0	2

也就是说，当E(m)=E(m1)+E(m2)E(m)=E(m_1)+E(m_2)E(m)=E(m1​)+E(m2​)​​​​​​的值为$m=2$​​​​​​时，代表m1∧ˉm2=0m_1 \bar \wedge m_2=0m1​∧ˉm2​=0​​​​​​。当m∈{0,1}m\in\{0,1\}m∈{0,1}​​​​​时，m1∧ˉm2=1m_1 \bar\wedge m_2=1m1​∧ˉm2​=1​​​​​​。​利用这个性质，就可以对$E(m)$进行一个简单的仿射变换⁴来将密文变为E(m1∧ˉm2)E(m_1 \bar\wedge m_2)E(m1​∧ˉm2​)。这里用到的是54−12(m1+m2)\frac{5}{4}-\frac{1}{2}(m_1 + m_2)45​−21​(m1​+m2​)​​​​​。再考虑如下真值表：

m1m_1m1​	m2m_2m2​	54−12(m1+m2)\frac{5}{4}-\frac{1}{2}(m_1 +m_2)45​−21​(m1​+m2​)​​	⌊54−12(m1+m2)⌉\lfloor \frac{5}{4} – \frac{1}{2}(m_1 + m_2) \rceil⌊45​−21​(m1​+m2​)⌉​​
0	0	54\frac{5}{4}45​​	1
0	1	34\frac{3}{4}43​	1
1	0	34\frac{3}{4}43​	1
1	1	14\frac{1}{4}41​	0

通过这样的方式来构造的NAND门，比之前的方法（通过乘法构造）的噪音要低很多。因此，噪声刷新操作（bootstrapping）也更加简单。

Bootstrapping

本文的第二个关键技术时基于文章Faster Bootstrapping with Polynomial Error⁵，LWE密文的解密可以由一次模q的内积和一次取整操作得到。bootstrapping就是在密文上同态地执行模q的内积以及取整。文章⁵中使用了一个模q的加密算法，可以很快速的计算内积。具体的做法使用一个一比特的加密算法，将一个循环群中的元素$v\in C$​，加密为一个向量E(x1),…,E(x∣C∣)E(x_1),…,E(x_{|C|})E(x1​),…,E(x∣C∣​)，其中xi=1x_i=1xi​=1当且仅当$i=v$​。​本文将⁵中的方法扩张到了多项式环上，那就支持FFT来加速运算的操作，效率得到了进一步的提高。而且还利用了多项式环的性质，将循环群中元素直接映射到多项式环上：i→Xii \to X^ii→Xi，其中$i$​​是模$q$的原根。​​

另外，这篇文章还使用了binary value的私钥（也就是只有0，1），来减少key switching过程中的噪声。之前有文章证明过$s$是0，1值的时候安全性与普通的LWE问题困难度一致。

LWE对称加密

加密形式

先引入一个随机取整函数$\chi :\mathbb{R}\to \mathbb{Z}$。这个函数将一个实数映射为一个整数，满足$\chi (x+n)=\chi (x)+n$。将$\chi (x)-x$称为rounding error。注意到如果$x\in Z$，那么$\chi (x)=x+\chi (0)$，$\chi (0)$是一个固定的噪声分布。

记一个密文为
LWE⁡st/q(m)=(a,χ(a⋅s+mq/t)modq)∈Zqn+1\operatorname{LWE}_{\mathbf{s}}^{t/q}(m) = (\mathbf{a},\chi (\mathbf{a} \cdot \mathbf{s} + m q/t) \bmod q) \in \mathbb{Z}_q^{n+1} LWEst/q​(m)=(a,χ(a⋅s+mq/t)modq)∈Zqn+1​
可以通过如下方式解密：
m′=⌊t(b−a⋅s)/q⌉modt∈Ztm^{\prime}=\lfloor t(b-\mathbf{a}\cdot \mathbf{s})/q \rceil \bmod t \in \mathbb{Z}_t m′=⌊t(b−a⋅s)/q⌉modt∈Zt​
要求error bound为$q/2t$时才能正确解密，原因是：
⌊t(b−a⋅s)/q⌉modt=⌊tq⋅(qtm+e)⌉=⌊m+tqe⌉=mmodt\lfloor t(b-\mathbf{a}\cdot \mathbf{s})/q \rceil \bmod t = \left\lfloor \frac{t}{q} \cdot (\frac{q}{t}m + e) \right\rceil = \left\lfloor m+ \frac{t}{q}e \right\rceil= m \bmod t ⌊t(b−a⋅s)/q⌉modt=⌊qt​⋅(tq​m+e)⌉=⌊m+qt​e⌉=mmodt
这里就要求∣tqe∣<12|\frac{t}{q}e| < \frac{1}{2}∣qt​e∣<21​，因此$|e|<q/2t$​，记一个bound为$q/2t$的密文为LWEst/q(m,q/2t)\mathsf{LWE}_{\mathbf{s}}^{t/q}(m,q/2t)LWEst/q​(m,q/2t)。

模数替换

可以将LWE密文从一个模数Q转换到另外一个模数$q$，使用一个随机取整函数[⋅]Q:q:ZQ→Zq[\cdot]_{Q:q}:\mathbb{Z}_Q \to \mathbb{Z}_q[⋅]Q:q​:ZQ​→Zq​。
[x]Q:q=⌊qx/Q⌋+B,B∈{0,1}[x]_{Q:q} = \lfloor qx/Q \rfloor + B,B\in \{0,1\} [x]Q:q​=⌊qx/Q⌋+B,B∈{0,1}
$B$是一个随机数，Pr{B=1}=(qx/Q)−⌊qx/Q⌋Pr\{B=1\} = (qx/Q)-\lfloor qx/Q \rfloorPr{B=1}=(qx/Q)−⌊qx/Q⌋，也就是$qx/Q$的小数部分越大，$B$越可能是1。

定义ModSwitch：
ModSwitch⁡(a,b)=[(a,b)]Q:q=(([a1]Q:q,…,[an]Q:q),[b]Q:q)\operatorname{ModSwitch}(\mathbf{a},b) = [(\mathbf{a},b)]_{Q:q} = (([a_1]_{Q:q},…,[a_n]_{Q:q}),[b]_{Q:q}) ModSwitch(a,b)=[(a,b)]Q:q​=(([a1​]Q:q​,…,[an​]Q:q​),[b]Q:q​)

密钥替换

密钥替换允许将LWEzt/q\mathsf{LWE}_{\mathbf{z}}^{t/q}LWEzt/q​​​变为LWEst/q\mathsf{LWE}_{\mathbf{s}}^{t/q}LWEst/q​​​，其中z∈ZqN\mathbf{z}\in \mathbb{Z}_q^Nz∈ZqN​​​，s∈Zqn\mathbf{s} \in \mathbb{Z}_q^ns∈Zqn​​​。

记BksB_{\mathsf{ks}}Bks​​是一个分解基数，记dks=⌈log⁡Bksq⌉d_{\mathsf{ks}}=\lceil \log_{B_{\mathsf{ks}}}q \rceildks​=⌈logBks​​q⌉。ai=∑jai,jBksj,j=0,…,dks−1a_{i}=\sum_j a_{i,j} B_{\mathsf{ks}}^j,j=0,…,d_{\mathsf{ks}}-1ai​=∑j​ai,j​Bksj​,j=0,…,dks​−1。

对于i=1,…,N,ai,j∈{0,…,Bks},j=0,…,dks−1i = 1,…,N,a_{i,j}\in\{0,…,B_{\mathsf{ks}}\},j=0,…,d_{\mathsf{ks}}-1i=1,…,N,ai,j​∈{0,…,Bks​},j=0,…,dks​−1​。记ki,j,ai,j=LWEsq/q(ai,jziBksj)\mathbf{k}_{i,j,a_{i,j}}=\mathsf{LWE}_{\mathbf{s}}^{q/q}(a_{i,j}z_i B_{\mathsf{ks}}^j)ki,j,ai,j​​=LWEsq/q​(ai,j​zi​Bksj​)​。

记K={ki,j,ai,j}\mathfrak{K}=\{\mathbf{k}_{i,j,a_{i,j}}\}K={ki,j,ai,j​​}，密文(a,b)∈LWEzt/q(m)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{z}}^{t/q}(m)(a,b)∈LWEzt/q​(m)，
KeySwitch((a,b),K)=(0,b)−∑i,jki,j,ai,j\mathsf{KeySwitch}((\mathbf{a},b),\mathfrak{K})=(\mathbf{0},b)-\sum_{i,j}\mathbf{k}_{i,j,a_{i,j}} KeySwitch((a,b),K)=(0,b)−i,j∑​ki,j,ai,j​​
正确性：

记(a′,b′)=∑i,jki,j,ai,j(\mathbf{a}',b')=\sum_{i,j} \mathbf{k}_{i,j,a_{i,j}}(a′,b′)=∑i,j​ki,j,ai,j​​，则b′−a′s=a⋅zb'-\mathbf{a'}s = \mathbf{a} \cdot \mathbf{z}b′−a′s=a⋅z

因此ctxt′=KeySwitch((a,b)=(−a′,b−b′)\mathsf{ctxt}' = \mathsf{KeySwitch}((\mathbf{a},b)=(-\mathbf{a}',b-b')ctxt′=KeySwitch((a,b)=(−a′,b−b′)

Dec(ctxt′)=t/q⌊b−(b′−a′s)⌉=m+t/q(z⋅a+e−a⋅z)=m\mathsf{Dec(ctxt')}= t/q\lfloor b-(b'-\mathbf{a}'s) \rceil=m+ t/q(\mathbf{z} \cdot \mathbf{a} + e-\mathbf{a\cdot z}) = mDec(ctxt′)=t/q⌊b−(b′−a′s)⌉=m+t/q(z⋅a+e−a⋅z)=m​​​

其中，将aia_iai​分解的目的是为了降低$\mathsf{KeySwitch}$过程中添加的噪声。

本文的FHE：高层结构

主要目的是为了做如下事情：给定ci∈LWEst/q(mi,E),i=0,1c_i\in \mathsf{LWE}_{\mathbf{s}}^{t/q}(m_i,E),i=0,1ci​∈LWEst/q​(mi​,E),i=0,1​​​​，计算c∈LWEst/q(m,E)c\in \mathsf{LWE}_{\mathbf{s}}^{t/q}(m,E)c∈LWEst/q​(m,E)​​​​，其中m=1−m0⋅m1=m0∧ˉm1m=1-m_0 \cdot m_1=m_0 \bar\wedge m_1m=1−m0​⋅m1​=m0​∧ˉm1​​​​​。

一种新的同态NAND门

主要思想是将输入密文变为有一点点不同的形式：ci∈LWEs4/q(mi,q/16)c_i \in \mathsf{LWE}_{\mathbf{s}}^{4/q}(m_i,q/16)ci​∈LWEs4/q​(mi​,q/16)，这里明文模数$t=4$，噪声bound为$E=q/16$。（标准的LWE密文$t=2$,$E=q/4$）
HomNAND:LWEs4/q(m0,q/16)×LWEs4/q(m1,q/16)→LWEs2/q(m0∧ˉm1,q/4)\mathsf{HomNAND:LWE}_{\mathbf{s}}^{4/q}(m_0,q/16) \times \mathsf{LWE}_{\mathbf{s}}^{4/q}(m_1,q/16) \to \mathsf{LWE}_{\mathbf{s}}^{2/q}(m_0 \bar \wedge m_1 ,q/4) 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)(\mathbf{a}, b)=\mathsf{HomNAND}\left(\left(\mathbf{a}_{0}, b_{0}\right),\left(\mathbf{a}_{1}, b_{1}\right)\right)=\left(-\mathbf{a}_{0}-\mathbf{a}_{1}, \frac{5 q}{8}-b_{0}-b_{1}\right) (a,b)=HomNAND((a0​,b0​),(a1​,b1​))=(−a0​−a1​,85q​−b0​−b1​)
要证明：(a,b)∈LWEs2/q(1−m0m1,q/4)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{s}}^{2/q}(1-m_0m_1,q/4)(a,b)∈LWEs2/q​(1−m0​m1​,q/4)​。即证明Decs2/q(a,b)≈1−m0m1\mathsf{Dec}_{\mathbf{s}}^{2/q}(\mathbf{a},b) \approx 1-m_0m_1Decs2/q​(a,b)≈1−m0​m1​，且error bound为$q/4$。

考虑：
b−a⋅s−(1−m0m1)q2=5q8−b0−b1+a0⋅s+a1⋅s−q2+q2⋅m0m1=q8−q4m0−e0−q4m1−e1+q2m0m1=q4(12−m02+2m0m1−m12)−(e0+e1)=q4(12−(m0−m1)2)−(e0+e1)=±q8−(e0+e1)\begin{aligned} b-\mathbf{a \cdot s} – (1-m_0m_1) \frac{q}{2} &= \frac{5q}{8}-b_0 – b_1 + \mathbf{a}_0 \cdot \mathbf{s} +\mathbf{a}_1 \cdot \mathbf{s} -\frac{q}{2}+\frac{q}{2}\cdot m_0m_1 \\ &=\frac{q}{8}-\frac{q}{4}m_0-e_0-\frac{q}{4}m_1-e_1 + \frac{q}{2}m_0m_1\\ &= \frac{q}{4}(\frac{1}{2}-m_0^2 +2m_0m_1 -m_1^2)-(e_0+e_1)\\ &= \frac{q}{4}(\frac{1}{2}-(m_0-m_1)^2)-(e_0+e_1)\\ & = \pm \frac{q}{8}-(e_0+e_1) \end{aligned} b−a⋅s−(1−m0​m1​)2q​​=85q​−b0​−b1​+a0​⋅s+a1​⋅s−2q​+2q​⋅m0​m1​=8q​−4q​m0​−e0​−4q​m1​−e1​+2q​m0​m1​=4q​(21​−m02​+2m0​m1​−m12​)−(e0​+e1​)=4q​(21​−(m0​−m1​)2)−(e0​+e1​)=±8q​−(e0​+e1​)​
所以b−a⋅s=q2⋅(1−m0m1)+e,e=±q8−(e0+e1)b-\mathbf{a}\cdot \mathbf{s} = \frac{q}{2}\cdot(1-m_0m_1) + e,e= \pm\frac{q}{8}-(e_0+e_1)b−a⋅s=2q​⋅(1−m0​m1​)+e,e=±8q​−(e0​+e1​)
∣e∣=∣±q8−(e0+e1)∣<q8+q16+q16=q4|e|=|\pm\frac{q}{8}-(e_0+e_1)|<\frac{q}{8}+\frac{q}{16}+\frac{q}{16}=\frac{q}{4} ∣e∣=∣±8q​−(e0​+e1​)∣<8q​+16q​+16q​=4q​
因此，(a,b)∈LWEs2/q(1−m0m1,q/4)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{s}}^{2/q}(1-m_0m_1,q/4)(a,b)∈LWEs2/q​(1−m0​m1​,q/4)​。

通过同态累加器进行噪声刷新

思想（通过ACC进行Refresh）

对于执行完ctxt=HomNAND(⋅)∈LWEs2/q(m,q/4)\mathsf{ctxt} = \mathsf{HomNAND}(\cdot) \in \mathsf{LWE}_{\mathbf{s}}^{2/q}(m,q/4)ctxt=HomNAND(⋅)∈LWEs2/q​(m,q/4)​的密文来说，要将其重新返回到LWEs4/q(m,q/16)\mathsf{LWE}_{\mathbf{s}}^{4/q}(m,q/16)LWEs4/q​(m,q/16)​​中，以便作为下一个NAND门的输入。因此要执行一个Refresh操作。
Refresh:LWEs2/q(m,q/4)→LWEs4/q(m,q/16)\mathsf{Refresh}: \mathsf{LWE}_{\mathbf{s}}^{2/q}(m,q/4) \rightarrow \mathsf{LWE}_{\mathbf{s}}^{4/q}(m,q/16) Refresh:LWEs2/q​(m,q/4)→LWEs4/q​(m,q/16)
在之前的FHE中，Refresh是通过Gentry提出的Bootstrapping来做到的，对于一个LWE密文(a,b)∈LWEs2/q(m)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{s}}^{2/q}(m)(a,b)∈LWEs2/q​(m)。我们的目的是得到一个新的密文$E(m)$，其中$E(\cdot )$是一种满足同态性质的加密方案，其实在实践中就是$\mathsf{LWE}$加密本身，但这里为了便于理解，写为$E$。为了从一个$(\mathbf{a},b)$中得到$E(m)$，需要在$(\mathbf{a},b)$上同态地执行解密操作，具体来说，我们使用$E$加密$\mathbf{s}$得到$E(\mathbf{s})$，然后计算
$$\lfloor 2/q(b-\mathbf{a}\cdot E(\mathbf{s}))\rceil \mathrm{mod}2\approx E(m)$$
那如果$E$就是一个LWE加密的话，就得到了$E(m)\in \mathsf{LWE}(m)$，且这个密文的噪声经过了刷新。

这里涉及到两个问题

1. 首先，要在密文上做向量的内积$\mathbf{a}\cdot E(\mathbf{s})\to E(\mathbf{a}\cdot \mathbf{s})$​，这点不难，只要对$\mathbf{s}$​向量每个元素进行分别加密：E(s)=(E(s1),…,E(sn))E(\mathbf{s})=(E(s_1),…,E(s_n))E(s)=(E(s1​),…,E(sn​))。那么就可以得到b−a⋅E(s)=E(b−a⋅s)=E(q2⋅m)b-\mathbf{a}\cdot E(\mathbf{s})=E(b-\mathbf{a\cdot s})=E(\frac{q}{2}\cdot m)b−a⋅E(s)=E(b−a⋅s)=E(2q​⋅m)。
2. 下一个问题是，如何在密文上做rounding操作。这里采用了一个密文上的提取最高位的操作来得到一个$\mathsf{LWE}(m)$​​，考虑$m=0,E(0),m=1,E(q/2)$​​，采用最高位提取ctxt=msbExtract(E(q2m))\mathsf{ctxt=msbExtract}(E(\frac{q}{2}m))ctxt=msbExtract(E(2q​m))​​，则若$m=0,\mathsf{ctxt}\in \mathsf{LWE}(0)$，若$m=1,\mathsf{ctxt}\in \mathsf{LWE}(1)$。

定义（同态累加器）

**定义（同态累加器）**同态累加器由一个四元组构成$(E,\mathsf{Init},\mathsf{Incr},\mathsf{msbExtract})$​​，四个算法都需要模数$t,q$​​，$E$​​以及$\mathsf{msbExtract}$​​需要一些与$\mathbf{s}$​​相关的密钥材料。为了书写简单，这里记$\mathsf{ACC}\leftarrow v\iff \mathsf{ACC}\leftarrow \mathsf{Init}(v)$​，ACC←+E(v)⇔ACC←Incr(ACC,E(v))\mathsf{ACC} \stackrel{+}\gets E(v) \Leftrightarrow \mathsf{ACC} \gets \mathsf{Incr}(\mathsf{ACC},E(v))ACC←+E(v)⇔ACC←Incr(ACC,E(v))​。​

对于一系列的数v0,v1,…,vℓ∈Zqv_0,v_1,…,v_{\ell}\in \mathbb{Z}_qv0​,v1​,…,vℓ​∈Zq​，在进行如下操作后：
ACC←v0,ACC←+E(vi),i=1,…,l\mathsf{ACC}\gets v_0, \mathsf{ACC} \stackrel{+}\gets E(v_i), i= 1,…,l ACC←v0​,ACC←+E(vi​),i=1,…,l
称这样的$\mathsf{ACC}$​是一个$v$​的$\ell -encryption$​，其中v=∑i=0ℓvimodqv=\sum_{i=0}^{\ell}v_i \bmod qv=∑i=0ℓ​vi​modq​​。

我们称一个同态累加器是$\mathcal{E}-correct$​的，当且仅当​​对于任意$v$的一个$\ell -encryption$，$\mathbf{c}\leftarrow \mathsf{msbExtract}(\mathsf{ACC})$有很大概率得到c∈LWEst/q(v,E(ℓ))\mathbf{c}\in\mathsf{LWE}_{\mathbf{s}}^{t/q}(v,\mathcal{E}(\ell))c∈LWEst/q​(v,E(ℓ))。

算法（Refresh）

在这里Refresh算法中使用到了累加器的参数为$t=4$​​​​，$\mathcal{E}(\ell )\le q/16$​​​​​​。用到了一个分解系数BrB_rBr​​​​​，这里的$r$​​​​下标指Refresh。刷新过程的输入为一个密文(a,b)∈LWEs2/q(m,q/4)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{s}}^{2/q}(m,q/4)(a,b)∈LWEs2/q​(m,q/4)​​​​，以及一个密钥材料Ki,j=E(siBrjmodq)K_{i,j}=E(s_i B_r^j \bmod q)Ki,j​=E(si​Brj​modq)​​​，在实际使用中，我们采用Ki,ai,j,j=ai,jE(siBrjmodq)=E(ai,jsiBrjmodq)K_{i,a_{i,j},j}=a_{i,j}E(s_iB_r^j \bmod q)=E(a_{i,j}s_iB_r^j \bmod q)Ki,ai,j​,j​=ai,j​E(si​Brj​modq)=E(ai,j​si​Brj​modq)​​​​。因为采用了标量乘法，所以要多aia_iai​​​​进行分解−ai=∑jai,jBrj-a_i = \sum_j a_{i,j}B_r^j−ai​=∑j​ai,j​Brj​​​​，来降低Ki,ai,j,jK_{i,a_{i,j},j}Ki,ai,j​,j​​​​​的噪音。其中ai,j∈{0,…,Br−1}a_{i,j}\in\{0,…,B_r-1\}ai,j​∈{0,…,Br​−1}​​, j=0,…,dr−1j=0,…,d_r-1j=0,…,dr​−1​​, dr=⌈log⁡Brq⌉d_r=\lceil \log_{B_r}q \rceildr​=⌈logBr​​q⌉​​​​, $i=1,\dots ,n$​。

---

Algorithm RefreshK(a,b)\mathsf{Refresh}_{\mathcal{K}}(\mathbf{a},b)RefreshK​(a,b)​​​, for K={Ki,j}i≤n,j≤dr\mathcal{K}=\{K_{i,j}\}_{i\le n,j \le d_r}K={Ki,j​}i≤n,j≤dr​​​​​​

---

$\mathsf{ACC}\leftarrow b+(q/4)$

for $i=1,\dots ,n$​​​ do

​ 计算−ai=∑jBrj⋅ai,j(modq)-a_i=\sum_jB_r^j \cdot a_{i,j} \pmod q−ai​=∑j​Brj​⋅ai,j​(modq)​，Ki,ai,j,j=ai,jE(siBrj)=E(ai,jsiBrj)K_{i,a_{i,j},j}=a_{i,j}E(s_i B_r^j)=E(a_{i,j}s_i B_r^j)Ki,ai,j​,j​=ai,j​E(si​Brj​)=E(ai,j​si​Brj​)​

​ for j=0,…,dr−1j=0,…,d_r-1j=0,…,dr​−1 do ACC←+Ki,ai,j,j\mathsf{ACC} \stackrel{+}\gets K_{i,a_{i,j},j}ACC←+Ki,ai,j​,j​

end for

输出$\mathsf{msbExtract}(\mathsf{ACC})$

---

Theorem： 如果$(E,\mathsf{Init},\mathsf{Incr},\mathsf{msbExtract})$​是一个正确的同态累加器，那么$\mathsf{Refresh}$​算法，在输入任意密文(a,b)∈LWEs2/q(m,q/4)(\mathbf{a},b)\in \mathsf{LWE}_{\mathbf{s}}^{2/q}(m,q/4)(a,b)∈LWEs2/q​(m,q/4)​，​以及有效的刷新密钥K={Ki,j=E(siBrj)}i,j\mathcal{K}=\{K_{i,j}=E(s_iB_r^j)\}_{i,j}K={Ki,j​=E(si​Brj​)}i,j​的情况下，会输出一个密文RefreshK(c)∈LWEst/q(m,E(nd))\mathsf{Refresh}_{\mathcal{K}}(\mathbf{c})\in \mathsf{LWE}_{\mathbf{s}}^{t/q}(m,\mathcal{E}(nd))RefreshK​(c)∈LWEst/q​(m,E(nd))。

Proof. 刷新操作首先初始化累加器为$b+q/4$，然后进行了$nd$次的加法Ki,ai,j,j=E(ai,jsiBrj)K_{i,a_{i,j},j}=E(a_{i,j}s_i B_r^j)Ki,ai,j​,j​=E(ai,j​si​Brj​)。所以最后的结果是一个噪声为$\mathcal{E}(nd)$的LWE密文，累加器中的内容值$v$为：

v−q4=b+∑i,jai,jsiBrj=b+∑isi∑jBrjai,j=b+(−∑iaisi)=q2m+ev-\frac{q}{4}=b+\sum_{i,j}a_{i,j}s_iB_r^j=b+\sum_i s_i \sum_j B_r^ja_{i,j} = b+(-\sum_i a_is_i)=\frac{q}{2}m+e v−4q​=b+i,j∑​ai,j​si​Brj​=b+i∑​si​j∑​Brj​ai,j​=b+(−i∑​ai​si​)=2q​m+e
v=q2m+e+q4v=\frac{q}{2}m+e+\frac{q}{4}v=2q​m+e+4q​​​​​，这里的$e$​​​是输入密文$(\mathbf{a},b)$​​​的噪声。根据假设$\left|e\right|<q/4$​​，所以有0<e+q4<q20<e+\frac{q}{4}<\frac{q}{2}0<e+4q​<2q​​​。所以当$m=0$​​时，$0<v<q/2$​​，$v$的最高位为0，当$m=1$时，$q/2<v<q$，$v$的最高位为1。因为在实际应用中$q$是$power-of-two$，所以$v$的最高位为$m$，那么$\mathsf{msbExtract}(\mathsf{ACC})$能得到LWEsq/t(m)\mathsf{LWE}_{\mathbf{s}}^{q/t}(m)LWEsq/t​(m)​​。

由RGSW构造同态累加器

在构造同态累加器时，我们使用的参数为$t=4$, q=2kq=2^kq=2k, $E$是一个Zq\mathbb{Z}_qZq​​内的加密方案。这里的构造采用了Alperin-Sheriff⁵的思想。但是与他们不同的是，这篇文章直接将Zq\mathbb{Z}_qZq​当做$\mathcal{R}$的原根构成的乘法子环。

这个方案里面取一个模数$Q$，多项式环的阶N=2KN=2^KN=2K，满足$q|2N$，为了方便理解，这篇笔记里采用$q=2N$，一个分解系数BgB_gBg​（这里$g$指gadget）。这里假设Q=BgdgQ=B_g^{d_g}Q=Bgdg​​，其中BgB_gBg​是$power-of-three$。令R=Z[X]/(XN+1)\mathcal{R}=\mathbb{Z}[X]/(X^N+1)R=Z[X]/(XN+1)，RQ=(R/QR)\mathcal{R}_Q=(\mathcal{R}/Q\mathcal{R})RQ​=(R/QR)，以及一个额外的参数$u$，这里$u$是取一个Zq\mathbb{Z}_qZq​内接近$Q/2t$的可逆的数，因为$Q$是3的幂次，所以$\lfloor Q/2t\rfloor$,$\lceil Q/2t\rceil$中必有一个可逆，所以$|u-Q/2t|<1$。

消息$m$被加密为原根Xm∈RX^m\in \mathcal{R}Xm∈R的形式，原根构成一个循环群G=⟨X⟩={1,X,…,XN−1,−1,−X,…,−XN−1}\mathcal{G}=\langle X \rangle = \{1,X,…,X^{N-1},-1,-X,…,-X^{N-1}\}G=⟨X⟩={1,X,…,XN−1,−1,−X,…,−XN−1}​。当$q=2N$时，Zq≃⟨X⟩\mathbb{Z}_q\simeq \langle X \rangleZq​≃⟨X⟩。

基于RGSW的累加器的构造

---

−Ez(m)-E_z(m)−Ez​(m)：输入为消息$m$，密钥$z\in \mathcal{R}$​，

​ 选取a∈RQ2dg\mathbf{a}\in \mathcal{R}_{Q}^{2d_g}a∈RQ2dg​​是一个随机分布，e∈R2dg≃Z2dgN\mathbf{e} \in \mathcal{R}^{2d_g} \simeq \mathbb{Z}^{2d_gN}e∈R2dg​≃Z2dg​N是一个满足参数为$\varsigma$的次高斯分布。输出
Ez(m)=[a,a⋅z+e]+uXmG∈RQ2dg×2E_z(m)=[\mathbf{a},\mathbf{a}\cdot z + \mathbf{e}] + uX^m \mathbf{G} \in \mathcal{R}_Q^{2d_g \times 2} Ez​(m)=[a,a⋅z+e]+uXmG∈RQ2dg​×2​
​ 其中G=(I,BgI,…,Bgdg−1I)∈R2dg×2\mathbf{G} = (\mathbf{I},B_g\mathbf{I},…,B_g^{d_g-1}\mathbf{I})\in \mathcal{R}^{2d_g \times 2}G=(I,Bg​I,…,Bgdg​−1​I)∈R2dg​×2。

$-\mathsf{Init}(\mathsf{ACC}\leftarrow v)$：输入为v∈Zqv\in \mathbb{Z}_qv∈Zq​，

​ 直接设定ACC:=uXv⋅G∈RQ2dg×2\mathsf{ACC}:=u X^v\cdot \mathbf{G} \in \mathcal{R}_Q^{2d_g \times 2}ACC:=uXv⋅G∈RQ2dg​×2​。

−Incr(ACC←+C)-\mathsf{Incr}(\mathsf{ACC} \stackrel{+}\gets \mathbf{C})−Incr(ACC←+C)，输入为当前的ACC∈RQ2dg×2\mathsf{ACC}\in\mathcal{R}_{Q}^{2d_g\times2}ACC∈RQ2dg​×2​​，以及一个密文C∈RQ2dg×2\mathbf{C}\in \mathcal{R}_Q^{2d_g\times 2}C∈RQ2dg​×2​，首先计算u−1ACCu^{-1}\mathsf{ACC}u−1ACC的分解为u−1ACC=∑i=1dgBgi−1Diu^{-1}\mathsf{ACC}=\sum_{i=1}^{d_g}B_g^{i-1}\mathbf{D}_iu−1ACC=∑i=1dg​​Bgi−1​Di​（其中每个Di∈R2dg×2\mathbf{D}_i\in \mathcal{R}^{2d_g\times 2}Di​∈R2dg​×2，每项的系数在{1−Bg2,…,Bg−12}\{\frac{1-B_g}{2},…,\frac{B_g-1}{2}\}{21−Bg​​,…,2Bg​−1​}之内）。并更新累加器的值：
ACC:=[D1,…,Ddg]⋅C\mathsf{ACC}:= [\mathbf{D}_1,…,\mathbf{D}_{d_g}]\cdot \mathbf{C} ACC:=[D1​,…,Ddg​​]⋅C
$-\mathsf{msbExtract}$:输入为一个$\mathsf{KeySwitch}$​​​密钥$\mathfrak{K}$​​​，一个测试向量t=−∑i=0N−1Xi→\mathbf{t}=-\sum_{i=0}^{N-1} \overrightarrow{X^{i}}t=−∑i=0N−1​Xi​​​，其实t=(−1,−1,…,−1)∈ZN\mathbf{t}=(-1,-1,…,-1) \in \mathbb{Z}^Nt=(−1,−1,…,−1)∈ZN​​。最后提取的正确性在于：t⋅Xv→\mathbf{t}\cdot \overrightarrow{X^v}t⋅Xv​的值：如果$0\le v<N$，那么t⋅Xv→=−1\mathbf{t}\cdot \overrightarrow{X^v}=-1t⋅Xv=−1，如果$N\le v<2N$，那么t⋅Xv→=1\mathbf{t}\cdot \overrightarrow{X^v}=1t⋅Xv=1​。具体算法如下：

两个符号：⋅→:a=a0+a1x+…+aN−1xN−1∈R\overrightarrow{\cdot}:a=a_0+a_1x+…+a_{N-1}x^{N-1}\in\mathcal{R}⋅:a=a0​+a1​x+…+aN−1​xN−1∈R, a→=(a0,…,aN−1)∈ZN\overrightarrow{a}=(a_0,…,a_{N-1})\in \mathbb{Z}^Na=(a0​,…,aN−1​)∈ZN。

⋅⇒:a=a0+a1x+…+aN−1xN−1∈R\stackrel{\Rightarrow}{\cdot}: a=a_0+a_1x+…+a_{N-1}x^{N-1}\in \mathcal{R}⋅⇒:a=a0​+a1​x+…+aN−1​xN−1∈R，a⇒∈ZN×N\stackrel{\Rightarrow}{a}\in \mathbb{Z}^{N \times N}a⇒∈ZN×N是一个负循环矩阵，a⇒\stackrel{\Rightarrow}{a}a⇒的第一列为a→\overrightarrow{a}a。​
a⇒=[a0−aN−1⋯−a2−a1a1a0−aN−1−a2⋮a1a0⋱⋮aN−2⋱⋱−aN−1aN−1aN−2⋯a1a0]\stackrel{\Rightarrow}{a}=\left[\begin{array}{ccccc} a_{0} & -a_{N-1} & \cdots & -a_{2} & -a_{1} \\ a_{1} & a_{0} & -a_{N-1} & & -a_{2} \\ \vdots & a_{1} & a_{0} & \ddots & \vdots \\ a_{N-2} & & \ddots & \ddots & -a_{N-1} \\ a_{N-1} & a_{N-2} & \cdots & a_{1} & a_{0} \end{array}\right] a⇒=​a0​a1​⋮aN−2​aN−1​​−aN−1​a0​a1​aN−2​​⋯−aN−1​a0​⋱⋯​−a2​⋱⋱a1​​−a1​−a2​⋮−aN−1​a0​​​

原文这里switching key有点错误，纠正一下

算法 msbExtractK(ACC)\mathsf{msbExtract}_{\mathfrak{K}}(\mathsf{ACC})msbExtractK​(ACC), for K={ki,j,w}i≤N,j≤dks,w≤Bks\mathfrak{K}=\{\mathbf{k}_{i,j,w}\}_{i\le N,j\le d_{ks},w\le B_{ks}}K={ki,j,w​}i≤N,j≤dks​,w≤Bks​​。

需要一个switching keyK={ki,j,w}i,j,w\mathfrak{K}=\{\mathbf{k}_{i,j,w}\}_{i,j,w}K={ki,j,w​}i,j,w​​是将密钥$\mathbf{z}$替换为密钥$\mathbf{s}$的：ki,j,w←LWEsq/q(w⋅zi⋅Bksj)\mathbf{k}_{i,j,w}\gets \mathsf{LWE}_{\mathbf{s}}^{q/q}(w\cdot z_i \cdot B_{ks}^j)ki,j,w​←LWEsq/q​(w⋅zi​⋅Bksj​)。$\mathsf{ACC}$是$v$的一个$\ell$-encryption。
1: [at,bt]←([0→t,tt,0→t,…,0→t]⋅ACC⇒)∈ZQ2N//ACC⇒∈Z2Ndg×2N\left[\mathbf{a}^{t}, \mathbf{b}^{t}\right] \leftarrow([\overrightarrow{0}^{t}, \mathbf{t}^{t}, \overrightarrow{0}^{t}, \ldots, \overrightarrow{0}^{t}] \cdot \stackrel{\Rightarrow}{\mathsf{ACC}} ) \in \mathbb{Z}_{Q}^{2 N} \quad / / \stackrel{\Rightarrow}{\mathsf{ACC}} \in \mathbb{Z}^{2 N d_{\mathrm{g}} \times 2 N}[at,bt]←([0t,tt,0t,…,0t]⋅ACC⇒)∈ZQ2N​//ACC⇒∈Z2Ndg​×2N​​​​​​​​​
2: c←(a,b0+u)∈LWE⁡z→t/Q(msb⁡(v))\mathbf{c} \leftarrow\left(\mathbf{a}, b_{0}+u\right)\quad\quad \in \operatorname{LWE}_{\overrightarrow{z}}^{t / Q}(\operatorname{msb}(v))c←(a,b0​+u)∈LWEzt/Q​(msb(v))​​​​​​​​
3: c′←KeySwitch(c,K)∈LWEst/Q(msb⁡(v))\mathbf{c}^{\prime} \gets \mathsf{KeySwitch} (\mathbf{c}, \mathfrak{K}) \in \mathsf{LWE}_{\mathbf{s}}^{t / Q}(\operatorname{msb}(v))c′←KeySwitch(c,K)∈LWEst/Q​(msb(v))​​​​​
4: c′′←ModSwitch(c′)∈LWEst/q(msb⁡(v))\mathbf{c}^{\prime \prime} \gets \mathsf{ModSwitch} \left(\mathbf{c}^{\prime}\right) \in \mathsf{LWE}_{\mathbf{s}}^{t / q}(\operatorname{msb}(v))c′′←ModSwitch(c′)∈LWEst/q​(msb(v))​​​​​
5: Return c′\mathbf{c}^{\prime}c′​​​​​​​​​.

---

正确性

噪声分析的部分就略过了，主要看一下流程的正确性。

首先理解一下Ez(m)E_z(m)Ez​(m)​的结构：Ez(m)=[a,a⋅z+e]+uXmG∈RQ2dg×2E_z(m)=[\mathbf{a},\mathbf{a}\cdot z + \mathbf{e}] + uX^m \mathbf{G} \in \mathcal{R}_Q^{2d_g \times 2}Ez​(m)=[a,a⋅z+e]+uXmG∈RQ2dg​×2​​,G=(I,BgI,…,Bgdg−1I)∈R2dg×2\mathbf{G} = (\mathbf{I},B_g\mathbf{I},…,B_g^{d_g-1}\mathbf{I})\in \mathcal{R}^{2d_g \times 2}G=(I,Bg​I,…,Bgdg​−1​I)∈R2dg​×2​
I=[1001],G=[1001Bg00Bg⋮⋮Bgdg−100Bgdg−1],uXmG=[uXm00uXmBguXm00BguXm⋮⋮Bgdg−1uXm00Bgdg−1uXm]\mathbf{I} = \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix},\mathbf{G}=\begin{bmatrix} 1&0 \\ 0&1 \\ B_g&0 \\ 0& B_g\\ \vdots &\vdots\\ B_g^{d_g-1}& 0\\ 0&B_g^{d_g-1} \end{bmatrix},uX^m\mathbf{G}=\begin{bmatrix} uX^m&0 \\ 0&uX^m \\ B_guX^m&0 \\ 0& B_guX^m\\ \vdots &\vdots\\ B_g^{d_g-1}uX^m& 0\\ 0&B_g^{d_g-1}uX^m \end{bmatrix} I=[10​01​],G=​10Bg​0⋮Bgdg​−1​0​010Bg​⋮0Bgdg​−1​​​,uXmG=​uXm0Bg​uXm0⋮Bgdg​−1​uXm0​0uXm0Bg​uXm⋮0Bgdg​−1​uXm​​

[a,a⋅z+e]=[a0a0z+e0a1a1z+e1a2a2z+e2a3a3z+e3⋮⋮a2dg−2a2dg−2z+e2dg−2a2dg−1a2dg−1z+e2dg−1],Ez(m)=[a0+uXma0z+e0a1a1z+e1+uXma2+BguXma2z+e2a3a3z+e3+BguXm⋮⋮a2dg−2+Bgdg−1uXma2dg−2z+e2dg−2a2dg−1a2dg−1z+e2dg−1+Bgdg−1uXm][\mathbf{a},\mathbf{a}\cdot z+\mathbf{e}]=\begin{bmatrix} a_0&a_0z+e_0 \\ a_1&a_1z+e_1 \\ a_2&a_2z+e_2 \\ a_3&a_3z+e_3\\ \vdots &\vdots\\ a_{2d_g-2}&a_{2d_g-2}z+e_{2d_g-2}\\ a_{2d_g-1}&a_{2d_g-1}z+e_{2d_g-1} \end{bmatrix} ,E_z(m)=\begin{bmatrix} a_0+uX^m&a_0z+e_0 \\ a_1&a_1z+e_1+uX^m \\ a_2+B_guX^m&a_2z+e_2 \\ a_3&a_3z+e_3+B_guX^m\\ \vdots &\vdots\\ a_{2d_g-2}+B_g^{d_g-1}uX^m&a_{2d_g-2}z+e_{2d_g-2}\\ a_{2d_g-1}&a_{2d_g-1}z+e_{2d_g-1}+B_g^{d_g-1}uX^m \end{bmatrix} [a,a⋅z+e]=​a0​a1​a2​a3​⋮a2dg​−2​a2dg​−1​​a0​z+e0​a1​z+e1​a2​z+e2​a3​z+e3​⋮a2dg​−2​z+e2dg​−2​a2dg​−1​z+e2dg​−1​​​,Ez​(m)=​a0​+uXma1​a2​+Bg​uXma3​⋮a2dg​−2​+Bgdg​−1​uXma2dg​−1​​a0​z+e0​a1​z+e1​+uXma2​z+e2​a3​z+e3​+Bg​uXm⋮a2dg​−2​z+e2dg​−2​a2dg​−1​z+e2dg​−1​+Bgdg​−1​uXm​​

可以看出，Ez(m)E_z(m)Ez​(m)​​​中的第二行，其实是(a1,a1z+e1+uXm)≈RLWEzt/Q(12Xm)(a_1,a_1z+e_1+uX^m)\approx\mathsf{RLWE}_{z}^{t/Q}(\frac{1}{2}X^m)(a1​,a1​z+e1​+uXm)≈RLWEzt/Q​(21​Xm)​​​，因为​​

$u\approx Q/2t$​, RLWEzt/q(m)=(a,az+e+Q/tm)≈(a,az+e+2um)\mathsf{RLWE}_{z}^{t/q}(m)=(a,az+e+Q/tm)\approx (a,az+e+2um)RLWEzt/q​(m)=(a,az+e+Q/tm)≈(a,az+e+2um)​。

ACC的正确性没有给出证明，而是直接作为一个结果。

根据Fact 9，可以直接得到最后ACC=[a,az+e]+uXvG\mathsf{ACC}=[\mathbf{a},\mathbf{a}z+\mathbf{e}]+uX^v\mathbf{G}ACC=[a,az+e]+uXvG​​​。这里v=q2m+e+q4v=\frac{q}{2}m+e+\frac{q}{4}v=2q​m+e+4q​​​​。$m=\mathsf{msb}(v)$​​，这个性质是在之前**算法(Refresh)**中证明过。

Extract正确性

在$\mathsf{msbExtract}$​算法中，我们计算了[at,bt]←([0→t,tt,0→t,…,0→t]⋅ACC⇒)∈ZQ2N\left[\mathbf{a}^{t}, \mathbf{b}^{t}\right] \leftarrow([\overrightarrow{0}^{t}, \mathbf{t}^{t}, \overrightarrow{0}^{t}, \ldots, \overrightarrow{0}^{t}] \cdot \stackrel{\Rightarrow}{\mathsf{ACC}} ) \in \mathbb{Z}_{Q}^{2 N}[at,bt]←([0t,tt,0t,…,0t]⋅ACC⇒)∈ZQ2N​​，其实这里就是求了tt\mathbf{t}^ttt​和$\mathsf{ACC}$​中第二行的乘积，令a,b′a,b'a,b′​为ACC中第二行的值，满足b′→=a⇒⋅z→+u⋅Xv→+e→\overrightarrow{b'}=\stackrel{\Rightarrow}{a}\cdot \overrightarrow{z}+u\cdot \overrightarrow{X^v}+\overrightarrow{e}b′=a⇒⋅z+u⋅Xv+e​。b0b_0b0​为b′b'b′的第一项，则[at,b0]←tt⋅[a⇒,b′→][\mathbf{a}^t,b_0] \gets \mathbf{t}^t\cdot\left[\stackrel{\Rightarrow}{a},\overrightarrow{b'}\right][at,b0​]←tt⋅[a⇒,b′]​。

观察到$m=\mathsf{msb}(v)$，当$m=0$, $0\le v<N$, tt⋅Xv→=−1\mathbf{t}^t \cdot \overrightarrow{X^v}=-1tt⋅Xv=−1，$m=1,N\le v<2N$, tt⋅Xv→=1\mathbf{t}^t \cdot \overrightarrow{X^v}=1tt⋅Xv=1。因此tt⋅Xv→=−(−1)msb(v)\mathbf{t}^t \cdot \overrightarrow{X^v}=-(-1)^{\mathsf{msb}(v)}tt⋅Xv=−(−1)msb(v)。观察到1−(−1)x=2×1-(-1)^x=2x1−(−1)x=2x，所以u(1+tt⋅Xv→)=2umsb(v)u(1+\mathbf{t}^t \cdot \overrightarrow{X^v})=2u\mathsf{msb}(v)u(1+tt⋅Xv)=2umsb(v)。

所以
c=(a,b0+u)=(a,a⋅z→+t⋅e+utt⋅Xv→+u)=(a,a⋅z→+t⋅e+2umsb(v))\mathbf{c}=(\mathbf{a},b_0+u) = (\mathbf{a},\mathbf{a}\cdot \overrightarrow{z} + \mathbf{t}\cdot \mathbf{e} +u\mathbf{t}^t \cdot \overrightarrow{X^v} + u)=(\mathbf{a},\mathbf{a}\cdot \overrightarrow{z} + \mathbf{t}\cdot \mathbf{e} +2u\mathsf{msb}(v)) c=(a,b0​+u)=(a,a⋅z+t⋅e+utt⋅Xv+u)=(a,a⋅z+t⋅e+2umsb(v))
又因为$u=\lfloor Q/2t\rceil$​：
c=(a,a⋅z→+t⋅e+⌊Q/t⌉msb(v))∈LWEz→t/Q(msb(v))=LWEz→t/Q(m)\mathbf{c} = (\mathbf{a},\mathbf{a}\cdot \overrightarrow{z} + \mathbf{t}\cdot \mathbf{e} +\lfloor Q/t \rceil\mathsf{msb}(v))\in \mathsf{LWE}_{\overrightarrow{z}}^{t/Q}(\mathsf{msb}(v))=\mathsf{LWE}_{\overrightarrow{z}}^{t/Q}(m) c=(a,a⋅z+t⋅e+⌊Q/t⌉msb(v))∈LWEzt/Q​(msb(v))=LWEzt/Q​(m)

噪声的刷新可以粗略的理解一下，因为是通过提取msb的方式来取得m，所以新的密文与之前的噪声大小就无关了，所以refresh就相当于进行了bootstrapping。

方案总览

总结

FHEW刷新密文的思想，主要是考虑q2m+e+q4\frac{q}{2}m+e+\frac{q}{4}2q​m+e+4q​这样一个式子，其中$q=2N$​​是2的幂次，∣e∣<q4|e|<\frac{q}{4}∣e∣<4q​，因此$msb(v)=m$​，将这个$v$编码到多项式的次数上Xv∈RX^v\in \mathcal{R}Xv∈R，当$m=0$，$0\le v<N$，XvX^vXv的系数是正的，当$m=1$，$N\le v<2N$，XvX^vXv的系数是负的。通过这样的一个性质，结合GSW的技术，可以在密文上提取出$v$​的最高位。相当于做了一次密文刷新。

小尾巴

本人正在入门密码学，欢迎各位同学或老师加我微信交流：shenghua-adije

---

1. Centrum Wiskunde and Informatica, Amsterdam, Netherlands; leo.ducas@cwi.nl ↩︎

2. University of California, San Diego, California, USA; daniele@cse.ucsd.edu ↩︎

3. 也不知道这里的bootstrapping是指对bit-wise密文还是word-wise密文。之后看一看 ↩︎

4. 所谓仿射变换，就是向量经过一次线性变换加一次平移变换，用公式可以表示为：q⃗=Ap⃗+b⃗\vec{q}=A \vec{p}+\vec{b}q​=Ap​+b​ ↩︎

5. Alperin-Sheriff J., Peikert C. (2014) Faster Bootstrapping with Polynomial Error. In: Garay J.A., Gennaro R. (eds) Advances in Cryptology – CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44371-2_17 ↩︎ ↩︎ ↩︎ ↩︎