参考文献:
- Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2012: 700-718.
- Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013: 75-92.
Gadget
2012年 Micciancio 和 Peikert 介绍了一种不是格基的陷门。首先构造了一类特殊的格族(family of lattices)Primitive Lattices,它们拥有快速、可并行的解码算法。令 primitive matrix G ∈ Z q n × w G \in \mathbb Z_q^{n \times w} G∈Zqn×w,它满足 G ⋅ Z w = Z q n G \cdot \mathbb Z^w = \mathbb Z_q^n G⋅Zw=Zqn,其中 k = ⌈ log 2 q ⌉ k=\lceil \log_2 q \rceil k=⌈log2q⌉, w = n k w=nk w=nk,
-
在格 Λ ⊥ ( G ) \Lambda^\perp(G) Λ⊥(G) 上,有一个已知的短格基 S ∈ Z w × w S \in \mathbb Z^{w \times w} S∈Zw×w,满足 ∥ S ~ ∥ ≤ 5 \|\tilde S\| \le \sqrt 5 ∥S~∥≤5, ∥ S ∥ ≤ max { 5 , k } \|S\| \le \max\{\sqrt 5,\sqrt k\} ∥S∥≤max{5,k}。如果 q = 2 k q=2^k q=2k,那么 S ~ = 2 I \tilde S = 2I S~=2I,从而 ∥ S ~ ∥ = 2 \|\tilde S\| = 2 ∥S~∥=2 以及 ∥ S ∥ = 5 \|S\| = \sqrt 5 ∥S∥=5。
-
函数
f G ( x ) : = G x ( m o d q ) f_G(x) := Gx \pmod{q} fG(x):=Gx(modq)的原像采样(preimage sampling)算法,只需要 O ( n ⋅ log c n ) O(n \cdot \log^c{n}) O(n⋅logcn) 的时间
-
函数
g G ( s , e ) : = s t G + e t ( m o d q ) g_G(s,e) := s^tG + e^t \pmod{q} gG(s,e):=stG+et(modq)的陷门求逆(trapdoor inversion)算法,只需要 O ( n ⋅ log c n ) O(n \cdot \log^c{n}) O(n⋅logcn) 的时间。
-
并且,这两个算法都可以 n n n 路并行,进一步降低为 O ( log c n ) O(\log^c{n}) O(logcn) 的时间。如果 q = 2 k q=2^k q=2k,那么这 O ( log c n ) O(\log^c n) O(logcn) 的运算就仅仅是 k k k 比特整数的加法和位移。
如果令 A ′ = [ A ‾ ∣ G ] A'=\left[\overline A \mid G\right] A′=[A∣G], T = [ I − R 0 I ] T = \begin{bmatrix}I&-R\\0&I\end{bmatrix} T=[I0−RI],设置 A = A ′ ⋅ T = [ A ‾ ∣ G − A ‾ R ] A = A' \cdot T = \left[\overline A \mid G-\overline A R\right] A=A′⋅T=[A∣G−AR],那么
- 易知 T − 1 = [ I R 0 I ] T^{-1} = \begin{bmatrix}I&R\\0&I\end{bmatrix} T−1=[I0RI],因此 A A A 和 A ′ A' A′ 之间的双向转换是容易的,花费是与 R R R 的矩阵乘。
- 函数 f A ( x ) : = A x ( m o d q ) f_A(x) := Ax \pmod{q} fA(x):=Ax(modq) 和 g A ( s , e ) : = s t A + e t ( m o d q ) g_A(s,e) := s^tA+e^t \pmod{q} gA(s,e):=stA+et(modq) 都可以归约到 f G f_G fG 和 g G g_G gG 上,归约的花费仅仅是与 R R R 的矩阵向量乘积。
博主只粗略浏览了论文的前两节(已在格密码综述里看过),旧内容见 格密码:陷门OWF(Short Basis、Gadget)。
GSW
2013年 Gentry, Sahai, Waters 三位大牛提出了一种不需要 evaluation key 的全同态加密方案,拉开了第三代全同态加密的帷幕。
Approximate Eigenvector
之前的 FHE 方案(BGV-type、FV-type)的乘法同态运算都“不自然”,需要密文的张量积、多项式乘积。那么,是否可以设计一种密码算法,它的同态运算就直接是环上的加法和乘法呢?GSW 提出了近似特征向量技术,将明文整数作为密文矩阵的特征值,而私钥是特征向量。
GSW 基于 LWE 问题,它在平均情况下的困难程度,至少是最坏情况下的一些格问题的困难程度。
整数环 Z q \mathbb Z_q Zq,明文 μ ∈ Z q \mu \in \mathbb Z_q μ∈Zq 是 “small integer”,密文 C ∈ Z q N × N C \in \mathbb Z_q^{N \times N} C∈ZqN×N 是 “small entries” 的方阵,私钥 v ∈ Z q N v \in \mathbb Z_q^N v∈ZqN 是至少有一个 “big coefficient” 的向量。
我们说
C
C
C 加密了
μ
\mu
μ,如果:
C
⋅
v
=
μ
⋅
v
+
e
C \cdot v = \mu \cdot v + e
C⋅v=μ⋅v+e
其中
e
e
e 是 “small error” 的向量。令
v
i
v_i
vi 是
v
v
v 中足够大的一项,令
C
i
C_i
Ci 是第
i
i
i 行向量(因为
C
i
⋅
v
=
μ
⋅
v
i
+
e
i
C_i \cdot v = \mu \cdot v_i + e_i
Ci⋅v=μ⋅vi+ei 包含的整数
μ
\mu
μ 精度最高, 仅当
∣
e
i
/
v
i
∣
>
0.5
|e_i/v_i|>0.5
∣ei/vi∣>0.5 时才会出错),那么:
μ
=
⌊
⟨
C
i
,
v
⟩
v
i
⌉
\mu = \left\lfloor \frac{\langle C_i,v \rangle}{v_i} \right\rceil
μ=⌊vi⟨Ci,v⟩⌉
假设 μ 1 \mu_1 μ1 的密文是 C 1 C_1 C1, μ 2 \mu_2 μ2 的密文是 C 2 C_2 C2,那么有
-
同态加法就是环加法: C + = C 1 + C 2 C^+ = C_1+C_2 C+=C1+C2,
C + ⋅ v = C 1 ⋅ v + C 2 ⋅ v = ( μ 1 + μ 2 ) ⋅ v + ( e 1 + e 2 ) \begin{aligned} C^+ \cdot v &= C_1 \cdot v + C_2 \cdot v \\ &= (\mu_1+\mu_2) \cdot v + (e_1+e_2)\\ \end{aligned} C+⋅v=C1⋅v+C2⋅v=(μ1+μ2)⋅v+(e1+e2) -
同态乘法就是环乘法: C × = C 1 ⋅ C 2 C^\times = C_1 \cdot C_2 C×=C1⋅C2,
C × ⋅ v = C 1 ⋅ ( C 2 ⋅ v ) = C 1 ⋅ ( μ 2 ⋅ v + e 2 ) = μ 2 ⋅ ( C 1 ⋅ v ) + C 1 ⋅ e 2 = ( μ 1 ⋅ μ 2 ) ⋅ v + ( C 1 ⋅ e 2 + μ 2 ⋅ e 1 ) \begin{aligned} C^\times \cdot v &= C_1 \cdot (C_2 \cdot v)\\ &= C_1 \cdot (\mu_2 \cdot v + e_2)\\ &= \mu_2 \cdot (C_1 \cdot v) + C_1 \cdot e_2\\ &= (\mu_1 \cdot \mu_2) \cdot v + (C_1 \cdot e_2 + \mu_2 \cdot e_1)\\ \end{aligned} C×⋅v=C1⋅(C2⋅v)=C1⋅(μ2⋅v+e2)=μ2⋅(C1⋅v)+C1⋅e2=(μ1⋅μ2)⋅v+(C1⋅e2+μ2⋅e1)
因此 GSW 的同态运算,就简单是矩阵加法和矩阵乘法,这是 “natural” 运算。
对于矩阵乘来说,在 Strassen 算法下的复杂度为 n 2.807 n^{2.807} n2.807,在 Schonhage 的 Laser Method 下的复杂度目前为 O ( n 2.3727 ) O(n^{2.3727}) O(n2.3727)(Williams 2012)。不过,似乎只有 Strassen 算法是实用的,任何渐进复杂度更低的矩阵乘算法都只适合 n n n 特别大的(现代计算机无法承受的地步)矩阵。而且这些算法由于浮点数精度问题,超大矩阵的计算误差也是大问题。还是分块、并行的 GEMM 更具实用性。
Flattening
我们说密文 C C C 是 B B B - bounded,如果 μ i \mu_i μi 和 C i C_i Ci, e i e_i ei 的数量级都至多是 B B B。
若 C 1 , C 2 C_1,C_2 C1,C2 是 B B B - bounded,那么
- C + C^+ C+ 是 2 B 2B 2B - bounded,深度为 L L L 的加法电路,得到的密文的噪音大小为 2 L B 2^L B 2LB
- C × C^\times C× 是 ( N + 1 ) B 2 (N+1)B^2 (N+1)B2 - bounded,深度为 L L L 的乘法电路,得到的密文的噪音大小为 ( N + 1 ) 2 L − 1 B 2 L (N+1)^{2^L-1} B^{2^L} (N+1)2L−1B2L
由于 q / B q/B q/B 至多是关于 N N N 的亚指数的(安全性),因此上述同态运算只能支持对数深度(log-depth)的电路。那么怎么才能限制噪声的增长呢?
我们说密文 C C C 是 B B B - strongly - bounded,如果 μ \mu μ 和 C C C 的数量级都至多是 1 1 1, e e e 的数量级至多是 B B B。
假如 C 1 , C 2 C_1,C_2 C1,C2 是 B B B - strongly - bounded,那么 C × C^\times C× 将是 ( N + 1 ) B (N+1)B (N+1)B - bounded,但 C × C^\times C× 的系数的数量级将成为 N N N。要是可以使得 C × C^\times C× 成为 ( N + 1 ) B (N+1)B (N+1)B - strongly - bounded,那么深度为 L L L 的乘法电路后的噪声大小为 ( N + 1 ) L B (N+1)^L B (N+1)LB,于是 q / B q/B q/B 就可以支持多项式深度(poly-depth)的电路了!
与 BGV 和 BFV 一样,GSW 也使用二进制分解(或者说 Gadget 矩阵 G G G)来约束噪声的增长:
-
B i t D e c o m p ( a ) BitDecomp(a) BitDecomp(a):输入 a = ( a 1 , ⋯ , a k ) ∈ Z q k a=(a_1,\cdots,a_k) \in \mathbb Z_q^k a=(a1,⋯,ak)∈Zqk,令 l = ⌊ log 2 q ⌋ + 1 l = \lfloor \log_2 q \rfloor+1 l=⌊log2q⌋+1, N = k ⋅ l N = k \cdot l N=k⋅l,设 a i = a i , 0 a i , 1 ⋯ a i , l − 1 a_i = a_{i,0}a_{i,1}\cdots a_{i,l-1} ai=ai,0ai,1⋯ai,l−1 是二进制分解,输出
a ′ = G − 1 ( a ) = ( a 1 , 0 , ⋯ , a 1 , l − 1 , ⋯ , a k , 0 , ⋯ , a k , l − 1 ) ∈ { 0 , 1 } N a' = G^{-1}(a) =(a_{1,0},\cdots,a_{1,l-1},\cdots,a_{k,0},\cdots,a_{k,l-1}) \in \{0,1\}^{N} a′=G−1(a)=(a1,0,⋯,a1,l−1,⋯,ak,0,⋯,ak,l−1)∈{0,1}N -
B i t D e c o m p − 1 ( a ′ ) BitDecomp^{-1}(a') BitDecomp−1(a′):输入 a ′ ∈ Z q N a' \in \mathbb Z_q^N a′∈ZqN(不必是 { 0 , 1 } N \{0,1\}^N {0,1}N),设 a i = ∑ j = 0 l − 1 2 j a i , j a_i = \sum_{j=0}^{l-1} 2^j a_{i,j} ai=∑j=0l−12jai,j 是二进制合成,输出
a = G ⋅ a ′ = ( a 1 , a 2 , ⋯ , a k ) ∈ Z q k a = G \cdot a' = (a_1,a_2,\cdots,a_k) \in \mathbb Z_q^k a=G⋅a′=(a1,a2,⋯,ak)∈Zqk -
F l a t t e n ( a ′ ) Flatten(a') Flatten(a′):输入 a ′ ∈ Z q N a' \in \mathbb Z_q^N a′∈ZqN(不必是 { 0 , 1 } N \{0,1\}^N {0,1}N),输出
B i t D e c o m p ( B i t D e c o m p − 1 ( a ′ ) ) ∈ { 0 , 1 } N BitDecomp(BitDecomp^{-1}(a')) \in \{0,1\}^N BitDecomp(BitDecomp−1(a′))∈{0,1}N -
F l a t t e n ( A ) Flatten(A) Flatten(A):输入 A ∈ Z q N × N A \in \mathbb Z_q^{N \times N} A∈ZqN×N,设 A i A_i Ai 是行向量,输出
( F l a t t e n ( A 1 ) , ⋯ , F l a t t e n ( A N ) ) T \left(Flatten(A_1),\cdots,Flatten(A_N)\right)^T (Flatten(A1),⋯,Flatten(AN))T -
P o w e r s o f 2 ( b ) Powersof2(b) Powersof2(b):输入 b = ( b 1 , ⋯ , b k ) ∈ Z q k b=(b_1,\cdots,b_k) \in \mathbb Z_q^k b=(b1,⋯,bk)∈Zqk,输出
b ′ = G t ⋅ b = ( b 1 , 2 b 1 , ⋯ , 2 l − 1 b 1 , ⋯ , b k , 2 b k , ⋯ , 2 l − 1 b k ) ∈ Z q N b' = G^t \cdot b = (b_1,2b_1,\cdots,2^{l-1}b_1,\cdots,b_k,2b_k,\cdots,2^{l-1}b_k) \in \mathbb Z_q^N b′=Gt⋅b=(b1,2b1,⋯,2l−1b1,⋯,bk,2bk,⋯,2l−1bk)∈ZqN
可以验证如下事实:
-
对于 a , b ∈ Z q k a,b \in \mathbb Z_q^k a,b∈Zqk,有
⟨ B i t D e c o m p ( a ) , P o w e r s o f 2 ( b ) ⟩ = b t ⋅ G ⋅ G − 1 ( a ) = ⟨ a , b ⟩ \lang BitDecomp(a),Powersof2(b)\rang = b^t \cdot G \cdot G^{-1}(a) = \lang a,b\rang ⟨BitDecomp(a),Powersof2(b)⟩=bt⋅G⋅G−1(a)=⟨a,b⟩ -
对于 a ′ ∈ Z q N a' \in \mathbb Z_q^N a′∈ZqN 和 b ∈ Z q k b \in \mathbb Z_q^k b∈Zqk,有
⟨ a ′ , P o w e r s o f 2 ( b ) ⟩ = b t ⋅ G ⋅ a ′ = ⟨ B i t D e c o m p − 1 ( a ′ ) , b ⟩ \lang a',Powersof2(b) \rang = b^t \cdot G \cdot a' = \lang BitDecomp^{-1}(a'),b \rang ⟨a′,Powersof2(b)⟩=bt⋅G⋅a′=⟨BitDecomp−1(a′),b⟩ -
明显, ⟨ a ′ , P o w e r s o f 2 ( b ) ⟩ = ⟨ F l a t t e n ( a ′ ) , P o w e r s o f 2 ( b ) ⟩ \lang a',Powersof2(b) \rang = \lang Flatten(a'),Powersof2(b) \rang ⟨a′,Powersof2(b)⟩=⟨Flatten(a′),Powersof2(b)⟩
采用增广形式的 LWE 样本。对于随机矩阵 A ∈ Z q m × ( n + 1 ) A \in \mathbb Z_q^{m \times (n+1)} A∈Zqm×(n+1),设秘密向量为 s ∈ Z q n + 1 s \in \mathbb Z_q^{n+1} s∈Zqn+1,满足 A ⋅ s = e A \cdot s=e A⋅s=e 是 B B B - bounded 噪声,令 v = P o w e r s o f ( s ) v = Powersof(s) v=Powersof(s),那么 v v v 确实至少有一个 “big coefficient”,并且 v v v 的随机性等同于 s s s 的随机性。
令
l
=
⌊
log
2
q
⌋
+
1
l = \lfloor \log_2 q \rfloor+1
l=⌊log2q⌋+1,
N
=
(
n
+
1
)
⋅
l
N = (n+1) \cdot l
N=(n+1)⋅l,容易看出
C
⋅
v
=
F
l
a
t
t
e
n
(
C
)
⋅
v
C \cdot v = Flatten(C) \cdot v
C⋅v=Flatten(C)⋅v
也就是说,把密文 ”拍平“ 并不会改变明文。
对于明文
μ
∈
Z
q
\mu \in \mathbb Z_q
μ∈Zq,随机选取
R
∈
{
0
,
1
}
N
×
m
R \in \{0,1\}^{N \times m}
R∈{0,1}N×m,“拍平” 的密文为:
C
=
F
l
a
t
t
e
n
(
μ
⋅
I
N
+
B
i
t
D
e
c
o
m
p
(
R
⋅
A
)
)
∈
Z
q
N
×
N
C = Flatten(\mu \cdot I_N + BitDecomp(R \cdot A)) \in \mathbb Z_q^{N \times N}
C=Flatten(μ⋅IN+BitDecomp(R⋅A))∈ZqN×N
容易验证 C ⋅ v = ( μ ⋅ I N + B i t D e c o m p ( R ⋅ A ) ) ⋅ v = μ ⋅ v + R ⋅ A ⋅ s C \cdot v = (\mu \cdot I_N + BitDecomp(R \cdot A)) \cdot v = \mu \cdot v + R \cdot A\cdot s C⋅v=(μ⋅IN+BitDecomp(R⋅A))⋅v=μ⋅v+R⋅A⋅s,包含的噪音 R ⋅ e R \cdot e R⋅e 很小。
如果 m = O ( n log q ) m = O(n \log q) m=O(nlogq),那么根据剩余哈希引理(leftover hash lemma) R ⋅ A R \cdot A R⋅A 是统计均匀的(statistically uniform)。因此 B i t D e c o m p − 1 ( C ) = B i t D e c o m p − 1 ( μ ⋅ I N ) + R ⋅ A BitDecomp^{-1}(C) = BitDecomp^{-1}(\mu \cdot I_N) + R \cdot A BitDecomp−1(C)=BitDecomp−1(μ⋅IN)+R⋅A 也是统计均匀的矩阵。
LHE
GSW 的方案如下:
同态运算为:
- 加法: A d d ( C 1 , C 2 ) = F l a t t e n ( C 1 + C 2 ) Add(C_1,C_2) = Flatten(C_1+C_2) Add(C1,C2)=Flatten(C1+C2),噪音为 e 1 + e 2 e_1+e_2 e1+e2,增长因子为 2 2 2
- 乘法: M u l t ( C 1 , C 2 ) = F l a t t e n ( C 1 ⋅ C 2 ) Mult(C_1,C_2) = Flatten(C_1 \cdot C_2) Mult(C1,C2)=Flatten(C1⋅C2),噪音为 μ 2 ⋅ e 1 + C 1 ⋅ e 2 \mu_2 \cdot e_1 + C_1 \cdot e_2 μ2⋅e1+C1⋅e2,增长因子为 μ 2 + N \mu_2+N μ2+N
- 乘常数: M u l t C o n s t ( C , α ) = F l a t t e n ( F l a t t e n ( α ⋅ I N ) ⋅ C ) MultConst(C,\alpha) = Flatten\left(Flatten(\alpha \cdot I_N) \cdot C\right) MultConst(C,α)=Flatten(Flatten(α⋅IN)⋅C),噪音为 F l a t t e n ( α ⋅ I N ) ⋅ e Flatten(\alpha \cdot I_N) \cdot e Flatten(α⋅IN)⋅e,增长因子为 N N N 而非 α \alpha α
- 与非门: N A N D ( C 1 , C 2 ) = F l a t t e n ( I N − C 1 ⋅ C 2 ) NAND(C_1,C_2) = Flatten(I_N - C_1 \cdot C_2) NAND(C1,C2)=Flatten(IN−C1⋅C2),噪音为 − μ 2 ⋅ e 1 − C 1 ⋅ e 2 -\mu_2 \cdot e_1 - C_1 \cdot e_2 −μ2⋅e1−C1⋅e2,由于 u 2 ∈ { 0 , 1 } u_2 \in \{0,1\} u2∈{0,1},增长因子为 N + 1 N+1 N+1
在解密时 x i = C i ⋅ v = μ ⋅ v i + R i ⋅ e x_i = C_i \cdot v = \mu \cdot v_i + R_i \cdot e xi=Ci⋅v=μ⋅vi+Ri⋅e, 令错误为 e ′ = R i ⋅ e e' = R_i \cdot e e′=Ri⋅e,那么 ∣ e ′ ∣ |e'| ∣e′∣ 的数量级为 ∥ e ∥ 1 \|e\|_1 ∥e∥1,仅当 ∣ e ′ / v i ∣ < 0.5 |e'/v_i| < 0.5 ∣e′/vi∣<0.5 时才不会出错。因为 v i ∈ ( q / 4 , q / 2 ] v_i \in (q/4,q/2] vi∈(q/4,q/2],所以只要 e ′ < q / 8 e' < q/8 e′<q/8,那么解密就是正确的。
如果布尔电路仅由与非门组成,那么 L L L 层计算后的噪声大小为 ( N + 1 ) L B (N+1)^L B (N+1)LB - bounded,那么令 q / B > 8 ( N + 1 ) L q/B > 8(N+1)^L q/B>8(N+1)L 即可保证噪音是 q / 8 q/8 q/8 - bounded,从而解密正确。
给定安全参数 λ \lambda λ,维度 n n n 应随着 log ( q / B ) \log(q/B) log(q/B) 线性增长。GSW 将 n n n 视作一个定值,选取不算太大的 B B B,记 κ = log q \kappa = \log q κ=logq,设置 κ = O ( L log N ) = O ( L log n ) \kappa = O(L \log N) = O(L \log n) κ=O(LlogN)=O(Llogn)
由于 N = O ( n κ ) = O ~ ( n L ) N = O(n \kappa) = \tilde O(nL) N=O(nκ)=O~(nL),因此同态运算的渐进复杂度为 O ~ ( ( n L ) w ) \tilde O((nL)^w) O~((nL)w),其中 w < 2.3727 w < 2.3727 w<2.3727。这个渐进复杂度优于基于 LWE 的 BGV 和 BFV 的 O ~ ( n 3 L 2 ) \tilde O(n^3L^2) O~(n3L2),但是比基于 RLWE 的 BGV / BFV 慢一些对数因子。GSW 可以显著降低存储开销,从伪立方降低到了伪平方。
IBHE & ABHE
之前的 FHE 都无法转化为基于身份的加密(IBE)和基于属性的加密(ABE),主要是因为同态计算需要 evaluation key,这个密钥无法根据身份 ID 来生成。
GSW 的同态运算完全不需要 evaluation key,只需要知道公开参数即可。因此,只要管理员生成 M S K MSK MSK,公布 M P K MPK MPK,然后
-
对于任意的 p k = ( M P K , I D ) pk=(MPK,ID) pk=(MPK,ID),管理员计算 s k I D ← K e y G e n ( M S K , I D ) sk_{ID} \leftarrow KeyGen(MSK,ID) skID←KeyGen(MSK,ID),那么就把 GSW 转化为了 IBHE。文章来源:https://www.toymoban.com/news/detail-402899.html
-
类似的,对于任意的属性 x x x,令公钥为 p k = ( M P K , x ) pk = (MPK,x) pk=(MPK,x),对于访问策略 y y y,管理员计算 s k y ← K e y G e n ( M S K , y ) sk_y \leftarrow KeyGen(MSK,y) sky←KeyGen(MSK,y),那么仅当 R ( x , y ) = 1 R(x,y)=1 R(x,y)=1 时才可以正确解密。这就把 GSW 转化为了 ABHE。文章来源地址https://www.toymoban.com/news/detail-402899.html
到了这里,关于全同态加密:GSW的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!