参考文献：
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, STOC, pages 84–93. ACM, 2005. Full version in J. ACM 56(6), 2009.
- V. Lyubashevsky, C. Peikert, and O. Regev. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 1–23. Springer, 2010. Full version of the paper available upon request from authors.
- Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. IACR Cryptology ePrint Archive, 2012:78, 2012.
- Fan J, Vercauteren F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2012.
文章目录
Regev Scheme
2009 年，Regev 提出了第一个基于 LWE 的加密方案。方案如下：
LPR Scheme
在 Regev Scheme 中，明文空间是
Z2\mathbb Z_2Z2，使用 most significant bit encoding。我们可以容易地修改它，使得密码方案基于 RLWE 问题，明文空间为Rt,t≥2R_t,\, t \ge 2Rt,t≥2 ，只需把δ=⌊q/2⌉\delta = \lfloor q/2 \rceilδ=⌊q/2⌉ 替换为Δ=⌊q/t⌉\Delta = \lfloor q/t \rceilΔ=⌊q/t⌉ 即可。方案如下：
BFV
Brakerski Scheme
Without Modulus Switching
此方案是基于 LWE 的。对于 Regev Scheme，如果将向量
s,cs,cs,c 写成增广形式，那么有<c,s>=q/2⋅m+e+qI<c,s> = q/2 \cdot m+e+qI<c,s>=q/2⋅m+e+qI，其中∣e∣≤E<q/4|e| \le E < q/4∣e∣≤E<q/4，I∈ZI \in \mathbb ZI∈Z 是个整数，密文ccc 的分量取值范围是(−q/2,q/2](-q/2,q/2](−q/2,q/2]
考虑分数密文（fractional ciphertext）
c’=c/qc’ = c/qc’=c/q，那么<c′,s>=12⋅m+e′+I<c',s> = \frac{1}{2} \cdot m + e' + I<c′,s>=21⋅m+e′+I
其中噪音
∣e′∣≤E/q=ϵ<0.25|e'| \le E/q = \epsilon < 0.25∣e′∣≤E/q=ϵ<0.25 是个小数，密文c’c’c’ 的各个分量的取值范围是(−1/2,1/2](-1/2,1/2](−1/2,1/2]
同态加法
cadd=c1+c2c_{add} = c_1+c_2cadd=c1+c2，有：<c1+c2,s>=<c1,s>+<c2,s>=12m+(e1+e2)mod1\begin{aligned} <c_1+c_2,\, s> &= <c_1,s> + <c_2,s> \\ &= \frac{1}{2} m + (e_1+e_2) \mod 1 \end{aligned}<c1+c2,s>=<c1,s>+<c2,s>=21m+(e1+e2)mod1
同态乘法
cmult=2⋅c1⊗c2c_{mult} = 2 \cdot c_1 \otimes c_2cmult=2⋅c1⊗c2，有：<2⋅c1⊗c2,s⊗s>=2⋅<c1,s>⋅<c2,s>=12m1m2+2(e1I2+e2I1)+e1m2+e2m1+2e1e2mod1\begin{aligned} <2 \cdot c_1 \otimes c_2,\, s \otimes s> &= 2 \cdot <c_1,s> \cdot <c_2,s> \\ &= \frac{1}{2} m_1m_2 + 2(e_1I_2 + e_2I_1) + e_1m_2 + e_2m_1 + 2e_1e_2 \mod 1 \end{aligned}<2⋅c1⊗c2,s⊗s>=2⋅<c1,s>⋅<c2,s>=21m1m2+2(e1I2+e2I1)+e1m2+e2m1+2e1e2mod1
其中
∣I1∣,∣I2∣|I_1|,|I_2|∣I1∣,∣I2∣ 的界约为∥s∥1\|s\|_1∥s∥1，所以cmultc_{mult}cmult 中的噪声的界为O(∥s∥1)⋅ϵO(\|s\|_1) \cdot \epsilonO(∥s∥1)⋅ϵ。由于 Regev Scheme 中的私钥取自均匀分布，因此∥s∥1≈nq\|s\|_1 \approx nq∥s∥1≈nq，模数qqq 是安全参数nnn 的指数级。而其他噪声e1m2+e2m1≤2tϵe_1m_2+e_2m_1 \le 2t \epsilone1m2+e2m1≤2tϵ，2e1e2≤2ϵ22e_1e_2 \le 2\epsilon^22e1e2≤2ϵ2 的占比很小。因此，主要噪声就是2(e1I2+e2I1)2(e_1I_2 + e_2I_1)2(e1I2+e2I1)
为了减小噪声，需要要减小私钥的
l1l_1l1 范数。我们可以对解密电路做**二进制分解**（*binary decomposition*），令s=∑j2js(j)s = \sum_j 2^j s^{(j)}s=∑j2js(j)，其中s(j)s^{(j)}s(j) 的各个元素是sss 的各个元素的第jjj 比特。那么，解密电路化为：<c,s>=∑j2j<c,s(j)>=<(c,2c,⋯),(s(0),s(1),⋯)>\begin{aligned} <c,s> &= \sum_j 2^j <c,s^{(j)}> \\ &= <(c,\, 2c,\, \cdots),\,\, (s^{(0)},\, s^{(1)},\, \cdots)> \end{aligned}<c,s>=j∑2j<c,s(j)>=<(c,2c,⋯),(s(0),s(1),⋯)>
那么，我们就将
sss 下的密文ccc，转化为了(s(0),s(1),⋯)(s^{(0)},\, s^{(1)},\, \cdots)(s(0),s(1),⋯) 下的密文(c,2c,⋯)(c,\, 2c,\, \cdots)(c,2c,⋯)
二进制私钥的
l1l_1l1 范数至多是其维度，即O(n⋅logq)=O(poly(n))O(n \cdot \log q) = O(poly(n))O(n⋅logq)=O(poly(n))，因此**噪声增长是多项式级别的**。也就是说，我们不必使用 BGV 中的模切换技术了！
在代码实现时，由于浮点数精度问题，我们将密文放大
qqq 倍。实质上是用Zq\mathbb Z_qZq 上的整数运算，来模拟R/ZR/\mathbb ZR/Z 上的浮点数运算：令yi=⌊qxi⌉y_i = \lfloor qx_i \rceilyi=⌊qxi⌉，那么y1+y2≈⌊q(x1+x2)⌉⌊(y1⋅y2)/q⌉≈⌊q⋅x1⋅x2⌉\begin{aligned} y_1+y_2 \approx \lfloor q(x_1+x_2) \rceil\\ \lfloor (y_1 \cdot y_2)/q \rceil \approx \lfloor q \cdot x_1 \cdot x_2 \rceil \end{aligned}y1+y2≈⌊q(x1+x2)⌉⌊(y1⋅y2)/q⌉≈⌊q⋅x1⋅x2⌉
这样，同态加法为
c1+c2c_1+c_2c1+c2，同态乘法为⌊2/q⋅c1⊗c2⌉\lfloor 2/q \cdot c_1 \otimes c_2 \rceil⌊2/q⋅c1⊗c2⌉
有趣的是，此时的 Brakerski Scheme 的加解密算法与 Regev Scheme 完全一致。
Scale Invariant LHE / FHE
于是，我们可以实现 scale invariant L-homomorphic scheme: BGV 中的计算复杂的 “refresh” 过程，被更简单的 key switching 取代。
本方案中使用 BGV 的向量解压和密钥切换过程，
Brakerski Scheme 如下：
同态运算后，密文中携带的噪声为：
为了实现 L-homomorphic，需要噪声分布
χ\chiχ 的界BBB 满足：q/B≥(O(nlogq))L+O(1)q/B \ge (O(n \log q))^{L+O(1)}q/B≥(O(nlogq))L+O(1)
由于解密电路的深度为
O(logn+loglogq)O(\log n + \log \log q)O(logn+loglogq)，因此为了满足 Bootstrapping 的运算条件，需要q/B≥(nlogq)O(logn+loglogq)q/B \ge (n \log q)^{O(\log n + \log \log q)}q/B≥(nlogq)O(logn+loglogq)
从而实现出一个 fully homomorphic encryption scheme
Fan-Vercauteren Scheme
Relinearisation
此方案将上述的基于 LWE 的 Brakerski Scheme 移植到了 RLWE 上。
在 LPR 方案中，环
R=Z[x]/(f(x))R=\mathbb Z[x]/(f(x))R=Z[x]/(f(x))，一般选取f(x)=x2n+1f(x)=x^{2^n}+1f(x)=x2n+1 为分圆多项式。在 FV Scheme 中，做优化s,u←R2s,u \leftarrow R_2s,u←R2（不再取自χ\chiχ），其他的与 LPR 相同。
密文形如
c=(c0,c1)∈R2c=(c_0,\, c_1) \in R^2c=(c0,c1)∈R2，密钥形如s′=(1,s)∈R2s'=(1,s) \in R^2s′=(1,s)∈R2，那么解密过程可以视作是**一次函数的求值**：<c,s′>=c0+c1s=c(s)=Δ⋅m+v+q⋅r<c,s'> = c_0 + c_1 s = c(s) = \Delta \cdot m+v + q \cdot r<c,s′>=c0+c1s=c(s)=Δ⋅m+v+q⋅r
其中
r∈Rr \in Rr∈R，噪音大小为∥v∥≤2δRB2+B\|v\| \le 2 \delta_R B^2 + B∥v∥≤2δRB2+B，这里δR=max{∥a⋅b∥∥a∥⋅∥b∥:a,b∈R}\delta_R = max\{ \frac{\|a \cdot b\|}{\|a\| \cdot \|b\|}:\, a,b \in R\}δR=max{∥a∥⋅∥b∥∥a⋅b∥:a,b∈R}
是扩张因子（expansion factor of
RRR），其中的∥a∥=maxi∣ai∣\|a\|=\max_i |a_i|∥a∥=maxi∣ai∣ 是**无穷范数**。
同态加法就是多项式加法
ctadd=ct1+ct2ct_{add} = ct_1+ct_2ctadd=ct1+ct2，那么[(ct1+ct2)(s)]q=Δ⋅[m1+m2]t+v3[(ct_1+ct_2)(s)]_q = \Delta \cdot [m_1+m_2]_t + v_3[(ct1+ct2)(s)]q=Δ⋅[m1+m2]t+v3
这里噪声
∥v3∥\|v_3\|∥v3∥ 的增长是线性的。
同态乘法就是多项式乘法
cmult=t/q⋅ct1⋅ct2c_{mult} = t/q \cdot ct_1 \cdot ct_2cmult=t/q⋅ct1⋅ct2，那么[(t/q⋅ct1⋅ct2)(s)]q=Δ⋅[m1⋅m2]t+v3[(t/q \cdot ct_1 \cdot ct_2)(s)]_q = \Delta \cdot [m_1 \cdot m_2]_t + v_3[(t/q⋅ct1⋅ct2)(s)]q=Δ⋅[m1⋅m2]t+v3
这里噪声
∥v3∥\|v_3\|∥v3∥ 的增长因子粗略的是2⋅t⋅δR2⋅∥s∥2\cdot t\cdot \delta_R^2 \cdot \|s\|2⋅t⋅δR2⋅∥s∥
类似于 BV 方案的张量积让密文规模扩大，需要执行密钥切换过程，以降低其规模。在 FV 方案中的多项式乘积让密文的成为二次函数。我们需要执行重线性化（Relinearisation）过程，使得密文保持为一次多项式：令
ct=[c0,c1,c2]ct = [c_0, c_1, c_2]ct=[c0,c1,c2]，寻找ct′=[c0′,c1′]ct' = [c_0', c_1']ct′=[c0′,c1′]，使得[c0+c1⋅s+c2⋅s2]q=[c0′+c1′⋅s+r]q[c_0+c_1 \cdot s+c_2 \cdot s^2]_q = [c_0'+c_1' \cdot s+r]_q[c0+c1⋅s+c2⋅s2]q=[c0′+c1′⋅s+r]q
要保证噪声的无穷范数
∥r∥\|r\|∥r∥ 很小。可以设置**重线性化密钥**（*relinearisation key*）为：rlk=([−(a0⋅s+e0)+s2]q,a0)rlk = ([-(a_0 \cdot s+e_0)+s^2]_q,\, a_0)rlk=([−(a0⋅s+e0)+s2]q,a0)
其中
e0←χe_0 \leftarrow \chie0←χ，a0←Rqa_0 \leftarrow R_qa0←Rq。注意到rlk[0]+rlk[1]⋅s=s2+e0rlk[0]+rlk[1] \cdot s = s^2+e_0rlk[0]+rlk[1]⋅s=s2+e0，那么令ct′=(c0+rlk[0]⋅c2,c1+rlk[1]⋅c2)ct' = (c_0+rlk[0] \cdot c_2,\, c_1+rlk[1] \cdot c_2)ct′=(c0+rlk[0]⋅c2,c1+rlk[1]⋅c2)
得到
r=e0⋅c2∈Rr=e_0 \cdot c_2 \in Rr=e0⋅c2∈R，但是由于c2∈Rqc_2 \in R_qc2∈Rq，所以噪声rrr 过大。需要降低∥c2∥\|c_2\|∥c2∥ 或者∥r∥\|r\|∥r∥
方案一
将
c2c_2c2 做TTT**进制分解**，从而降低范数∥c2∥\|c_2\|∥c2∥，令c2=∑i=0l−1Ti⋅c2(i)c_2 = \sum_{i=0}^{l-1} T^i \cdot c_2^{(i)}c2=∑i=0l−1Ti⋅c2(i)，其中l=⌈logT(q)⌉l = \lceil\log_T(q) \rceill=⌈logT(q)⌉
对应的，设置重线性化密钥为：
rlk={([−(ai⋅s+ei)+Ti⋅s2]q,ai):i=0,1,⋯,l−1}rlk = \{ ([-(a_i \cdot s+e_i) + T^i \cdot s^2]_q,\, a_i):\, i =0,1,\cdots,l-1 \}rlk={([−(ai⋅s+ei)+Ti⋅s2]q,ai):i=0,1,⋯,l−1}
那么，新密文是
c0′=[c0+∑irlk[i][0]⋅c2(i)]q,c1′=[c1+∑irlk[i][1]⋅c2(i)]qc_0' = \left[ c_0 + \sum_i rlk[i][0] \cdot c_2^{(i)} \right]_q,\,\, c_1' = \left[ c_1 + \sum_i rlk[i][1] \cdot c_2^{(i)} \right]_qc0′=[c0+i∑rlk[i][0]⋅c2(i)]q,c1′=[c1+i∑rlk[i][1]⋅c2(i)]q
此时，
r=∑ic2(i)⋅eir = \sum_i c_2^{(i)} \cdot e_ir=∑ic2(i)⋅ei，baseTTT 越小，则范数∥r∥\|r\|∥r∥ 越小，但rlkrlkrlk 越大，计算速度也越慢。注意到重线性化所引入的噪声rrr 独立于密文噪声，为了保持良好的同态能力，应使得rrr 不大于做密文噪声太多。
Dynamic Relinearisation：选取一个尽可能小的
TTT 计算出rlkrlkrlk，如果多次乘法后密文的噪声增大，那么就可以从中提取出恰当的TkT^kTk 的rlkrlkrlk，来加速重线性化过程。
方案二
使用模切换，在一个大的模
p⋅qp \cdot qp⋅q 上运算，然后使用**除法**降低范数∥r∥\|r\|∥r∥，令重线性化密钥为：rlk=([−(a0⋅s+e0)+p⋅s2]p⋅q,a0)rlk = ([-(a_0 \cdot s+e_0) + p \cdot s^2]_{p \cdot q},\, a_0)rlk=([−(a0⋅s+e0)+p⋅s2]p⋅q,a0)
其中
a0←Rp⋅qa_0 \leftarrow R_{p \cdot q}a0←Rp⋅q，e←χ′e \leftarrow \chi'e←χ′，这里的分布χ′≠χ\chi' \neq \chiχ′=χ 是新分布。如果p⋅q=qk,k∈Rp \cdot q=q^k,\, k \in \mathbb Rp⋅q=qk,k∈R，∥χ∥<B\|\chi\|<B∥χ∥<B，那么需要∥χ′∥=Bk>α1−k⋅qk−k⋅Bk\|\chi'\| = B_k > \alpha^{1-\sqrt k} \cdot q^{k-\sqrt k} \cdot B^{\sqrt k}∥χ′∥=Bk>α1−k⋅qk−k⋅Bk，α≈3.758\alpha \approx 3.758α≈3.758 是常数，以保证安全性不损失。
那么，
c0′′=[⌊c2⋅rlk[0]p⌉]q,c1′′=[⌊c2⋅rlk[1]p⌉]qc_0'' = \left[ \left\lfloor \frac{c_2 \cdot rlk[0]}{p} \right\rceil \right]_q,\,\, c_1'' = \left[ \left\lfloor \frac{c_2 \cdot rlk[1]}{p} \right\rceil \right]_qc0′′=[⌊pc2⋅rlk[0]⌉]q,c1′′=[⌊pc2⋅rlk[1]⌉]q
容易验证
c0′′+c1′′⋅s=c2⋅s2+rc_0''+c_1'' \cdot s = c_2 \cdot s^2 + rc0′′+c1′′⋅s=c2⋅s2+r，那么新密文就是ct′=(c0+c0′′,c1+c1′′)ct' = (c_0+c_0'',\, c_1+c_1'')ct′=(c0+c0′′,c1+c1′′)，其中∥r∥<q⋅Bk⋅δRp+δR⋅∥s∥+12\|r\| < \dfrac{q \cdot B_k \cdot \delta_R}{p} + \dfrac{\delta_R \cdot \|s\| + 1}{2}∥r∥<pq⋅Bk⋅δR+2δR⋅∥s∥+1，整数ppp 越大，那么范数∥r∥\|r\|∥r∥ 越小，但计算速度越慢。
Dynamic Relinearisation：选取一个足够大的
ppp 计算出rlkrlkrlk，如果多次乘法后密文的噪声增大，那么可以从中提取出p′∣pp'|pp′∣p 的rlkrlkrlk，来加速重线性化过程。
SHE / FHE
我们可以实现基于 RLWE 的 somewhat homomorphic encryption scheme，
同态运算后，密文中携带的噪声为：
为了实现 L-homomorphic，需要噪声分布
χ\chiχ 的界BBB 满足：4⋅δRL⋅(δ+1.25)L+1⋅tL−1<⌊qB⌋4 \cdot \delta_R^L \cdot (\delta+1.25)^{L+1} \cdot t^{L-1} < \left\lfloor \frac{q}{B} \right\rfloor4⋅δRL⋅(δ+1.25)L+1⋅tL−1<⌊Bq⌋
为了实现 FHE，只需使得解密电路的深度小于
LLL 即可。环RqR_qRq 上的多项式运算的深度，计算挺麻烦的，没仔细看 \（￣︶￣）/
本文转载自: https://blog.csdn.net/weixin_44885334/article/details/127469513
版权归原作者 山登绝顶我为峰 3(^v^)3 所有， 如有侵权，请联系我们删除。
版权归原作者 山登绝顶我为峰 3(^v^)3 所有， 如有侵权，请联系我们删除。