BGV主要优化了BV11中的维度-模约减技术，提出了模交换技术，同时也优化了重线性化技术，提出了密钥交换技术，使得无需Bootstrapping也能做到较多层数的同态乘法。
前置
另一种形势的LWE公钥加密
这里在介绍方案的时候采用的另一种形式的LWE公钥加密，不是原文中的内容，但是有必要提一下，不然对于小白会懵逼很久（比如我）。
实例依然是
A
s
+
e
As+e
As+e
K e n G e n ( ) KenGen() KenGen()：公钥 p k = [ − A s A + 2 e ] pk = \begin{bmatrix}-A \\ sA+2e\end{bmatrix} pk=[−AsA+2e]，私钥 s k = [ s , 1 ] sk = [s,1] sk=[s,1]，使得 s k ⋅ p k = 2 e sk \cdot pk =2 e sk⋅pk=2e（矩阵乘法即可验证）E n c ( ) Enc() Enc()： E n c p k ( m ) = p k ⋅ r + [ ⋮ 0 m ] ( m o d q ) Enc_{pk}(m) = pk \cdot r + \begin{bmatrix} \vdots \\ 0 \\ m\end{bmatrix} (\mod q) Encpk(m)=pk⋅r+⎣⎢⎡⋮0m⎦⎥⎤(modq)，其中 r r r均匀取自 { 0 , 1 } L \{0,1\}^L {0,1}L，是个只含0和1的列矩阵，消息 m ∈ { 0 , 1 } m \in \{0,1\} m∈{0,1}D e c ( ) Dec() Dec()： D e c s k ( c t ) = < s k , c t > m o d 2 Dec_{sk}(ct)=<sk,ct> \mod 2 Decsk(ct)=<sk,ct>mod2 可以解密验证一下 < s k , c t > = s k ⋅ ( p k ⋅ r + [ ⋮ 0 m ] ) = s k ⋅ p k ⋅ r + s k [ ⋮ 0 m ] = < 2 e , r > + m ≈ m \begin{aligned} <sk,ct> &= sk \cdot (pk \cdot r + \begin{bmatrix} \vdots \\ 0 \\ m\end{bmatrix}) \\ &=sk \cdot pk \cdot r+sk\begin{bmatrix} \vdots \\ 0 \\ m\end{bmatrix} \\ &= <2e,r>+m \\ &\approx m \end{aligned} <sk,ct>=sk⋅(pk⋅r+⎣⎢⎡⋮0m⎦⎥⎤)=sk⋅pk⋅r+sk⎣⎢⎡⋮0m⎦⎥⎤=<2e,r>+m≈m （ < , > <,> <,>这个是内积。） 文章中把 [ < c , s > ] q [<\mathbf{c},\mathbf s>]_q [<c,s>]q称为密钥 s \mathbf s s下密文 c c c的噪声
同态加法和乘法构建
接下来根据上面的来试着构建一下密文加法和乘法。
设两个密文
c
1
,
c
2
\mathbf{c_1},\mathbf{c_2}
c1,c2，满足
<
c
1
,
s
>
=
2
e
1
+
m
1
,
<
c
2
,
s
>
=
2
e
2
+
m
2
<\mathbf{c_1},\mathbf{s}>=2e_1+m_1,<\mathbf{c_2},\mathbf{s}>=2e_2+m_2
<c1,s>=2e1+m1,<c2,s>=2e2+m2
有些地方省略了一下但是默认要模
q
q
q
- 加法 想构造出明文消息相加的形式，比较简单 c a d d = < c 1 + c 2 > m o d q \mathbf {c}{add} =<\mathbf{c_1}+\mathbf{c_2}> \mod q cadd=<c1+c2>modq 解密： D e c ( c a d d ) = < c a d d , s > = < c 1 + c 2 , s > = < c 1 , s > + < c 2 , s > = m 1 + m 2 + n o i s e \begin{aligned} Dec(\mathbf {c}{add}) &= <\mathbf {c}_{add},\mathbf s> \ &=<\mathbf{c_1}+\mathbf{c_2},\mathbf s> \ &=<\mathbf{c_1},\mathbf s>+<\mathbf{c_2},\mathbf s> \ &=m_1+m_2+noise \end{aligned} Dec(cadd)=<cadd,s>=<c1+c2,s>=<c1,s>+<c2,s>=m1+m2+noise 显然符合同态加法。
- 乘法 想构造出两个密文的乘积解密后是两个明文乘积的样子。 这里BGV方案中作者观察到 < c 1 , s > ⋅ < c 2 , s > = < c 1 ⊗ c 2 , s ⊗ s > <\mathbf{c_1},\mathbf s> \cdot <\mathbf{c_2},\mathbf s> =<\mathbf{c_1} \otimes\mathbf{c_2},\mathbf{s} \otimes \mathbf{s}> <c1,s>⋅<c2,s>=<c1⊗c2,s⊗s> （ ⊗ \otimes ⊗这个是张量积），上面的等式可以通过把左边的每一项拆开计算，比如把 c c c和 s s s都看二维的，计算左边表达式的结果，然后把所有的 c c c和 s s s分开成内积的形式，就能得到这个结果。 事实上这个来源于克罗内克积
解密： D e c ( c m u l t ) = < c 1 ⊗ c 2 , s ⊗ s > = < c 1 , s > ⋅ < c 2 , s > = ( 2 e 1 + m 1 ) ( 2 e 2 + m 2 ) = m 1 m 2 + n o i s e \begin{aligned} Dec(\mathbf c_{mult})&= <\mathbf{c_1} \otimes\mathbf{c_2},\mathbf{s} \otimes \mathbf{s}> \ &= <\mathbf{c_1},\mathbf s> \cdot <\mathbf{c_2},\mathbf s> \ &= (2e_1+m_1) (2e_2+m_2) \ &= m_1m_2+noise \end{aligned} Dec(cmult)=<c1⊗c2,s⊗s>=<c1,s>⋅<c2,s>=(2e1+m1)(2e2+m2)=m1m2+noise
因此，定义的同态操作如下：
A
d
d
i
t
i
o
n
:
Dec
(
c
1
+
c
2
,
s
)
=
Dec
(
c
1
,
s
)
+
Dec
(
c
2
,
s
)
M
u
l
t
p
l
i
c
a
t
i
o
n
:
Dec
(
c
1
⊗
c
2
,
s
⊗
s
)
=
Dec
(
c
1
,
s
)
⋅
Dec
(
c
2
,
s
)
\begin{array}{l} Addition:\operatorname{Dec}\left(c_{1}+c_{2}, s\right)=\operatorname{Dec}\left(c_{1}, s\right)+\operatorname{Dec}\left(c_{2}, s\right) \\\\ Multplication:\operatorname{Dec}\left(c_{1} \otimes c_{2}, s \otimes s\right)=\operatorname{Dec}\left(c_{1}, s\right) \cdot \operatorname{Dec}\left(c_{2}, s\right) \end{array}
Addition:Dec(c1+c2,s)=Dec(c1,s)+Dec(c2,s)Multplication:Dec(c1⊗c2,s⊗s)=Dec(c1,s)⋅Dec(c2,s)
同时我们可以看到，由于乘法定义为了张量积，那么密文和私钥就会膨胀得很厉害，所以需要降低它们。
GLWE（General Learning with Errors）
在BGV方案中把LWE和RLWE统一成了GLWE。
LWE中实例为
(
a
,
b
)
←
Z
q
n
×
Z
q
(a,b) \leftarrow \mathbb{Z}_q^n \times \mathbb{Z}_q
(a,b)←Zqn×Zq
RLWE中的实例为
(
a
i
,
b
i
)
←
R
q
×
R
q
(a_i,b_i) \leftarrow {R}_q\times {R}_q
(ai,bi)←Rq×Rq
如果把
Z
\mathbb{Z}
Z也看做环，那么即可将二者统一起来。
GLWE的定义如下，
则，可以通过两个参数(d,n)来确定选择的是LWE还是RLWE，LWE 只是用 d = 1 实例化的 GLWE。RLWE 是用 n = 1 实例化的 GLWE。
总之这不是一个新的结构，实际使用的还是RLWE和LWE。
基本方案
E . S e t u p ( 1 λ , 1 μ , b ) \mathsf{E.Setup}(1^\lambda,1^\mu,b) E.Setup(1λ,1μ,b): 由比特 b b b来确定我们是构造LWE假设下的方案( b = 0 b=0 b=0)还是RLWE假设下的方案( b = 1 b=1 b=1). 选择一个 μ \mu μ比特的模数 q q q和参数 d = d ( λ , μ , b ) , n = n ( λ , μ , b ) , N = ⌈ ( 2 n + 1 ) log q ⌉ , χ = χ ( λ , μ , b ) d=d(\lambda,\mu,b),n=n(\lambda,\mu,b),N=\lceil (2n+1)\log q\rceil, \chi=\chi(\lambda, \mu, b) d=d(λ,μ,b),n=n(λ,μ,b),N=⌈(2n+1)logq⌉,χ=χ(λ,μ,b) 此处要求最终的参数使得GLWE问题实例具有 2 λ 2^{\lambda} 2λ强度. 令 R = Z [ x ] / ( x d + 1 ) R=\mathbb Z[x]/(x^d+1) R=Z[x]/(xd+1), 并令参数集合 p a r a m s = ( q , d , n , N , χ ) params=(q,d,n,N,\chi) params=(q,d,n,N,χ).E . S e c r e t K e y G e n ( p a r a m s ) \mathsf{E.SecretKeyGen}(params) E.SecretKeyGen(params): 选择 s ′ ← χ n \mathbf s'\leftarrow\chi^n s′←χn, 输出 s k = s = ( 1 , s ′ [ 1 ] , ⋯ , s ′ [ n ] ) ∈ R q n + 1 sk=\mathbf s=(1,\mathbf s'[1],\cdots,\mathbf s'[n])\in R_q^{n+1} sk=s=(1,s′[1],⋯,s′[n])∈Rqn+1.E . P u b l i c K e y G e n ( p a r a m s , s k ) \mathsf{E.PublicKeyGen}(params,sk) E.PublicKeyGen(params,sk): 均匀选择 A ′ ← R q N × n \mathbf A'\leftarrow R_q^{N\times n} A′←RqN×n, 选择 e ← χ N \mathbf e\leftarrow \chi^N e←χN并令 b = A ′ s ′ + 2 e \mathbf b=\mathbf A'\mathbf s'+2\mathbf e b=A′s′+2e. 并令 p k = A = [ b ∣ − A ′ ] pk=\mathbf A=[\mathbf b|-\mathbf A'] pk=A=[b∣−A′]或者 [ b , − A ′ ] [\mathbf b,-\mathbf A'] [b,−A′](一个拼装矩阵)。这里 A ⋅ s = 2 e \mathbf A \cdot \mathbf s = 2e A⋅s=2eE . E n c ( p a r a m s , p k , m ∈ { 0 , 1 } ) \mathsf{E.Enc}(params,pk,m\in\{0,1\}) E.Enc(params,pk,m∈{0,1}): 令 m = ( m , 0 , ⋯ , 0 ) ∈ R q n + 1 \mathbf m=(m,0,\cdots,0)\in R_q^{n+1} m=(m,0,⋯,0)∈Rqn+1, 选择 r ← R q N \mathbf r\leftarrow R_q^N r←RqN, 输出密文 c = m + A T r ∈ R q n + 1 \mathbf c=\mathbf m+\mathbf A^T\mathbf r\in R_q^{n+1} c=m+ATr∈Rqn+1.E . D e c ( p a r a m s , s k , c ) \mathsf{E.Dec}(params,sk,\mathbf c) E.Dec(params,sk,c): 输出 m ← [ [ ⟨ c , s ⟩ ] q ] 2 m\leftarrow [[\langle\mathbf c,\mathbf s\rangle]_q]_2 m←[[⟨c,s⟩]q]2.
这套基本方案其实就是BV11中描述的，只不过是换了一种形式。
密钥交换（Key Switching）
目的就是为了减小膨胀的密文和密钥。将因为张量积而扩张的大密文和大密钥替换成小密文和小密钥，且保持解密消息基本不变。
理论
先熟悉两个函数
B
i
t
D
e
c
o
m
p
(
)
BitDecomp()
BitDecomp()和
P
o
w
e
r
o
f
2
(
)
Powerof2()
Powerof2()，在这篇文章的扁平化小节有介绍不熟悉的可以看看。
简单来说，第一个函数的功能是把参数拆成二进制比特，第二个函数的功能是把参数扩张成2的幂次乘以参数的形式，使得内积乘积不变化。
⟨
BitDecomp
(
c
,
q
)
,
Powersof2
(
s
,
q
)
⟩
=
∑
j
=
0
⌊
log
q
⌋
⟨
u
j
,
2
j
⋅
s
⟩
=
∑
j
=
0
⌊
log
q
⌋
⟨
2
j
⋅
u
j
,
s
⟩
=
⟨
∑
j
=
0
⌊
log
q
⌋
2
j
⋅
u
j
,
s
⟩
=
⟨
c
,
s
⟩
\langle\operatorname{BitDecomp}(\mathbf{c}, q), \text { Powersof2}(\mathbf{s}, q)\rangle=\sum_{j=0}^{\lfloor\log q\rfloor}\left\langle\mathbf{u}_{j}, 2^{j} \cdot \mathbf{s}\right\rangle=\sum_{j=0}^{\lfloor\log q\rfloor}\left\langle 2^{j} \cdot \mathbf{u}_{j}, \mathbf{s}\right\rangle=\left\langle\sum_{j=0}^{\lfloor\log q\rfloor} 2^{j} \cdot \mathbf{u}_{j}, \mathbf{s}\right\rangle=\langle\mathbf{c}, \mathbf{s}\rangle
⟨BitDecomp(c,q), Powersof2(s,q)⟩=j=0∑⌊logq⌋⟨uj,2j⋅s⟩=j=0∑⌊logq⌋⟨2j⋅uj,s⟩=⟨j=0∑⌊logq⌋2j⋅uj,s⟩=⟨c,s⟩
密钥交换主要来自[BV11]中的重线性化操作，但作者发现重线性化不仅仅可以通过更换密钥来降低密钥的维数，还可以将第一个密钥下的密文转换成第二个密钥下的密文，而二者加密的消息是相同的，这样可以直接在第二个密钥下进行解密。
密钥交换主要有两个步骤:
第一个算法
S
w
i
t
c
h
K
e
y
G
e
n
(
s
1
,
q
,
n
1
,
s
2
，
n
2
)
SwitchKeyGen(\mathbf s_1,q,n_1,\mathbf s_2，n_2)
SwitchKeyGen(s1,q,n1,s2，n2)接收两个密钥向量，向量各自的维数，和共同模数作为输入，输出一些辅助信息
τ
s
1
→
s
2
\tau_{\mathbf{s}_{1} \rightarrow \mathbf{s}_{2}}
τs1→s2。第二个算法
S
w
i
t
c
h
K
e
y
(
τ
s
1
→
s
2
,
c
1
,
n
1
,
n
2
,
q
)
SwitchKey(\tau_{\mathbf{s}_{1} \rightarrow \mathbf{s}_{2}},\mathbf c_1,n_1,n_2,q)
SwitchKey(τs1→s2,c1,n1,n2,q)接收辅助信息和前密钥加密的密文，来输出在后一个密钥下加密的密文。
理解说明：我们要将密钥
s
1
\mathbf{s}_{1}
s1下的密文
c
1
\mathbf{c}_{1}
c1切换到密钥
s
2
\mathbf{s}_{2}
s2下的密文
c
2
\mathbf{c}_{2}
c2，就需要先使用
s
2
\mathbf{s}_{2}
s2作为私钥，生成一个公钥，将
P
o
w
e
r
s
o
f
2
(
s
1
)
Powersof2( \left.\mathbf{s}_{1}\right)
Powersof2(s1)的每一项
2
τ
⋅
s
1
[
i
]
2^\tau \cdot \mathbf{s}_{1}[i]
2τ⋅s1[i]进行加密，把这些密文的集合记作
τ
s
1
→
s
2
\tau_{\mathbf{s}_{1} \rightarrow \mathbf{s}_{2}}
τs1→s2，可以看到，之前在BV11方案中密钥是有二次项的，但是这里直接一个
s
1
\mathbf{s}_{1}
s1就把所有的一次二次项全部囊括了，只需要简单的理解到
s
1
=
s
⊗
s
\mathbf{s}_{1}=\mathbf{s} \otimes \mathbf{s}
s1=s⊗s即可。
算法
具体操作如下，
S w i t c h K e y G e n ( s 1 ∈ R q n 1 , s 2 ∈ R q n 2 ) SwitchKeyGen(\mathbf s_1 \in R_q^{n_1},\mathbf s_2 \in R_q^{n_2}) SwitchKeyGen(s1∈Rqn1,s2∈Rqn2): 首先 A ← E . P u b l i c k e y G e n ( s 2 , N ) \mathbf{A} \leftarrow E.PublickeyGen \left(\mathbf{s}_{2}, N\right) A←E.PublickeyGen(s2,N)， N = n 1 ⋅ ⌈ log q ⌉ N=n_{1} \cdot\lceil\log q\rceil N=n1⋅⌈logq⌉，这里有 s 2 ⋅ A = 2 e \mathbf{s}_{2} \cdot \mathbf A = 2e s2⋅A=2e。 接着 B ← A + P o w e r s o f 2 ( s 1 ) \mathbf{B} \leftarrow \mathbf{A}+ Powersof2( \mathbf{s}_{1}) B←A+Powersof2(s1)：也就是把 P o w e r s o f 2 ( s 1 ) Powersof2( \left.\mathbf{s}_{1}\right) Powersof2(s1)加到 A \mathbf{A} A的第一列，得到矩阵 B \mathbf{B} B，输出 τ s 1 → s 2 = B \tau_{\mathbf{s}_{1} \rightarrow \mathbf{s}_{2}}=\mathbf{B} τs1→s2=B，可以把 B \mathbf{B} B看成 B = [ P o w e r s o f 2 ( s 1 ) ∣ A ] \mathbf{B} = [Powersof2(\mathbf{s}_{1})| \mathbf A] B=[Powersof2(s1)∣A]或者 B = [ P o w e r s o f 2 ( s 1 ) , A ] \mathbf{B} = [Powersof2(\mathbf{s}_{1}),\mathbf A] B=[Powersof2(s1),A]S w i t c h K e y ( τ s 1 → s 2 , c 1 ) SwitchKey(\tau_{\mathbf{s}_{1} \rightarrow \mathbf{s}_{2}},\mathbf c_1) SwitchKey(τs1→s2,c1): 输出 c 2 = B i t D e c o m p ( c 1 ) T ⋅ B ∈ R q n 2 \mathbf c_2=\mathsf{BitDecomp}(\mathbf c_1)^T\cdot \mathbf B\in R_q^{n_2} c2=BitDecomp(c1)T⋅B∈Rqn2
正确性验证，
⟨
c
2
,
s
2
⟩
=
BitDecomp
(
c
1
)
T
⋅
B
⋅
s
2
=
BitDecomp
(
c
1
)
T
⋅
[
Powersof2
(
s
1
)
,
A
]
⋅
[
1
,
s
2
′
]
T
=
BitDecomp
(
c
1
)
T
⋅
(
2
e
2
+
Powersof
2
(
s
1
)
)
=
2
⟨
BitDecomp
(
c
1
)
,
e
2
⟩
+
⟨
BitDecomp
(
c
1
)
,
Powersof
2
(
s
1
)
⟩
=
2
⟨
BitDecomp
(
c
1
)
,
e
2
⟩
+
⟨
c
1
,
s
1
⟩
\begin{aligned} \left\langle\mathbf{c}_{2}, \mathbf{s}_{2}\right\rangle &=\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right)^{T} \cdot \mathbf{B} \cdot \mathbf{s}_{2} \\ &=\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right)^{T} \cdot [\operatorname{Powersof2}(\mathbf{s}_{1}),\mathbf A] \cdot [1,\mathbf {s_2'}]^T\\ &=\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right)^{T} \cdot\left(2 \mathbf{e}_{2}+\operatorname{Powersof} 2\left(\mathbf{s}_{1}\right)\right) \\ &=2\left\langle\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right), \mathbf{e}_{2}\right\rangle+\left\langle\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right), \operatorname{Powersof} 2\left(\mathbf{s}_{1}\right)\right\rangle \\ &=2\left\langle\operatorname{BitDecomp}\left(\mathbf{c}_{1}\right), \mathbf{e}_{2}\right\rangle+\left\langle\mathbf{c}_{1}, \mathbf{s}_{1}\right\rangle \end{aligned}
⟨c2,s2⟩=BitDecomp(c1)T⋅B⋅s2=BitDecomp(c1)T⋅[Powersof2(s1),A]⋅[1,s2′]T=BitDecomp(c1)T⋅(2e2+Powersof2(s1))=2⟨BitDecomp(c1),e2⟩+⟨BitDecomp(c1),Powersof2(s1)⟩=2⟨BitDecomp(c1),e2⟩+⟨c1,s1⟩
由于二进制化了，所以噪声就很小。
模交换（Modulus Switching）
目的是减小噪声，在[BV11]中的模数切换操作仅仅在同态计算结束后使用，并获得一个小的密文。在BGV中是迭代的使用来保持噪声水平基本不变，但是作为牺牲，模数会逐步减小至无法继续计算，也就是说深度基本上由模数来控制了。
如果噪声界限是
B
B
B的话，那么同态乘法会产生
B
2
B^2
B2的噪声，后续就是双指数级别的增长。模交换的核心就是做一次乘法计算就将噪声
B
2
B^2
B2削减为
B
B
B，使得噪声基本维持不变，模数就会从
q
L
q^L
qL一直减小到
q
q
q。
这就无需bootstrapping也能控制噪声的增长，从而达到一个有限级同态加密。
理论
目标是
[
⟨
c
,
s
⟩
]
q
m
o
d
2
=
[
⟨
c
′
,
s
⟩
]
p
m
o
d
2
[\langle\mathbf c,\mathbf s\rangle]_q \mod 2=[\langle \mathbf c',\mathbf s\rangle]_p \mod 2
[⟨c,s⟩]qmod2=[⟨c′,s⟩]pmod2
类似[BV11]中的一样，从
c
c
c到
c
′
c'
c′的切换只需要缩放一个
(
p
/
q
)
(p/q)
(p/q)并适当的舍入。但是，有个惊人的发现就是如果
s
s
s很短且
p
p
p比
q
q
q小很多，那么噪声也会缩小的。
设
p
p
p和
q
q
q是两个奇数模数,
c
\mathbf c
c是一个整数向量. 令
c
’
\mathbf c’
c’为一个距离
(
p
/
q
)
⋅
c
(p/q)\cdot\mathbf c
(p/q)⋅c最近的一个整数向量满足
c
′
=
c
m
o
d
2
\mathbf c'=\mathbf c\mod 2
c′=cmod2，同时
p
=
q
m
o
d
2
p = q\mod 2
p=qmod2
我们知道
[
⟨
c
,
s
⟩
]
q
=
⟨
c
,
s
⟩
−
k
q
[\langle\mathbf c,\mathbf s\rangle]_q=\langle\mathbf c,\mathbf s\rangle-kq
[⟨c,s⟩]q=⟨c,s⟩−kq和
[
⟨
c
′
,
s
⟩
]
p
=
⟨
c
′
,
s
⟩
−
k
p
[\langle \mathbf c',\mathbf s\rangle]_p =\langle \mathbf c',\mathbf s\rangle-kp
[⟨c′,s⟩]p=⟨c′,s⟩−kp（模计算可以表示成减去模数的倍数）
由此得到第一个结论
[
[
⟨
c
′
,
s
⟩
]
p
]
2
=
[
⟨
c
′
,
s
⟩
−
k
p
]
2
=
[
⟨
c
,
s
⟩
−
k
q
]
2
=
[
⟨
c
,
s
⟩
]
q
m
o
d
2
[[\langle \mathbf c',\mathbf s\rangle]_p]_2=[\langle \mathbf c',\mathbf s\rangle-kp]_2=[\langle\mathbf c,\mathbf s\rangle-kq]_2=[\langle\mathbf c,\mathbf s\rangle]_q \mod 2
[[⟨c′,s⟩]p]2=[⟨c′,s⟩−kp]2=[⟨c,s⟩−kq]2=[⟨c,s⟩]qmod2
保证了解密时的正确性。
接着因为
s
s
s很小，且
[
⟨
c
′
,
s
⟩
]
p
=
⟨
c
′
,
s
⟩
−
k
p
=
⟨
c
′
,
s
⟩
−
k
q
⋅
p
q
=
⟨
c
′
,
s
⟩
+
p
q
⋅
(
[
⟨
c
,
s
⟩
]
q
−
⟨
c
,
s
⟩
)
=
⟨
c
′
,
s
⟩
−
p
q
⟨
c
,
s
⟩
+
p
q
[
⟨
c
,
s
⟩
]
q
=
p
q
⋅
[
⟨
c
,
s
⟩
]
q
+
⟨
c
′
−
(
p
q
)
c
,
s
⟩
=
p
q
⋅
[
⟨
c
,
s
⟩
]
q
+
s
m
a
l
l
\begin{aligned} [\langle \mathbf c',\mathbf s\rangle]_p =\langle \mathbf c',\mathbf s\rangle-kp &=\langle \mathbf c',\mathbf s\rangle-kq\cdot \frac pq \\ &= \langle \mathbf c',\mathbf s\rangle+\frac pq\cdot ([\langle\mathbf c,\mathbf s\rangle]_q-\langle\mathbf c,\mathbf s\rangle)\\ &=\langle \mathbf c',\mathbf s\rangle - \frac pq \langle\mathbf c,\mathbf s\rangle + \frac pq [\langle\mathbf c,\mathbf s\rangle]_q\\ &=\frac pq\cdot [\langle\mathbf c,\mathbf s\rangle]_q+\langle\mathbf c'-(\frac pq)\mathbf c,\mathbf s\rangle \\ &=\frac pq\cdot [\langle\mathbf c,\mathbf s\rangle]_q+small \end{aligned}
[⟨c′,s⟩]p=⟨c′,s⟩−kp=⟨c′,s⟩−kq⋅qp=⟨c′,s⟩+qp⋅([⟨c,s⟩]q−⟨c,s⟩)=⟨c′,s⟩−qp⟨c,s⟩+qp[⟨c,s⟩]q=qp⋅[⟨c,s⟩]q+⟨c′−(qp)c,s⟩=qp⋅[⟨c,s⟩]q+small
倒数第二行等式的
c
′
−
(
p
q
)
c
\mathbf c'-(\frac pq)\mathbf c
c′−(qp)c是一个的系数在
(
−
1
,
1
)
(-1,1)
(−1,1)内的矩阵，所以内积肯定比
ℓ
1
(
s
)
\ell_1(s)
ℓ1(s)要小（
ℓ
1
\ell_1
ℓ1表示一阶范数，即向量每个元素的绝对值之和，它其实可以看作单位矩阵和
s
s
s做内积，对每个维度加上个绝对值）
由此得到第二个结论
∣
[
⟨
c
’
,
s
⟩
]
p
∣
=
p
q
⋅
[
⟨
c
,
s
⟩
]
q
+
⟨
c
′
−
(
p
q
)
c
,
s
⟩
<
(
p
q
)
⋅
∣
[
⟨
c
,
s
⟩
]
q
∣
+
ℓ
1
(
s
)
<
q
/
2
\begin{aligned} |[\langle \mathbf c’,\mathbf s\rangle]_p|&=\frac pq\cdot [\langle\mathbf c,\mathbf s\rangle]_q+\langle\mathbf c'-(\frac pq)\mathbf c,\mathbf s\rangle\\ &<(\frac pq)\cdot |[\langle\mathbf c,\mathbf s\rangle]_q|+\ell_1(\mathbf s)\\ &<q/2 \end{aligned}
∣[⟨c’,s⟩]p∣=qp⋅[⟨c,s⟩]q+⟨c′−(qp)c,s⟩<(qp)⋅∣[⟨c,s⟩]q∣+ℓ1(s)<q/2
即，噪声也近乎按照比例下降。可做的乘法次数就从对数级别上升到了线性级别（
log
k
→
k
\log k \rightarrow k
logk→k），由此无需自举也能构建有限级加密方案。
算法
c
′
←
S
c
a
l
e
(
c
,
q
,
p
,
r
)
\mathbf c'\leftarrow\mathsf{Scale}(\mathbf c,q,p,r)
c′←Scale(c,q,p,r):获取一个最靠近的整数向量，和前面理论说过的一样。使得后面满足
m
=
[
[
<
c
,
s
>
]
q
]
r
=
[
[
<
c
′
,
s
>
]
p
]
r
m = [[<\mathbf c,\mathbf s>]_q]_r =[[<\mathbf c',\mathbf s>]_p]_r
m=[[<c,s>]q]r=[[<c′,s>]p]r
同态方案
方案算法：
F H E . S e t u p ( 1 λ , 1 L , b ) \mathsf{FHE.Setup}(1^\lambda,1^L,b) FHE.Setup(1λ,1L,b):1. 输入安全参数、级别数和用来确定用LWE还是RLWE的参数，设 μ = μ ( λ , L , b ) = θ ( log λ + log L ) \mu=\mu(\lambda,L,b)=\theta(\log\lambda+\log L) μ=μ(λ,L,b)=θ(logλ+logL).2. 对于每个 j = L j=L j=L(电路输入层) to 0 \text{ to } 0 to 0(电路输出层):执行 p a r a m s j ← E . S e t u p ( 1 λ , 1 ( j + 1 ) ⋅ μ , b ) params_j\leftarrow\mathsf{E.Setup}(1^\lambda,1^{(j+1)\cdot \mu},b) paramsj←E.Setup(1λ,1(j+1)⋅μ,b), 生成一个阶梯式的模数（从 q L ( ( L + 1 ) ⋅ μ b i t s ) q_L((L+1)\cdot \mu bits) qL((L+1)⋅μbits)降低到 q 0 ( μ b i t s ) q_0(\mu bits) q0(μbits)3. 对于每个 j = L − 1 to 0 j=L-1\text{ to } 0 j=L−1 to 0 令 d j = d L d_j=d_L dj=dL, χ j = χ L \chi_j=\chi_L χj=χL。此外, 每一层的 d , χ d,\chi d,χ参数需要与 L L L层统一, 而维数 n n n则没有这个要求.（这是由于在 q q q变小时, 维数的减少不会影响方案的安全性, 毕竟当 q q q下降时, 维数的减小不会让破解变得容易)F H E . K e y G e n ( { p a r a m s j } ) \mathsf{FHE.KeyGen}(\{params_j\}) FHE.KeyGen({paramsj}):1. 对于每个 j = L to 0 j=L\text{ to }0 j=L to 0, 执行: 执行 s j ← E . S e c r e t K e y G e n ( p a r a m s s j ) \mathbf s_j\leftarrow \mathsf{E.SecretKeyGen}(paramss_j) sj←E.SecretKeyGen(paramssj)和 A j ← E . P u b l i c K e y G e n ( p a r a m s j , s j ) \mathbf A_j\leftarrow\mathsf{E.PublicKeyGen}(params_j,\mathbf s_j) Aj←E.PublicKeyGen(paramsj,sj)2. 令 s j ′ ← s j ⊗ s j \mathbf s_j'\leftarrow \mathbf s_j\otimes\mathbf s_j sj′←sj⊗sj。3. 令 s j ′ ′ ← B i t D e c o m p ( s j ′ , q j ) \mathbf s_j''\leftarrow \mathsf{BitDecomp}(\mathbf s_j',q_j) sj′′←BitDecomp(sj′,qj).（以 log q \log q logq位二进制展开）4. 令 τ s j ′ ′ → s j − 1 ← S w i t c h K e y G e n ( s j ′ ′ , s j − 1 ) \tau_{\mathbf s_{j}''\to\mathbf s_{j-1}}\leftarrow \mathsf{SwitchKeyGen}(\mathbf s_j'',\mathbf s_{j-1}) τsj′′→sj−1←SwitchKeyGen(sj′′,sj−1) (当 j = L j=L j=L时不执行该步骤)。 实际上上述算法中, 我们就生成了每一层的公私钥, 并且做好了每一层的 τ s j ′ ′ → s j − 1 \tau_{\mathbf s_{j}''\to\mathbf s_{j-1}} τsj′′→sj−1。F H E . E n c ( p a r a m s , p k , m ∈ { 0 , 1 } ) \mathsf{FHE.Enc}(params,pk,m\in\{0,1\}) FHE.Enc(params,pk,m∈{0,1}): 计算并输出 E . E n c ( A L , m ) \mathsf{E.Enc}(\mathbf A_L,m) E.Enc(AL,m).F H E . D e c ( p a r a m s , s k , c ) \mathsf{FHE.Dec}(params,sk,\mathbf c) FHE.Dec(params,sk,c): 根据密钥的层数选择 s j \mathbf s_j sj, 计算并输出 E . D e c ( s j , c ) \mathsf{E.Dec}(\mathbf s_j,\mathbf c) E.Dec(sj,c). 此处我们忽略了确定密文层数的参数来化简表示，原文写的可以使用一个指示参数来指定。
同态计算中要用到模数交换过程和密钥交换过程, 作者将其统一为一个
R
e
f
r
e
s
h
\mathsf{Refresh}
Refresh过程：首先要根据计算密钥的格式, 将乘法(或加法)得到的结果进行
P
o
w
e
r
o
f
2
\mathsf{Powerof2}
Powerof2操作, 然后依次进行模数切换和密钥切换，即，把一个
s
j
’
=
s
j
⊗
s
j
\mathbf s_j’=\mathbf{s}_j\otimes\mathbf s_j
sj’=sj⊗sj下得密文变为
s
j
−
1
\mathbf s_{j-1}
sj−1下得密文.。
F H E . R e f r e s h ( c , τ s j ′ ′ → s j − 1 , q j , q j − 1 ) \mathsf{FHE.Refresh}(\mathbf c,\tau_{\mathbf s_j''\to\mathbf s_{j-1},q_j,q_{j-1}}) FHE.Refresh(c,τsj′′→sj−1,qj,qj−1): 输入的是一个由 s j ′ \mathbf s_{j}' sj′加密的密文、密钥交换辅助信息，当前层和下一层的模数。 1. 扩张密文，使得密文与密钥的内积不变。计算 c 1 ← P o w e r o f 2 ( c , q j ) \mathbf c_1\leftarrow\mathsf{Powerof2}(\mathbf c,q_j) c1←Powerof2(c,qj)（这里能想到 < c 1 , s j ′ ′ > = < c , s j ′ > <\mathbf c_1,\mathbf s_j''> = <\mathbf c , \mathbf s_j'> <c1,sj′′>=<c,sj′> 从前面的二进制转换那里能总结出来）2. 模交换，计算 c 2 ← S c a l e ( c 1 , q j , q j − 1 , 2 ) \mathbf c_2\leftarrow\mathsf{Scale}(\mathbf c_1,q_j,q_{j-1},2) c2←Scale(c1,qj,qj−1,2)3. 密钥交换，计算并输出 c 3 ← S w i t c h K e y ( τ s j ’ ’ → s j − 1 , c 2 , q j − 1 ) \mathbf c_3\leftarrow \mathsf{SwitchKey}(\tau_{\mathbf s_j’’\to\mathbf s_{j-1}},\mathbf c_2,q_{j-1}) c3←SwitchKey(τsj’’→sj−1,c2,qj−1)
最后我们补充完同态借助
R
e
f
r
e
s
h
\mathsf{Refresh}
Refresh完成的同态运算过程（输入的两个密文都是同一个密钥加密出来的）:
F H E . A d d ( p k , c 1 , c 2 ) \mathsf{FHE.Add}(pk,\mathbf c_1,\mathbf c_2) FHE.Add(pk,c1,c2): 首先计算 c 3 = c 1 + c 2 \mathbf c_3=\mathbf c_1+\mathbf c_2 c3=c1+c2, 再计算输出 c 4 = F H E . R e f r e s h ( c 3 , q j , q j − 1 ) \mathbf c_4=\mathsf{FHE.Refresh}(\mathbf c_3,q_j,q_{j-1}) c4=FHE.Refresh(c3,qj,qj−1)。（有需要就调用刷新）F H E . M u l t ( p k , c 1 , c 2 ) \mathsf{FHE.Mult}(pk,\mathbf c_1,\mathbf c_2) FHE.Mult(pk,c1,c2): 首先计算 c 3 \mathbf c_3 c3, 即由 c 1 , c 2 \mathbf c_1,\mathbf c_2 c1,c2所表示的多项式函数相乘得到的多项式函数对应的密文, 再计算并输出 c 4 = F H E . R e f r e s h ( c 3 , q j , q j − 1 ) \mathbf c_4=\mathsf{FHE.Refresh}(\mathbf c_3,q_j,q_{j-1}) c4=FHE.Refresh(c3,qj,qj−1)。
最后来看看整个方案的噪声增长：
在密钥交换和模交换后都会诞生一部分小的噪声，如果在模交换的时候设置模数为
q
q
q，那么乘法后的噪声就是
B
2
/
(
B
+
s
m
a
l
l
)
→
B
⋅
p
o
l
y
(
n
)
B^2/(B+small)\rightarrow B\cdot poly(n)
B2/(B+small)→B⋅poly(n)
参考
同态加密(3) BGV方案
全同态加密：BGV
同态加密（七）无自举的分级全同态加密 1 (Leveled)Fully Homomorphic Encryption without Bootstrapping
Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.
全同态加密I：理论与基础
本文转载自: https://blog.csdn.net/qq_43271194/article/details/127647277
版权归原作者 Amire0x 所有， 如有侵权，请联系我们删除。
版权归原作者 Amire0x 所有， 如有侵权，请联系我们删除。