参考文献：
- 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 中，明文空间是
Z
2
\mathbb Z_2
Z2，使用 most significant bit encoding。我们可以容易地修改它，使得密码方案基于 RLWE 问题，明文空间为
R
t
,
t
≥
2
R_t,\, t \ge 2
Rt,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
,
c
s,c
s,c 写成增广形式，那么有
<
c
,
s
>
=
q
/
2
⋅
m
+
e
+
q
I
<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
∈
Z
I \in \mathbb Z
I∈Z 是个整数，密文
c
c
c 的分量取值范围是
(
−
q
/
2
,
q
/
2
]
(-q/2,q/2]
(−q/2,q/2]
考虑分数密文（fractional ciphertext）
c
’
=
c
/
q
c’ = c/q
c’=c/q，那么
<
c
′
,
s
>
=
1
2
⋅
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]
同态加法
c
a
d
d
=
c
1
+
c
2
c_{add} = c_1+c_2
cadd=c1+c2，有：
<
c
1
+
c
2
,
s
>
=
<
c
1
,
s
>
+
<
c
2
,
s
>
=
1
2
m
+
(
e
1
+
e
2
)
m
o
d
1
\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
同态乘法
c
m
u
l
t
=
2
⋅
c
1
⊗
c
2
c_{mult} = 2 \cdot c_1 \otimes c_2
cmult=2⋅c1⊗c2，有：
<
2
⋅
c
1
⊗
c
2
,
s
⊗
s
>
=
2
⋅
<
c
1
,
s
>
⋅
<
c
2
,
s
>
=
1
2
m
1
m
2
+
2
(
e
1
I
2
+
e
2
I
1
)
+
e
1
m
2
+
e
2
m
1
+
2
e
1
e
2
m
o
d
1
\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
其中
∣
I
1
∣
,
∣
I
2
∣
|I_1|,|I_2|
∣I1∣,∣I2∣ 的界约为
∥
s
∥
1
\|s\|_1
∥s∥1，所以
c
m
u
l
t
c_{mult}
cmult 中的噪声的界为
O
(
∥
s
∥
1
)
⋅
ϵ
O(\|s\|_1) \cdot \epsilon
O(∥s∥1)⋅ϵ。由于 Regev Scheme 中的私钥取自均匀分布，因此
∥
s
∥
1
≈
n
q
\|s\|_1 \approx nq
∥s∥1≈nq，模数
q
q
q 是安全参数
n
n
n 的指数级。而其他噪声
e
1
m
2
+
e
2
m
1
≤
2
t
ϵ
e_1m_2+e_2m_1 \le 2t \epsilon
e1m2+e2m1≤2tϵ，
2
e
1
e
2
≤
2
ϵ
2
2e_1e_2 \le 2\epsilon^2
2e1e2≤2ϵ2 的占比很小。因此，主要噪声就是
2
(
e
1
I
2
+
e
2
I
1
)
2(e_1I_2 + e_2I_1)
2(e1I2+e2I1)
为了减小噪声，需要要减小私钥的
l
1
l_1
l1 范数。我们可以对解密电路做**二进制分解**（*binary decomposition*），令
s
=
∑
j
2
j
s
(
j
)
s = \sum_j 2^j s^{(j)}
s=∑j2js(j)，其中
s
(
j
)
s^{(j)}
s(j) 的各个元素是
s
s
s 的各个元素的第
j
j
j 比特。那么，解密电路化为：
<
c
,
s
>
=
∑
j
2
j
<
c
,
s
(
j
)
>
=
<
(
c
,
2
c
,
⋯
)
,
(
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),⋯)>
那么，我们就将
s
s
s 下的密文
c
c
c，转化为了
(
s
(
0
)
,
s
(
1
)
,
⋯
)
(s^{(0)},\, s^{(1)},\, \cdots)
(s(0),s(1),⋯) 下的密文
(
c
,
2
c
,
⋯
)
(c,\, 2c,\, \cdots)
(c,2c,⋯)
二进制私钥的
l
1
l_1
l1 范数至多是其维度，即
O
(
n
⋅
log
q
)
=
O
(
p
o
l
y
(
n
)
)
O(n \cdot \log q) = O(poly(n))
O(n⋅logq)=O(poly(n))，因此**噪声增长是多项式级别的**。也就是说，我们不必使用 BGV 中的模切换技术了！
在代码实现时，由于浮点数精度问题，我们将密文放大
q
q
q 倍。实质上是用
Z
q
\mathbb Z_q
Zq 上的整数运算，来模拟
R
/
Z
R/\mathbb Z
R/Z 上的浮点数运算：令
y
i
=
⌊
q
x
i
⌉
y_i = \lfloor qx_i \rceil
yi=⌊qxi⌉，那么
y
1
+
y
2
≈
⌊
q
(
x
1
+
x
2
)
⌉
⌊
(
y
1
⋅
y
2
)
/
q
⌉
≈
⌊
q
⋅
x
1
⋅
x
2
⌉
\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⌉
这样，同态加法为
c
1
+
c
2
c_1+c_2
c1+c2，同态乘法为
⌊
2
/
q
⋅
c
1
⊗
c
2
⌉
\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
χ 的界
B
B
B 满足：
q
/
B
≥
(
O
(
n
log
q
)
)
L
+
O
(
1
)
q/B \ge (O(n \log q))^{L+O(1)}
q/B≥(O(nlogq))L+O(1)
由于解密电路的深度为
O
(
log
n
+
log
log
q
)
O(\log n + \log \log q)
O(logn+loglogq)，因此为了满足 Bootstrapping 的运算条件，需要
q
/
B
≥
(
n
log
q
)
O
(
log
n
+
log
log
q
)
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
)
=
x
2
n
+
1
f(x)=x^{2^n}+1
f(x)=x2n+1 为分圆多项式。在 FV Scheme 中，做优化
s
,
u
←
R
2
s,u \leftarrow R_2
s,u←R2（不再取自
χ
\chi
χ），其他的与 LPR 相同。
密文形如
c
=
(
c
0
,
c
1
)
∈
R
2
c=(c_0,\, c_1) \in R^2
c=(c0,c1)∈R2，密钥形如
s
′
=
(
1
,
s
)
∈
R
2
s'=(1,s) \in R^2
s′=(1,s)∈R2，那么解密过程可以视作是**一次函数的求值**：
<
c
,
s
′
>
=
c
0
+
c
1
s
=
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
∈
R
r \in R
r∈R，噪音大小为
∥
v
∥
≤
2
δ
R
B
2
+
B
\|v\| \le 2 \delta_R B^2 + B
∥v∥≤2δRB2+B，这里
δ
R
=
m
a
x
{
∥
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
R
R
R），其中的
∥
a
∥
=
max
i
∣
a
i
∣
\|a\|=\max_i |a_i|
∥a∥=maxi∣ai∣ 是**无穷范数**。
同态加法就是多项式加法
c
t
a
d
d
=
c
t
1
+
c
t
2
ct_{add} = ct_1+ct_2
ctadd=ct1+ct2，那么
[
(
c
t
1
+
c
t
2
)
(
s
)
]
q
=
Δ
⋅
[
m
1
+
m
2
]
t
+
v
3
[(ct_1+ct_2)(s)]_q = \Delta \cdot [m_1+m_2]_t + v_3
[(ct1+ct2)(s)]q=Δ⋅[m1+m2]t+v3
这里噪声
∥
v
3
∥
\|v_3\|
∥v3∥ 的增长是线性的。
同态乘法就是多项式乘法
c
m
u
l
t
=
t
/
q
⋅
c
t
1
⋅
c
t
2
c_{mult} = t/q \cdot ct_1 \cdot ct_2
cmult=t/q⋅ct1⋅ct2，那么
[
(
t
/
q
⋅
c
t
1
⋅
c
t
2
)
(
s
)
]
q
=
Δ
⋅
[
m
1
⋅
m
2
]
t
+
v
3
[(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
这里噪声
∥
v
3
∥
\|v_3\|
∥v3∥ 的增长因子粗略的是
2
⋅
t
⋅
δ
R
2
⋅
∥
s
∥
2\cdot t\cdot \delta_R^2 \cdot \|s\|
2⋅t⋅δR2⋅∥s∥
类似于 BV 方案的张量积让密文规模扩大，需要执行密钥切换过程，以降低其规模。在 FV 方案中的多项式乘积让密文的成为二次函数。我们需要执行重线性化（Relinearisation）过程，使得密文保持为一次多项式：令
c
t
=
[
c
0
,
c
1
,
c
2
]
ct = [c_0, c_1, c_2]
ct=[c0,c1,c2]，寻找
c
t
′
=
[
c
0
′
,
c
1
′
]
ct' = [c_0', c_1']
ct′=[c0′,c1′]，使得
[
c
0
+
c
1
⋅
s
+
c
2
⋅
s
2
]
q
=
[
c
0
′
+
c
1
′
⋅
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*）为：
r
l
k
=
(
[
−
(
a
0
⋅
s
+
e
0
)
+
s
2
]
q
,
a
0
)
rlk = ([-(a_0 \cdot s+e_0)+s^2]_q,\, a_0)
rlk=([−(a0⋅s+e0)+s2]q,a0)
其中
e
0
←
χ
e_0 \leftarrow \chi
e0←χ，
a
0
←
R
q
a_0 \leftarrow R_q
a0←Rq。注意到
r
l
k
[
0
]
+
r
l
k
[
1
]
⋅
s
=
s
2
+
e
0
rlk[0]+rlk[1] \cdot s = s^2+e_0
rlk[0]+rlk[1]⋅s=s2+e0，那么令
c
t
′
=
(
c
0
+
r
l
k
[
0
]
⋅
c
2
,
c
1
+
r
l
k
[
1
]
⋅
c
2
)
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
=
e
0
⋅
c
2
∈
R
r=e_0 \cdot c_2 \in R
r=e0⋅c2∈R，但是由于
c
2
∈
R
q
c_2 \in R_q
c2∈Rq，所以噪声
r
r
r 过大。需要降低
∥
c
2
∥
\|c_2\|
∥c2∥ 或者
∥
r
∥
\|r\|
∥r∥
方案一
将
c
2
c_2
c2 做
T
T
T**进制分解**，从而降低范数
∥
c
2
∥
\|c_2\|
∥c2∥，令
c
2
=
∑
i
=
0
l
−
1
T
i
⋅
c
2
(
i
)
c_2 = \sum_{i=0}^{l-1} T^i \cdot c_2^{(i)}
c2=∑i=0l−1Ti⋅c2(i)，其中
l
=
⌈
log
T
(
q
)
⌉
l = \lceil\log_T(q) \rceil
l=⌈logT(q)⌉
对应的，设置重线性化密钥为：
r
l
k
=
{
(
[
−
(
a
i
⋅
s
+
e
i
)
+
T
i
⋅
s
2
]
q
,
a
i
)
:
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}
那么，新密文是
c
0
′
=
[
c
0
+
∑
i
r
l
k
[
i
]
[
0
]
⋅
c
2
(
i
)
]
q
,
c
1
′
=
[
c
1
+
∑
i
r
l
k
[
i
]
[
1
]
⋅
c
2
(
i
)
]
q
c_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]_q
c0′=[c0+i∑rlk[i][0]⋅c2(i)]q,c1′=[c1+i∑rlk[i][1]⋅c2(i)]q
此时，
r
=
∑
i
c
2
(
i
)
⋅
e
i
r = \sum_i c_2^{(i)} \cdot e_i
r=∑ic2(i)⋅ei，base
T
T
T 越小，则范数
∥
r
∥
\|r\|
∥r∥ 越小，但
r
l
k
rlk
rlk 越大，计算速度也越慢。注意到重线性化所引入的噪声
r
r
r 独立于密文噪声，为了保持良好的同态能力，应使得
r
r
r 不大于做密文噪声太多。
Dynamic Relinearisation：选取一个尽可能小的
T
T
T 计算出
r
l
k
rlk
rlk，如果多次乘法后密文的噪声增大，那么就可以从中提取出恰当的
T
k
T^k
Tk 的
r
l
k
rlk
rlk，来加速重线性化过程。
方案二
使用模切换，在一个大的模
p
⋅
q
p \cdot q
p⋅q 上运算，然后使用**除法**降低范数
∥
r
∥
\|r\|
∥r∥，令重线性化密钥为：
r
l
k
=
(
[
−
(
a
0
⋅
s
+
e
0
)
+
p
⋅
s
2
]
p
⋅
q
,
a
0
)
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)
其中
a
0
←
R
p
⋅
q
a_0 \leftarrow R_{p \cdot q}
a0←Rp⋅q，
e
←
χ
′
e \leftarrow \chi'
e←χ′，这里的分布
χ
′
≠
χ
\chi' \neq \chi
χ′=χ 是新分布。如果
p
⋅
q
=
q
k
,
k
∈
R
p \cdot q=q^k,\, k \in \mathbb R
p⋅q=qk,k∈R，
∥
χ
∥
<
B
\|\chi\|<B
∥χ∥<B，那么需要
∥
χ
′
∥
=
B
k
>
α
1
−
k
⋅
q
k
−
k
⋅
B
k
\|\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 是常数，以保证安全性不损失。
那么，
c
0
′
′
=
[
⌊
c
2
⋅
r
l
k
[
0
]
p
⌉
]
q
,
c
1
′
′
=
[
⌊
c
2
⋅
r
l
k
[
1
]
p
⌉
]
q
c_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]_q
c0′′=[⌊pc2⋅rlk[0]⌉]q,c1′′=[⌊pc2⋅rlk[1]⌉]q
容易验证
c
0
′
′
+
c
1
′
′
⋅
s
=
c
2
⋅
s
2
+
r
c_0''+c_1'' \cdot s = c_2 \cdot s^2 + r
c0′′+c1′′⋅s=c2⋅s2+r，那么新密文就是
c
t
′
=
(
c
0
+
c
0
′
′
,
c
1
+
c
1
′
′
)
ct' = (c_0+c_0'',\, c_1+c_1'')
ct′=(c0+c0′′,c1+c1′′)，其中
∥
r
∥
<
q
⋅
B
k
⋅
δ
R
p
+
δ
R
⋅
∥
s
∥
+
1
2
\|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，整数
p
p
p 越大，那么范数
∥
r
∥
\|r\|
∥r∥ 越小，但计算速度越慢。
Dynamic Relinearisation：选取一个足够大的
p
p
p 计算出
r
l
k
rlk
rlk，如果多次乘法后密文的噪声增大，那么可以从中提取出
p
′
∣
p
p'|p
p′∣p 的
r
l
k
rlk
rlk，来加速重线性化过程。
SHE / FHE
我们可以实现基于 RLWE 的 somewhat homomorphic encryption scheme，
同态运算后，密文中携带的噪声为：
为了实现 L-homomorphic，需要噪声分布
χ
\chi
χ 的界
B
B
B 满足：
4
⋅
δ
R
L
⋅
(
δ
+
1.25
)
L
+
1
⋅
t
L
−
1
<
⌊
q
B
⌋
4 \cdot \delta_R^L \cdot (\delta+1.25)^{L+1} \cdot t^{L-1} < \left\lfloor \frac{q}{B} \right\rfloor
4⋅δRL⋅(δ+1.25)L+1⋅tL−1<⌊Bq⌋
为了实现 FHE，只需使得解密电路的深度小于
L
L
L 即可。环
R
q
R_q
Rq 上的多项式运算的深度，计算挺麻烦的，没仔细看 \（￣︶￣）/
本文转载自: https://blog.csdn.net/weixin_44885334/article/details/127469513
版权归原作者 山登绝顶我为峰 3(^v^)3 所有， 如有侵权，请联系我们删除。
版权归原作者 山登绝顶我为峰 3(^v^)3 所有， 如有侵权，请联系我们删除。