参考文献:
- [BMMP18] Bourse F, Minelli M, Minihold M, et al. Fast homomorphic evaluation of deep discretized neural networks[C]//Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III 38. Springer International Publishing, 2018: 483-512.
- [CDKS21] Chen H, Dai W, Kim M, et al. Efficient homomorphic conversion between (ring) LWE ciphertexts[C]//International Conference on Applied Cryptography and Network Security. Cham: Springer International Publishing, 2021: 460-479.
- [MP21] Micciancio D, Polyakov Y. Bootstrapping in FHEW-like cryptosystems[C]//Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. 2021: 17-28.
- [LMK+23] Lee Y, Micciancio D, Kim A, et al. Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer Nature Switzerland, 2023: 227-256.
- [KLD+23] Kim A, Lee Y, Deryabin M, et al. LFHE: Fully homomorphic encryption with bootstrapping key size less than a megabyte[J]. Cryptology ePrint Archive, 2023.
- [DKM+24] De Micheli G, Kim D, Micciancio D, et al. Faster amortized FHEW bootstrapping using ring automorphisms. Public Key Cryptography 2024 (4): 322-353.
文章目录
[KLD+23] 关注 Blind Rotation Key 的传输开销,用于客户端能力受限的场景。
Packing and Reconstruction
对于 TFHE-type 盲旋转算法,自举密钥形如 { R G S W z ( s i ) } 0 ≤ i ≤ n − 1 \{RGSW_z(s_i)\}_{0\le i\le n-1} {
RGSWz(si)}0≤i≤n−1,其中 R G S W z ( s i ) = ( R L W E z ′ ( s i ) , R L W E z ′ ( s i z ) ) RGSW_z(s_i) = (RLWE_z'(s_i), RLWE_z'(s_iz)) RGSWz(si)=(RLWEz′(si),RLWEz′(siz)),这里 R L W E z ′ ( m ) = { R L W E z ( m B j ) } 0 ≤ j ≤ d d − 1 RLWE_z'(m)=\{RLWE_z(mB^j)\}_{0\le j\le d_d-1} RLWEz′(m)={
RLWEz(mBj)}0≤j≤dd−1
容易发现,RGSW 密文由一堆 RLWE 密文组成,每个 RLWE 密文都只加密了常数多项式。因此 [KLD+23] 将它们系数打包在少量 RLWE 密文中,然后使用 [CDKS21] 的分圆塔算法提取各个系数。疑问:FHEW-type 中的非常数单项式,如何打包?
对于自举密钥的第一分量 R L W E z ′ ( s i ) RLWE_z'(s_i) RLWEz′(si),可以打包为:
其中的 N − 1 N^{-1} N−1 是为了抵消分圆塔上 Trace 的缩放因子。然后使用如下的自同构,
ψ N + 1 ( m ) = ∑ i = 0 N / 2 − 1 m 2 i X 2 i − ∑ i = 0 N / 2 − 1 m 2 i + 1 X 2 i + 1 , ∀ m ∈ Z [ X ] / ( X N + 1 ) \psi_{N+1}(m) = \sum_{i=0}^{N/2-1} m_{2i}X^{2i} - \sum_{i=0}^{N/2-1}m_{2i+1}X^{2i+1}, \forall m \in \mathbb Z[X]/(X^N+1) ψN+1(m)=i=0∑N/2−1m2iX2i−i=0∑N/2−1m2i+1X2i+1,∀m∈Z[X]/(XN+1)
利用 [CDKS21] 的算法来提取 RLWE 密文 p b k k pbk_k pbkk 中的各个系数:
对于自举密钥的第二分量 R L W E z ′ ( s i z ) RLWE_z'(s_iz) RLWEz′(siz),为了减小噪声增长,不是采用 BV-Mult,而是采用了 BV-type KS,给定 ( b i j , a i j ) ∈ R L W E ( s i B j ) (b_{ij}, a_{ij}) \in RLWE(s_iB^j) (bij,aij)∈RLWE(siBj)。这个在 [DKM+24] 中称为 “ R L W E ′ RLWE' RLWE′ to R G S W RGSW RGSW scheme switching” 技术:
b i j ⋅ ( 0 , 1 ) + a i j ⊙ R L W E z ′ ( z 2 ) = R L W E ( ( b i j + a i j z ) z ) = R L W E ( s i B j z ) b_{ij} \cdot (0,1) + a_{ij} \odot RLWE_z'(z^2) = RLWE((b_{ij}+a_{ij}z)z) =RLWE(s_iB^jz) bij⋅(0,1)+aij⊙RLWEz′(z2)=RLWE((bij+aijz)z)=RLWE(siBjz)
因此,所需的密钥包括:打包的盲旋转密钥的第一部分、用于解包的密钥切换密钥、用于计算盲旋转密钥的第二部分的密钥切换密钥。密钥生成算法:
密钥重建算法:
Smooth Converting Process
在 FHEW/TFHE 的自举噪声中,盲旋转之后的密钥切换噪声有较大影响,而参数集(本身较小)对于自举噪声的规模十分敏感(LWE 的模数增大 1 1 1 比特、ACC 的维度翻倍)。
对于 LWE 的密钥切换,使用 BV-type KS 过程。为了尽可能降低噪声,采用了枚举技术,设置:
K S K = { L W E z ( k B j s i } 0 ≤ i ≤ n − 1 , 0 ≤ j ≤ d − 1 , − B / 2 < k ≤ B / 2 KSK = \{LWE_z(kB^js_i\}_{0\le i\le n-1, 0 \le j\le d-1, -B/2 < k \le B/2} KSK={
LWEz(kBjsi}0≤i≤n−1,0≤j≤d−1,−B/2<k≤B/2
其中 d = ⌈ log B Q ⌉ d=\lceil\log_B Q\rceil d=⌈logBQ⌉,规模是 n d Q 1 / d ndQ^{1/d} ndQ1/d 个 LWE 密文,因此 d d d 越大,存储越少。
密钥切换的执行:
L W E z ( m ) = ( b , 0 n ) + ∑ i , j L W E z ( h ( a i ) j ⋅ B j s i ) LWE_{z}(m) = (b,0^n) + \sum_{i,j} LWE_z(h(a_i)_j \cdot B^js_i) LWEz(m)=(b,0n)+i,j∑LWEz(h(ai)j⋅Bjsi)
不需要同态数乘,噪声被简单的加在一起。其中 h ( a i ) ∈ Z d h(a_i) \in \mathbb Z^d h(ai)∈Zd 是 Gadget 分解出的短向量,用于挑选 KSK 的某个分量。假设 KSK 的噪声方差是 σ f r e s h 2 \sigma_{fresh}^2 σfresh2,那么密钥切换噪声的方差是 d n ⋅ σ f r e s h 2 dn\cdot\sigma_{fresh}^2 dn⋅σfresh2,因此 d d d 越小,噪声越小。注意,如果使用数乘而非枚举,那么 d d d 越大 B = Q 1 / d B=Q^{1/d} B=Q1/d 越小,噪声才会越小。疑问:把 LWE 嵌入到 RLWE 上效率是否会更好,以及 RLWE 如何用枚举来降低噪声?
FHEW/TFHE 的自举流程:
-
原始的 FHEW 的输入输出都在最小参数集 ( q , n ) (q,n) (q,n) 上,盲旋转得到 ( Q , N ) (Q,N) (Q,N) 的 ACC 密文,首先提取出 LWE 密文,然后再依次执行 KS 和 MS(不仅仅要求 ( q , n ) (q,n) (q,n) 安全,还要求 ( Q , n ) (Q,n) (Q,n) 也是安全的,LWE 维度 n n n 不能太小)
-
[MP21] 设置了额外的模数 q < Q K S < Q q < Q_{KS} < Q q<QKS<Q,在做 KS 之前先做一次 MS,使得模数满足 KSK 的安全需求(因为 s ∈ Z n , z ∈ R N , n < N s \in \mathbb Z^n, z \in R_N, n < N s∈Zn,z∈RN,n<N),只需要 ( Q K S , n ) (Q_{KS},n) (QKS,n) 是安全的即可,LWE 维度降低
-
[CGGI20] 修改了 TFHE 的流程,使得输入输出维持在最高参数集 ( Q , N ) (Q,N) (Q,N) 上,仅在盲旋转之前才执行 KS 和 MS,这可以降低噪声增长(从而 q q q 可以降低,使得 N N N 降低)
从 ( Q k s , N ) (Q_{ks},N) (Qks,N)-LWE 切换到 ( Q k s , n ) (Q_{ks},n) (Qks,n)-LWE,
- KSK 的存储开销: d k s Q k s 1 / d k s N ( n + 1 ) log Q k s d_{ks}Q_{ks}^{1/d_{ks}}N(n+1)\log Q_{ks} dksQks1/dksN(n+1)logQks
- KS 噪声的方差: d k s N σ e r r 2 d_{ks}N\sigma_{err}^2 dksNσerr2
上述的 KS 都是在 LWE 密文上执行的,但是 LWE-KSK(尤其是枚举版本)的规模远大于 RLWE-KSK 的规模。如果直接对 ACC 做密钥切换,噪声则会变大,但是 RLWE-KS 在较小参数下对噪声很敏感。[KLD+23] 组合使用 RLWE-KS 以及 LWE-KS,降低 KSK 规模的同时,还降低了 KS-Error 的大小。
使用四个模数 q < Q k s < Q s m < Q q < Q_{ks} < Q_{sm} < Q q<Qks<Qsm<Q,使用三个维度 n < N s m < N n < N_{sm} < N n<Nsm<N,保证: ( Q k s , n ) (Q_{ks},n) (Qks,n) 安全, ( Q s m , N s m ) (Q_{sm}, N_{sm}) (Qsm,Nsm) 安全, ( Q , N ) (Q,N) (Q,N) 安全。对应的私钥是 s ∈ Z n , z s m ∈ R N s m , z ∈ R N s \in\mathbb Z^n, z_{sm} \in R_{N_{sm}}, z \in R_N s∈Zn,zsm∈RNsm,z∈RN,那么
- ( Q s m , N ) (Q_{sm},N) (Qsm,N)-RLWE 切换到 ( Q s m , N s m ) (Q_{sm},N_{sm}) (Qsm,Nsm)-RLWE 的密钥: R L W E z s m ′ ( z i ) RLWE_{z_{sm}}'(z_i) RLWEzsm′(zi),其中 z i ∈ R N s m , 0 ≤ i ≤ N / N s m − 1 z_i \in R_{N_{sm}}, 0 \le i \le N/N_{sm}-1 zi∈RNsm,0≤i≤N/Nsm−1 是私钥 z z z 的分片。
- ( Q k s , N s m ) (Q_{ks},N_{sm}) (Qks,Nsm)-LWE 切换到 ( Q k s , n ) (Q_{ks},n) (Qks,n)-LWE 的密钥: L W E z ( k B j ( z ⃗ s m ) i ) LWE_z(kB^j(\vec z_{sm})_i) LWEz(kBj(zsm)i),这里的 z ⃗ s m ∈ Z N s m \vec z_{sm} \in \mathbb Z^{N_{sm}} zsm∈ZNsm 是私钥 z s m z_{sm} zsm 的系数向量。
自举的流程是:
两个 KSK 的总大小是:
2 d s m N log Q s m + d k s Q k s 1 / d k s N s m ( n + 1 ) log Q k s 2d_{sm}N\log Q_{sm} + d_{ks}Q_{ks}^{1/d_{ks}}N_{sm}(n+1)\log Q_{ks} 2dsmNlogQsm+dksQks1/dksNsm(n+1)logQks
前者是 RLWE-KSK( N / N s m N/N_{sm} N/Nsm 个 R L W E z s m ′ RLWE'_{z_{sm}} RLWEzsm′ 密文),后者是 LWE-KSK( d k s Q k s 1 / d k s N s m d_{ks}Q_{ks}^{1/d_{ks}}N_{sm} dksQks1/dksNsm 个 L W E s LWE_s LWEs 密文)。容易看出 LWE-KSK 占据主要的大小,存储比单独使用 LWE-KS 减小了 N / N s m N/N_{sm} N/Nsm 因子。
两次 KS 的噪声方差是:
( Q k s Q s m ) 2 ⋅ d s m N ⋅ ( σ e r r 2 ⋅ Q s m 2 / d s m 12 ) + d k s N s m σ e r r 2 \left(\frac{Q_{ks}}{Q_{sm}}\right)^2 \cdot d_{sm}N \cdot \left(\sigma_{err}^2 \cdot \frac{Q_{sm}^{2/d_{sm}}}{12}\right) + d_{ks}N_{sm}\sigma_{err}^2 (QsmQks)2⋅dsmN⋅(σerr2⋅12Qsm2/dsm)+dksNsmσerr2
前者是 RLWE-KS( d s m N / N s m d_{sm}N/N_{sm} dsmN/Nsm 个系数范围 Q s m 1 / d s m Q_{sm}^{1/d_{sm}} Qsm1/dsm 的 N s m N_{sm} Nsm 维均匀多项式的数乘,然后模切换),后者是 LWE-KS( N s m d k s N_{sm}d_{ks} Nsmdks 次加法)。容易看出 LWE-KS 的贡献占主导,噪声比单独使用 LWE-KS 也减小了 N / N s m N/N_{sm} N/Nsm 因子。
Key Unrolling Technique
[BMMP18] 提出了密钥展开,以降低 Binary TFHE 的外积数量。
原始的盲旋转密钥是 R G S W z ( s i ) RGSW_z(s_i) RGSWz(si),设置 u u u 是展开因子(an unrolling factor),对应的向量集合 V = { 0 , 1 } u \ 0 u V = \{0,1\}^u \backslash 0^u V={
0,1}u\0u,将 LWE 私钥分成 n / u n/u n/u 个长度 u u u 的分片,记为 s ( l ) , 0 ≤ l ≤ n / u − 1 s_{(l)}, 0\le l\le n/u-1 s(l),0≤l≤n/u−1。指示函数:
∀ v ∈ V , l ∈ [ n / u ] , δ v , l = { 1 , s ( l ) = v , 0 , otherwise. \forall v \in V, l \in [n/u],\,\, \delta_{v,l} = \left\{\begin{aligned} 1, && s_{(l)} = v,\\ 0, && \text{otherwise.} \end{aligned}\right. ∀v∈V,l∈[n/u],δv,l={
1,0,s(l)=v,otherwise.
那么自举密钥就是 { R G S W ( δ v , l ) } v , l \{RGSW(\delta_{v,l})\}_{v,l} {
RGSW(δv,l)}v,l,规模是 ( 2 u − 1 ) n / u (2^u-1)n/u (2u−1)n/u 个 RGSW 密文,这比原始的 n n n 个 R G S W ( s i ) RGSW(s_i) RGSW(si) 密文,增大了 O ( 2 u ) O(2^u) O(2u) 倍。
盲旋转算法是:
R L W E ( f ) ⊡ ( R G S W ( 1 ) + ∑ v ∈ V ( X * a ( j ) , v * − 1 ) ⋅ R G S W ( δ v , l ) ) = R L W E ( f ⋅ X * a ( l ) , s ( l ) * ) RLWE(f) \boxdot\left( RGSW(1) + \sum_{v \in V} (X^{\langle a_{(j)}, v\rangle}-1) \cdot RGSW(\delta_{v,l}) \right) = RLWE(f \cdot X^{\langle a_{(l)}, s_{(l)}\rangle}) RLWE(f)⊡(RGSW(1)+v∈V∑(X*a(j),v*−1)⋅RGSW(δv,l))=RLWE(f⋅X*a(l),s(l)*)
只需对于 n / u n/u n/u 次外积运算,但是需要 2 u 2^u 2u 次数乘和加法。
[ZYL+18] 设置了 V = { 0 , 1 } u V = \{0,1\}^u V={
0,1}u,那么自举密钥会更大一些,但是盲旋转更加简单,噪声会更小:
R L W E ( f ) ⊡ ( ∑ v ∈ V X * a ( j ) , v * ⋅ R G S W ( δ v , l ) ) = R L W E ( f ⋅ X * a ( l ) , s ( l ) * ) RLWE(f) \boxdot\left( \sum_{v \in V} X^{\langle a_{(j)}, v\rangle} \cdot RGSW(\delta_{v,l}) \right) = RLWE(f \cdot X^{\langle a_{(l)}, s_{(l)}\rangle}) RLWE(f)⊡(v∈V∑X*a(j),v*⋅RGSW(δv,l))=RLWE(f⋅X*a(l),s(l)*)
Approximate Gadget Decomposition
[CGGI20] 对于实数环面(无限精度),提出了近似分解。为了减小自举密钥大小、盲旋转时间,[LMK+23] 提出了整数上的近似分解:原本的 Gadget Vector 是 g = ( 1 , B g , B g 2 , ⋯ , B g d g − 1 ) g=(1,B_g,B_g^2,\cdots,B_g^{d_g-1}) g=(1,Bg,Bg2,⋯,Bgdg−1),简单丢弃分解结果 h ( a ) h(a) h(a) 的第一个分量,它和 R G S W z ( m ) RGSW_z(m) RGSWz(m) 的外积是(这里的 m ∈ R m \in R m∈R 是任意的多项式,不必是单项式):
∑ i = 1 d g − 1 h ( a ) i ⋅ R L W E z ( g i m ) = R L W E z ( m ⋅ ∑ i = 1 d g − 1 g i h ( a ) i ) \sum_{i=1}^{d_g-1} h(a)_i \cdot RLWE_z(g_im) = RLWE_z\left(m \cdot \sum_{i=1}^{d_g-1} g_ih(a)_i\right) i=1∑dg−1h(a)i⋅RLWEz(gim)=RLWEz
m⋅i=1∑dg−1gih(a)i
那么 BTS-Key 中的 R L W E ′ RLWE' RLWE′ 可以减少一个 R L W E RLWE RLWE 分量,外积也减少了一次 NTT 运算。噪声方差为:
( d g − 1 ) N σ 2 ⋅ B g 2 12 + V a r ( h ( a ) 0 ⋅ m ) (d_g-1)N\sigma^2 \cdot \frac{B_g^2}{12} + Var(h(a)_0 \cdot m) (dg−1)Nσ2⋅12Bg2+Var(h(a)0⋅m)
这里省去了一个 RLWE 数乘的噪声,但是多了一个近似误差。由于 h ( a ) 0 h(a)_0 h(a)0 是系数范围 B g B_g Bg 的均匀多项式,如果满足 V a r ( m ) ≤ σ 2 Var(m) \le \sigma^2 Var(m)≤σ2,这个噪声就比原始的 d g N σ 2 B g 2 / 12 d_gN\sigma^2B_g^2/12 dgNσ2Bg2/12 更小。
[KLD+23] 从打包密文中重构的盲旋转秘钥的噪声偏大( ∥ e ∥ ∞ ≥ B \|e\|_\infty \ge B ∥e∥∞≥B,破坏了更多的 LSB 信息),因此只丢弃第一分量并不适合(可以丢弃更多)。他们采用 [CGGI20] 中的近似分解(把实数环面放大 Q Q Q 倍),先选取一个近似因子 δ \delta δ,然后设置
g δ = ( δ , B δ , B 2 δ , ⋯ , B d − 1 δ ) g_\delta = (\delta, B\delta, B^2\delta, \cdots, B^{d-1}\delta) gδ=(δ,Bδ,B2δ,⋯,Bd−1δ)
其中满足 B d δ ≥ Q B^d\delta \ge Q Bdδ≥Q,那么环元素 a ∈ R Q a \in R_Q a∈RQ 可以分解为 ( a 0 , a 1 , ⋯ , a d − 1 ) ∈ R d (a_0,a_1,\cdots,a_{d-1}) \in R^d (a0,a1,⋯,ad−1)∈Rd,满足 ∥ a i ∥ ∞ ≤ B / 2 \|a_i\|_\infty \le B/2 ∥ai∥∞≤B/2(平衡的进制表示),使得近似误差 ∥ a − ∑ i a i B i δ ∥ ∞ \|a - \sum_i a_iB^i\delta\|_\infty ∥a−∑iaiBiδ∥∞ 最小化。文中没说怎么找出这个近似分解,我自己想了一下,可能是这么做的:
- 将环元素 a ∈ R Q a \in R_Q a∈RQ 写成平衡的代表,系数范围 ( − Q / 2 , Q / 2 ] (-Q/2,Q/2] (−Q/2,Q/2]
- 从 j = d − 1 , ⋯ , 1 , 0 j=d-1,\cdots,1,0 j=d−1,⋯,1,0 依次迭代,计算 a j = ⌊ a / ( B j δ ) ⌉ a_j=\lfloor a/(B^j\delta)\rceil aj=⌊a/(Bjδ)⌉,然后赋值 a = a − a j B j δ a = a-a_jB^j\delta a=a−ajBjδ,类似于浮点尾数
- 容易验证 ∥ a − ∑ i = j d − 1 a i B i δ ∥ ∞ ≤ B j δ / 2 \|a - \sum_{i=j}^{d-1} a_iB^i\delta\|_\infty \le B^j\delta/2 ∥a−∑i=jd−1aiBiδ∥∞≤Bjδ/2,最终会是 ≤ δ / 2 \le \delta/2 ≤δ/2
现在根据 g δ g_\delta gδ 来分解环元素,那么(近似的)强线性同态的密文形如:
R L W E z ′ ( m ) = ( R L W E z ( m δ ) , R L W E z ( m B δ ) , ⋯ , R L W E z ( m B d − 1 δ ) ) RLWE'_z(m) = (RLWE_z(m\delta), RLWE_z(mB\delta), \cdots, RLWE_z(mB^{d-1}\delta)) RLWEz′(m)=(RLWEz(mδ),RLWEz(mBδ),⋯,RLWEz(mBd−1δ))
假设近似误差是 ϵ = a − * g δ , h δ ( a ) * ∈ R \epsilon = a-\langle g_\delta,h_\delta(a)\rangle \in R ϵ=a−*gδ,hδ(a)*∈R,密文 R L W E ′ RLWE' RLWE′ 的噪声是 e ∈ R d e \in R^d e∈Rd,那么
( a ⊙ R L W E z ′ ( m ) ) ( z ) = * h δ ( a ) , R L W E z ′ ( 0 ) + m ⋅ g δ * ( z ) = ( * h δ ( a ) , R L W E z ′ ( 0 ) * + m ⋅ * h δ ( a ) , g δ * ) ( z ) = m ⋅ a + ( * h δ ( a ) , e * − m ⋅ ϵ ) \begin{aligned} (a \odot RLWE'_z(m))(z) &= \langle h_\delta(a), RLWE'_z(0)+m \cdot g_\delta\rangle(z)\\ &= (\langle h_\delta(a), RLWE'_z(0)\rangle + m \cdot \langle h_\delta(a), g_\delta\rangle)(z)\\ &= m \cdot a + (\langle h_\delta(a), e\rangle - m \cdot\epsilon) \end{aligned} (a⊙RLWEz′(m))(z)=*hδ(a),RLWEz′(0)+m⋅gδ*(z)=(*hδ(a),RLWEz′(0)*+m⋅*hδ(a),gδ*)(z)=m⋅a+(*hδ(a),e*−m⋅ϵ)
假设 R L W E ′ RLWE' RLWE′ 加密噪声的方差是 σ e r r 2 \sigma_{err}^2 σerr2,那么这个外积的方差是
V a r ( E r r ( a ⊙ R L W E z ′ ( m ) ) ) ≤ V a r ( * h δ ( a ) , e * ) + V a r ( m ⋅ ϵ ) ≤ d N ⋅ B 2 12 ⋅ σ e r r 2 + ∥ m ∥ 2 2 ⋅ δ 2 12 \begin{aligned} Var(Err(a \odot RLWE'_z(m))) &\le Var(\langle h_\delta(a), e\rangle) + Var(m \cdot\epsilon)\\ &\le dN\cdot \frac{B^2}{12} \cdot \sigma_{err}^2 + \|m\|_2^2 \cdot \frac{\delta^2}{12} \end{aligned} Var(Err(a⊙RLWEz′(m)))≤Var(*hδ(a),e*)+Var(m⋅ϵ)≤dN⋅12B2⋅σerr2+∥m∥22⋅12δ2
如果已知 m ∈ R m \in R m∈R 的形式,可以预先确定 ∥ m ∥ 2 2 \|m\|_2^2 ∥m∥22,从而找出对应的最合适的 δ \delta δ 取值(如果固定 B B B,则 d d d 是关于 δ \delta δ 的函数)。例如:对于盲旋转,使用 R L W E z ′ ( X a i s i ) RLWE'_z(X^{a_is_i}) RLWEz′(Xaisi),因此 ∥ m ∥ 2 2 = 1 \|m\|_2^2 = 1 ∥m∥22=1;对于二元秘密的密钥切换,使用 R L W E z ′ ( s ) RLWE'_z(s) RLWEz′(s),因此 ∥ m ∥ 2 2 ≤ N \|m\|_2^2 \le N ∥m∥22≤N。
Implementation
参数设置、运行结果:
好处是通信代价小于 1 MB,且自举密钥生成时间也很小。但是由于打包/解包带来的噪声增长,为了自举正确性 ACC 的模数变得很大,导致 ACC 维度翻倍,自举时间翻倍。
文章评论