作者: Plot 邮箱：NoNeedToKnow@xxx.xx
在BFV中，密文的模数q q q q q q { p 0 , p 1 , … , p L } \{p_0,p_1,\dots,p_L\} { p 0 , p 1 , … , p L } q l ( 0 ≤ l ≤ L ) q_l (0\leq l \leq L) q l ( 0 ≤ l ≤ L ) l l l L L L l l l l − 1 l -1 l − 1
另外在BFV中，明文处在密文的顶端，即MSB（Most Significant Bits），这是通过缩放 Δ \Delta Δ
与BFV相似，BGV的明文，密文空间如下：
Plaintext: P = R t = Z t [ x ] / ( x n + 1 ) \mathcal{P} = R_t = \mathbb{Z}_t[x]/(x^n+1) P = R t = Z t [ x ] / ( x n + 1 ) t ∈ Z t \in \mathbb{Z} t ∈ Z Ciphertext: C = R q l × R q l \mathcal{C} = R_{q_l} \times R_{q_l} C = R q l × R q l R q l ∈ Z q l [ x ] / ( x n + 1 ) R_{q_l} \in \mathbb{Z}_{q_l}[x]/(x^n +1) R q l ∈ Z q l [ x ] / ( x n + 1 ) q l ∈ Z q_l \in \mathbb{Z} q l ∈ Z l l l 一般，n = 2 k n = 2^k n = 2 k k ∈ Z k \in \mathbb{Z} k ∈ Z q q q t t t
与BFV相似，BGV的参数除了包含1.1中( t , q , n ) (t,q,n) ( t , q , n )
R 2 R_2 R 2 { − 1 , 0 , 1 } \{-1,0,1\} { − 1 , 0 , 1 } X \mathcal{X} X R q R_q R q R q R_q R q 与BFV相似，BGV可使用整数编码方案(The integer encoding scheme)： 对于给定的Message m m m M M M
二进制表示m m m m = a n − 1 … a 2 a 1 a 0 m = a_{n-1}\dots a_2a_1a_0 m = a n − 1 … a 2 a 1 a 0 转成多项式M = a n − 1 x n − 1 + ⋯ + a 2 x 2 + a 1 x + a 0 M =a_{n-1}x^{n-1}+\dots+a_2x^2+a_1x+a_0 M = a n − 1 x n − 1 + ⋯ + a 2 x 2 + a 1 x + a 0 在后续计算的过程中，系数和阶数都会增长，所以我们要确保
系数不超过t t t 阶数不超过n n n SK : 从R 2 R_2 R 2 { − 1 , 0 , 1 } \{-1,0,1\} { − 1 , 0 , 1 }
PK ：是一对多项式（P K 1 PK_1 P K 1 P K 2 PK_2 P K 2
P K 1 = [ − 1 ( a ⋅ SK + t ⋅ e ) ] q L PK_1 = [-1(a\cdot\text{SK} + t\cdot e)]_{q_L} P K 1 = [ − 1 ( a ⋅ SK + t ⋅ e ) ] q L P K 2 = a PK_2 =a P K 2 = a 其中 a a a R q ∈ Z q [ x ] / ( x n + 1 ) R_q \in \mathbb{Z}_q[x]/(x^n +1) R q ∈ Z q [ x ] / ( x n + 1 ) e e e X \mathcal{X} X [ ⋅ ] q [\cdot]_q [ ⋅ ] q q q q e e e t t t
加密： 首先生成三个小的 随机多项式，u u u R 2 R_2 R 2 e 1 , e 2 e_1,e_2 e 1 , e 2 X \mathcal{X} X
然后生成密文（Ciphertext）C = ( C 1 , C 2 ) C = (C_1,C_2) C = ( C 1 , C 2 )
C 1 = [ P K 1 ⋅ u + t ⋅ e 1 + M ] q l C_1 = [PK_1\cdot u +t\cdot e_1+ M]_{q_l} C 1 = [ P K 1 ⋅ u + t ⋅ e 1 + M ] q l C 2 = [ P K 2 ⋅ u + t ⋅ e 2 ] q l C_2 = [PK_2 \cdot u +t\cdot e_2]_{q_l} C 2 = [ P K 2 ⋅ u + t ⋅ e 2 ] q l 在密文 C 1 C_1 C 1 e e e t t t M M M Δ \Delta Δ
对比BFV中的加密方式：
C 1 = [ P K 1 ⋅ u + e 1 + Δ M ] q C_1 = [PK_1\cdot u +e_1+\Delta M]_q C 1 = [ P K 1 ⋅ u + e 1 + Δ M ] q C 2 = [ P K 2 ⋅ u + e 2 ] q C_2 = [PK_2 \cdot u +e_2]_q C 2 = [ P K 2 ⋅ u + e 2 ] q 我们可以得到以下的密文结构对比图：
解密： 解密就是加密的逆过程，M M M
M = [ [ C 1 + C 2 ⋅ S K ] q l ] t M = [[C_1+C_2\cdot SK]_{q_l}]_t M = [[ C 1 + C 2 ⋅ S K ] q l ] t 其中：
C 1 + C 2 ⋅ S K = M + t ⋅ v C_1 + C_2 \cdot SK = M + t\cdot v C 1 + C 2 ⋅ S K = M + t ⋅ v 因此得确保∥ v ∥ ∞ < q l 2 t \|v\|_\infty < \frac{q_l}{2t} ∥ v ∥ ∞ < 2 t q l M M M
加法与BFV类似。
E v a l A d d ( C 1 , C 2 ) = ( [ C 1 1 + C 1 2 ] q l , [ C 2 1 + C 2 2 ] q l ) = ( C 1 3 , C 2 3 ) = C 3 EvalAdd(C^1,C^2) = ([C^1_1 + C^2_1]_{q_l},[C^1_2 +C^2_2]_{q_l}) = (C^3_1,C^3_2) = C^3 E v a l A dd ( C 1 , C 2 ) = ([ C 1 1 + C 1 2 ] q l , [ C 2 1 + C 2 2 ] q l ) = ( C 1 3 , C 2 3 ) = C 3 其证明较为简单，略。在最坏的情况，C 3 C^3 C 3 C 1 C^1 C 1 C 2 C^2 C 2
与BFV中类似，我们先尝试将两个密文解密后相乘C 1 ( S K ) ⋅ C 2 ( S K ) C^1(SK)\cdot C^2(SK) C 1 ( S K ) ⋅ C 2 ( S K )
C 1 ( S K ) = M 1 + t ⋅ v 1 + q ⋅ r 1 C 2 ( S K ) = M 2 + t ⋅ v 2 + q ⋅ r 2 \begin{aligned} C^1(SK) = M^1 +t\cdot v_1 + q\cdot r_1 \\ C^2(SK) = M^2 +t\cdot v_2 + q\cdot r_2 \end{aligned} C 1 ( S K ) = M 1 + t ⋅ v 1 + q ⋅ r 1 C 2 ( S K ) = M 2 + t ⋅ v 2 + q ⋅ r 2 那么，
( C 1 ⋅ C 2 ) ( S K ) = M 1 ⋅ M 2 + t ( M 1 ⋅ v 2 + M 2 ⋅ v 1 + t ⋅ v 1 ⋅ v 2 ) \begin{aligned} (C^1\cdot C^2)(SK) = M^1\cdot M^2 + t(M^1\cdot v_2 + M^2\cdot v_1 + t\cdot v_1 \cdot v_2) \end{aligned} ( C 1 ⋅ C 2 ) ( S K ) = M 1 ⋅ M 2 + t ( M 1 ⋅ v 2 + M 2 ⋅ v 1 + t ⋅ v 1 ⋅ v 2 ) 可以发现，密文的噪音是以乘积 t ⋅ v 1 ⋅ v 2 t\cdot v_1 \cdot v_2 t ⋅ v 1 ⋅ v 2
同样的，BGV的乘法可用如下表示：
E v a l M u l t ( C 1 , C 2 ) = ( [ C 1 1 + C 1 2 ] q l , [ C 1 1 ⋅ C 2 2 + C 2 1 ⋅ C 1 2 ] q l , [ C 2 1 + C 2 2 ] q l ) EvalMult(C^1,C^2)=([C^1_1 + C^2_1]_{q_l},[C^1_1\cdot C^2_2 + C^1_2\cdot C^2_1]_{q_l},[C^1_2 + C^2_2]_{q_l}) E v a lM u lt ( C 1 , C 2 ) = ([ C 1 1 + C 1 2 ] q l , [ C 1 1 ⋅ C 2 2 + C 2 1 ⋅ C 1 2 ] q l , [ C 2 1 + C 2 2 ] q l ) 与BFV类似，在BGV中，密文多项式经过乘法后，由两项变为三项，所以需要用到重线性化的技术。
乘法在密文结构图上的表示如下：
与BFV类似，BGV的重线性化只是有模数的差别。 重线性化就是在乘法后，将三项密文变为两项。 问题可形式化为，对于密文C = { C 1 , C 2 , C 3 } C = \{C_1,C_2,C_3\} C = { C 1 , C 2 , C 3 } C ∗ = { C 1 ∗ , C 2 ∗ } C^* = \{C_1^*,C_2^*\} C ∗ = { C 1 ∗ , C 2 ∗ }
[ C 1 + C 2 ⋅ S K + C 3 ⋅ S K 2 ] q l ≈ [ C 1 ∗ + C 2 ∗ ⋅ S K + r ] q l [C_1 + C_2 \cdot SK + C_3 \cdot SK^2]_{q_l} \approx [C_1^* + C_2^*\cdot SK + r]_{q_l} [ C 1 + C 2 ⋅ S K + C 3 ⋅ S K 2 ] q l ≈ [ C 1 ∗ + C 2 ∗ ⋅ S K + r ] q l 成立。
为了访问S K 2 SK^2 S K 2 E K = ( − ( a ⋅ S K + e ) + S K 2 , a ) EK = (-(a\cdot SK + e)+SK^2,a) E K = ( − ( a ⋅ S K + e ) + S K 2 , a ) E K 1 + E K 2 ⋅ S K = S K 2 − e EK_1 +EK_2 \cdot SK = SK^2 -e E K 1 + E K 2 ⋅ S K = S K 2 − e C ∗ C^* C ∗
C 1 ∗ = [ C 1 + E K 1 ⋅ C 3 ] q l C 2 ∗ = [ C 2 + E K 2 ⋅ C 3 ] q l \begin{aligned} C_1^* = [C_1 + EK_1 \cdot C_3]_{q_l} \\ C_2^* = [C_2 + EK_2 \cdot C_3]_{q_l} \end{aligned} C 1 ∗ = [ C 1 + E K 1 ⋅ C 3 ] q l C 2 ∗ = [ C 2 + E K 2 ⋅ C 3 ] q l 我们可对C ∗ C^* C ∗
C 1 ∗ + C 2 ∗ ⋅ S K = C 1 + E K 1 ⋅ C 3 + S K ⋅ ( C 2 + E K 2 ⋅ C 3 ) = C 1 + C 2 ⋅ S K + C 3 ⋅ ( E K 1 + E K 2 ⋅ S K ) = C 1 + C 2 ⋅ S K + C 3 ⋅ S K 2 + C 3 ⋅ e \begin{aligned} C_1^* +C_2^*\cdot SK &=C_1 + EK_1 \cdot C_3 + SK\cdot (C_2 + EK_2 \cdot C_3) \\ &= C_1 + C_2\cdot SK + C_3\cdot (EK_1 + EK_2 \cdot SK) \\ &= C_1 + C_2\cdot SK + C_3 \cdot SK^2 + C_3 \cdot e \end{aligned} C 1 ∗ + C 2 ∗ ⋅ S K = C 1 + E K 1 ⋅ C 3 + S K ⋅ ( C 2 + E K 2 ⋅ C 3 ) = C 1 + C 2 ⋅ S K + C 3 ⋅ ( E K 1 + E K 2 ⋅ S K ) = C 1 + C 2 ⋅ S K + C 3 ⋅ S K 2 + C 3 ⋅ e 其中C 3 C_3 C 3
模数变换（ModSwitch）用于控制乘法计算中的噪音增长。它的主要思想是将密文 C C C q q q q ′ q' q ′ S K SK S K
[ C ( S K ) ] q = [ C ′ ( S K ) ] q ′ [C(SK)]_q = [C'(SK)]_{q'} [ C ( S K ) ] q = [ C ′ ( S K ) ] q ′ 细节上，这个变换是将密文 C C C q ′ q \frac{q'}{q} q q ′
C ′ = [ q ′ q ⋅ C ] C' = [\frac{q'}{q}\cdot C] C ′ = [ q q ′ ⋅ C ] 之前我们提到，BGV定义了一系列的模数 { p 0 , p 1 , … , p L } \{p_0,p_1,\dots,p_L\} { p 0 , p 1 , … , p L } l l l l − 1 l-1 l − 1 明文 ，因为对于q l q_l q l l ∈ { 0 , … , L } l \in \{0,\dots,L\} l ∈ { 0 , … , L }
q l ≡ q L m o d t q_l \equiv q_L \mod t q l ≡ q L mod t 可以简单理解为不影响密文中低 t t t
Modswitch在密文结构图上的表示如下：
Introduction to the BGV encryption scheme
Homomorphic encryption security standard
相关论文：
Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) fully homomorphic encryption without bootstrapping.” ACM Transactions on Computation Theory (TOCT) 6.3 (2014): 1-36. 
