FHE 的高精度算术:BGV-big、BFV-big

2023-10-31 09:28
文章标签 高精度 big 算术 fhe bgv bfv

本文主要是介绍FHE 的高精度算术:BGV-big、BFV-big,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考文献:

  1. [NL11] Naehrig M, Lauter K, Vaikuntanathan V. Can homomorphic encryption be practical?[C]//Proceedings of the 3rd ACM workshop on Cloud computing security workshop. 2011: 113-124.
  2. [GC15] Geihs M, Cabarcas D. Efficient integer encoding for homomorphic encryption via ring isomorphisms[C]//Progress in Cryptology-LATINCRYPT 2014: Third International Conference on Cryptology and Information Security in Latin America Florianópolis, Brazil, September 17–19, 2014 Revised Selected Papers 3. Springer International Publishing, 2015: 48-63.
  3. [CS16] Costache A, Smart N P. Which ring based somewhat homomorphic encryption scheme is best?[C]//Topics in Cryptology-CT-RSA 2016: The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29-March 4, 2016, Proceedings. Springer International Publishing, 2016: 325-340.
  4. [CSVW17] Costache A, Smart N P, Vivek S, et al. Fixed-point arithmetic in SHE schemes[C]//Selected Areas in Cryptography–SAC 2016: 23rd International Conference, St. John’s, NL, Canada, August 10-12, 2016, Revised Selected Papers 23. Springer International Publishing, 2017: 401-422.
  5. [CJLL17] Cheon J H, Jeong J, Lee J, et al. Privacy-preserving computations of predictive medical models with minimax approximation and non-adjacent form[C]//Financial Cryptography and Data Security: FC 2017 International Workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, Malta, April 7, 2017, Revised Selected Papers 21. Springer International Publishing, 2017: 53-74.
  6. [CLPX18] Chen H, Laine K, Player R, et al. High-precision arithmetic in homomorphic encryption[C]//Cryptographers’ Track at the RSA Conference. Cham: Springer International Publishing, 2018: 116-136.
  7. [BGGJ20] Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316-338.

文章目录

  • BGV-big-number
    • Bit Coefficient Encoding
    • Ring Isomorphism Encoding
  • BFV-big-number
    • New Level FHE
    • Fractional Encoder
      • odd base
      • even base
    • Result

BGV-big-number

类似于 [HS00] 的 NTRU 优化技巧,[GC15] 提出了 Ring Isomorphism Encoding 编码方案,使用形如 p = x − b p=x-b p=xb 的明文模数,给出了高精度整数的 BV/BGV 变体

Bit Coefficient Encoding

[NL11] 给出了 BFV 的代码实现。除此之外,它还给出了如何把平凡的消息空间(整数、比特串)的编码到明文多项式环 R p = Z p [ x ] / ( x N + 1 ) R_p=\mathbb Z_p[x]/(x^N+1) Rp=Zp[x]/(xN+1)。这种编码方案,被 [GC15] 称为 BCE 编码。

BCE.Encode:给定 n n n 比特的整数 m m m,二进制分解,编码为多项式:
p m ( x ) = ∑ i = 0 n − 1 m i x i p_m(x) = \sum_{i=0}^{n-1} m_ix^i pm(x)=i=0n1mixi

BCE.Decode:就是 m = p m ( 2 ) m = p_m(2) m=pm(2),多项式求值。

运算就是多项式加法/多项式乘法,

  • 对于 l l l 个整数的连续加法,需要 p > l p>l p>l
  • 对于 l l l 个整数的连续乘法,需要 N > n l N>nl N>nl,并且 p > n l − 1 p>n^{l-1} p>nl1

Ring Isomorphism Encoding

但是 BCE 的两个空间并非同构,因此需要追踪是否越界 p p p 以及 x n + 1 x^n+1 xn+1

[GC15] 提出了另一种编码方式: 明文多项式环 R p = Z [ x ] / ( x N + 1 , p ) R_p=\mathbb Z[x]/(x^N+1,p) Rp=Z[x]/(xN+1,p),其中的 p ∈ Z [ x ] p \in \mathbb Z[x] pZ[x] 是多项式(不必是常数)。

特别地,对于 a ∈ Z a \in \mathbb Z aZ,映射 ϕ : Z [ x ] / ( x n + 1 , x − a ) → Z / ( a n + 1 ) \phi: \mathbb Z[x]/(x^n+1,x-a) \to \mathbb Z/(a^n+1) ϕ:Z[x]/(xn+1,xa)Z/(an+1) 定义为
f ( x ) + ( x n + 1 , x − a ) ↦ f ( a ) + ( a n + 1 ) f(x)+(x^n+1,x-a) \mapsto f(a) + (a^n+1) f(x)+(xn+1,xa)f(a)+(an+1)

容易验证 ϕ \phi ϕ 是两个整环的同构映射

对于不同的 a a a,环 R p R_p Rp 可以同构于:整环、有限域、整环直积,代码实现的效率也有差异。方便起见,[GC15] 选取了 p = x − 2 p=x-2 p=x2,此时 R p ≅ Z 2 n + 1 R_p \cong \mathbb Z_{2^n+1} RpZ2n+1 环同构。我们需要约束下 R p R_p Rp 的代表元的范围,
T n = { a ( x ) = ∑ i = 0 n − 1 a i x i : a i ∈ { 0 , ± 1 } } T_n = \{a(x) = \sum_{i=0}^{n-1} a_ix^i:a_i \in \{0,\pm 1\} \} Tn={a(x)=i=0n1aixi:ai{0,±1}}

易知 ∣ T n ∣ = 3 n > 2 n + 1 |T_n| = 3^n>2^n+1 Tn=3n>2n+1,从而这个集合包含了全部的 R p R_p Rp 代表元。例如, 2 x 2 + x + 1 ≡ ( x − 2 ) x 2 + 2 x 2 + x + 1 ≡ x 3 + x + 1 ( m o d x − 2 ) 2x^2+x+1 \equiv (x-2)x^2 + 2x^2+x+1 \equiv x^3 + x + 1\pmod{x-2} 2x2+x+1(x2)x2+2x2+x+1x3+x+1(modx2)取模 p = x − 2 p=x-2 p=x2 时,并非是把高次项都消除,而是要将较大的系数消除,多项式次数甚至会更高了)。

RIE.Encode:给定整数 z ∈ Z z \in \mathbb Z zZ,取值范围 [ − 2 n − 1 , ⋯ , 0 , ⋯ , 2 n − 1 ] [-2^{n-1},\cdots,0,\cdots,2^{n-1}] [2n1,,0,,2n1]

  1. 寻找 z i ∈ { 0 , ± 1 } z_i \in \{0,\pm1\} zi{0,±1},满足
    z ≡ ∑ i = 0 n − 1 z i 2 i ( m o d 2 n + 1 ) z\equiv \sum_{i=0}^{n-1} z_i 2^i \pmod{2^n+1} zi=0n1zi2i(mod2n+1)

    并且要使得 ∑ i ∣ z i ∣ \sum_i |z_i| izi 最小化

  2. 编码为多项式
    m ( x ) = ∑ i = 0 n − 1 z i x i m(x) = \sum_{i=0}^{n-1} z_i x^i m(x)=i=0n1zixi

    可以验证 ϕ : m ( x ) → z \phi:m(x) \to z ϕ:m(x)z 成立

RIE.Decode:给定多项式 m ∈ R p m \in R_p mRp(系数不一定还是 { 0 , ± 1 } \{0,\pm 1\} {0,±1} 的)

  1. 多项式求值 z ′ = m ( 2 ) ( m o d 2 n + 1 ) z' = m(2) \pmod{2^n+1} z=m(2)(mod2n+1),取值范围 [ 0 , ⋯ , 2 n ] [0,\cdots,2^n] [0,,2n]
  2. z ′ > 2 n − 1 z'>2^{n-1} z>2n1 时,输出 z ′ − ( 2 n + 1 ) z'-(2^n+1) z(2n+1)(负数)
  3. 否则,直接输出 z ′ z' z(正数)

因为 R p ≅ Z a n + 1 R_p \cong \mathbb Z_{a^n+1} RpZan+1,因此 RIE 码字的同态运算是自然的(不必担心 p p p x n + 1 x^n+1 xn+1 是否溢出):多项式加法就是整数加法、多项式乘法就是整数乘法。此外,如果 a n + 1 a^n+1 an+1 可以分解为一些互素的因子 n 1 , ⋯ , n t n_1,\cdots,n_t n1,,nt,那么就有 CRT 分解(SIMD 槽)
R p ≅ Z a n + 1 ≅ ∏ i = 1 t Z n i R_p \cong \mathbb Z_{a^n+1} \cong \prod_{i=1}^t \mathbb Z_{n_i} RpZan+1i=1tZni

对于 RLWE-based BGV 方案,

  • 密文的代数结构是 R q L R_{q_L} RqL,密文模数 q L q_L qL 是素数的乘积(常数多项式)
  • 明文的代数结构是 R p R_p Rp,明文模数 p = x − 2 p=x-2 p=x2 是个多项式

对于加密、解密、同态运算、秘钥切换,除了把 ( m o d p ) \pmod p (modp) 替换为了 ( m o d x − b ) \pmod{x-b} (modxb),这个 BGV 变体的计算方式都是与原始方案一样的。略微修改 BGV 的模切换算法,就可以适应这个明文模数。算法 s c a l e ( c , q , q ′ , p ) scale(c,q,q',p) scale(c,q,q,p)

  1. 对于密文模数 q ′ < q q'<q q<q,满足 q ≡ q ′ ≡ 1 m o d p q \equiv q' \equiv 1 \mod p qq1modp
  2. R q R_q Rq 提升到 Q [ x ] \mathbb Q[x] Q[x],计算 y = ( q ′ / q ) c ∈ Q [ x ] y = (q'/q)c \in \mathbb Q[x] y=(q/q)cQ[x]
  3. 寻找多项式 c ′ ∈ Z [ x ] c' \in \mathbb Z[x] cZ[x],满足如下条件
    • 保持解密正确性:只需满足 c ′ ≡ c ( m o d x n + 1 , x − 2 ) c' \equiv c \pmod{x^n+1,x-2} cc(modxn+1,x2)
    • 最小化舍入噪声:使得系数向量的距离 ∥ y − c ′ ∥ ∞ \|y-c'\|_\infty yc 最小化

可以证明,对于 p = x − 2 p=x-2 p=x2,舍入噪声的规模为 ∥ y − c ′ ∥ ∞ ≤ 1.5 \|y-c'\|_\infty \le 1.5 yc1.5

BFV-big-number

[CLPX18] 将上述的 RIE 应用到了 B/FV 方案上,得到了高精度整数的 B/FV 变体,并且给出了有理数的编码方案(分数格式)。另外它利用 [CS16] 提出的平均情况下的启发式噪声上界(heuristic upper bounds for the noise growth),评估了这个 BFV 变体的噪声增长(原始 B/FV 使用最坏的噪声估计,参数很不紧)。

New Level FHE

类似于 BCE,我们令消息空间 M = [ − ⌈ b n / 2 ⌉ , ⌊ b n / 2 ⌋ ] ∩ Z M = [-\lceil b^n/2 \rceil, \lfloor b^n/2 \rfloor] \cap \mathbb Z M=[bn/2,bn/2⌋]Z(大小为 b n + 1 b^n+1 bn+1 的对称区间)。那么,对于任意的 m ∈ M m \in M mM,总是存在至少一个短的多项式 m ^ ( x ) ∈ Z [ x ] \hat m(x) \in \mathbb Z[x] m^(x)Z[x],满足 deg ⁡ m ^ ≤ n − 1 \deg \hat m \le n-1 degm^n1 以及 ∥ m ^ ∥ ∞ ≤ ( b + 1 ) / 2 \|\hat m\|_\infty \le (b+1)/2 m^(b+1)/2(如果系数大小约束为 b / 2 b/2 b/2 则只能表示 b n b^n bn 个元素),使得 m ^ ( b ) = m ( m o d b n + 1 ) \hat m(b)=m \pmod{b^n+1} m^(b)=m(modbn+1)

我们设置明文模数 p = x − b ∈ Z [ x ] p=x-b \in \mathbb Z[x] p=xbZ[x],密文模数 q ∈ Z q \in \mathbb Z qZ,BFV 工作的多项式环 R = Z [ x ] / ( x n + 1 ) R=\mathbb Z[x]/(x^n+1) R=Z[x]/(xn+1),其中 n n n 是二的幂次。那么,
R / p R ≅ Z / ( b n + 1 ) Z m ^ ( x ) ↦ m = m ^ ( b ) R/pR \cong \mathbb Z/(b^n+1)\mathbb Z\\ \hat m(x) \mapsto m=\hat m(b) R/pRZ/(bn+1)Zm^(x)m=m^(b)

可以验证, p = x − b p=x-b p=xb 在分圆数域 Q [ x ] / ( x n + 1 ) \mathbb Q[x]/(x^n+1) Q[x]/(xn+1) 中的逆元为:
p − 1 = − 1 b n + 1 ( x n − 1 + b x n − 2 + ⋯ + b b n − 1 ) ∈ Q [ x ] p^{-1} = -\dfrac{1}{b^n+1} (x^{n-1} + bx^{n-2} + \cdots + b^{b^{n-1}}) \in \mathbb Q[x] p1=bn+11(xn1+bxn2++bbn1)Q[x]

因此,我们定义
Δ b : = ⌊ q p ⌉ = ⌊ − q b n + 1 ( x n − 1 + b x n − 2 + ⋯ + b b n − 1 ) ⌉ ∈ Z [ x ] \Delta_b := \left\lfloor \dfrac{q}{p} \right\rceil = \left\lfloor -\dfrac{q}{b^n+1} (x^{n-1} + bx^{n-2} + \cdots + b^{b^{n-1}}) \right\rceil \in \mathbb Z[x] Δb:=pq=bn+1q(xn1+bxn2++bbn1)Z[x]

构造出 BFV 变体,

  • 秘钥:私钥 s k = s ∈ R sk=s \in R sk=sR,公钥 p k = ( p 0 , p 1 ) ∈ R q 2 pk=(p_0,p_1) \in R_q^2 pk=(p0,p1)Rq2,满足 p 0 + p 1 s = e ≈ 0 ( m o d q ) p_0+p_1s = e\approx 0 \pmod{q} p0+p1s=e0(modq)

  • 加密:消息 m ∈ M m \in M mM 是有界的整数,编码为多项式 m ^ ( x ) ∈ R p \hat m(x) \in R_p m^(x)Rp,短随机带 r ∈ R r \in R rR,中心离散高斯 e 0 , e 1 ∈ R e_0,e_1 \in R e0,e1R
    c t : = ( [ Δ b ⋅ m ^ + p 0 r + e 0 ] q , [ p 1 r + e 1 ] q ) ∈ R q 2 ct := ([\Delta_b \cdot \hat m + p_0r + e_0]_q, [p_1r + e_1]_q) \in R_q^2 ct:=([Δbm^+p0r+e0]q,[p1r+e1]q)Rq2

  • 解密:密文 c t = ( c 0 , c 1 ) ct=(c_0,c_1) ct=(c0,c1),计算
    m ^ = ⌊ x − b q [ c 0 + c 1 s ] q ⌉ ∈ R p \hat m = \left\lfloor \dfrac{x-b}{q} [c_0+c_1s]_q \right\rceil \in R_p m^=qxb[c0+c1s]qRp

    输出 m = m ^ ( b ) ∈ M m = \hat m(b) \in M m=m^(b)M

  • 加法:输入 c t 0 , c t 1 ct_0,ct_1 ct0,ct1,输出 c t a d d = c t 0 + c t 1 ct_{add} = ct_0 + ct_1 ctadd=ct0+ct1

  • 乘法:输入 c t 0 = ( c 0 , c 1 ) , c t 1 = ( d 0 , d 1 ) ct_0=(c_0,c_1),ct_1=(d_0,d_1) ct0=(c0,c1),ct1=(d0,d1),计算 c t m u l t ′ = ( c 0 ′ , c 1 ′ , c 2 ′ ) ∈ R q 3 ct_{mult}'=(c_0',c_1',c_2') \in R_q^3 ctmult=(c0,c1,c2)Rq3,其中
    c 0 ′ = [ ⌊ x − b q ( c 0 d 0 ) ⌉ ] q c 1 ′ = [ ⌊ x − b q ( c 0 d 0 + c 1 d 0 ) ⌉ ] q c 2 ′ = [ ⌊ x − b q ( c 1 d 1 ) ⌉ ] q \begin{aligned} c_0' &= \left[\left\lfloor \dfrac{x-b}{q} (c_0d_0) \right\rceil\right]_q\\ c_1' &= \left[\left\lfloor \dfrac{x-b}{q} (c_0d_0+c_1d_0) \right\rceil\right]_q\\ c_2' &= \left[\left\lfloor \dfrac{x-b}{q} (c_1d_1) \right\rceil\right]_q\\ \end{aligned} c0c1c2=[qxb(c0d0)]q=[qxb(c0d0+c1d0)]q=[qxb(c1d1)]q

    然后执行 Relinearize 操作,得到 c t m u l t ∈ R q 2 ct_{mult} \in R_q^2 ctmultRq2

我们采取启发式的噪声估计,规范嵌入范数(Canonical Embedding Norm)定义为
∥ a ∥ ∞ c a n : = ∥ ( a ( ζ m i ) ) i ∈ Z m ∗ ∥ ∞ \|a\|_\infty^{can} := \|(a(\zeta_m^i))_{i \in \mathbb Z_m^*}\|_\infty acan:=(a(ζmi))iZm

其中 ζ m ∈ C \zeta_m \in \mathbb C ζmC 是本原单位根。它有良好的性质,

  • 适合评估乘积的范数, ∥ a ⋅ b ∥ ∞ c a n ≤ ∥ a ∥ ∞ c a n ⋅ ∥ b ∥ ∞ c a n \|a \cdot b\|_\infty^{can} \le \|a\|_\infty^{can} \cdot \|b\|_\infty^{can} abcanacanbcan
  • 约束了 L1 范数的下界, ∥ a ∥ ∞ c a n ≤ ∥ a ∥ 1 \|a\|_\infty^{can} \le \|a\|_1 acana1
  • 约束了无穷范数的上界, ∥ a ∥ ∞ ≤ c m ⋅ ∥ a ∥ ∞ c a n \|a\|_\infty \le c_m \cdot\|a\|_\infty^{can} acmacan,其中 c m = ∥ C R T m − 1 ∥ ∞ c_m=\|CRT_m^{-1}\|_\infty cm=CRTm1 是只和 m m m 有关的环常数(ring constant)

启发式的,如果 a ∈ R Q a \in R_\mathbb Q aRQ 的各个系数是根据标准差 σ \sigma σ 独立采样的,那么以压倒性概率满足 ∥ a ∥ ∞ c a n ≤ 6 σ n \|a\|_\infty^{can} \le 6 \sigma\sqrt n acan6σn ,除了 e r f c ( 6 ) ≈ 2 − 55 erfc(6) \approx 2^{-55} erfc(6)255 的小尾巴。

  1. 同态加法的噪声,
    ∥ E r r ( v a d d ) ∥ c a n ≤ ∥ E r r ( v 1 ) ∥ c a n + ∥ E r r ( v 2 ) ∥ c a n \|Err(v_{add})\|^{can} \le \|Err(v_{1})\|^{can} + \|Err(v_{2})\|^{can} Err(vadd)canErr(v1)can+Err(v2)can

  2. 同态乘法的噪声,
    ∥ E r r ( v m u l t ) ∥ c a n ≲ 14 ( b + 1 ) n max ⁡ { ∥ E r r ( v 1 ) ∥ c a n , ∥ E r r ( v 2 ) ∥ c a n } \|Err(v_{mult})\|^{can} \lesssim 14(b+1)n\max\{\|Err(v_{1})\|^{can},\|Err(v_{2})\|^{can}\} Err(vmult)can14(b+1)nmax{Err(v1)can,Err(v2)can}

Fractional Encoder

类似于 SEAL 的思路,[CLPX18] 也是采用基于分数的有理数编码器,而非基于缩放的有理数编码器,[CSVW17] 证明了这两种有理数编码器同构,但是后者需要追踪 scale 的大小。

抽象地,分数编码器是 ( P , E n c o d e , D e c o d e ) (P,Encode,Decode) (P,Encode,Decode),其中 P ⊆ Q P \subseteq \mathbb Q PQ 是有限子集,编码函数 E n c o d e : P → M Encode:P \to M Encode:PM,解码函数 D e c o d e : M → P Decode: M \to P Decode:MP,我们要求:

  1. 编码器是可逆的( E n c o d e Encode Encode单射 D e c o d e Decode Decode左逆),
    D e c o d e ( E n c o d e ( x ) ) = x , ∀ x ∈ P Decode(Encode(x)) = x,\forall x \in P Decode(Encode(x))=x,xP

  2. 具有同态的性质,
    E n c o d e ( x + y ) = E n c o d e ( x ) + E n c o d e ( y ) E n c o d e ( x y ) = E n c o d e ( x ) ⋅ E n c o d e ( y ) Encode(x+y) = Encode(x)+Encode(y)\\ Encode(xy) = Encode(x)\cdot Encode(y) Encode(x+y)=Encode(x)+Encode(y)Encode(xy)=Encode(x)Encode(y)

设置 M = Z / ( b n + 1 ) Z M = \mathbb Z/(b^n+1)\mathbb Z M=Z/(bn+1)Z,定义编码函数为
E n c o d e ( x y ) = x y − 1 ( m o d b n + 1 ) Encode\left(\dfrac{x}{y}\right) = xy^{-1} \pmod{b^n+1} Encode(yx)=xy1(modbn+1)

现在,我们需要选择合适的 P P P(比如 g c d ( y , b n + 1 ) ≠ 1 gcd(y,b^n+1) \neq 1 gcd(y,bn+1)=1 就明显不可逆),并构造对应的解码函数,使得它们满足我们要求的可逆、同态的性质。

odd base

假如 b ∈ Z b \in \mathbb Z bZ 是奇数,设置
P = { c ⋅ b n / 2 + d b n / 2 : c , d ∈ [ − b n / 2 − 1 2 , b n / 2 − 1 2 ] ∩ Z } P = \left\{ \dfrac{c \cdot b^{n/2} + d}{b^{n/2}}: c,d \in \left[-\dfrac{b^{n/2}-1}{2},\dfrac{b^{n/2}-1}{2}\right] \cap \mathbb Z \right\} P={bn/2cbn/2+d:c,d[2bn/21,2bn/21]Z}

可以证明,上述定义的 E n c o d e : P → M Encode: P \to M Encode:PM 是单射,其中 ( b n / 2 ) − 1 = − b n / 2 ( m o d b n + 1 ) (b^{n/2})^{-1} = -b^{n/2} \pmod{b^n+1} (bn/2)1=bn/2(modbn+1)

定义它的左逆,对于 z ∈ E n c o d e ( P ) z \in Encode(P) zEncode(P)
D e c o d e ( z ) = [ z ⋅ b n / 2 ] b n + 1 b n / 2 Decode(z) = \dfrac{[z \cdot b^{n/2}]_{b^n+1}}{b^{n/2}} Decode(z)=bn/2[zbn/2]bn+1

可以验证 ( P , E n c o d e , D e c o d e ) (P,Encode,Decode) (P,Encode,Decode) 满足我们的抽象要求。

even base

假如 b ∈ Z b \in \mathbb Z bZ 是偶数,由于证明编码函数是单射的限制,需要把整数部分 c c c 或者小数部分 d d d 的位数降低一位(没看懂里面的 b / ( b − 1 ) b/(b-1) b/(b1) 代表什么意思)。我们把 d d d 减少到 n / 2 − 1 n/2-1 n/21 位,那么
P = { c ⋅ b n / 2 − 1 + d b n / 2 − 1 : c ∈ [ − ( b n / 2 − 1 ) b 2 ( b − 1 ) , ( b n / 2 − 1 ) b 2 ( b − 1 ) ] ∩ Z , d ∈ [ − ( b n / 2 − 1 − 1 ) b 2 ( b − 1 ) , ( b n / 2 − 1 − 1 ) b 2 ( b − 1 ) ] ∩ Z } P = \left\{ \dfrac{c \cdot b^{n/2-1} + d}{b^{n/2-1}}: c \in \left[-\dfrac{(b^{n/2}-1)b}{2(b-1)},\dfrac{(b^{n/2}-1)b}{2(b-1)}\right] \cap \mathbb Z,\,\, d \in \left[-\dfrac{(b^{n/2-1}-1)b}{2(b-1)},\dfrac{(b^{n/2-1}-1)b}{2(b-1)}\right] \cap \mathbb Z \right\} P={bn/21cbn/21+d:c[2(b1)(bn/21)b,2(b1)(bn/21)b]Z,d[2(b1)(bn/211)b,2(b1)(bn/211)b]Z}

可以证明,上述定义的 E n c o d e : P → M Encode: P \to M Encode:PM 是单射,其中 ( b n / 2 − 1 ) − 1 = − b n / 2 + 1 ( m o d b n + 1 ) (b^{n/2-1})^{-1} = -b^{n/2+1} \pmod{b^n+1} (bn/21)1=bn/2+1(modbn+1)

定义它的左逆,对于 z ∈ E n c o d e ( P ) z \in Encode(P) zEncode(P)
D e c o d e ( z ) = [ z ⋅ b n / 2 − 1 ] b n + 1 b n / 2 − 1 Decode(z) = \dfrac{[z \cdot b^{n/2-1}]_{b^n+1}}{b^{n/2-1}} Decode(z)=bn/21[zbn/21]bn+1

可以验证 ( P , E n c o d e , D e c o d e ) (P,Encode,Decode) (P,Encode,Decode) 满足我们的抽象要求。

Result

使用正则电路(regular circuit): A A A 层加法, 1 1 1 层乘法,迭代 L L L 轮,整数范围 [ − L , L ] [-L,L] [L,L],来评估 BFV-big-number 的效率。

原始 BFV,采取 [CJLL17] 的 NAF 编码器,

在这里插入图片描述

本文的高精度 BFV 变体,

在这里插入图片描述

这篇关于FHE 的高精度算术:BGV-big、BFV-big的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/314362

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

高精度打表-Factoring Large Numbers

求斐波那契数,不打表的话会超时,打表的话普通的高精度开不出来那么大的数组,不如一个int存8位,特殊处理一下,具体看代码 #include<stdio.h>#include<string.h>#define MAX_SIZE 5005#define LEN 150#define to 100000000/*一个int存8位*/int num[MAX_SIZE][LEN];void

高精度计算----减法运算(浮点型)

基于上一贴,修改减法运算适合于高精度浮点型计算。 因为减法比加法难度大一点,考虑的地方也要多一些,可能代码有欠缺,欢迎指出。 运算说明: 1、相减函数依旧没改变,包括上一贴的判断被减数与减数的大小函数也没变。 2、增加两个函数,取小数位数函数和结果处理(回归小数点)函数 3、与加法浮点高精度运算相比,这里改变较多的是结果处理函数,加法加完后,位数不减反增,而且最多增一位。减法会消失掉好多

高精度计算----减法运算

处理大数减法运算: 1、首先要判断被减数与减数哪个更大,再相应的带入减法函数去处理。具体的比较可以使用字符串的相关知识去比较。 2、相减要先对齐数组,依照减数的长度,执行相应的减法运算次数。 3、不需要借位相减的话,直接减去;需要的话,向前借一位,若前一位是0,则再前借(此时前一位的0变为10)。 测试程序效果如下:   以下代码包括相减函数,比较被减数减数函数,若有错误,请指出:

高精度加法,乘法,阶乘

#include <iostream>#include <map>#include <string>#include <algorithm>using namespace std;const int Max = 50000;string str1,str2;/***********乘法***********/void chenfa(){cin >> str1>>str2;int a

【OpenCV2.2】图像的算术与位运算(图像的加法运算、图像的减法运算、图像的融合)、OpenCV的位运算(非操作、与运算、或和异或)

1 图像的算术运算 1.1 图像的加法运算 1.2 图像的减法运算 1.3 图像的融合 2 OpenCV的位运算 2.1 非操作 2.2 与运算 2.3 或和异或 1 图像的算术运算 1.1 图像的加法运算 add opencv使用add来执行图像的加法运算 图片就是矩阵, 图片的加法运算就是矩阵的加法运算, 这就要求加法运算的两张图shape必须是相同的. # 图片加法imp

高精度治具加工的重要性和创新性

在现代制造业中,高精度治具加工扮演着至关重要的角色。它不仅是生产过程中的关键环节,更是推动行业不断创新和发展的重要力量。时利和将解析高精度治具加工的重要性和创新性。   一、高精度治具加工的重要性   1.确保产品质量   高精度治具能够为生产过程提供准确的定位、夹紧和导向功能,从而确保产品的尺寸精度、形状精度和表面质量。例如,在电子制造领域,高精度的治具可以保证芯片的精确安装,提高电子

【HDU】4927 Series 1 高精度

传送门:【HDU】4927 Series 1 题目分析:公式很好推,到最后就是C(n-1,0)*a[n]-C(n-1,1)*a[n-1]+C(n-1,2)*a[n-2]+...+C(n-1,n-1)*a[n]。 用C(n,k)=C(n,k-1)*(n-k+1)/k即可快速得到一行的二项式系数。 我看JAVA不到1000B 15分钟就能过。。。我又敲了大数模板然后将近2个小时才过T U

从VHDL代码到真实硬件:设计一个8位算术逻辑单元

在这个项目中,我们使用VHDL语言创建了一个8位算术逻辑单元(ALU),并在连接到带有输入开关和LED显示器的自定义PCB的Altera CPLD开发板上运行它。 本文引用地址:https://www.eepw.com.cn/article/202409/462593.htm 使用基于硬件的方法开发电子系统并不总是需要将各种晶体管和逻辑门物理连接到面包板或PCB上。可以使用离散逻辑构建算术逻辑单

高精度加、减、乘、除(高精除以低精)

高精度加法 法1:P1601 A+B Problem(高精) #include <bits/stdc++.h>using namespace std;char s1[510], s2[510];int a[510], b[510], sum[510];int lena, lenb, lens;int main(){cin >> s1 >> s2;lena=strlen(s1);le