参考文献：
- [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.
- [KDE+23] Kim A, Deryabin M, Eom J, et al. General bootstrapping approach for RLWE-based homomorphic encryption[J]. IEEE Transactions on Computers, 2023.
文章目录
- Scaled Modulus Raising
- Bootstrapping for CKKS
- Multiprecision CKKS
- RNS-CKKS
- Bootstrapping for BGV
- Multiprecision BGV
- RNS-BGV
- Bootstrapping for BFV
- Multiprecision BFV
- RNS-BFV
- Compact Representation of Blind Rotation Keys
- Reconstruction
- On the Fly
[KDE+23] 提出可以使用 FHEW-like 实现 BV-like 的通用自举程序。文章说给出了 C++ 实现，不过没有给代码链接；文章中说性能依旧需要继续改进，没有给出具体的数据。
首先，我们定义一些密文类型：
- L W E q , s ( m ) = ( a , m + e − ⟨ a , s ⟩ ) ∈ Z q n + 1 LWE_{q,s}(m) = (a,m+e-\langle a,s\rangle) \in \mathbb Z_q^{n+1} LWEq,s(m)=(a,m+e−⟨a,s⟩)∈Zqn+1
- R L W E Q , s ( m ) = ( a , m + e − a ⋅ s ) ∈ R Q 2 RLWE_{Q,s}(m)=(a,m+e-a\cdot s) \in R_Q^2 RLWEQ,s(m)=(a,m+e−a⋅s)∈RQ2
- R L W E Q , s ′ ( m ) = ( R L W E Q , s ( g 0 ⋅ m ) , ⋯ , R L W E Q , s ( g d − 1 ⋅ m ) ) ∈ R Q 2 d RLWE'_{Q,s}(m) = (RLWE_{Q,s}(g_0\cdot m),\cdots,RLWE_{Q,s}(g_{d-1}\cdot m)) \in R_Q^{2d} RLWEQ,s′(m)=(RLWEQ,s(g0⋅m),⋯,RLWEQ,s(gd−1⋅m))∈RQ2d
- R G S W Q , s ( m ) = ( R L W E Q , s ′ ( s ⋅ m ) , R L W E Q , s ′ ( m ) ) RGSW_{Q,s}(m)=(RLWE'_{Q,s}(s\cdot m),RLWE'_{Q,s}(m)) RGSWQ,s(m)=(RLWEQ,s′(s⋅m),RLWEQ,s′(m))
简记无噪声的密文为 R L W E 0 ( u ) RLWE^0(u) RLWE0(u)，这里 u u u 是其（无编码的）相位。
Scaled Modulus Raising
[KDE+23] 首先介绍了一个核心算法，它用于将较小密文模数 q q q 下的消息，提升到更大的密文模数 Q Q Q。这需要消除模 Q Q Q 下出现的 q q q-overflower，因此明显需要自举程序。
我们设置 q = 2 N q=2N q=2N，给定相位是 ∥ u ∥ ∞ ≤ c < N / 2 \|u\|_\infty \le c<N/2 ∥u∥∞≤c<N/2 的密文，记为 R L W E 2 N , s 0 ( u ) RLWE_{2N,s}^0(u) RLWE2N,s0(u)，
- Extraction：采取 FHEW 的系数提取过程，获得 L W E 2 N , s ( u i ) , i ∈ [ N ] LWE_{2N,s}(u_i), i\in[N] LWE2N,s(ui),i∈[N]
- Blind Rotation：使用 FHEW/TFHE 盲旋转过程，初始设置 ACC 加密 f = − ∑ j = − c c Δ j ⋅ X j f=-\sum_{j=-c}^c \Delta j\cdot X^j f=−∑j=−ccΔj⋅Xj，最终获得 R L W E Q , s ( f ⋅ X u i ) , i ∈ [ N ] RLWE_{Q,s}(f\cdot X^{u_i}), i\in[N] RLWEQ,s(f⋅Xui),i∈[N]，相位的常数项是 Δ u i \Delta u_i Δui，并且 X 2 c + 1 , ⋯ , X N − 2 c − 2 X^{2c+1},\cdots,X^{N-2c-2} X2c+1,⋯,XN−2c−2 的系数都是零，将它简记为 u ( i ) ∈ R Q u^{(i)} \in R_Q u(i)∈RQ
- Repacking：将这 N N N 个密文组合成单个密文 R L W E Q , s ( Δ u ) RLWE_{Q,s}(\Delta u) RLWEQ,s(Δu)
由于
c
<
N
/
2
c<N/2
c<N/2，我们选取大于
2
c
2c
2c 的最小二的幂次
n
=
n
c
n=n_c
n=nc，那么就可以将
N
N
N 个 RLWE 密文分为若干组
{
R
L
W
E
(
u
i
+
n
k
}
k
∈
[
N
/
n
]
,
i
∈
[
n
]
\{RLWE(u^{i+nk}\}_{k\in[N/n]}, i\in[n]
{RLWE(ui+nk}k∈[N/n],i∈[n]，我们计算：
∑
k
=
0
N
/
n
−
1
R
L
W
E
(
u
(
i
+
n
k
)
)
⋅
X
n
k
=
R
L
W
E
(
u
(
i
,
n
)
:
=
∑
k
=
0
N
/
n
−
1
u
(
i
+
n
k
)
X
n
k
)
\sum_{k=0}^{N/n-1} RLWE(u^{(i+nk)}) \cdot X^{nk} = RLWE\left(u^{(i,n)}:=\sum_{k=0}^{N/n-1} u^{(i+nk)} X^{nk}\right)
k=0∑N/n−1RLWE(u(i+nk))⋅Xnk=RLWE
u(i,n):=k=0∑N/n−1u(i+nk)Xnk
因为间隔
n
>
2
c
n>2c
n>2c 足够大，因此获得的相位
u
(
i
,
n
)
u^{(i,n)}
u(i,n) 的位置
n
k
,
k
∈
[
N
/
n
]
nk,k\in[N/n]
nk,k∈[N/n] 恰好就是
Δ
u
i
+
n
k
\Delta u_{i+nk}
Δui+nk 本身。
接着利用 [CDKS21] 的打包技术，自同构
τ
1
+
2
N
/
n
\tau_{1+2N/n}
τ1+2N/n 应用到
u
(
i
,
n
)
u^{(i,n)}
u(i,n)，它保持位置
X
n
k
X^{nk}
Xnk 的系数，翻转位置
X
n
k
+
n
/
2
X^{nk+n/2}
Xnk+n/2 的系数符号；剩余位置的系数被打乱或者变号（我们不关心）。因此，对于
i
∈
[
n
/
2
]
i\in[n/2]
i∈[n/2]，计算
R
L
W
E
(
2
⋅
u
(
i
,
n
/
2
)
)
=
(
R
L
W
E
(
u
(
i
,
n
)
)
+
X
n
/
2
⋅
R
L
W
E
(
u
(
i
+
n
/
2
,
n
)
)
)
+
τ
1
+
2
N
/
n
(
R
L
W
E
(
u
(
i
,
n
)
)
−
X
n
/
2
⋅
R
L
W
E
(
u
(
i
+
n
/
2
,
n
)
)
)
\begin{aligned} RLWE(2\cdot u^{(i,n/2)}) &= \left(RLWE(u^{(i,n)})+X^{n/2}\cdot RLWE(u^{(i+n/2,n)})\right)\\ &+ \tau_{1+2N/n}\left(RLWE(u^{(i,n)})-X^{n/2}\cdot RLWE(u^{(i+n/2,n)})\right) \end{aligned}
RLWE(2⋅u(i,n/2))=(RLWE(u(i,n))+Xn/2⋅RLWE(u(i+n/2,n)))+τ1+2N/n(RLWE(u(i,n))−Xn/2⋅RLWE(u(i+n/2,n)))
这就将
N
/
n
N/n
N/n 个密文合并为了
N
/
2
n
N/2n
N/2n 个密文。迭代执行对数次，可以最终合并出单个密文
R
L
W
E
(
n
⋅
Δ
u
)
RLWE(n \cdot \Delta u)
RLWE(n⋅Δu)。为了移除额外的因子
n
n
n，
- 假如 Q Q Q 和 n n n 互素，那么在 f f f 中使用 [ n − 1 ] Q ⋅ Δ [n^{-1}]_Q \cdot \Delta [n−1]Q⋅Δ 代替原本的 Δ \Delta Δ 即可
- 假如 Q Q Q 是二的幂次（ n n n 也是），那么使用 Q n Qn Qn 代替原本的 Q Q Q，最后缩放 n n n 同时在消息和模数上消除它
打包算法：
Bootstrapping for CKKS
Multiprecision CKKS
使用的密文模数
q
q
q 是二的幂次，相位形如
c
t
(
s
)
=
m
+
e
+
q
v
∈
R
ct(s) = m+e+qv \in R
ct(s)=m+e+qv∈R
令
q
′
=
q
/
2
N
q'=q/2N
q′=q/2N，计算
c
t
′
=
c
t
(
m
o
d
q
′
)
ct'=ct \pmod{q'}
ct′=ct(modq′)，那么
c
t
′
(
s
)
=
m
+
e
+
q
′
u
∈
R
ct'(s) = m+e+q'u \in R
ct′(s)=m+e+q′u∈R
我们可计算
c
t
p
r
e
p
=
(
a
−
[
a
]
q
′
q
′
,
b
−
[
b
]
q
′
q
′
)
∈
R
2
N
2
ct_{prep} = \left( \frac{a-[a]_{q'}}{q'}, \frac{b-[b]_{q'}}{q'} \right) \in R_{2N}^2
ctprep=(q′a−[a]q′,q′b−[b]q′)∈R2N2
易知
c
t
p
r
e
p
(
s
)
=
(
q
v
−
q
′
u
)
/
q
′
=
−
u
+
2
N
v
ct_{prep}(s)=(qv-q'u)/q'=-u+2Nv
ctprep(s)=(qv−q′u)/q′=−u+2Nv，从而它是
R
L
W
E
2
N
,
s
0
(
−
u
)
RLWE_{2N,s}^0(-u)
RLWE2N,s0(−u)
现在，利用 Scaled Modulus 过程，可以获得 c t s m = R L W E Q , s ( − q ′ u ) ct_{sm}=RLWE_{Q,s}(-q'u) ctsm=RLWEQ,s(−q′u)
继续计算
c
t
b
o
o
t
=
c
t
s
m
+
c
t
′
(
m
o
d
Q
)
ct_{boot} = ct_{sm}+ct' \pmod Q
ctboot=ctsm+ct′(modQ)，它满足
c
t
b
o
o
t
(
s
)
=
−
q
′
u
+
e
s
m
+
m
+
e
+
q
′
u
=
m
+
(
e
+
e
s
m
)
ct_{boot}(s) = -q'u+e_{sm} + m+e+q'u = m+(e+e_{sm})
ctboot(s)=−q′u+esm+m+e+q′u=m+(e+esm)
自举算法为：
对于稀疏打包的密文（这里指相位落在子环内），假设 c t ( s ) = m ( Y ) + q ⋅ v ( X ) ct(s)=m(Y)+q\cdot v(X) ct(s)=m(Y)+q⋅v(X)，其中 Y = X N / n Y=X^{N/n} Y=XN/n 是子环的本原单位根。
利用自同构 X → X − X n + 1 + X 2 n + 1 − ⋯ − X N − n + 1 X\to X-X^{n+1}+X^{2n+1}-\cdots-X^{N-n+1} X→X−Xn+1+X2n+1−⋯−XN−n+1 的性质，它将 ( N / n ) ∣ k (N/n) \mid k (N/n)∣k 的那些项 X k X^k Xk 的系数翻倍 N / n N/n N/n 因子，其余的项的系数都被消除。因此，我们可以使用同态自同构的加和，将 Y Y Y 子环以外的系数全都消除，获得 c t ′ ( s ) = m ( Y ) + q ⋅ v ′ ( Y ) ct'(s)=m(Y)+q\cdot v'(Y) ct′(s)=m(Y)+q⋅v′(Y)
现在，我们只需对这些稀疏的系数执行 Scaled Modulus 过程即可。
RNS-CKKS
使用的密文模数
q
q
q 是素数的乘积，相位形如
c
t
(
s
)
=
m
+
e
+
q
v
∈
R
ct(s) = m+e+qv \in R
ct(s)=m+e+qv∈R
首先计算
c
t
′
=
2
N
⋅
c
t
(
m
o
d
q
)
ct'=2N\cdot ct \pmod q
ct′=2N⋅ct(modq)，
c
t
′
(
s
)
=
2
N
⋅
(
m
+
e
)
+
q
u
∈
R
ct'(s) = 2N\cdot(m+e) + qu \in R
ct′(s)=2N⋅(m+e)+qu∈R
然后计算
c
t
p
r
e
p
=
(
2
N
a
−
[
2
N
a
]
q
′
q
′
,
2
N
b
−
[
2
N
b
]
q
′
q
′
)
∈
R
2
N
2
ct_{prep} = \left( \frac{2Na-[2Na]_{q'}}{q'}, \frac{2Nb-[2Nb]_{q'}}{q'} \right) \in R_{2N}^2
ctprep=(q′2Na−[2Na]q′,q′2Nb−[2Nb]q′)∈R2N2
它的相位是
−
u
(
m
o
d
2
N
)
-u \pmod{2N}
−u(mod2N)，利用 Scaled Modulus 过程获得
c
t
s
m
=
R
L
W
E
Q
p
,
s
(
−
q
u
)
ct_{sm}=RLWE_{Qp,s}(-qu)
ctsm=RLWEQp,s(−qu)，其中的
p
p
p 是 auxiliary prime 用于控制噪声
计算
c
t
′
′
=
c
t
s
m
+
c
t
′
(
m
o
d
Q
p
)
ct''=ct_{sm}+ct' \pmod{Qp}
ct′′=ctsm+ct′(modQp)，满足
c
t
′
′
(
s
)
=
−
q
u
+
e
s
m
+
2
N
⋅
(
m
+
e
)
+
q
u
=
2
N
m
+
(
2
N
e
+
e
s
m
)
ct''(s) = -qu+e_{sm} + 2N\cdot(m+e)+qu = 2Nm + (2Ne+e_{sm})
ct′′(s)=−qu+esm+2N⋅(m+e)+qu=2Nm+(2Ne+esm)
最后将它乘以
p
/
2
N
p/2N
p/2N 接着缩放
p
p
p 因子，获得
c
t
b
o
o
t
(
s
)
=
m
+
(
e
+
e
s
m
/
2
N
+
e
r
s
)
(
m
o
d
Q
)
ct_{boot}(s) = m + (e+e_{sm}/2N + e_{rs}) \pmod Q
ctboot(s)=m+(e+esm/2N+ers)(modQ)
完整的自举程序为
Bootstrapping for BGV
Multiprecision BGV
模数是二的幂次。与 CKKS 的自举步骤基本一样，
RNS-BGV
模数是素数乘积。与 CKKS 的自举步骤基本一样，
Bootstrapping for BFV
Multiprecision BFV
BFV 的自举略有不同，它并不是消除 overflow 去提升模数，而是需要降低噪声。
模数
Q
Q
Q 是二的幂次，密文相位是
c
t
(
s
)
=
e
+
Q
t
m
∈
R
Q
ct(s) = e+\frac{Q}{t}m \in R_Q
ct(s)=e+tQm∈RQ
首先计算
c
t
′
=
t
⋅
c
t
(
m
o
d
Q
)
ct'=t \cdot ct \pmod Q
ct′=t⋅ct(modQ)，
c
t
′
(
s
)
=
t
e
+
Q
v
∈
R
ct'(s) = te + Qv \in R
ct′(s)=te+Qv∈R
令
Q
′
=
Q
/
2
N
Q'=Q/2N
Q′=Q/2N，接着计算
c
t
′
′
=
c
t
′
(
m
o
d
Q
′
)
ct''=ct' \pmod{Q'}
ct′′=ct′(modQ′)，
c
t
′
′
(
s
)
=
t
e
+
Q
′
u
∈
R
ct''(s) = te + Q'u \in R
ct′′(s)=te+Q′u∈R
于是可以计算
c
t
p
r
e
p
=
c
t
′
−
c
t
′
′
Q
′
∈
R
2
N
2
ct_{prep} = \frac{ct'-ct''}{Q'} \in R_{2N}^2
ctprep=Q′ct′−ct′′∈R2N2
它的相位是
−
u
+
2
N
v
-u+2Nv
−u+2Nv，利用 Scaled Modulus 过程获得
c
t
s
m
=
R
L
W
E
Q
t
,
s
(
Q
′
u
)
ct_{sm}=RLWE_{Qt,s}(Q'u)
ctsm=RLWEQt,s(Q′u)
然后计算
c
t
′
′
′
=
c
t
s
m
+
t
⋅
c
t
−
c
t
′
′
(
m
o
d
Q
t
)
ct'''=ct_{sm}+t \cdot ct-ct'' \pmod{Qt}
ct′′′=ctsm+t⋅ct−ct′′(modQt)，
c
t
′
′
′
(
s
)
=
(
Q
′
u
+
e
s
m
)
+
(
t
e
+
Q
m
)
−
(
t
e
+
Q
′
u
)
=
Q
m
+
e
s
m
ct'''(s) = (Q'u+e_{sm}) + (te+Qm) - (te+Q'u) = Qm+e_{sm}
ct′′′(s)=(Q′u+esm)+(te+Qm)−(te+Q′u)=Qm+esm
最后缩放
t
t
t 因子，获得
c
t
b
o
o
t
=
R
L
W
E
Q
,
s
(
m
)
ct_{boot}=RLWE_{Q,s}(m)
ctboot=RLWEQ,s(m)
完整的自举算法为：
RNS-BFV
模数是素数乘积。就是上述自举算法的变体，
Compact Representation of Blind Rotation Keys
[KDE+23] 还给出了压缩 BK 的方法。
采取三元秘密，原本的 BK 形如： R G S W s ( s i + ) RGSW_s(s_i^+) RGSWs(si+) 以及 R G S W s ( s i − ) RGSW_s(s_i^-) RGSWs(si−)，其中的 s i + = [ s i = 1 ] s_i^+=[s_i=1] si+=[si=1] 和 s i − = [ s i = − 1 ] s_i^-=[s_i=-1] si−=[si=−1] 作为 CMux 控制位。
Reconstruction
为了减少通信开销，[KDE+23] 仅生成
R
L
W
E
s
′
(
s
±
)
RLWE_s'(s^\pm)
RLWEs′(s±) 和
R
L
W
E
s
′
(
s
2
)
RLWE_s'(s^2)
RLWEs′(s2) 两个密文，其中
s
±
(
X
)
=
∑
i
=
0
N
−
1
s
i
±
X
i
s^{\pm}(X) = \sum_{i=0}^{N-1} s_i^\pm X^i
s±(X)=i=0∑N−1si±Xi
利用自同构的保持/翻转各个位置系数的符号的特点，我们可以根据
R
L
W
E
s
′
(
s
±
)
RLWE_s'(s^\pm)
RLWEs′(s±) 恢复出全部的
R
L
W
E
s
′
(
s
i
±
)
RLWE_s'(s_i^\pm)
RLWEs′(si±)。算法为：
消除因子
N
N
N 是容易的。接着，利用计算出的各个分量
R
L
W
E
s
(
g
j
s
i
±
)
=
(
a
i
j
,
b
i
j
)
RLWE_s(g_js_i^\pm)=(a_{ij},b_{ij})
RLWEs(gjsi±)=(aij,bij)，可以计算出：
R
L
W
E
s
(
a
i
j
⋅
s
2
+
b
i
j
⋅
s
)
=
R
L
W
E
s
(
g
j
s
i
±
⋅
s
)
RLWE_s(a_{ij} \cdot s^2 + b_{ij} \cdot s) = RLWE_s(g_js_i^\pm\cdot s)
RLWEs(aij⋅s2+bij⋅s)=RLWEs(gjsi±⋅s)
它们组成了
R
L
W
E
s
′
(
s
i
±
s
)
RLWE_s'(s_i^\pm s)
RLWEs′(si±s)，于是我们就得到了
R
G
S
W
s
(
s
i
±
)
=
(
R
L
W
E
s
′
(
s
i
±
)
,
R
L
W
E
s
′
(
s
i
±
s
)
)
RGSW_s(s_i^\pm) = (RLWE_s'(s_i^\pm), RLWE_s'(s_i^\pm s))
RGSWs(si±)=(RLWEs′(si±),RLWEs′(si±s))
On the Fly
为了减少内存开销，[KDE+23] 还提出了动态重构 BK 的方法，用完就立即丢弃。
这儿也是利用了自同构，消除常数项以外的其他系数。我们首先乘以 X − i X^{-i} X−i，从而提取任意位置的 s i ± s_i^\pm si± 的密文。算法为：
[KDE+23] 提出了一种新的盲旋转过程，它不需要重构出
R
L
W
E
s
′
(
s
i
±
⋅
s
)
RLWE_s'(s_i^\pm \cdot s)
RLWEs′(si±⋅s)，而是直接根据
R
L
W
E
s
′
(
s
i
±
)
RLWE_s'(s_i^\pm)
RLWEs′(si±) 和
R
L
W
E
s
′
(
s
2
)
RLWE_s'(s^2)
RLWEs′(s2) 来计算：给定
A
C
C
=
R
L
W
E
s
(
f
)
=
(
a
,
b
)
ACC=RLWE_s(f)=(a,b)
ACC=RLWEs(f)=(a,b)，给定密文
L
W
E
s
(
u
)
=
(
α
,
β
)
LWE_s(u)=(\alpha,\beta)
LWEs(u)=(α,β)，先计算
a
⋅
R
L
W
E
s
′
(
X
α
i
s
i
)
=
R
L
W
E
s
′
(
a
⋅
X
α
i
s
i
)
=
(
a
′
,
b
′
)
a\cdot RLWE_s'(X^{\alpha_is_i}) = RLWE_s'(a\cdot X^{\alpha_is_i}) = (a',b')
a⋅RLWEs′(Xαisi)=RLWEs′(a⋅Xαisi)=(a′,b′)
然后计算
a
′
⋅
R
L
W
E
s
′
(
s
2
)
+
(
b
′
,
0
)
=
R
L
W
E
s
(
a
′
s
2
+
b
′
s
)
=
R
L
W
E
s
(
a
s
⋅
X
α
i
s
i
)
a' \cdot RLWE_s'(s^2) + (b',0) = RLWE_s(a's^2+b's) = RLWE_s(as \cdot X^{\alpha_is_i})
a′⋅RLWEs′(s2)+(b′,0)=RLWEs(a′s2+b′s)=RLWEs(as⋅Xαisi)
最后计算出
R
L
W
E
s
(
a
s
⋅
X
α
i
s
i
)
+
R
L
W
E
s
(
b
⋅
X
α
i
s
i
)
=
R
L
W
E
s
(
f
⋅
X
α
i
s
i
)
RLWE_s(as \cdot X^{\alpha_is_i}) + RLWE_s(b \cdot X^{\alpha_is_i}) = RLWE_s(f \cdot X^{\alpha_is_i})
RLWEs(as⋅Xαisi)+RLWEs(b⋅Xαisi)=RLWEs(f⋅Xαisi)
对于每个
i
i
i 都这么计算，最终可以获得
R
L
W
E
s
(
f
⋅
X
u
)
RLWE_s(f \cdot X^u)
RLWEs(f⋅Xu)
![[机器学习]KNN——K邻近算法实现](https://img-blog.csdnimg.cn/direct/de0fd9fea44941a790726c7392dc81ca.png)
