参考文献:
- [Nuss80] Nussbaumer H. Fast polynomial transform methods for multidimensional DFTs[C]//ICASSP’80. IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 1980, 5: 235-237.
- [SV11] Smart N P, Vercauteren F. Fully homomorphic SIMD operations[J]. Designs, codes and cryptography, 2014, 71: 57-81.
- [GHS12a] Gentry C, Halevi S, Smart N P. Fully homomorphic encryption with polylog overhead[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 465-482.
- [GHS12b] Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic evaluation of the AES circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 850–867, Santa Barbara, CA, USA, August 19–23, 2012. Springer, Heidelberg, Germany
- [GHS12c] Gentry C, Halevi S, Smart N P. Better bootstrapping in fully homomorphic encryption[C]//International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 1-16.
- [GHS12d] Gentry C, Halevi S, Peikert C, et al. Ring switching in BGV-style homomorphic encryption[C]//International Conference on Security and Cryptography for Networks. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 19-37.
- [GHPS12] Gentry C, Halevi S, Peikert C, et al. Field switching in BGV-style homomorphic encryption[J]. Journal of Computer Security, 2013, 21(5): 663-684.
- [AP13] Alperin-Sheriff J, Peikert C. Practical bootstrapping in quasilinear time[C]//Annual Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 1-20.
- [AP14] J. Alperin-Sheriff and C. Peikert. Faster bootstrapping with polynomial error. In CRYPTO 2014, volume 8616 of Lecture Notes in Computer Science, pages 297–314, 2014.
- [BV14] Brakerski Z, Vaikuntanathan V. Lattice-based FHE as secure as PKE[C]//Proceedings of the 5th conference on Innovations in theoretical computer science. 2014: 1-12.
- [DM15] L. Ducas and D. Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In EUROCRYPT (1), volume 9056 of Lecture Notes in Computer Science, pages 617–640. Springer, 2015.
- [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
文章目录
- Nussbaumer Transform
- Multi-dimensional DFT
- Polynomial Transform
- Breaking Polynomials in Parts
- Amortized FHEW bootstrapping
- High level outline
- Modulus Switching
- Ring packing
- Homomorphic Registers
- Slow Multiplication
- Homomorphic DFT
- Ring Decrypt
- MSB Extract
- Refreshing
- Recursive optimization
Nussbaumer Transform
Multi-dimensional DFT
令 p 1 , p 2 , . . . , p b p_1,p_2,...,p_b p1,p2,...,pb 是 b b b 个整数,令 ζ j = e − 2 π i / p j \zeta_j = e^{-2 \pi i/p_j} ζj=e−2πi/pj 是 p j p_j pj 阶单位根,其中 i 2 + 1 = 0 i^2+1=0 i2+1=0。定义有限群 G : = Z p 1 × Z p 2 × ⋯ × Z p b G:= Z_{p_1} \times Z_{p_2} \times \dots \times Z_{p_b} G:=Zp1×Zp2×⋯×Zpb,容易验证 G G G 是拥有 p 1 p 2 … p b p_1p_2 \dots p_b p1p2…pb 个元素的群。对于群元素 x ∈ G x \in G x∈G,我们简单记做向量形式 ( x 1 , x 2 , … , x b ) , x j ∈ Z p j (x_1,x_2, \dots, x_b),\, x_j \in Z_{p_j} (x1,x2,…,xb),xj∈Zpj
函数
f
:
G
→
C
f:G \rightarrow C
f:G→C(索引为
x
∈
G
≅
[
p
j
]
j
x \in G \cong [p_j]_j
x∈G≅[pj]j 的高阶查找表)执行离散傅里叶变换,得到
F
:
G
→
C
F:G \rightarrow C
F:G→C (索引为
α
∈
G
≅
[
p
j
]
j
\alpha \in G \cong [p_j]_j
α∈G≅[pj]j 的另一个高阶查找表),
F
(
α
)
=
D
F
T
(
f
,
[
ζ
j
]
j
)
:
=
∑
x
∈
G
(
f
(
x
)
⋅
∏
j
=
1
b
ζ
j
α
j
x
j
)
F(\alpha) = DFT(f,[\zeta_j]_j) := \sum_{x \in G} \left( f(x) \cdot \prod_{j=1}^{b} \zeta_{j}^{\alpha_j x_j} \right)
F(α)=DFT(f,[ζj]j):=x∈G∑(f(x)⋅j=1∏bζjαjxj)
逆离散傅里叶变换的公式为:
f
(
x
)
=
I
n
v
D
F
T
(
F
,
[
ζ
j
]
j
)
:
=
1
p
1
p
2
…
p
b
∑
α
∈
G
(
F
(
α
)
⋅
∏
j
=
1
b
ζ
j
−
α
j
x
j
)
f(x) = InvDFT(F,[\zeta_j]_j) := \frac{1}{p_1p_2 \dots p_b} \sum_{\alpha \in G} \left( F(\alpha) \cdot \prod_{j=1}^{b} \zeta_{j}^{ - \alpha_j x_j} \right)
f(x)=InvDFT(F,[ζj]j):=p1p2…pb1α∈G∑(F(α)⋅j=1∏bζj−αjxj)
容易验证,上式是正确的。由于
ζ
j
0
=
1
\zeta_j^{0} = 1
ζj0=1,并且有
ζ
j
0
+
ζ
j
1
+
⋯
+
ζ
j
p
j
−
1
=
0
,
∀
j
\zeta_j^0+\zeta_j^1+ \dots + \zeta_j^{p_j-1} = 0,\forall j
ζj0+ζj1+⋯+ζjpj−1=0,∀j,因此:
∑
α
∈
G
(
∏
j
=
1
b
ζ
j
α
j
(
x
j
−
x
j
′
)
)
=
{
∣
G
∣
x
=
x
′
0
x
≠
x
′
\sum_{\alpha \in G}( \prod_{j=1}^{b} \zeta_{j}^{ \alpha_j (x_j-x_j')} ) = \left\{ \begin{aligned} |G| && x = x'\\ 0 && x \not = x'\\ \end{aligned} \right.
α∈G∑(j=1∏bζjαj(xj−xj′))={∣G∣0x=x′x=x′
其中
∣
G
∣
=
p
1
p
2
…
p
b
|G| = p_1p_2 \dots p_b
∣G∣=p1p2…pb,所以 DFT 公式和 InvDFT 公式之间多了一个因子
I
n
v
D
F
T
(
F
,
[
ζ
j
]
j
)
:
=
1
∣
G
∣
⋅
D
F
T
(
F
,
[
ζ
j
−
1
]
j
)
InvDFT(F,[\zeta_j]_j) := \frac{1}{|G|} \cdot DFT(F,[\zeta_j^{-1}]_j)
InvDFT(F,[ζj]j):=∣G∣1⋅DFT(F,[ζj−1]j)
Polynomial Transform
对于维度
N
×
N
,
N
=
2
t
N \times N,N=2^t
N×N,N=2t 的数组
{
x
n
1
,
n
2
}
n
1
,
n
2
∈
[
N
]
\{x_{n_1,n_2}\}_{n_1,n_2 \in [N]}
{xn1,n2}n1,n2∈[N],它的 DFT 公式为
x
ˉ
k
1
,
k
2
=
∑
n
1
=
0
N
−
1
∑
n
2
=
0
N
−
1
x
n
1
,
n
2
ζ
N
n
1
k
2
+
n
2
k
2
\bar x_{k_1,k_2} = \sum_{n_1=0}^{N-1} \sum_{n_2=0}^{N-1} x_{n_1,n_2}\zeta_N^{n_1k_2+n_2k_2}
xˉk1,k2=n1=0∑N−1n2=0∑N−1xn1,n2ζNn1k2+n2k2
令
w
=
ζ
N
w=\sqrt{\zeta_N}
w=ζN,我们对这个数组
{
x
n
1
,
n
2
}
n
1
,
n
2
\{x_{n_1,n_2}\}_{n_1,n_2}
{xn1,n2}n1,n2 按列抽取,扭曲后组成多项式,第
n
2
n_2
n2 列表示为:
x
n
2
(
z
)
:
=
∑
n
1
(
x
n
1
,
n
2
⋅
w
−
n
1
)
⋅
z
n
1
x_{n_2}(z) := \sum_{n_1} (x_{n_1,n_2} \cdot w^{-n_1})\cdot z^{n_1}
xn2(z):=n1∑(xn1,n2⋅w−n1)⋅zn1
以它们作为系数,构造多项式:
x
ˉ
k
2
(
z
)
:
=
∑
n
2
x
n
2
(
z
)
⋅
w
2
n
2
k
2
(
m
o
d
z
N
+
1
)
\bar x_{k_2}(z) := \sum_{n_2} x_{n_2}(z) \cdot w^{2n_2k_2} \pmod{z^N+1}
xˉk2(z):=n2∑xn2(z)⋅w2n2k2(modzN+1)
那么可以验证,二维 DFT 被表示为在
z
=
w
2
k
1
+
1
z=w^{2k_1+1}
z=w2k1+1 的求值:
x
ˉ
k
1
,
k
2
=
x
ˉ
k
2
(
z
)
(
m
o
d
z
−
w
2
k
1
+
1
)
\bar x_{k_1,k_2} = \bar x_{k_2}(z) \pmod{z-w^{2k_1+1}}
xˉk1,k2=xˉk2(z)(modz−w2k1+1)
由于
gcd
(
2
k
1
+
1
,
N
)
=
1
\gcd(2k_1+1,N)=1
gcd(2k1+1,N)=1,因此
k
2
↦
(
2
k
1
+
1
)
k
2
(
m
o
d
N
)
k_2 \mapsto (2k_1+1)k_2 \pmod N
k2↦(2k1+1)k2(modN) 是一个置换。我们重写
x
ˉ
k
2
\bar x_{k_2}
xˉk2 为如下形式(不需要实际置换,仅仅是一种表示),
x
ˉ
(
2
k
1
+
1
)
k
2
(
z
)
=
∑
n
2
x
n
2
(
z
)
⋅
z
2
n
2
k
2
(
m
o
d
z
N
+
1
)
\bar x_{(2k_1+1)k_2}(z) = \sum_{n_2} x_{n_2}(z) \cdot z^{2n_2k_2} \pmod{z^N+1}
xˉ(2k1+1)k2(z)=n2∑xn2(z)⋅z2n2k2(modzN+1)
对应的,
x
ˉ
k
1
,
(
2
k
1
+
1
)
k
2
=
x
ˉ
(
2
k
1
+
1
)
k
2
(
z
)
(
m
o
d
z
−
w
2
k
1
+
1
)
\bar x_{k_1,(2k_1+1)k_2} = \bar x_{(2k_1+1)k_2}(z) \pmod{z-w^{2k_1+1}}
xˉk1,(2k1+1)k2=xˉ(2k1+1)k2(z)(modz−w2k1+1)
由于
deg
x
ˉ
(
2
k
1
+
1
)
k
2
(
z
)
≤
N
−
1
\deg\bar x_{(2k_1+1)k_2}(z) \le N-1
degxˉ(2k1+1)k2(z)≤N−1,因此可以把它记为
x
ˉ
(
2
k
1
+
1
)
k
2
(
z
)
=
∑
l
=
0
N
−
1
y
k
2
,
l
⋅
z
l
\bar x_{(2k_1+1)k_2}(z) = \sum_{l=0}^{N-1} y_{k_2,l} \cdot z^l
xˉ(2k1+1)k2(z)=l=0∑N−1yk2,l⋅zl
因此二维 DFT 表示为
x
ˉ
k
1
,
(
2
k
1
+
1
)
k
2
=
∑
l
=
0
N
−
1
y
k
2
,
l
⋅
(
w
2
k
1
+
1
)
l
=
∑
l
=
0
N
−
1
(
y
k
2
,
l
⋅
w
l
)
⋅
w
2
l
k
1
\begin{aligned} \bar x_{k_1,(2k_1+1)k_2} &= \sum_{l=0}^{N-1} y_{k_2,l} \cdot (w^{2k_1+1})^l\\ &= \sum_{l=0}^{N-1} (y_{k_2,l}\cdot w^l) \cdot w^{2lk_1}\\ \end{aligned}
xˉk1,(2k1+1)k2=l=0∑N−1yk2,l⋅(w2k1+1)l=l=0∑N−1(yk2,l⋅wl)⋅w2lk1
总结一下,二维数组的 DFT 的计算方法为:
- 输入数组 { x n 1 , n 2 } n 1 , n 2 ∈ [ N ] \{x_{n_1,n_2}\}_{n_1,n_2 \in [N]} {xn1,n2}n1,n2∈[N]
- 对所有的 x n 1 , n 2 x_{n_1,n_2} xn1,n2 扭曲角度 w − n 1 w^{-n_1} w−n1,构造出 N N N 个长度 N N N 的小多项式 x n 2 ( z ) x_{n_2}(z) xn2(z)
- 对于不同的 k 2 k_2 k2,将它们作为系数,分别组合出 N N N 个系数的多项式 x ˉ k 2 ( z ) \bar x_{k_2}(z) xˉk2(z)
- 对于每个 k 2 k_2 k2,扭曲 x ˉ k 2 ( z ) \bar x_{k_2}(z) xˉk2(z) 的系数 [ y k 2 , l ] l [y_{k_2,l}]_l [yk2,l]l 角度 w l w^l wl,得到长度 N N N 的一维样本 [ y k 2 , l ⋅ w l ] l [y_{k_2,l}\cdot w^l]_l [yk2,l⋅wl]l
- 对于每个 k 2 k_2 k2,对样本 [ y k 2 , l ⋅ w l ] l [y_{k_2,l}\cdot w^l]_l [yk2,l⋅wl]l 做关于 w 2 k 1 , k 1 ∈ [ N ] w^{2k_1},k_1\in [N] w2k1,k1∈[N] 的一维 FFT/NTT(同时执行 N N N 个 x ˉ ( 2 k 1 + 1 ) k 2 ( w 2 k 1 ) \bar x_{(2k_1+1)k_2}(w^{2k_1}) xˉ(2k1+1)k2(w2k1) 的求值),就可以实现二维 DFT 的计算
step 2 需要 O ( N 2 ) O(N^2) O(N2) 次数乘,step 3 需要 O ( N 2 ) O(N^2) O(N2) 次加法,step 4 需要 O ( N 2 ) O(N^2) O(N2) 次数乘,step 5 需要 O ( N ) O(N) O(N) 次长度为 O ( N ) O(N) O(N) 的 FFT/DFT 子例程,总的复杂度为 O ( N 2 log N ) O(N^2\log N) O(N2logN)
Breaking Polynomials in Parts
[GHS12d] 中为了实现分园环上的 Ring Switching 任务,也采取了类似的多项式切分策略。后续的另一篇文章 [GHPS12] 则采取了完全不同的技术路径,使用分园环塔上的 Trace 来实现 Field Switching 任务。这个技术可以用于加速 BGV 的 Bootstrapping 过程,甚至可以加速同态运算本身。
我们定义 R m = Z [ x ] / ( Φ m ( x ) ) R_m=\mathbb Z[x]/(\Phi_m(x)) Rm=Z[x]/(Φm(x)),定义 C m = Z [ x ] / ( x m − 1 ) C_m=\mathbb Z[x]/(x^m-1) Cm=Z[x]/(xm−1)。利用 Modulus Lift 技术,存在多项式 G ( x ) ∈ Z [ x ] G(x) \in \mathbb Z[x] G(x)∈Z[x],使得 a ( x ) ∈ R m ↦ G ( x ) ⋅ a ( x ) ∈ C m a(x) \in R_m \mapsto G(x) \cdot a(x) \in C_m a(x)∈Rm↦G(x)⋅a(x)∈Cm 是单的加群同态。
对于 m = u ⋅ w m=u \cdot w m=u⋅w,就有以下的良好性质:
- 给定三个次数至多为 ϕ ( w ) − 1 \phi(w)-1 ϕ(w)−1 的多项式 f , g , h f,g,h f,g,h,如果满足 h ( x ) = f ( x ) ⋅ g ( x ) ( m o d Φ w ( x ) ) h(x) = f(x) \cdot g(x) \pmod{\Phi_w(x)} h(x)=f(x)⋅g(x)(modΦw(x)),那么 h ( x u ) = f ( x u ) ⋅ g ( x u ) ( m o d Φ m ( x ) ) h(x^u) = f(x^u) \cdot g(x^u) \pmod{\Phi_m(x)} h(xu)=f(xu)⋅g(xu)(modΦm(x))
- 给定三个次数至多为 w − 1 w-1 w−1 的多项式 f , g , h f,g,h f,g,h,如果满足 h ( x ) = f ( x ) ⋅ g ( x ) ( m o d x w − 1 ) h(x) = f(x) \cdot g(x) \pmod{x^w-1} h(x)=f(x)⋅g(x)(modxw−1),那么 h ( x u ) = f ( x u ) ⋅ g ( x u ) ( m o d x m − 1 ) h(x^u) = f(x^u) \cdot g(x^u) \pmod{x^m-1} h(xu)=f(xu)⋅g(xu)(modxm−1)
假设
m
=
u
⋅
w
m=u \cdot w
m=u⋅w,那么
C
w
C_w
Cw 可以视为
C
m
C_m
Cm 的子环,以及
R
w
R_w
Rw 可以视为
R
m
R_m
Rm 的子环,对应的环嵌入是
x
↦
x
u
x \mapsto x^u
x↦xu。给定
Z
[
x
]
/
(
x
m
−
1
)
\mathbb Z[x]/(x^m-1)
Z[x]/(xm−1) 中的多项式,
a
(
x
)
=
∑
i
=
0
m
−
1
a
i
⋅
x
i
=
∑
k
=
0
u
−
1
∑
j
=
0
w
−
1
a
u
j
+
k
⋅
x
u
j
+
k
=
∑
k
=
0
u
−
1
(
∑
j
=
0
w
−
1
a
u
j
+
k
⋅
x
u
j
)
⋅
x
k
\begin{aligned} a(x) &= \sum_{i=0}^{m-1} a_i \cdot x^i\\ &= \sum_{k=0}^{u-1}\sum_{j=0}^{w-1} a_{uj+k} \cdot x^{uj+k}\\ &= \sum_{k=0}^{u-1}\left(\sum_{j=0}^{w-1} a_{uj+k} \cdot x^{uj}\right) \cdot x^k\\ \end{aligned}
a(x)=i=0∑m−1ai⋅xi=k=0∑u−1j=0∑w−1auj+k⋅xuj+k=k=0∑u−1(j=0∑w−1auj+k⋅xuj)⋅xk
定义
a
(
k
)
=
∑
j
=
0
w
−
1
a
u
j
+
k
⋅
x
j
∈
Z
[
x
]
/
(
x
w
−
1
)
a_{(k)} = \sum_{j=0}^{w-1} a_{uj+k} \cdot x^{j} \in \mathbb Z[x]/(x^w-1)
a(k)=∑j=0w−1auj+k⋅xj∈Z[x]/(xw−1),那么
a
(
x
)
=
∑
k
=
0
u
−
1
a
(
k
)
(
x
u
)
⋅
x
k
a(x) = \sum_{k=0}^{u-1} a_{(k)}(x^u) \cdot x^k
a(x)=k=0∑u−1a(k)(xu)⋅xk
[GHPS12] 将上述的 a ∈ C m ↦ [ a ( k ) ] k ∈ C w u a \in C_m \mapsto [a_{(k)}]_k \in C_w^u a∈Cm↦[a(k)]k∈Cwu 切分过程称为 split coefficients。容易看出它是可逆的,其逆过程称为 reconstruction。特别地,切分过程是投影,而重构过程是线性组合,从而它们可以和其他的线性函数(比如解密函数)交换。[GHPS12] 提出了 Ring-Switching,首先把大环 R m R_m Rm 上密文的秘钥切换到子环 R w R_w Rw 上(需保证子环维度足够大,从而安全),接着执行 Modulus Lift 把密文映射到 C m C_m Cm 上,然后 Split 得到 C w C_w Cw 上的若干碎片,最后取模获得小环 R w R_w Rw 上的若干密文。可以证明,这些小环密文的明文槽中,加密了大环密文的明文槽(但是有额外的槽内线性变换)。
Amortized FHEW bootstrapping
[MS18] 给出了第一个 “困难假设的近似因子为多项式” 并且 “自举复杂度是(均摊)亚线性” 的 FHE 方案。虽然单次自举的复杂度略高于 FHEW,但是可以批处理,因此均摊下来减少了大约 O ( n ) O(n) O(n) 因子。
High level outline
[BGV12] 提出 BGV 方案时,便给出了 Batching Bootstrapping 的设计,使用底层代数自带的 Rotation 实现各个槽之间的迁移,同时自举 O ~ ( λ ) \tilde O(\lambda) O~(λ) 个密文,获得了拟线性的均摊自举时间。 但是,[BGV12] 使用的是布尔电路,因此速度很慢。
[GHS12c] 提出了特殊密文模数 q 0 = p t q_0=p^t q0=pt 的快速解密例程(完全算术的),然后采取 p-adic number 以及 Hensel Lifting,扩展了 [SV11] 的 SIMD 技术,使得明文槽成为环 Z p t \mathbb Z_{p^t} Zpt 而非有限域 G F ( p t ) GF(p^t) GF(pt),最后再通过 [GHS12a] 的 Slot Permutation 技术,执行同态 DFT 来实现 coeff packing 和 slot packing 之间的转换,于是实现了并行的解密。
[AP13] 并不采用 Benes 置换网络来实现同态 DFT,而是通过[GHS12D] 和 [GHPS12] 的 Field Switching(用 Trace 实现任意的线性函数),以及分园环的 Tensorial Decomposition,直接将 coeff 映射到 slot 上。另外 [AP13] 使用分园环上的 Ideal Factorization 来推广 [SV11] 的 SIMD 技术到环 Z p t \mathbb Z_{p^t} Zpt 的明文槽,而非 p-进数。
不过,上述的这些 BGV 的并行自举方案,都导致噪声的超多项式增长,因此需要假设近似因子为超多项式的格上问题困难。基于 GSW 方案,[BV14] 给出了第一个近似因子为多项式的 FHE 方案,但是解需要利用 5-PBP 实现布尔解密电路,计算复杂度。之后 [AP14] 使用 GSW 构造出 HE-Perm 方案(实际就是同态累加器),用它来自举任意的单个 LWE 密文,计算复杂度仅为 O ~ ( λ ) \tilde O(\lambda) O~(λ),同时所依赖的假设近似因子是多项式的。
[MS18] 给出了第一个 “困难假设的近似因子为多项式” 并且 “自举复杂度是(均摊)亚线性” 的 FHE 方案。虽然单次自举的复杂度略高于 FHEW,但是可以批处理,因此均摊下来减少了大约 O ( n ) O(n) O(n) 因子。一些方案的计算复杂度比较,如图所示:
大体思路为:
- 选取 L W E n 2 / q LWE^{2/q}_n LWEn2/q 的参数:代数结构 Z q n + 1 \mathbb Z_q^{n+1} Zqn+1,密文模数 q q q,明文模数 t = 2 t=2 t=2,维度 n = 2 l − 1 n=2^{l-1} n=2l−1
- 选取 R L W E d 2 / 2 n RLWE^{2/2n}_d RLWEd2/2n 的参数:代数结构 Z 2 n [ x ] / ( Φ d ( x ) ) \mathbb Z_{2n}[x]/(\Phi_d(x)) Z2n[x]/(Φd(x)),密文模数 2 n 2n 2n,明文模数 t = 2 t=2 t=2,维度 ϕ ( d ) \phi(d) ϕ(d)
- 选取 R G S W N 2 n / Q RGSW^{2n/Q}_N RGSWN2n/Q 的参数:代数结构 Z Q [ x ] / ( Φ N ( x ) ) \mathbb Z_Q[x]/(\Phi_N(x)) ZQ[x]/(ΦN(x)),密文模数 Q Q Q,维度 2 n ∣ ϕ ( N ) 2n\mid\phi(N) 2n∣ϕ(N),被编码在多项式的指数上的明文空间大小为 2 n 2n 2n
- 我们使用 RGSW 构造一个比 FHEW 的累加器(仅支持加法)更强的同态寄存器 R E G 2 n / Q REG^{2n/Q} REG2n/Q,它支持 Z 2 n \mathbb Z_{2n} Z2n 中的加法和减法(不支持数乘)
- 为了同态解密 b − a ⋅ s ∈ R d , 2 n b-a \cdot s \in R_{d,2n} b−a⋅s∈Rd,2n,我们把私钥预处理为 DFT 格式 D F T ( s ) DFT(s) DFT(s),设置自举秘钥为 B K : = R E G 2 n / Q ( [ 2 j ⋅ D F T ( s ) i ] i , j ) BK:=REG^{2n/Q}([2^j \cdot DFT(s)_i]_{i,j}) BK:=REG2n/Q([2j⋅DFT(s)i]i,j)
- 我们首先把 ϕ ( d ) \phi(d) ϕ(d) 个 LWE 密文,打包到单个 RLWE 密文中,并执行模切换将模数从 q q q 降低到 2 n 2n 2n
- 然后对这个打包的 RLWE 密文 ( a , b ) ∈ R d , 2 n 2 (a,b) \in R_{d,2n}^2 (a,b)∈Rd,2n2 做同态解密:将 a a a 视为常数多项式,明文下转化为 D F T ( a ) DFT(a) DFT(a),然后和 B K BK BK 做阿达玛积(数乘),得到 D F T ( s ⋅ a ) i ∈ Z 2 n DFT(s \cdot a)_i \in \mathbb Z_{2n} DFT(s⋅a)i∈Z2n 的累加器状态
- 现在执行同态 InvDFT,这个过程中我们仅仅能够使用 R E G 2 n / Q REG^{2n/Q} REG2n/Q 所支持的加法和乘法操作。其中的与单位根的数乘,通过 Nussbaumer Transform 变为子环的旋转(取模运算需要 Z 2 n \mathbb Z_{2n} Z2n 上的减法)
- 经过一些转换,现在我们得到了加密 s ⋅ a ∈ R d , 2 n s \cdot a \in R_{d,2n} s⋅a∈Rd,2n 各个系数的寄存器,从而可以计算出 m ≈ b − a ⋅ s m\approx b-a \cdot s m≈b−a⋅s 的寄存器(共有 O ( d ) O(d) O(d) 个 RGSW 密文分别加密 m ( x ) m(x) m(x) 的各个系数)
- 最后,利用 R G S W N 2 n / Q RGSW_N^{2n/Q} RGSWN2n/Q 的明文 one-hot 性质,利用各个系数对应的寄存器,查找舍入函数的 Lookup Table(反循环向量)获取 m i = M S B ( m i + e ) m_i=MSB(m_i+e) mi=MSB(mi+e) 的值,这便是我们一开始输入的那些 LWE 密文的明文
现在有如下几个问题:怎么打包 LWE 到 RLWE、怎么构造支持减法的寄存器、怎么将 InvDFT 的数乘运算仅使用加/减法实现。其他的诸如模切换、提取 MSB 都是简单的。
Modulus Switching
[MS18] 采取了随机化园整的模切换变体。定义随机函数 $\lfloor \cdot \rceil_$: \mathbb R \to \mathbb Z$,
⌊
x
⌉
$
:
=
{
⌊
x
⌋
,
P
r
=
⌈
x
⌉
−
x
⌈
x
⌉
,
P
r
=
x
−
⌊
x
⌋
\lfloor x \rceil_\$ := \left\{\begin{aligned} \lfloor x\rfloor,&& Pr=\lceil x\rceil-x\\ \lceil x\rceil,&& Pr=x-\lfloor x\rfloor\\ \end{aligned}\right.
⌊x⌉$:={⌊x⌋,⌈x⌉,Pr=⌈x⌉−xPr=x−⌊x⌋
舍入噪声为 $-1< x-\lfloor x \rceil_$<1$,因此它是参数 2 π \sqrt{2\pi} 2π 的亚高斯分布。
模切换算法为
对于 LWE 密文:它的输入是
L
W
E
s
t
/
Q
[
m
,
β
]
LWE^{t/Q}_s[m,\beta]
LWEst/Q[m,β],其输出为
L
W
E
s
t
/
q
[
m
,
β
′
]
LWE^{t/q}_s[m,\beta']
LWEst/q[m,β′],简记 $e=(\lfloor (n/q)b \rceil_$,\lfloor (n/q)a \rceil_$)$(参数
2
π
\sqrt{2\pi}
2π 的亚高斯),那么噪声界以极高的概率为
β
′
=
q
Q
⋅
β
+
∥
e
⋅
(
1
,
−
s
)
∥
=
q
Q
⋅
β
+
O
(
∥
s
∥
)
\beta' = \dfrac{q}{Q}\cdot\beta + \|e\cdot(1,-s)\| = \dfrac{q}{Q}\cdot\beta + O(\|s\|)
β′=Qq⋅β+∥e⋅(1,−s)∥=Qq⋅β+O(∥s∥)
对于 RLWE 密文:它的输入是
R
L
W
E
z
t
/
q
[
m
,
β
]
RLWE^{t/q}_z[m,\beta]
RLWEzt/q[m,β],其输出为
L
W
E
s
t
/
n
[
m
,
β
′
]
LWE^{t/n}_s[m,\beta']
LWEst/n[m,β′],简记 $e_0=\lfloor (n/q)b \rceil_$$ 和 $e_1=\lfloor (n/q)a \rceil_$$(参数
2
π
\sqrt{2\pi}
2π 的亚高斯),那么噪声界以极高的概率为
β
′
=
n
q
⋅
β
+
∥
e
0
∥
+
∥
e
1
⋅
z
∥
=
n
q
⋅
β
+
w
(
d
log
d
)
⋅
∥
z
∥
\beta' = \dfrac{n}{q}\cdot\beta + \|e_0\|+\|e_1\cdot z\| = \dfrac{n}{q}\cdot\beta + w\left(\sqrt{d \log d}\right) \cdot \|z\|
β′=qn⋅β+∥e0∥+∥e1⋅z∥=qn⋅β+w(dlogd)⋅∥z∥
Ring packing
类似于 TFHE 的 functional Key-switch 例程,我们可以把一些 LWE 密文打包到单个 RLWE 密文中。
算法如下:
打包秘钥
K
j
,
l
P
∈
R
L
W
E
z
q
/
q
[
s
l
⋅
2
j
,
β
P
]
K_{j,l}^P \in RLWE^{q/q}_z[s_l\cdot 2^j,\beta_P]
Kj,lP∈RLWEzq/q[sl⋅2j,βP],输入
ϕ
(
d
)
\phi(d)
ϕ(d) 个
L
W
E
n
t
/
q
[
m
i
,
Δ
]
LWE^{t/q}_n[m_i,\Delta]
LWEnt/q[mi,Δ],输出单个
R
L
W
E
z
t
/
q
[
m
(
x
)
,
β
]
RLWE^{t/q}_z[m(x),\beta]
RLWEzt/q[m(x),β],其中
m
(
x
)
=
∑
i
m
i
x
i
m(x) = \sum_i m_ix^{i}
m(x)=∑imixi,它的噪声界是
β
=
O
(
d
⋅
Δ
+
d
n
log
q
⋅
β
P
)
\beta = O(\sqrt d\cdot \Delta + \sqrt{dn\log q}\cdot \beta_P)
β=O(d⋅Δ+dnlogq⋅βP)
在对这个打包的 RLWE 密文执行同态解密之前,执行 Modulus Switching 将模数从 q q q 降低到 2 n 2n 2n(环面以 1 / 2 n 1/2n 1/2n 精度离散化),从而可以被 RGSW 自举(没看懂为啥 RGSW 的维度要和 LWE 的维度有关,没必要吧?)
此时我们拥有了打包密文 ( a , b ) ∈ R L W E z t / 2 n [ m ( x ) , β ] ⊆ R d , 2 n 2 (a,b) \in RLWE^{t/2n}_z[m(x),\beta] \subseteq R_{d,2n}^2 (a,b)∈RLWEzt/2n[m(x),β]⊆Rd,2n2,秘钥为 z ∈ R d , 2 n z \in R_{d,2n} z∈Rd,2n,我们接下来需要同态地计算 b − a ⋅ z ∈ R d , 2 n b-a \cdot z \in R_{d,2n} b−a⋅z∈Rd,2n 并且同态地园整。
Homomorphic Registers
FHEW 的累加器仅支持同态加法,不支持减法( homomorphic inversion),难以支持数乘( homomorphic exponentiation)。[MS18] 类似于 FHEW 采取 RGSW 来构建同态累加器(而非 TFHE 采用的 RLWE),但是通过冗余,增强实现了支持减法的寄存器。
对于加密系统 R G S W N 2 n / Q RGSW^{2n/Q}_N RGSWN2n/Q,这里的上角标 2 n / Q 2n/Q 2n/Q 并非纠错码缩放倍率,而是指的明文空间为 Z 2 n \mathbb Z_{2n} Z2n(编码在多项式指数上)。对于 v ∈ Z 2 n v \in \mathbb Z_{2n} v∈Z2n,假设 Y = X N / 2 n Y=X^{N/2n} Y=XN/2n 是 2 n 2n 2n 次本原单位根,FHEW 的累加器为 R G S W N 2 n / Q ( u ⋅ Y v ) RGSW^{2n/Q}_N(u \cdot Y^v) RGSWN2n/Q(u⋅Yv),其中的 u ≈ Q / 2 t u\approx Q/2t u≈Q/2t 是 RLWE 的纠错码缩放倍率。我们选取 t = 4 t=4 t=4,它对应于 Z 4 \mathbb Z_4 Z4 的纠错编码倍率 Q / t Q/t Q/t 的一半(反循环函数)
FHEW 的累加器:
-
初始化(Initialization):记为 v ← w v \gets w v←w,状态为无噪密文
C = u ⋅ X w G ∈ R G S W z 2 n / Q ( u ⋅ X w ) C=u \cdot X^w G \in RGSW^{2n/Q}_z(u \cdot X^w) C=u⋅XwG∈RGSWz2n/Q(u⋅Xw) -
常数加法(Increment):记为 v ← v + c v \gets v+c v←v+c,状态转换为
C ⋅ X c ∈ R G S W z 2 n / Q ( u ⋅ X w + c ) C \cdot X^c \in RGSW^{2n/Q}_z(u \cdot X^{w+c}) C⋅Xc∈RGSWz2n/Q(u⋅Xw+c) -
密文加法(Addition):记为 v ← v + C ′ v \gets v+C' v←v+C′,状态转换为
( u − 1 ⋅ C ) ⋅ G − 1 ( C ′ ) ∈ R G S W z 2 n / Q ( u ⋅ X v + w ) (u^{-1} \cdot C) \cdot G^{-1}(C') \in RGSW^{2n/Q}_z(u \cdot X^{v+w}) (u−1⋅C)⋅G−1(C′)∈RGSWz2n/Q(u⋅Xv+w) -
密文提取(Extraction):从 C C C 中提取出 LWE 密文
为了使得同态寄存器也支持减法,[MS18] 将数值
v
∈
Z
2
n
v \in \mathbb Z_{2n}
v∈Z2n 存储为冗余的一对 RGSW 密文(两个反向的累加器),
R
E
G
z
2
n
/
Q
[
v
,
β
]
:
=
(
R
G
S
W
z
2
n
/
Q
(
u
⋅
X
v
)
,
R
G
S
W
z
2
n
/
Q
(
u
⋅
X
−
v
)
)
REG^{2n/Q}_z[v,\beta] := \left(RGSW^{2n/Q}_z(u \cdot X^{v}),\,\, RGSW^{2n/Q}_z(u \cdot X^{-v})\right)
REGz2n/Q[v,β]:=(RGSWz2n/Q(u⋅Xv),RGSWz2n/Q(u⋅X−v))
这个寄存器的:初始化、常数加法、密文加法,都是从累加器自然继承的。密文提取就是对第一分量 C C C 的密文提取。它额外支持减法:简单交换两个累加器, ( C , C ′ ) ↦ ( C ′ , C ) (C,C') \mapsto (C',C) (C,C′)↦(C′,C)
后文中,我们使用符号 [ [ v ] ] [\![v]\!] [[v]] 简记加密 v ∈ Z 2 n [ x ] ≅ Z 2 n ∞ v \in \mathbb Z_{2n}[x] \cong \mathbb Z_{2n}^\infty v∈Z2n[x]≅Z2n∞ 的一组寄存器。
Slow Multiplication
现在,我们看一下如何在 R E G 2 n / Q REG^{2n/Q} REG2n/Q 下,计算 R d , 2 n R_{d,2n} Rd,2n 中环元素的数乘 a ⋅ [ [ z ] ] a \cdot [\![z]\!] a⋅[[z]]
由于 z ∈ R d , 2 n z \in R_{d,2n} z∈Rd,2n 是各个系数单独加密在 REG 内的,并且 a ∈ R d , 2 n a \in R_{d,2n} a∈Rd,2n 的各个系数都已知的 l = log n + 1 l=\log n+1 l=logn+1 比特常数。因此我们可以在 REG 中存储私钥的二的幂, f ( z ) : = [ z k 2 j ] k , j ∈ Z 2 n l × ϕ ( d ) f(z) := [z_k2^j]_{k,j} \in \mathbb Z_{2n}^{l \times \phi(d)} f(z):=[zk2j]k,j∈Z2nl×ϕ(d) 的值,然后将 a i ∈ Z 2 n a_i \in \mathbb Z_{2n} ai∈Z2n 做二进制分解 ∑ j = 0 l − 1 a i j 2 j \sum_{j=0}^{l-1} a_{ij}2^j ∑j=0l−1aij2j
定义计算标量数乘
a
i
⋅
z
k
∈
Z
2
n
a_i \cdot z_k \in \mathbb Z_{2n}
ai⋅zk∈Z2n 的同态电路
C
a
i
(
[
[
f
(
z
)
]
]
,
k
)
:
=
∑
j
∈
[
l
]
,
a
i
j
=
1
[
[
z
k
2
j
]
]
C_{a_i}([\![f(z)]\!], k) := \sum_{j \in [l],\,\, a_{ij}=1} [\![z_k2^j]\!]
Cai([[f(z)]],k):=j∈[l],aij=1∑[[zk2j]]
上述过程中,仅仅需要同态加法(不需要计算幂次),这是寄存器所支持的。
于是环元素数乘 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} a⋅z∈Rd,2n 的同态电路 C a C_a Ca 为:
- R d , 2 n R_{d,2n} Rd,2n 的长度为 d d d,因此我们先提升到整数多项式环,计算 a ⋅ z ∈ Z 2 n [ x ] a \cdot z \in\mathbb Z_{2n}[x] a⋅z∈Z2n[x],它的长度为 2 d − 1 2d-1 2d−1
- 每个系数 ( a ⋅ z ) i = ∑ i = j + k a j ⋅ z k ∈ Z 2 n (a \cdot z)_i = \sum_{i=j+k} a_j \cdot z_k \in \mathbb Z_{2n} (a⋅z)i=∑i=j+kaj⋅zk∈Z2n 是若干数乘的加和,采取 C a j ( [ [ f ( z ) ] ] , k ) C_{a_j}([\![f(z)]\!], k) Caj([[f(z)]],k) 来实现,共计 O ( d 2 ⋅ l ) O(d^2\cdot l) O(d2⋅l) 个同态加法
- 现在模掉 Φ d ( x ) \Phi_d(x) Φd(x) 回到分圆环 R d , 2 n R_{d,2n} Rd,2n 上,假如我们选取 d d d 是素数幂次,那么 Φ d ( x ) \Phi_d(x) Φd(x) 的系数都是 { 0 , 1 } \{0,1\} {0,1} 的,从而模约减只需要若干的减法
令
p
p
p 是素数,
k
k
k是自然数,那么
Q
p
k
(
x
)
=
x
p
k
−
1
Q
1
(
x
)
Q
p
(
x
)
⋯
Q
p
k
−
1
(
x
)
=
x
p
k
−
1
x
p
k
−
1
−
1
=
1
+
x
p
k
−
1
+
x
2
p
k
−
1
+
⋯
+
x
(
p
−
1
)
p
k
−
1
\begin{aligned} Q_{p^k}(x) &= \dfrac{x^{p^{k}}-1}{Q_1(x)Q_p(x) \cdots Q_{p^{k-1}}(x)}\\ &= \dfrac{x^{p^{k}}-1}{x^{p^{k-1}}-1}\\ &= 1 + x^{p^{k-1}} + x^{2p^{k-1}} + \cdots + x^{(p-1)p^{k-1}} \end{aligned}
Qpk(x)=Q1(x)Qp(x)⋯Qpk−1(x)xpk−1=xpk−1−1xpk−1=1+xpk−1+x2pk−1+⋯+x(p−1)pk−1
它仅包含 p p p 个系数是 1 1 1,其他的系数都是 0 0 0,于是模约减容易的。素数 p p p 越小,模约减复杂度的常数因子越小。
假设
B
g
B_g
Bg 是 RGSW 的 Gadget 矩阵的参数,
d
g
=
log
B
g
Q
d_g=\log_{B_g} Q
dg=logBgQ 是分解位数,那么存在算法
S
l
o
w
M
u
l
t
:
R
d
,
2
n
×
R
E
G
z
l
×
ϕ
(
d
)
→
R
E
G
z
ϕ
(
d
)
SlowMult: R_{d,2n}\times REG^{l \times \phi(d)}_z \to REG^{\phi(d)}_z
SlowMult:Rd,2n×REGzl×ϕ(d)→REGzϕ(d),
(
a
,
[
R
E
G
z
2
n
/
Q
[
f
(
z
)
j
,
k
,
β
]
]
j
,
k
)
↦
[
R
E
G
z
2
n
/
Q
[
(
a
⋅
z
)
i
,
β
′
]
]
i
\left( a, \left[REG^{2n/Q}_z[f(z)_{j,k}, \beta]\right]_{j,k} \right) \mapsto \left[ REG^{2n/Q}_z[(a\cdot z)_i, \beta'] \right]_i
(a,[REGz2n/Q[f(z)j,k,β]]j,k)↦[REGz2n/Q[(a⋅z)i,β′]]i
以压倒性概率 β ′ = O ~ ( β B g ⋅ n d g ⋅ d ) \beta' = \tilde O\left(\beta B_g \cdot \sqrt{n d_g\cdot d}\right) β′=O~(βBg⋅ndg⋅d),它的计算复杂度为 O ~ ( d 2 ) \tilde O(d^2) O~(d2) 次同态加法/减法。
Homomorphic DFT
然而,上述 Slow Multiplication 的计算效率太低了(拟二次函数),即使 ϕ ( d ) \phi(d) ϕ(d) 个密文均摊下来复杂度依旧是拟线性的。我们希望把均摊成本降低到亚线性,也就是说多项式的同态乘法的复杂度应当为拟线性。如果可以在 DFT 域上计算阿达玛乘法,然后再利用 InvFFT 算法得到它的系数表示,计算复杂度就降低到了拟线性级别。
我们简记 R d : = Z [ x ] / ( Φ d ( x ) ) R_{d}:=\mathbb Z[x]/(\Phi_d(x)) Rd:=Z[x]/(Φd(x)) 是分园数域的整数环( d d d 是任意整数),令商环 R d , q : = R d / q R d R_{d,q}:=R_d/qR_d Rd,q:=Rd/qRd,另外简记 C m : = R m : = Z [ x ] / ( x m − 1 ) C_m:=R_{m}:=\mathbb Z[x]/(x^m-1) Cm:=Rm:=Z[x]/(xm−1) 是循环卷积环( m m m 是素数幂次)
C
m
C_m
Cm 上的 DFT 的公式为,
x
ˉ
i
=
D
F
T
(
x
)
i
:
=
∑
k
=
0
m
−
1
x
k
ζ
m
i
k
x
k
=
D
F
T
−
1
(
x
)
i
:
=
∑
i
=
0
m
−
1
x
ˉ
i
ζ
m
−
i
k
\begin{array}{ccrcl} \bar x_i &=& DFT(x)_i &:=& \sum_{k=0}^{m-1} x_k \zeta_m^{ik}\\ x_k &=& DFT^{-1}(x)_i &:=& \sum_{i=0}^{m-1} \bar x_i \zeta_m^{-ik}\\ \end{array}
xˉixk==DFT(x)iDFT−1(x)i:=:=∑k=0m−1xkζmik∑i=0m−1xˉiζm−ik
那么对于
a
,
z
∈
R
d
a,z \in R_d
a,z∈Rd 的多项式乘法,只要满足
deg
a
⋅
z
<
m
\deg a\cdot z < m
dega⋅z<m(即
m
>
2
ϕ
(
d
)
−
1
m>2\phi(d)-1
m>2ϕ(d)−1),就可以先在
C
m
C_m
Cm 的 DFT 域上计算阿达玛积,然后 InvFFT 回到
C
m
C_m
Cm 上并且模掉
Φ
d
(
x
)
\Phi_d(x)
Φd(x) 得到
R
d
R_d
Rd 上结果,
(
a
(
x
)
⋅
z
(
x
)
(
m
o
d
x
m
−
1
)
)
(
m
o
d
Φ
d
(
x
)
)
=
D
F
T
−
1
(
1
m
D
F
T
(
z
)
⊙
D
F
T
(
a
)
)
(
m
o
d
Φ
d
(
x
)
)
\left(a(x) \cdot z(x) \pmod{x^m-1}\right) \pmod{\Phi_d(x)} = DFT^{-1}\left( \dfrac{1}{m}DFT(z) \odot DFT(a) \right) \pmod{\Phi_d(x)}
(a(x)⋅z(x)(modxm−1))(modΦd(x))=DFT−1(m1DFT(z)⊙DFT(a))(modΦd(x))
然而,我们的 RGSW 累加器(用同态乘法实现指数上的算术加法)难以计算数乘。DFT 可以在明文下预处理,然而 InvDFT 必须在密文下同态计算。但是让 R E G ( x ˉ i ) REG(\bar x_i) REG(xˉi) 和 ζ m − i k ∈ C \zeta_m^{-ik} \in \mathbb C ζm−ik∈C 数乘,显然不是什么好主意。
[MS18] 使用 Nussbaumer Transform 来解决这个问题。它使用了更加代数化的语言,描述 Nussbaumer 的映射过程。给定
m
∣
d
m|d
m∣d 都是素数
p
≥
2
p \ge 2
p≥2 的幂次,并且满足
d
≥
p
m
2
d\ge pm^2
d≥pm2(为了使得
p
m
∣
d
/
m
pm\mid d/m
pm∣d/m 次本原根落在
R
d
/
m
R_{d/m}
Rd/m 内),简记
r
=
ϕ
(
d
/
m
)
=
ϕ
(
d
)
/
m
r=\phi(d/m)=\phi(d)/m
r=ϕ(d/m)=ϕ(d)/m,那么单变元
(
x
)
(x)
(x) 的多项式,可以映射为双变元
(
x
,
y
=
x
m
)
(x,y=x^m)
(x,y=xm) 的多项式。确切地,映射为(其实就只是一种表示而已,不需要实际的映射/置换),
ψ
:
R
d
,
q
→
R
d
/
m
,
q
[
x
]
/
(
x
m
−
y
)
a
(
x
)
=
∑
i
=
0
ϕ
(
d
)
a
i
x
i
↦
a
(
x
,
y
)
=
∑
j
=
0
m
−
1
(
∑
i
=
0
r
−
1
a
m
i
+
j
y
i
)
x
j
\begin{array}{crcl} \psi:& R_{d,q} &\to& R_{d/m,q}[x]/(x^m-y)\\ & a(x)=\sum_{i=0}^{\phi(d)}a_ix^i &\mapsto& a(x,y)=\sum_{j=0}^{m-1}\left(\sum_{i=0}^{r-1}a_{mi+j}y^i\right)x^j \end{array}
ψ:Rd,qa(x)=∑i=0ϕ(d)aixi→↦Rd/m,q[x]/(xm−y)a(x,y)=∑j=0m−1(∑i=0r−1ami+jyi)xj
其中 a ( j ) ( y ) : = ∑ i = 0 r − 1 a m i + j y i ∈ Z q [ y ] / ( Φ d / m ( y ) ) a_{(j)}(y) := \sum_{i=0}^{r-1}a_{mi+j}y^i \in \mathbb Z_q[y]/(\Phi_{d/m}(y)) a(j)(y):=∑i=0r−1ami+jyi∈Zq[y]/(Φd/m(y)),由于 x x x 是 d d d 次本原单位根,因此 y = x m ∈ R m , q y=x^m \in R_{m,q} y=xm∈Rm,q 是 d / m d/m d/m 次本原单位根。
为了快速计算多项式乘法,我们试图对 a ( x , y ) a(x,y) a(x,y) 做关于 R d / m , q [ x ] / ( x p m − 1 ) R_{d/m,q}[x]/(x^{pm}-1) Rd/m,q[x]/(xpm−1) 的 DFT(简单的 Lift,两个关于 x x x 的次数至多为 m − 1 m-1 m−1 的多项式,乘积的次数不会越过 p m − 1 pm-1 pm−1,因此计算正确),那么就需要 p m pm pm 次本原单位根,而恰好 y d / ( p m 2 ) ∈ R d / m , q y^{d/(pm^2)} \in R_{d/m,q} yd/(pm2)∈Rd/m,q 就是!因此,DFT 中的关于本原根的大环中的数乘运算,完全的转化为了小环中的多项式旋转(寄存器加密了小环元素的 Z 2 n \mathbb Z_{2n} Z2n 上系数,并且 Φ d / m ( y ) \Phi_{d/m}(y) Φd/m(y) 是稀疏 { 0 , 1 } \{0,1\} {0,1} 系数的,因此系数旋转就是少量的减法)
现在我们整理下 a ⋅ s ∈ R d a \cdot s \in R_d a⋅s∈Rd 的计算流程:
- 秘钥 s ∈ R d s \in R_d s∈Rd 是关于 x x x 的度数 ϕ ( d ) − 1 \phi(d)-1 ϕ(d)−1 单变元多项式,经过映射 ψ ( s ) ∈ R d / m [ x ] / ( x m − y ) \psi(s) \in R_{d/m}[x]/(x^m-y) ψ(s)∈Rd/m[x]/(xm−y) 得到了关于 x x x 的度数 m − 1 m-1 m−1 且关于 y y y 的度数 r − 1 r-1 r−1 的双变元多项式
- 关于变元 x x x,预计算 f = 1 m D F T ( ψ ( s ) ) f = \dfrac{1}{m}DFT(\psi(s)) f=m1DFT(ψ(s)),所使用的本原根是 y d / ( p m 2 ) ∈ R d / m y^{d/(pm^2)} \in R_{d/m} yd/(pm2)∈Rd/m,其中的 ψ ( s ) \psi(s) ψ(s) 被提升到了 R d / m [ x ] / ( x p m − 1 ) R_{d/m}[x]/(x^{pm}-1) Rd/m[x]/(xpm−1) 上
- 将向量 f f f 按照各个系数(落在环 R d / m R_{d/m} Rd/m 中)分别加密到 RGSW 密文(二进制分解的冗余累加器,可计算加/减法和数乘),简记为 [ E ( 2 j f k ) ] k , j [E(2^j f_k)]_{k,j} [E(2jfk)]k,j,每个 E ( 2 j f k ) E(2^j f_k) E(2jfk) 实际包含了小环 R d / m R_{d/m} Rd/m 中的 r r r 个系数 f k , i f_{k,i} fk,i 的密文
- 类似地,密文 a ∈ R d a \in R_d a∈Rd 作为常数(因此 s , a s,a s,a 的 DFT 都不是同态计算的),计算出 a ˉ i = D F T ( ψ ( a ) ) i \bar a_i=DFT(\psi(a))_i aˉi=DFT(ψ(a))i
- 使用二进制分解手段,将 a ˉ i \bar a_i aˉi 数乘 f i f_i fi 转化为:使用 a i j a_{ij} aij 挑选 E ( 2 j f k ) E(2^jf_k) E(2jfk),共计算 p m pm pm 个 R d / m R_{d/m} Rd/m 上的数乘,获得了 c ˉ : = 1 m D F T ( ψ ( z ) ) ⊙ D F T ( ψ ( a ) ) \bar c :=\dfrac{1}{m}DFT(\psi(z)) \odot DFT(\psi(a)) cˉ:=m1DFT(ψ(z))⊙DFT(ψ(a))
- 现在,我们执行 InvDFT 操作,简单按照公式 c k = ∑ i = 0 m − 1 c ˉ i ζ m − i k c_k=\sum_{i=0}^{m-1} \bar c_i \zeta_m^{-ik} ck=∑i=0m−1cˉiζm−ik 来计算即可(不要使用 FFT/NTT,多层迭代导致了无法利用 GSW 的不对称噪声增长特性),其中的数乘 ζ m − i k \zeta_m^{-ik} ζm−ik 就是在小环 R d / m R_{d/m} Rd/m 中旋转系数向量(需要模掉 Φ d / m ( y ) \Phi_{d/m}(y) Φd/m(y),它仅包含 p p p 项非零,因此通过稀疏的减法来实现)。
- 现在我们得到了 c : = ψ ( z ) ⋅ ψ ( a ) ∈ R d / m [ x ] / ( x p m − 1 ) c:=\psi(z) \cdot \psi(a) \in R_{d/m}[x]/(x^{pm}-1) c:=ψ(z)⋅ψ(a)∈Rd/m[x]/(xpm−1) 的(各个系数的系数)密文,把它同态的模掉 ( x m − y ) (x^m-y) (xm−y) 得到 ψ ( z ⋅ a ) ∈ R d / m [ x ] / ( x m − y ) \psi(z \cdot a) \in R_{d/m}[x]/(x^m-y) ψ(z⋅a)∈Rd/m[x]/(xm−y),它其实就是 z ⋅ a ∈ R d z \cdot a \in R_d z⋅a∈Rd
Ring Decrypt
我们选取三的幂次的分园环,设置
d
=
3
k
d=3^k
d=3k,令
m
=
d
ϵ
=
3
ϵ
k
m=d^{\epsilon}=3^{\epsilon k}
m=dϵ=3ϵk 满足
d
≥
3
m
2
d \ge 3m^2
d≥3m2,简记
r
=
ϕ
(
d
/
m
)
=
ϕ
(
d
1
−
ϵ
)
r=\phi(d/m)=\phi(d^{1-\epsilon})
r=ϕ(d/m)=ϕ(d1−ϵ),那么密文
(
a
,
b
)
∈
R
L
W
E
z
t
/
2
n
(a,b) \in RLWE^{t/2n}_z
(a,b)∈RLWEzt/2n 的 Nussbaumer 转换为:
ψ
:
R
d
,
2
n
→
R
d
/
m
,
2
n
[
x
]
/
(
x
m
−
y
)
\psi: R_{d,2n} \to R_{d/m,2n}[x]/(x^m-y)
ψ:Rd,2n→Rd/m,2n[x]/(xm−y)
其中 ζ 3 m : = y d / ( 3 m 2 ) ∈ R d / m , 2 n \zeta_{3m}:=y^{d/(3m^2)} \in R_{d/m,2n} ζ3m:=yd/(3m2)∈Rd/m,2n 是 3 m 3m 3m 次本原单位根
同态线性解密的过程为:
-
我们将 a , z ∈ R d , 2 n a,z \in R_{d,2n} a,z∈Rd,2n 映射为 ψ ( a ) , ψ ( z ) ∈ R d / m , 2 n [ x ] / ( x m − y ) \psi(a),\psi(z) \in R_{d/m,2n}[x]/(x^m-y) ψ(a),ψ(z)∈Rd/m,2n[x]/(xm−y)
-
然后将 ψ ( a ) , ψ ( z ) \psi(a),\psi(z) ψ(a),ψ(z) 提升到 R d / m , 2 n [ x ] / ( x 3 m − 1 ) R_{d/m,2n}[x]/(x^{3m}-1) Rd/m,2n[x]/(x3m−1),现在可以对 ψ ( a ) , ψ ( z ) \psi(a),\psi(z) ψ(a),ψ(z) 执行 DFT/InvDFT
-
我们定义私钥在 DFT 域的二的幂次,
f ( z ) = ( 1 , 2 , 4 , ⋯ , 2 l − 1 ) ⊗ [ 1 3 ⋅ D F T ( ψ ( z ) ) i ] i ∈ [ 3 m ] ∈ R d / m , 2 n l × 3 m f(z)=(1,2,4,\cdots,2^{l-1}) \otimes \left[\dfrac{1}{3}\cdot DFT(\psi(z))_i\right]_{i \in [3m]} \in R_{d/m,2n}^{l \times 3m} f(z)=(1,2,4,⋯,2l−1)⊗[31⋅DFT(ψ(z))i]i∈[3m]∈Rd/m,2nl×3m将它用寄存器加密为 [ [ f ( z ) ] ] [\![f(z)]\!] [[f(z)]]
-
计算 a ˉ i = D F T ( ψ ( a ) ) i \bar a_i = DFT(\psi(a))_i aˉi=DFT(ψ(a))i,然后用 SlowMult 电路 C a ˉ i ( [ [ f ( z ) ] ] ) C_{\bar a_i}([\![f(z)]\!]) Caˉi([[f(z)]]) 计算小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 上的阿达玛乘积
-
再令电路 C F C_{F} CF 是利用公式 ( a ⋅ z ) k = ∑ i = 0 3 m − 1 ( a ⋅ z ) i ‾ ζ 3 m − i k (a \cdot z)_k = \sum_{i=0}^{3m-1} \overline{(a \cdot z)_i} \zeta_{3m}^{-ik} (a⋅z)k=∑i=03m−1(a⋅z)iζ3m−ik 同态计算 InvDFT 的电路(因为 ζ 3 m ∈ R d / m , 2 n \zeta_{3m} \in R_{d/m,2n} ζ3m∈Rd/m,2n,所以只需要同态加/减法),那么计算 a ⋅ z ∈ R d , 2 n a \cdot z \in R_{d,2n} a⋅z∈Rd,2n 的电路为
[ [ a ⋅ z ] ] = C a ( [ [ f ( z ) ] ] ) : = C F ( [ C a ˉ i ( [ [ f ( z ) ] ] ) ] i ) ( m o d x m − y ) [\![a \cdot z]\!] = C_a([\![f(z)]\!]) := C_F(\left[C_{\bar a_i}([\![f(z)]\!])\right]_i) \pmod{x^m-y} [[a⋅z]]=Ca([[f(z)]]):=CF([Caˉi([[f(z)]])]i)(modxm−y) -
接着定义电路 C a , b ( [ [ f ( z ) ] ] ) = b − C a ( [ [ f ( z ) ] ] ) C_{a,b}([\![f(z)]\!])=b-C_a([\![f(z)]\!]) Ca,b([[f(z)]])=b−Ca([[f(z)]]) 是计算 b − a ⋅ z ∈ R d , 2 n b-a\cdot z \in R_{d,2n} b−a⋅z∈Rd,2n 的同态电路
我们设置 refreshing key 成为
3
m
×
l
×
r
3m \times l \times r
3m×l×r 的寄存器矩阵,
K
R
=
K
i
j
k
R
:
=
R
E
G
z
2
n
/
Q
[
1
3
m
⋅
D
F
T
(
ψ
(
z
)
)
i
,
k
⋅
2
j
,
β
R
]
i
∈
[
3
m
]
,
j
∈
[
l
]
,
k
∈
[
r
]
K^R = K_{ijk}^R := REG_z^{2n/Q}\left[\dfrac{1}{3m} \cdot DFT(\psi(z))_{i,k} \cdot 2^j,\,\, \beta_R\right]_{i \in [3m], j \in [l], k \in [r]}
KR=KijkR:=REGz2n/Q[3m1⋅DFT(ψ(z))i,k⋅2j,βR]i∈[3m],j∈[l],k∈[r]
解密算法为:
其中的
D
F
T
−
1
DFT^{-1}
DFT−1,由于
m
∣
d
m|d
m∣d 都是三的幂次,令
r
=
ϕ
(
d
)
/
m
r=\phi(d)/m
r=ϕ(d)/m,变元
y
d
/
m
=
1
y^{d/m}=1
yd/m=1,
Φ
d
/
m
(
y
)
=
y
r
+
y
r
/
2
+
1
\Phi_{d/m}(y)=y^r+y^{r/2}+1
Φd/m(y)=yr+yr/2+1
于是数乘
ζ
3
m
−
i
k
\zeta_{3m}^{-ik}
ζ3m−ik 可以表示为对
R
d
/
m
,
2
n
R_{d/m,2n}
Rd/m,2n 上的各个项
a
⋅
y
v
a\cdot y^v
a⋅yv 乘以某个
y
i
y^i
yi,然后模掉稀疏的
Φ
d
/
m
(
y
)
\Phi_{d/m}(y)
Φd/m(y)。注意:我们分别加密
R
d
/
m
,
2
n
R_{d/m,2n}
Rd/m,2n 的各个系数,成为带索引的寄存器
(
R
E
G
(
a
)
,
v
)
(REG(a), v)
(REG(a),v),而变元
y
v
y^v
yv 并不被加密,乘以
y
i
y^i
yi 就只是把系数的密文简单的置换到
y
v
+
i
y^{v+i}
yv+i 位置。模约减的公式为:
(
a
⋅
y
v
)
⋅
y
i
(
m
o
d
Φ
d
/
m
(
y
)
)
=
{
a
⋅
y
v
+
i
,
for
v
+
i
<
r
−
a
⋅
y
v
+
i
(
m
o
d
r
)
−
a
⋅
y
v
+
i
+
r
/
2
(
m
o
d
r
)
,
for
r
≤
v
+
i
<
d
/
m
a
⋅
y
v
+
i
(
m
o
d
d
/
m
)
,
for
v
+
i
≥
d
/
m
(a\cdot y^v) \cdot y^i \pmod{\Phi_{d/m}(y)} = \left\{\begin{array}{l} a\cdot y^{v+i},& \text{for } v+i<r\\ -a\cdot y^{v+i\pmod{r}} - a\cdot y^{v+i+r/2\pmod{r}},& \text{for } r\le v+i<d/m\\ a\cdot y^{v+i\pmod{d/m}},& \text{for } v+i\ge d/m\\ \end{array}\right.
(a⋅yv)⋅yi(modΦd/m(y))=⎩
⎨
⎧a⋅yv+i,−a⋅yv+i(modr)−a⋅yv+i+r/2(modr),a⋅yv+i(modd/m),for v+i<rfor r≤v+i<d/mfor v+i≥d/m
复杂度分析:
-
朴素的 InvDFT 共计花费 ( 3 m ) 2 (3m)^2 (3m)2 次小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 的元素与 ζ 3 m − i k \zeta_{3m}^{-ik} ζ3m−ik 的数乘,每个数乘(旋转系数)的开销是 O ( r ) O(r) O(r) 次减法,共计 O ( ( 3 m ) 2 r ) O((3m)^2r) O((3m)2r) 次减法
-
在 SlowMult 步骤,执行了 3 m 3m 3m 个小环 R d / m , 2 n R_{d/m,2n} Rd/m,2n 上的常数乘法,每个数乘(子集加和)开销是 O ( r 2 ⋅ l ) O(r^2 \cdot l) O(r2⋅l) 次加法,共计 O ( 3 m r 2 l ) O(3mr^2l) O(3mr2l) 个加法
-
其他运算的计算复杂度都很低
假设
d
=
3
k
d=3^k
d=3k,由于
d
>
3
m
2
d>3m^2
d>3m2,可推出
ϵ
≤
1
2
−
1
2
k
\epsilon \le \frac{1}{2} - \frac{1}{2k}
ϵ≤21−2k1,因此 RingDecrypt 的(关于 REG 同态加/减法)总复杂度为:
O
(
(
3
m
)
2
r
+
3
m
r
2
l
)
=
O
~
(
d
1
+
ϵ
+
d
2
−
ϵ
)
=
O
~
(
d
2
−
ϵ
)
O((3m)^2r + 3mr^2l) = \tilde O(d^{1+\epsilon} + d^{2-\epsilon}) = \tilde O(d^{2-\epsilon})
O((3m)2r+3mr2l)=O~(d1+ϵ+d2−ϵ)=O~(d2−ϵ)
于是选取
m
≈
d
,
ϵ
≈
0.5
m \approx \sqrt d, \epsilon \approx 0.5
m≈d,ϵ≈0.5 将会导致更好的性能。它输出了
ϕ
(
d
)
\phi(d)
ϕ(d) 个寄存器
R
E
G
z
2
n
/
Q
[
m
~
i
,
β
′
]
REG^{2n/Q}_z[\tilde m_i, \beta']
REGz2n/Q[m~i,β′],噪声界为
β
′
=
O
~
(
β
R
B
g
4
⋅
(
n
d
g
)
3.5
⋅
d
ϵ
+
0.5
)
\beta' = \tilde O(\beta_R B_g^4 \cdot (nd_g)^{3.5}\cdot d^{\epsilon+0.5})
β′=O~(βRBg4⋅(ndg)3.5⋅dϵ+0.5)
它与原始 LWE 密文的噪声无关,仅依赖于自举秘钥 K R K^R KR 的噪声 β R \beta_R βR
MSB Extract
现在我们获得了 ϕ ( d ) \phi(d) ϕ(d) 个寄存器 R E G z 2 n / Q [ m ~ i , β ′ ] REG^{2n/Q}_z[\tilde m_i, \beta'] REGz2n/Q[m~i,β′],类似于 FHEW 那样从寄存器第一分量 R G S W z 2 n / Q ( u ⋅ Y m ~ i ) RGSW^{2n/Q}_z(u \cdot Y^{\tilde m_i}) RGSWz2n/Q(u⋅Ym~i) 中提取出 R L W E z 2 n / Q ( u ⋅ Y m ~ i ) RLWE^{2n/Q}_z(u \cdot Y^{\tilde m_i}) RLWEz2n/Q(u⋅Ym~i),其中的 m ~ i = n ⋅ m i ∈ Z 2 n \tilde m_i = n\cdot m_i \in \mathbb Z_{2n} m~i=n⋅mi∈Z2n
使用这个 RLWE 密文,作用于舍入函数(反循环函数)的 Lookup Table,提取出 m i ∈ Z 4 m_i \in \mathbb Z_4 mi∈Z4 的 LWE 密文,编码倍率为 2 u = Q / 4 2u=Q/4 2u=Q/4
简记 ( ( z ) ) (\!\!(z)\!\!) ((z)) 是多项式 z ∈ R d , 2 n z \in R_{d,2n} z∈Rd,2n 的系数向量,密文提取算法为:
现在的密文是 L W E ϕ ( d ) 4 / Q LWE^{4/Q}_{\phi(d)} LWEϕ(d)4/Q,我们还应当执行密钥-维度-模数切换,回到本来的 L W E n 4 / q LWE^{4/q}_n LWEn4/q 上。
Refreshing
综合上述的技术,我们就得到了亚线性(均摊)复杂度的自举方案。给定 packing key K P K^P KP 和 refreshing key K R K^R KR,批处理的自举算法的具体步骤如下:
它的计算复杂度和噪声增长为:
Recursive optimization
可以递归地使用 Nussbaumer 转换,每层的每个小环元素拆分出 m m m 个更小的环元素。对于固定的 ϵ \epsilon ϵ,确定某个递归深度 ρ \rho ρ,使得 Z 2 n [ y ′ ] / Φ d / m ρ ( y ′ ) \mathbb Z_{2n}[y']/\Phi_{d/m^\rho}(y') Z2n[y′]/Φd/mρ(y′) 中存在 3 m 3m 3m 次本原单位根。这要求 d / m ρ ≥ 3 m d/m^\rho \ge 3m d/mρ≥3m,其中 m = d ϵ m=d^\epsilon m=dϵ,求出最大深度为 ρ < 1 / ϵ − 1 \rho < 1/\epsilon-1 ρ<1/ϵ−1
迭代方式的计算效率更高,但是噪声增长也更快:
在最优参数下复杂度为 O ~ ( d 1 + ϵ ) \tilde O(d^{1+\epsilon}) O~(d1+ϵ),批处理 ϕ ( d ) = O ( d ) \phi(d)=O(d) ϕ(d)=O(d) 个 LWE 密文的均摊成本仅为 O ~ ( d ϵ ) \tilde O(d^{\epsilon}) O~(dϵ)