Full-RNS CKKS

参考文献:

  1. [HS13] Halevi S, Shoup V. Design and implementation of a homomorphic-encryption library[J]. IBM Research (Manuscript), 2013, 6(12-15): 8-36.
  2. [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.
  3. [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.
  4. [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.
  5. [CHH18] Cheon J H, Han K, Hhan M. Faster homomorphic discrete fourier transforms and improved fhe bootstrapping[J]. Cryptology ePrint Archive, 2018.
  6. [HS18] Halevi S, Shoup V. Faster homomorphic linear transformations in HElib[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2018: 93-120.
  7. [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.
  8. [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.
  9. [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=q1qi,集合 { q i } \{q_i\} {qi} 称为 RNS Base,它们的大小至多为 64 64 64 比特。我们希望 FHE 的全部运算都是单精度的(现代计算机的机器字),也就是全部运算都在 RNS 下完成,而不需要多精度算术。

[BEHZ16] 提出了可以在不同的 RNS(扩展到新的 RNS Base 对应的系数)之间快速转换的算法。将环元素 a ∈ R Q a \in \mathcal R_Q aRQ 从模数 Q = q 1 ⋯ q l Q=q_1\cdots q_l Q=q1ql 下的 [ a ] Q [a]_Q [a]Q 转换到模数 P = p 1 ⋯ p k P=p_1\cdots p_k P=p1pk 下的 [ [ 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=1l[a(qiQ)1]qiqiQ(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} qiq~i1(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[aq~i]qiqi=[a]Q+uQZ
其中的 ∥ u ∥ ∞ ≤ l / 2 \|u\|_\infty \le l/2 ul/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+uQ]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} aRQl 的 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 [ql1([a]qj[a]ql)]qj,∀0j<l 就是 ⌊ a / q l ⌉ ∈ R Q l − 1 \lfloor a/q_l\rceil \in R_{Q_{l-1}} a/qlRQl1 的 RNS 表示。

Approximate Modulus Switching

原始的 CKKS 的模数链,形如 Q l = q 0 ⋅ q l Q_l = q_0 \cdot q^l Ql=q0ql,其中 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(12η,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 ql1m 的误差为 2 − η ⋅ ∣ q l − 1 ⋅ m ∣ 2^{-\eta} \cdot |q_l^{-1} \cdot m| 2ηql1m,应当使得 η \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,,pk1,q0,,ql1},它分为两个子集 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} aZQ 的 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 aa~modQ 以及 ∣ a ~ ∣ ≪ P Q |\tilde a| \ll PQ a~PQ(不需要具有相同的整数代表)

根据 Fast Base Conversion 的结果,它的 overflow 规模仅为 l / 2 ≪ P l/2 \ll P l/2P,因此获得的 [ a + u ⋅ Q ] P [a + u \cdot Q]_P [a+uQ]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[Q1]P[a+uQ]P+P[P1]Q[a]Q=Q[Q1]P(a+uQ+vP)+P[P1]Q(a+wQ)=(Q[Q1]P+P[P1]Q)a+uQ2[Q1]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} bZQ 的 RNS 表示,满足 b ≈ P − 1 ⋅ b ~ b \approx P^{-1} \cdot \tilde b bP1b~(不需要等于实数除法的舍入)

由于 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 ∣∣uk/2Q,这就满足了要求:

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} ConvBC C o n v C → B Conv_{C\to B} ConvCB 的复杂度都是 O ( k ⋅ l ) O(k \cdot l) O(kl) M o d U p C → D ModUp_{C \to D} ModUpCD 的复杂度为 O ( k ⋅ l ) O(k \cdot l) O(kl) M o d D o w n D → C ModDown_{D \to C} ModDownDC 的复杂度为 O ( k ⋅ l + l ) O(k \cdot l+l) O(kl+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=[qiq~i]i(modQ) 是 RNS Base(二进制分解与 RNS 不兼容),对于 ∀ d ∈ R \forall d \in R dR 满足线性运算 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]qiwi(modQ)。当然,对于每个分量 [ d ] q i [d]_{q_i} [d]qi 可以进一步采用二进制分解,用更高的计算复杂度换取更小的噪声。

在这里插入图片描述
在这里插入图片描述

对于二的幂次 N ≥ 8 N\ge8 N8,总是有 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(ζ2N1)] 可以稍稍扭曲为
τ : 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 XX5(所生成的循环子群)可用于自然的槽旋转,剩下的一个非凡的自同构 X ↦ X − 1 X \mapsto X^{-1} XX1 用于槽的复共轭。利用 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α,i1(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α,iq~α,i,0i<β 可以作为 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 Pqα,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+sPwi+ei]PQL,[ai]PQL),0i<β
注意,KSK 是包含 β \beta β 个分量的密文向量(加密了 s ′ P w s'Pw sPw 的各个分量 ),每个分量都存储为 RNS 表示(长度 α + L + 1 \alpha+L+1 α+L+1 的单精度向量)。执行 KS 过程时,

  1. 输入密文 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 分量
  2. 然后使用 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 β 的分解向量)
  3. 最后将这个分解出的向量和 KSK 做内积(需要 NTT/INTT),计算出 c ⋅ s ′ P c \cdot s'P csP,最后做实数除法并舍入
  4. 上述所有运算都是单精度的,不需要高精度算术

在这里插入图片描述

Improved Hoisted-Rotations

同态自同构(使用 BV-KS)包含了三个步骤:自同构(就是系数置换)、数字分解(需要 NTT/INTT 做 DCRT 和 RNS 之间的转换)、密钥切换(同态的线性解密)。

[HS18] 观察到自同构 ϕ k : X ↦ X 5 k \phi_k: X \mapsto X^{5^k} ϕk:XX5k 不会严重地改变范数,它可以和二进制分解交换。同样的,它也和 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) ϕk1(s) 加密 s P w i sPw_i sPwi(执行 KS 时的私钥还是 s s s,后续的自同构将 ϕ k − 1 ( s ) \phi_k^{-1}(s) ϕk1(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ϕk1(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 n1n2 时最优。

在这里插入图片描述

以单精度的模乘运算作为单位,[BMTH21] 分析了槽旋转的四个步骤的复杂度,发现主要的瓶颈是数字分解和模切换(都需要 NTT/INTT 转换),

在这里插入图片描述

在算法 5 中,step 2 需要 n 1 n_1 n1 次槽旋转,step 10 需要 n 2 n_2 n2 次槽旋转,它们各自都需要分别执行它们内部的数字分解和模切换。我们可以对它做两层优化,

  1. [HS13] 考虑了 step 2 的那些旋转,利用 Hoisted-Rotations 复用数字分解的结果
  2. [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 n1n2,[BMTH21] 确定出最佳选取移动到了 8 ≤ n 1 / n 2 ≤ 16 8 \le n_1/n_2 \le 16 8n1/n216(分析它们的单精度模乘的数量),并且当 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]QLk,其中 ∥ e ′ ∥ > ∣ ∣ e ∣ ∣ \|e'\| > ||e|| e>∣∣e∣∣

自举流程为:

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/429551.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Java EE初阶二十九】Linux 系统的学习

当前写的博客系统程序,只是部署在咱们自己的电脑上,其他用户是无法直接访问的.由于 NAT 机制的存在,导致了IP 地址就被分成了 内网 IP 和 外网 IP. 云服务器,包括公司中使用专用服务器,一般都是 Linux 系统&#xff0c;这个系统的使用和 Windows 差异很大.(通过命令行来操作的系…

汽车零部件制造中的信息抽取技术:提升效率与质量的关键

一、引言 在汽车制造业中&#xff0c;零部件的生产是整个制造流程的关键一环。这些零部件&#xff0c;包括但不限于制动系统、转向系统和传动系统&#xff0c;是确保汽车安全、可靠运行的基础。为了满足现代汽车工业对效率和质量的严格要求&#xff0c;制造商们纷纷投入到高度…

b站小土堆pytorch学习记录—— P17 土堆说卷积操作

文章目录 一、前置知识什么是卷积操作 二、代码 一、前置知识 什么是卷积操作 推荐几个高赞博客&#xff1a; 卷积最容易理解的解释 卷积神经网络&#xff08;CNN&#xff09;详细介绍及其原理详解 还有pytorch官网的动态图&#xff1a; pytorch卷积 二、代码 import t…

第五套CCF信息学奥赛c++练习题 CSP-J认证初级组 中小学信奥赛入门组初赛考前模拟冲刺题(阅读程序题)

第五套中小学信息学奥赛CSP-J考前冲刺题 二、阅读程序题 (程序输入不超过数组或字符串定义的范围&#xff0c;判断题正确填√错误填X;除特殊说明外&#xff0c;判断题 1.5分&#xff0c;选择题3分&#xff0c;共计40分) 第一题 递归函数 1 #include<iostream> 2 usin…

02. Nginx入门-Nginx安装

Nginx安装 yum安装 编辑yum环境 cat > /etc/yum.repos.d/nginx.repo << EOF [nginx-stable] namenginx stable repo baseurlhttp://nginx.org/packages/centos/$releasever/$basearch/ gpgcheck1 enabled1 gpgkeyhttps://nginx.org/keys/nginx_signing.key module_…

【LeetCode每日一题】【BFS模版与例题】【二维数组】130被围绕的区域 994 腐烂的橘子

前几天写过一篇BFS比较基础版的遍历 【LeetCode每日一题】【BFS模版与例题】863.二叉树中所有距离为 K 的结点 &#xff0c;可以先看一下再看本文 用 BFS 算法遍历二维数组 遍历二维矩阵&#xff1a;二维矩阵中的一个位置看做一个节点&#xff0c;这个节点的上下左右四个位置…

gRPC入门

文章目录 1. 简介2. 安装gRPC2.1. 下载protobuf2.2. 安装grpc核心库2.3. 安装protoc的Go插件2.4. 检查 3. 入门示例4. proto文件介绍5. 服务端代码编写6. 客户端代码编写7. 认证以及安全传输 1. 简介 在 gRPC 中&#xff0c;客户端应用程序可以像本地对象一样直接调用不同机器…

Flutter中的Provider状态管理工具有哪些优势

在Flutter应用开发中&#xff0c;状态管理是一个至关重要的方面。而Provider作为一种简单、灵活且高效的状态管理工具&#xff0c;在众多Flutter开发者中备受青睐。本文将深入探讨Provider在Flutter中的优势&#xff0c;帮助读者更好地理解其价值和应用场景。 简单易用 Provi…

《数字图像处理(MATLAB版)》相关算法代码及其分析(3)

目录 1 对边界进行子采样 1.1 输入参数检查 1.2 处理重复坐标 1.3 计算边界最大范围 1.4 确定网格线数量 1.5 构建网格位置向量 1.6 计算曼哈顿距离 1.7 整理输出结果 1.8 返回结果 2 改变图像的存储类别 2.1 函数输入 2.2 数据类型转换 2.3 错误处理 2.4 返回结…

Flutter整体框架

Flutter整体框架由三部分组成&#xff1a;Framework、Engine和Embedder。 Framework Framework提供了一个用 Dart 语言编写的现代、反应式框架&#xff0c;由许多抽象的层级组成。它包括一套丰富的布局、动画、绘制、手势UI组件及配套代码&#xff0c;以及更基础的异步、文件、…

参数引入和全局变量引入实现-目标和

LCR 102. 目标和 - 力扣&#xff08;LeetCode&#xff09; 分析题意&#xff0c;画出决策树&#xff0c;其他的思路都跟前面讲过的类似&#xff1a; 全局变量引入实现&#xff1a; 全局变量的引入&#xff0c;需要手动处理回溯&#xff1b; class Solution {int ret; //…

视频拉流推流技术梳理

概况 视频的整个流程主要分为推流和拉流 摄像头场景&#xff1a; 摄像头捕捉视频画面&#xff0c;推流到服务器&#xff0c;服务器分发到CDN&#xff0c; 客户端从CDN地址拉流&#xff0c;客户端进行播放 直播场景&#xff1a; 主播通过手机&#xff0c;电脑等客户端&…

前端爬虫+可视化Demo

爬虫简介 可以把互联网比做成一张 “大网”&#xff0c;爬虫就是在这张大网上不断爬取信息的程序。 爬虫是请求网站并提取数据的自动化程序。 省流&#xff1a;Demo实现前置知识&#xff1a; JS 基础Node 基础 &#xff08;1&#xff09;爬虫基本工作流程&#xff1a; 向…

RK3568平台 USB基础知识

一.现实工作中USB实际例子 现象&#xff1a;把USB设备比如Android手机接到PC 右下角弹出"发现android phone"跳出一个对话框&#xff0c;提示你安装驱动程序 问1&#xff1a;USB设备插到电脑上去&#xff0c;接触到的对方设备是什么&#xff1f; 答1&#xff1a;…

yum 和 rpm

rpm说明 rpm -qa &#xff1a;列出所有已安装的软件包 [roothub ~] rpm -qa geoipupdate-2.5.0-1.el7.x86_64 ncurses-base-5.9-14.20130511.el7_4.noarch libndp-1.2-9.el7.x86_64 libfastjson-0.99.4-3.el7.x86_64 。。。 rpm -qf FILENAME &#xff1a;查找提供 FILENAME…

SwiftUI之CoreData详解(一)

coreData 是一种数据持久化的方案&#xff0c;是对SQLite的一种封装。一说到这种桌面化的数据库&#xff0c;我就无比的怀念Foxbase|Foxpro, 多好的数据库产品&#xff0c;被微软扼杀了&#xff0c;相当年教大学生妹子们国家二级数据库时都是手把手教的&#xff0c;呃~~~&#…

wordpress模板官网

移民wordpress主题 移民代办wordpress主题&#xff0c;适合做海外移民咨询的代理公司搭建wordpress企业官方网站使用。 https://www.jianzhanpress.com/?p5130 夏令营wordpress主题 绿色夏令营wordpress主题&#xff0c;适合做夏令营或户外拓展的公司搭建wordpress官方网站…

【动态规划】第十一届蓝桥杯省赛第二场C++ C组《数字三角形》(c++)

1.题目描述 上图给出了一个数字三角形。 从三角形的顶部到底部有很多条不同的路径。 对于每条路径&#xff0c;把路径上面的数加起来可以得到一个和&#xff0c;你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。 …

绝地求生:小团团曝被判8年:地图语音包或将下架,公会和主播被一锅端

这两天大家都在讨论某鱼平台办卡抽奖的事情。这件事发生之后没多久&#xff0c;某鱼平台里面的大量主播在同一时间停播&#xff0c;闲游盒认为大家应该也懂的&#xff0c;这次停播就是因为这些主播也参与了办卡抽奖&#xff0c;都需要接受调查&#xff0c;在两个月左右的调查中…

【项目实践】如何发掘用户隐性需求推送PUSH

1.背景 对比业界广告推荐、触达成熟的平台&#xff0c;例如抖音&#xff0c;小红书&#xff0c;淘宝&#xff0c;知乎等&#xff0c;都已经站在巨量数据的基础之上&#xff0c;具备了 “用户意图分析” 的能力&#xff0c;可以分析出 “用户的隐性需求”&#xff0c;假设我们同…