参考文献:
- [HS13] Halevi S, Shoup V. Design and implementation of a homomorphic-encryption library[J]. IBM Research (Manuscript), 2013, 6(12-15): 8-36.
- [BEHZ16] Bajard J C, Eynard J, Hasan M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[C]//International Conference on Selected Areas in Cryptography. Cham: Springer International Publishing, 2016: 423-442.
- [CHKKS18a] Cheon J H, Han K, Kim A, et al. A full RNS variant of approximate homomorphic encryption[C]//Selected Areas in Cryptography–SAC 2018: 25th International Conference, Calgary, AB, Canada, August 15–17, 2018, Revised Selected Papers 25. Springer International Publishing, 2019: 347-368.
- [CHKKS18b] Cheon J H, Han K, Kim A, et al. Bootstrapping for approximate homomorphic encryption[C]//Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part I 37. Springer International Publishing, 2018: 360-384.
- [CHH18] Cheon J H, Han K, Hhan M. Faster homomorphic discrete fourier transforms and improved fhe bootstrapping[J]. Cryptology ePrint Archive, 2018.
- [HS18] Halevi S, Shoup V. Faster homomorphic linear transformations in HElib[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2018: 93-120.
- [CCS19] Chen H, Chillotti I, Song Y. Improved bootstrapping for approximate homomorphic encryption[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2019: 34-54.
- [HK20] Han K, Ki D. Better bootstrapping for approximate homomorphic encryption[C]//Cryptographers’ Track at the RSA Conference. Cham: Springer International Publishing, 2020: 364-390.
- [BMTH21] Bossuat J P, Mouchet C, Troncoso-Pastoriza J, et al. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2021: 587-617.
文章目录
- RNS-CKKS
- Fast Base Conversion
- Approximate Modulus Switching
- Full RNS Variant CKKS
- Efficient Bootstrapping with Non-Sparse Keys
- Improved Key-switch
- Improved Hoisted-Rotations
- Double-hoisting BSGS algorithm
- Bootstrapping for RNS-CKKS
RNS-CKKS
[CHKKS18a] 提出了 CKKS 的 RNS 变体。
Fast Base Conversion
一般地 FHE 需要很大的模数 Q Q Q,将它写作 Q = ∏ i = 1 L q i Q=\prod_{i=1}^L q_i Q=∏i=1Lqi,满足 q i = 1 ( m o d 2 N ) q_i=1\pmod{2N} qi=1(mod2N),我们简记 Q i = q 1 ⋯ q i Q_i=q_1\cdots q_i Qi=q1⋯qi,集合 { q i } \{q_i\} {qi} 称为 RNS Base,它们的大小至多为 64 64 64 比特。我们希望 FHE 的全部运算都是单精度的(现代计算机的机器字),也就是全部运算都在 RNS 下完成,而不需要多精度算术。
[BEHZ16] 提出了可以在不同的 RNS(扩展到新的 RNS Base 对应的系数)之间快速转换的算法。将环元素
a
∈
R
Q
a \in \mathcal R_Q
a∈RQ 从模数
Q
=
q
1
⋯
q
l
Q=q_1\cdots q_l
Q=q1⋯ql 下的
[
a
]
Q
[a]_Q
[a]Q 转换到模数
P
=
p
1
⋯
p
k
P=p_1\cdots p_k
P=p1⋯pk 下的
[
[
a
]
Q
]
P
[[a]_Q]_P
[[a]Q]P,可以直接在 RNS 下计算:
FastBaseExt
(
a
,
Q
,
P
)
=
{
∑
i
=
1
l
[
a
⋅
(
Q
q
i
)
−
1
]
q
i
⋅
Q
q
i
(
m
o
d
p
j
)
}
j
=
1
,
⋯
,
k
\text{FastBaseExt}(a,Q,P) = \left\{ \sum_{i=1}^l \left[ a \cdot \left(\dfrac{Q}{q_i}\right)^{-1} \right]_{q_i} \cdot \dfrac{Q}{q_i} \pmod{p_j} \right\}_{j=1,\cdots,k}
FastBaseExt(a,Q,P)=⎩
⎨
⎧i=1∑l[a⋅(qiQ)−1]qi⋅qiQ(modpj)⎭
⎬
⎫j=1,⋯,k
我们简记
q
i
∗
:
=
Q
/
q
i
q_i^*:=Q/q_i
qi∗:=Q/qi 和
q
~
i
:
=
(
Q
/
q
i
)
−
1
(
m
o
d
q
i
)
\tilde q_i:=(Q/q_i)^{-1} \pmod{q_i}
q~i:=(Q/qi)−1(modqi),满足
q
i
∗
⋅
q
~
i
≡
1
(
m
o
d
q
i
)
q_i^* \cdot \tilde q_i\equiv 1 \pmod{q_i}
qi∗⋅q~i≡1(modqi),那么根据 CRT 合成定理,转换的结果是:
∑
i
[
a
⋅
q
~
i
]
q
i
⋅
q
i
∗
=
[
a
]
Q
+
u
⋅
Q
∈
Z
\sum_i [a\cdot \tilde q_i]_{q_i} \cdot q_i^* = [a]_Q + u \cdot Q \in \mathbb Z
i∑[a⋅q~i]qi⋅qi∗=[a]Q+u⋅Q∈Z
其中的
∥
u
∥
∞
≤
l
/
2
\|u\|_\infty \le l/2
∥u∥∞≤l/2(采用中心化的取模运算)称为
Q
Q
Q-overflow,因此算法
FastBaseExt
(
a
,
Q
,
P
)
\text{FastBaseExt}(a,Q,P)
FastBaseExt(a,Q,P) 输出的只是
[
[
a
]
Q
]
P
[[a]_Q]_P
[[a]Q]P 的近似值
[
[
a
]
Q
+
u
⋅
Q
]
P
[[a]_Q + u \cdot Q]_P
[[a]Q+u⋅Q]P
后续 [HPS19] 给出了纠正错误 u u u 的浮点数算法,不过在 [CHKKS18a] 中并不需要纠错,因为 CKKS 本身就是近似计算的。
特别地,如果 Q = q Q=q Q=q 是单个素数,那么 q ∗ = q ~ = 1 q^*=\tilde q=1 q∗=q~=1,从而就有 FastBaseExt ( a , q , P ) = { [ a ] q ( m o d p j ) } j \text{FastBaseExt}(a,q,P)=\{[a]_{q} \pmod{p_j}\}_j FastBaseExt(a,q,P)={[a]q(modpj)}j,并且 u = 0 u=0 u=0 没有错误。这个特例被用于 CKKS 的相邻模数之间的 RS 过程:输入 a ∈ R Q l a \in R_{Q_l} a∈RQl 的 RNS 表示,那么 [ q l − 1 ⋅ ( [ a ] q j − [ a ] q l ) ] q j , ∀ 0 ≤ j < l [q_l^{-1} \cdot ([a]_{q_j}-[a]_{q_l})]_{q_j}, \forall 0\le j<l [ql−1⋅([a]qj−[a]ql)]qj,∀0≤j<l 就是 ⌊ a / q l ⌉ ∈ R Q l − 1 \lfloor a/q_l\rceil \in R_{Q_{l-1}} ⌊a/ql⌉∈RQl−1 的 RNS 表示。
Approximate Modulus Switching
原始的 CKKS 的模数链,形如 Q l = q 0 ⋅ q l Q_l = q_0 \cdot q^l Ql=q0⋅ql,其中 q q q 是某个固定的 Base(例如 q = 2 q=2 q=2)。显然它与 RNS 不兼容,因此无法使用 Double-CRT 来加速(multi-precision FFT 的速度很慢)
[CHKKS18a] 提出了 Approximate Base 解决这个问题,代价是引入了额外的舍入误差。我们选取 C = { q 0 , q 1 , ⋯ , q L } \mathcal C = \{q_0,q_1,\cdots,q_L\} C={q0,q1,⋯,qL},满足 q j / q ∈ ( 1 − 2 − η , 1 + 2 − η ) , ∀ j = 1 , ⋯ , L q_j/q \in (1-2^{-\eta},1+2^{-\eta}),\forall j=1,\cdots,L qj/q∈(1−2−η,1+2−η),∀j=1,⋯,L(注意最底层的 q 0 q_0 q0 不需要),同时它们都是 NTT-friendly 的素数。定义 Q l = ∏ i = 0 l q l Q_l=\prod_{i=0}^l q_l Ql=∏i=0lql 是模数链,于是相邻的模数的比值都接近 q q q,利用 RNS Base 之间的转换,将 m m m 缩放为 q l − 1 ⋅ m q_l^{-1} \cdot m ql−1⋅m 的误差为 2 − η ⋅ ∣ q l − 1 ⋅ m ∣ 2^{-\eta} \cdot |q_l^{-1} \cdot m| 2−η⋅∣ql−1⋅m∣,应当使得 η \eta η 充分大(所以 q q q 也不会很小)。
模切换过程(提升、约简)会出现在同态乘法(之前、之后)以及秘钥切换(GHS、Hybrid)中,一般化地表示出: D = { p 0 , ⋯ , p k − 1 , q 0 , ⋯ , q l − 1 } \mathcal D = \{p_0,\cdots,p_{k-1},q_0,\cdots,q_{l-1}\} D={p0,⋯,pk−1,q0,⋯,ql−1},它分为两个子集 B = { p i } \mathcal B=\{p_i\} B={pi} 和 C = { q j } \mathcal C=\{q_j\} C={qj},设置对应的模数 P = ∏ i p i P=\prod_i p_i P=∏ipi 以及 Q = ∏ j Q j Q=\prod_j Q_j Q=∏jQj
Modulus Raising:输入 a ∈ Z Q a \in \mathbb Z_{Q} a∈ZQ 的 RNS 表示,输出 a ~ ∈ Z P Q \tilde a \in \mathbb Z_{PQ} a~∈ZPQ 的 RNS 表示,满足 a ≡ a ~ m o d Q a \equiv \tilde a \bmod Q a≡a~modQ 以及 ∣ a ~ ∣ ≪ P Q |\tilde a| \ll PQ ∣a~∣≪PQ(不需要具有相同的整数代表)
根据 Fast Base Conversion 的结果,它的 overflow 规模仅为
l
/
2
≪
P
l/2 \ll P
l/2≪P,因此获得的
[
a
+
u
⋅
Q
]
P
[a + u \cdot Q]_P
[a+u⋅Q]P 级联原本的
[
a
]
Q
[a]_Q
[a]Q,就得到了满足要求的
[
a
~
]
P
Q
[\tilde a]_{PQ}
[a~]PQ,用 CRT 验证一下:
a
~
=
Q
[
Q
−
1
]
P
⋅
[
a
+
u
Q
]
P
+
P
[
P
−
1
]
Q
⋅
[
a
]
Q
=
Q
[
Q
−
1
]
P
⋅
(
a
+
u
Q
+
v
P
)
+
P
[
P
−
1
]
Q
⋅
(
a
+
w
Q
)
=
(
Q
[
Q
−
1
]
P
+
P
[
P
−
1
]
Q
)
⋅
a
+
u
Q
2
[
Q
−
1
]
P
=
a
+
u
Q
⋅
(
t
P
+
1
)
=
a
+
u
Q
(
m
o
d
P
Q
)
\begin{aligned} \tilde a &= Q[Q^{-1}]_P \cdot [a+uQ]_P + P[P^{-1}]_Q \cdot [a]_Q\\ &= Q[Q^{-1}]_P \cdot(a+uQ+vP) + P[P^{-1}]_Q \cdot (a+wQ)\\ &= (Q[Q^{-1}]_P + P[P^{-1}]_Q) \cdot a + uQ^2[Q^{-1}]_P\\ &= a+uQ \cdot (tP+1)\\ &= a+uQ \pmod{PQ} \end{aligned}
a~=Q[Q−1]P⋅[a+uQ]P+P[P−1]Q⋅[a]Q=Q[Q−1]P⋅(a+uQ+vP)+P[P−1]Q⋅(a+wQ)=(Q[Q−1]P+P[P−1]Q)⋅a+uQ2[Q−1]P=a+uQ⋅(tP+1)=a+uQ(modPQ)
算法如下,
Modulus Reduction:输入 b ~ ∈ Z P Q \tilde b \in \mathbb Z_{PQ} b~∈ZPQ 的 RNS 表示,输出 b ∈ Z Q b \in \mathbb Z_{Q} b∈ZQ 的 RNS 表示,满足 b ≈ P − 1 ⋅ b ~ b \approx P^{-1} \cdot \tilde b b≈P−1⋅b~(不需要等于实数除法的舍入)
由于 RNS 系统中无法计算带余除法,因此应当转化为整除法。我们简单从 b ~ \tilde b b~ 的 RNS 表示中截取出 [ b ~ ] P [\tilde b]_P [b~]P,然后利用 Fast Base Conversion 扩展出 [ [ b ~ ] P + u P ] Q [[\tilde b]_P + uP]_Q [[b~]P+uP]Q 部分,那么两者的级联就是 [ [ b ~ ] P + u P ] P Q [[\tilde b]_P + uP]_{PQ} [[b~]P+uP]PQ,将它从原本的 b ~ \tilde b b~ 中减掉。由于 ∣ ∣ u ∣ ∣ ∞ ≤ k / 2 ≪ Q ||u||_\infty \le k/2 \ll Q ∣∣u∣∣∞≤k/2≪Q,这就满足了要求:
b
~
−
[
b
~
]
P
+
u
P
=
P
⋅
(
⌊
b
~
/
P
⌉
+
u
)
\tilde b - [\tilde b]_P + uP = P \cdot \big(\lfloor\tilde b/P\rceil + u\big)
b~−[b~]P+uP=P⋅(⌊b~/P⌉+u)
算法如下,
无论是 Modulus Raising 还是 Modulus Reduction,结果中都带有错误 u u u,这是近似的模切换。按照 word operation 为计算单位, C o n v B → C Conv_{B\to C} ConvB→C 和 C o n v C → B Conv_{C\to B} ConvC→B 的复杂度都是 O ( k ⋅ l ) O(k \cdot l) O(k⋅l), M o d U p C → D ModUp_{C \to D} ModUpC→D 的复杂度为 O ( k ⋅ l ) O(k \cdot l) O(k⋅l), M o d D o w n D → C ModDown_{D \to C} ModDownD→C 的复杂度为 O ( k ⋅ l + l ) O(k \cdot l+l) O(k⋅l+l)
Full RNS Variant CKKS
现在我们可以将原始的 CKKS 转化到 Full-RNS 版本。采用 [BMTH21] 的算法描述,我们可以将 Key-Switch 作为一个通用的中间模块,它的 KSK-Gen 可用于所有 pk 的生成,KS 过程作用在单个环元素上。采取 Hybrid 版本(BV 效率太低,GHS 有安全损失),设置 w = [ q i ∗ ⋅ q ~ i ] i ( m o d Q ) w = [q_i^* \cdot \tilde q_i]_i \pmod Q w=[qi∗⋅q~i]i(modQ) 是 RNS Base(二进制分解与 RNS 不兼容),对于 ∀ d ∈ R \forall d \in R ∀d∈R 满足线性运算 d = ∑ i [ d ] q i ⋅ w i ( m o d Q ) d=\sum_i [d]_{q_i} \cdot w_i \pmod Q d=∑i[d]qi⋅wi(modQ)。当然,对于每个分量 [ d ] q i [d]_{q_i} [d]qi 可以进一步采用二进制分解,用更高的计算复杂度换取更小的噪声。
对于二的幂次
N
≥
8
N\ge8
N≥8,总是有
Z
N
∗
=
(
5
,
−
1
)
\mathbb Z_N^* = (5,-1)
ZN∗=(5,−1),因此
5
5
5 是循环乘法群
Z
N
∗
/
(
−
1
)
\mathbb Z_N^*/(-1)
ZN∗/(−1) 的生成元。令
K
=
Q
[
X
]
/
(
X
N
+
1
)
K=\mathbb Q[X]/(X^N+1)
K=Q[X]/(XN+1) 是分圆数域,它的典范嵌入
σ
:
a
(
X
)
↦
[
a
(
ζ
)
,
a
(
ζ
3
)
,
⋯
,
a
(
ζ
2
N
−
1
)
]
\sigma: a(X) \mapsto [a(\zeta),a(\zeta^3),\cdots,a(\zeta^{2N-1})]
σ:a(X)↦[a(ζ),a(ζ3),⋯,a(ζ2N−1)] 可以稍稍扭曲为
τ
:
a
(
X
)
↦
[
a
(
ζ
)
,
a
(
ζ
5
)
,
a
(
ζ
25
)
,
⋯
]
\tau: a(X) \mapsto [a(\zeta),a(\zeta^5),a(\zeta^{25}),\cdots]
τ:a(X)↦[a(ζ),a(ζ5),a(ζ25),⋯]
将它用于 SIMD 编码函数,那么自同构
X
↦
X
5
X \mapsto X^5
X↦X5(所生成的循环子群)可用于自然的槽旋转,剩下的一个非凡的自同构
X
↦
X
−
1
X \mapsto X^{-1}
X↦X−1 用于槽的复共轭。利用 KSK-Gen 生成对应的 KSK,当然 CKKS 的明文槽非常多(均摊自举比 BGV/BFV 快的多,甚至比 TFHE 还快),采取 [HS13] 的有向图路径分解的思路,可以有效减少存储开销。
RNS-CKKS 的同态运算的基本单元都是 word operation,不会出现 Multi-percision 表示,其中的乘法是在 DCRT 表示下计算的,而 RS、KS 则是在 RNS 表示下计算的,因此 NTT/INTT 占据了主要的开销。按照 [CHKKS18a] 的描述,使用 GHS 版本的重线性化、不追踪缩放因子,具体的算法为:
根据 [CHKKS18a],在某参数集下 RNS-CKKS 的各个功能的计算速度都大约提升了 10 倍。由于原始的基 q q q 和近似基 q j q_j qj 之间的差距,RNS-CKKS 的计算精度降低了 3 比特。可以利用 ( Q l , Δ ) (Q_l,\Delta) (Ql,Δ) 等标签追踪各个密文的实际缩放因子(根据所做的运算不同,相同 level 的密文的 Δ \Delta Δ 不一定相同),来消除这个精度损失。按照 [BMTH21],同态运算的 API 形如:
Efficient Bootstrapping with Non-Sparse Keys
[BMTH21] 提出了目前最快的 RNS-CKKS 自举算法,主要贡献是改进了:切比雪夫基下多项式求值的 BSGS 算法、明文槽线性变换的 BSGS 算法。前者是对噪声的优化,使得两个相加的密文总是具有恰好相同的缩放因子,因此消除了统一缩放因子时的近似噪声;后者是对 [HS18] 的进一步优化,将公共的运算提取合并在一起。自举算法还是按照 [CHKKS18b] 的框架,混合使用 [CHH18] [CCS19] 的 FFT-like 稀疏分解以及所改进的 BSGS 算法,对于不同的参数分别使用 [CCS19] 和 [HK20] 的同态取模算法。[BMTH21] 的自举算法支持稠密秘密,而之前的都仅考虑稀疏秘密。
Improved Key-switch
Mult 和 Rotation 都是依赖于 KS 过程的,[BMTH21] 采用了 Hybrid 版本。由于 RNS 系统中的素数较多,导致 RNS 分解后的 KSK 规模变大。可以类似于 [HS13] 将若干个素数合并为 digit,减小 RNS 向量的长度。
原本的 RNS Base 是素数集合 B = { q 0 , q 1 , ⋯ , q L } \mathcal B = \{q_0,q_1,\cdots,q_L\} B={q0,q1,⋯,qL},选取合适的 α \alpha α 和 β = ⌈ ( L + 1 ) / α ⌉ \beta=\lceil(L+1)/\alpha\rceil β=⌈(L+1)/α⌉,设置 q α , i = ∏ j = α i min ( α ( i + 1 ) − 1 , L ) q j q_{\alpha,i} = \prod_{j=\alpha i}^{\min(\alpha(i+1)-1,L)} q_j qα,i=∏j=αimin(α(i+1)−1,L)qj 是第 i i i 个长度 α \alpha α 区间的素数的乘积,那么 C = { q α , 0 , ⋯ , q α , β − 1 } \mathcal C = \{q_{\alpha,0},\cdots, q_{\alpha,\beta-1}\} C={qα,0,⋯,qα,β−1} 依旧是 Q L Q_L QL 的一组 RNS Base
我们设置
q
α
,
i
∗
=
Q
L
/
q
α
,
i
q_{\alpha,i}^*=Q_L/q_{\alpha,i}
qα,i∗=QL/qα,i 以及
q
~
α
,
i
=
q
α
,
i
−
1
(
m
o
d
q
α
,
i
)
\tilde q_{\alpha,i} = q_{\alpha,i}^{-1} \pmod{q_{\alpha,i}}
q~α,i=qα,i−1(modqα,i),那么
w
i
=
q
α
,
i
∗
q
~
α
,
i
,
0
≤
i
<
β
w_i=q_{\alpha,i}^* \tilde q_{\alpha,i}, 0 \le i<\beta
wi=qα,i∗q~α,i,0≤i<β 可以作为 RNS 分解向量。选取足够大的特殊素数
P
=
∏
j
=
0
α
−
1
p
j
P=\prod_{j=0}^{\alpha-1} p_j
P=∏j=0α−1pj 满足
P
≥
q
α
,
i
,
∀
i
P \ge q_{\alpha,i}, \forall i
P≥qα,i,∀i,将它用于 KS 过程的噪声控制。对应的 KSK 规模缩小了约
α
\alpha
α 倍(但是
P
P
P 增大了),
(
s
w
k
i
0
,
s
w
k
i
1
)
=
(
[
−
a
i
s
+
s
′
P
w
i
+
e
i
]
P
Q
L
,
[
a
i
]
P
Q
L
)
,
0
≤
i
<
β
(swk_i^0, swk_i^1) = ([-a_is + s'Pw_i + e_i]_{PQ_L}, [a_i]_{PQ_L}), 0 \le i < \beta
(swki0,swki1)=([−ais+s′Pwi+ei]PQL,[ai]PQL),0≤i<β
注意,KSK 是包含
β
\beta
β 个分量的密文向量(加密了
s
′
P
w
s'Pw
s′Pw 的各个分量 ),每个分量都存储为 RNS 表示(长度
α
+
L
+
1
\alpha+L+1
α+L+1 的单精度向量)。执行 KS 过程时,
- 输入密文 c c c 的关于 B \mathcal B B 的 RNS 表示,将它按照 C \mathcal C C 计算出各个 c ( m o d q α , i ) c \pmod{q_{\alpha,i}} c(modqα,i),其实就是简单截断 q α , i q_{\alpha,i} qα,i 所在的 RNS 分量
- 然后使用 FastBaseExt 将它们都扩展为 P Q L PQ_L PQL 上的 RNS 表示,这就得到了 c c c 关于 w w w 的 RNS 分解(也就是 c = ∑ i [ c ] q α , i w i ( m o d P Q L ) c=\sum_i [c]_{q_{\alpha,i}} w_i \pmod{PQ_L} c=∑i[c]qα,iwi(modPQL)),它包含 β \beta β 个长度为 α + L + 1 \alpha + L+1 α+L+1 的 RNS 表示(长度 β \beta β 的分解向量)
- 最后将这个分解出的向量和 KSK 做内积(需要 NTT/INTT),计算出 c ⋅ s ′ P c \cdot s'P c⋅s′P,最后做实数除法并舍入
- 上述所有运算都是单精度的,不需要高精度算术
Improved Hoisted-Rotations
同态自同构(使用 BV-KS)包含了三个步骤:自同构(就是系数置换)、数字分解(需要 NTT/INTT 做 DCRT 和 RNS 之间的转换)、密钥切换(同态的线性解密)。
[HS18] 观察到自同构 ϕ k : X ↦ X 5 k \phi_k: X \mapsto X^{5^k} ϕk:X↦X5k 不会严重地改变范数,它可以和二进制分解交换。同样的,它也和 RNS 分解交换,满足 [ ϕ k ( a ) ] q α , i = ϕ k ( [ a ] q α , i ) [\phi_k(a)]_{q_{\alpha,i}} = \phi_k([a]_{q_{\alpha,i}}) [ϕk(a)]qα,i=ϕk([a]qα,i)。当多个 rotation 作用到同一个密文上,我们可以把分解步骤交换到自同构步骤之前,从而复用 { [ a ] q α , i } i \{[a]_{q_{\alpha,i}}\}_i {[a]qα,i}i 结果(代价是每个碎片都需要做自同构),这被称为 Hoisting 技术。
虽然自同构本身只是线性复杂度的系数置换,[BMTH21] 进一步将自同构交换到密钥切换的后面,从而只需要对内积结果(不是碎片)做一次自同构。确切地说,将原始的用
s
s
s 加密
ϕ
k
(
s
)
P
w
i
\phi_k(s)Pw_i
ϕk(s)Pwi 的
r
o
t
k
rot_k
rotk,修改为用
ϕ
k
−
1
(
s
)
\phi_k^{-1}(s)
ϕk−1(s) 加密
s
P
w
i
sPw_i
sPwi(执行 KS 时的私钥还是
s
s
s,后续的自同构将
ϕ
k
−
1
(
s
)
\phi_k^{-1}(s)
ϕk−1(s) 转化回
s
s
s),
(
r
o
t
k
,
i
0
‾
,
r
o
t
k
,
i
1
‾
)
=
(
[
−
a
i
ϕ
k
−
1
(
s
)
+
s
P
w
i
+
w
i
]
P
Q
L
,
[
a
i
]
P
Q
L
)
(\overline{rot_{k,i}^0},\overline{rot_{k,i}^1}) = ([-a_i\phi_k^{-1}(s) + sPw_i + w_i]_{PQ_L}, [a_i]_{PQ_L})
(rotk,i0,rotk,i1)=([−aiϕk−1(s)+sPwi+wi]PQL,[ai]PQL)
那么如下的三种计算方法(BV11、HS18、BMTH21)是等价的,
⟨
d
e
c
o
m
p
(
ϕ
k
(
a
)
)
,
r
o
t
k
⟩
=
⟨
ϕ
k
(
d
e
c
o
m
p
(
a
)
)
,
r
o
t
k
⟩
=
ϕ
k
(
⟨
d
e
c
o
m
p
(
a
)
,
r
o
t
k
‾
⟩
)
\langle decomp(\phi_k(a)), rot_k\rangle = \langle \phi_k(decomp(a)), rot_k\rangle = \phi_k(\langle decomp(a), \overline{rot_k}\rangle)
⟨decomp(ϕk(a)),rotk⟩=⟨ϕk(decomp(a)),rotk⟩=ϕk(⟨decomp(a),rotk⟩)
总计一次分解、均摊一次自同构的多个槽旋转,算法步骤重排为:数字分解、同态内积、模切换(这是 GHS-KS 带来的,也需要 NTT/INTT)、自同构。
Double-hoisting BSGS algorithm
[HS18] 将矩阵表示为对角线形式,提出了复杂度为 O ( n ) O(\sqrt n) O(n) 次槽旋转的 BSGS 算法,这里的 n n n 表示非零的对角线的个数。分解 n = n 1 n 2 n=n_1n_2 n=n1n2,当 n 1 ≈ n 2 n_1 \approx n_2 n1≈n2 时最优。
以单精度的模乘运算作为单位,[BMTH21] 分析了槽旋转的四个步骤的复杂度,发现主要的瓶颈是数字分解和模切换(都需要 NTT/INTT 转换),
在算法 5 中,step 2 需要 n 1 n_1 n1 次槽旋转,step 10 需要 n 2 n_2 n2 次槽旋转,它们各自都需要分别执行它们内部的数字分解和模切换。我们可以对它做两层优化,
- [HS13] 考虑了 step 2 的那些旋转,利用 Hoisted-Rotations 复用数字分解的结果
- [BMTH21] 考虑了 step 10 的那些旋转,交换模切换和自同构的顺序,对加和的结果统一执行
上述算法的复杂度是: n 1 + n 2 n_1+n_2 n1+n2 次的内积和自同构, n 2 + 1 n_2+1 n2+1 次的模切换和数字分解。由于前者复杂度较低,后者复杂度较高,因此最优化的参数选取不再是 n 1 ≈ n 2 n_1 \approx n_2 n1≈n2,[BMTH21] 确定出最佳选取移动到了 8 ≤ n 1 / n 2 ≤ 16 8 \le n_1/n_2 \le 16 8≤n1/n2≤16(分析它们的单精度模乘的数量),并且当 n = 128 n=128 n=128 左右获得最佳的效率提升。对于稠密矩阵,可以将它分解为一些稀疏对角线的因子(例如 [CHH18] 和 [CCS19] 对于 DFT 矩阵的 FFT-like 算法),使得它们具有大约 128 条非零对角线。
Bootstrapping for RNS-CKKS
注意 CKKS 自举并不减小噪声(降低明文精度),而只能提升模数(增大计算容量):将 [ m + e ] Q 0 [m+e]_{Q_0} [m+e]Q0 强行提升为 [ m + e + u Q 0 ] Q L [m+e+uQ_0]_{Q_L} [m+e+uQ0]QL,再利用近似的取模函数获得 [ m + e ′ ] Q L − k [m+e']_{Q_{L-k}} [m+e′]QL−k,其中 ∥ e ′ ∥ > ∣ ∣ e ∣ ∣ \|e'\| > ||e|| ∥e′∥>∣∣e∣∣
自举流程为: