参考文献:
- 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⌋文章来源:https://www.toymoban.com/news/detail-400990.html
为了实现 FHE,只需使得解密电路的深度小于 L L L 即可。环 R q R_q Rq 上的多项式运算的深度,计算挺麻烦的,没仔细看 \( ̄︶ ̄)/文章来源地址https://www.toymoban.com/news/detail-400990.html
到了这里,关于全同态加密:BFV的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!