参考资料：

Micciancio D, Peikert C. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[C]//Eurocrypt. 2012, 7237: 700-718.
Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error[C]//Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34. Springer Berlin Heidelberg, 2014: 297-314.
Ducas L, Micciancio D. FHEW: bootstrapping homomorphic encryption in less than a second[C]//Advances in Cryptology–EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I 34. Springer Berlin Heidelberg, 2015: 617-640.

文章目录

AP14
- Embedding
- GSW
- HEPerm
- Bootstrapping
FHEW

AP14

2014 年，Alperin 和 Peikert 提出了一种快速 Bootstrapping 方案。他们将加法群

Z_q

$Z_{q}$

嵌入到对称群

S_q

$S_{q}$

（置换矩阵

}

\{0,1\}^{q \times q}

${0, 1}^{q \times q}$

的乘法群）上，在

代数电路上执行自举

，大大提高了自举效率。而之前的方案，基本都在布尔电路上运算，使用

Barrington‘s Theorem

将

NC^1

$N C^{1}$

电路转化为

5-PBP 置换分支程序

。

利用 GSW 乘法噪声增长的

非对称性

，采用右结合的乘法链其噪声增长是

拟加性

的（quasi-additive）。另外，他们给出了 GSW 的更简单的变体，可以证明两者是等价的。

本文重点关注如何快速自举，它可以兼容所有的基于 LWE 的 FHE。由于解密算法是：

(

)

⌊

⟨

⟩

⌉

Dec(s,c) := \lfloor \langle s,c \rangle \rceil_2

$Dec (s, c) := ⌊⟨ s, c ⟩ ⌉_{2}$

这里

⌉

⌊

⋅

⌉

\lfloor x \rceil_2 := \lfloor 2/q \cdot x \rceil

$⌊ x ⌉_{2} := ⌊ 2/ q \cdot x ⌉$

是从

Z_q

$Z_{q}$

到

Z_2

$Z_{2}$

的模切换，或者说是 MSB 的提取。那么，自举的关键就是：

对于固定的秘密
$\langle s,c \rangle ⟨ s , c ⟩ （这是 subset-sum，只需要同态加法）。$
对于计算出的
$\langle s,c \rangle ⟨ s , c ⟩ 的密文，提取出 MSB 对应的 LWE 密文（关键步骤）。$

Embedding

根据

Cayley’s Theorem

，任意的有限群

G

$G$

都可以嵌入（injective homomorphism）到

对称群

∣

S_{|G|}

$S_{∣ G ∣}$

中。而这个对称群同构于

∣

|G|

$∣ G ∣$

阶的

置换矩阵乘法群

，置换

\pi

$π$

对应的置换矩阵为：

[

(

)

(

)

⋯

(

∣

)

]

P_\pi := [e_{\pi(1)},e_{\pi(2)},\cdots,e_{\pi(|G|)}]

$P_{π} := [e_{π (1)}, e_{π (2)}, \dots, e_{π (∣ G ∣)}]$

因此，任意的加法群

)

(Z_r,+)

$(Z_{r}, +)$

都可以嵌入到对称群

S_r

$S_{r}$

中，也就是

r \times r

$r \times r$

的置换矩阵的乘法群。嵌入映射为：将元素

∈

x \in Z_r

$x \in Z_{r}$

映射到位移

x

$x$

的

循环置换

（the permutation that cyclically rotates by

x

positions）。

我们定义

→

(

)

\pi:i \to i+1 \pmod r

$π : i \to i + 1 (mod r)$

为循环位移置换，将

x

$x$

次置换的复合

∘

⋯

∘

\pi \circ \cdots \circ \pi

$π \circ \dots \circ π$

简记为

\pi^x

$π^{x}$

。容易看出，循环置换

P_{\pi^x}

$P_{π^{x}}$

可以被简化表示为一个

}

\{0,1\}^r

${0, 1}^{r}$

的

指示向量

e_x

$e_{x}$

（indicator vector），其第

x

$x$

个分量是

1

$1$

，其他分量都为

0

$0$

，而对应的置换矩阵就是将

e_x

$e_{x}$

作为第一列，其他列依次是

e_x

$e_{x}$

的循环移位（cyclic shift）。

此时，

Z_r

$Z_{r}$

与

S_r

$S_{r}$

上的运算对应关系为：

$Z_r Z r 中的加法 x + y ( m o d r ) x+y \pmod r x + y ( mod r ) ，同构于 S r S_r S r 中的置换复合，或者说置换矩阵乘法 P π x ⋅ P π y P_{\pi^x} \cdot P_{\pi^y} P π x ⋅ P π y ，可以简化为 P π x ⋅ e y P_{\pi^x} \cdot e_y P π x ⋅ e y （等价于多项式 e x , e y e_x,e_y e x , e y 的在 Z 2 [ x ] / ( x r − 1 ) Z_2[x]/(x^r-1) Z 2 [ x ] / ( x r − 1 ) 上的多项式乘积）$
$Z_r Z r 中的相等判定 x = v ( m o d r ) x = v \pmod r x = v ( mod r ) ，同构于 S r S_r S r 中的置换相等判定 P π x = P π v P_{\pi^x} = P_{\pi^v} P π x = P π v ，可以简化为 e x ( v ) e_x^{(v)} e x ( v ) $
$Z_r Z r 中的提取 MSB ⌊ x ⌉ 2 \lfloor x \rceil_2 ⌊ x ⌉ 2 ，同构于 S r S_r S r 中的一些相等判定的加和，即 ∑ v ∈ [ r ] s . t . ⌊ v ⌉ 2 = 1 e x ( v ) \sum_{v \in [r]\,s.t.\,\lfloor v \rceil_2=1} e_x^{(v)} ∑ v ∈ [ r ] s . t . ⌊ v ⌉ 2 = 1 e x ( v ) $

对于一个较大的模数

q

$q$

，直接将

Z_q

$Z_{q}$

嵌入到

S_q

$S_{q}$

效率很低。优化思路是利用

CRT

，如果让

∏

q = \prod_i r_i

$q = \prod_{i} r_{i}$

，其中

r_i

$r_{i}$

是规模

(

)

\tilde O(1)

$\tilde{O} (1)$

的素数幂，那么有

≅

∏

⊆

∏

Z_q \cong \prod_i Z_{r_i} \subseteq \prod_i S_{r_i}

$Z_{q} ≅ i \prod Z_{r_{i}} \subseteq i \prod S_{r_{i}}$

对应的嵌入映射为：

∈

↦

(

)

∈

∏

\phi: x \in Z_q \mapsto \left(e_{x \pmod{r_i}}\right)_i \in \prod_i S_{r_i}

$ϕ : x \in Z_{q} \mapsto (e_{x (mod r_{i})})_{i} \in i \prod S_{r_{i}}$

这样就可以在多个小规模的对称群

S_{r_i}

$S_{r_{i}}$

上执行计算。此时，

q

Z_q

$Z_{q}$

上的

加法

，同构于

i

S

r

i

\prod_i S_{r_i}

$\prod_{i} S_{r_{i}}$

上的各个分量的置换各自复合，即

x

+

y

)

:

=

(

P

π

x

(

m

o

d

r

i

)

⋅

e

y

(

m

o

d

r

i

)

)

i

(x+y) := \left(P_{\pi^{x \pmod{r_i}}} \cdot e_{y \pmod{r_i}}\right)_i

$(x + y) := (P_{π^{x (mod r_{i})}} \cdot e_{y (mod r_{i})})_{i}$
q

Z_q

$Z_{q}$

上的

相等判定

，同构于

i

S

r

i

\prod_i S_{r_i}

$\prod_{i} S_{r_{i}}$

上的各个分量的相等判定的乘积（逻辑 AND），即

x

=

v

]

:

=

∏

i

e

x

(

m

o

d

r

i

)

(

v

(

m

o

d

r

i

)

)

[x=v] := \prod_i e_{x \pmod{r_i}}^{(v \pmod{r_i})}

$[x = v] := i \prod e_{x (mod r_{i})}^{(v (mod r_{i}))}$
q

Z_q

$Z_{q}$

上的

提取 MSB

，同构于

i

S

r

i

\prod_i S_{r_i}

$\prod_{i} S_{r_{i}}$

上的一些相等判定的加和（逻辑 OR），即

x

⌉

2

:

=

∑

v

∈

[

q

]

s

.

t

.

⌊

v

⌉

2

=

1

[

x

=

v

]

\lfloor x \rceil_2 := \sum_{v \in [q]\,s.t.\,\lfloor v \rceil_2=1} [x=v]

$⌊ x ⌉_{2} := v \in [q] s . t . ⌊ v ⌉_{2} = 1 \sum [x = v]$

为了加速，文章选择让

q

$q$

是

⁡

\max_i r_i

$max_{i} r_{i}$

的指数级大。根据

second Chebyshev function

，

(

)

∑

≤

log

⁡

log

⁡

(

∏

≤

⌊

log

⁡

⌋

)

\psi(x) := \sum_{p^k \le x} \log p = \log\left(\prod_{p \le x} p^{\lfloor \log_p x \rfloor}\right)

$ψ (x) := p^{k} \leq x \sum lo g p = lo g (p \leq x \prod p^{⌊ l o g_{p} x ⌋})$

因此，所有的小于

x

$x$

的最大素数幂

⌊

log

⁡

⌋

r_i = p^{\lfloor \log_p x \rfloor}

$r_{i} = p^{⌊ l o g_{p} x ⌋}$

的乘积

∏

q=\prod_i r_i

$q = \prod_{i} r_{i}$

大小为

⁡

(

)

\exp(\psi(x))

$exp (ψ (x))$

。已知

(

)

(

log

⁡

)

\psi(x)=x+O(x/\log x)

$ψ (x) = x + O (x / lo g x)$

，并且对于所有的

≥

x \ge 7

$x \geq 7$

都有一个非渐进界

(

)

≥

\psi(x)\ge 3x/4

$ψ (x) \geq 3 x /4$

，所以有

≥

exp

⁡

(

)

≥

exp

⁡

(

⋅

max

⁡

)

q \ge \exp(3x/4) \ge \exp(3/4 \cdot \max_i r_i)

$q \geq exp (3 x /4) \geq exp (3/4 \cdot i max r_{i})$

选取很小的界

x

$x$

，就可以用一些最大素数幂

≤

r_i \le x

$r_{i} \leq x$

合成出一个指数级大的模数

q

$q$

。

GSW

本文给出了

GSW

的一个对称版本的更简单变体。

给定模数

q

$q$

，令

⌈

log

⁡

⌉

l = \lceil \log q \rceil

$l = ⌈ lo g q ⌉$

，定义 gadget column vector

(

⋯

−

)

∈

g = (1,2,4,\cdots,2^{l-1}) \in Z^l

$g = (1, 2, 4, \dots, 2^{l - 1}) \in Z^{l}$

，它的

倒数第二个分量

为

−

∈

[

)

2^{l-2} \in [q/4,q/2)

$2^{l - 2} \in [q /4, q /2)$

就是 GSW 中所谓 “big coefficient”。

根据 MP12，存在一个随机的可有效计算的函数

−

→

g^{-1}:Z_q \to Z^l

$g^{- 1} : Z_{q} \to Z^{l}$

，使得

←

−

(

)

x \leftarrow g^{-1}(a)

$x \leftarrow g^{- 1} (a)$

是一个满足

⟨

⟩

a=\langle g,x \rangle

$a = ⟨ g, x ⟩$

的参数

(

)

O(1)

$O (1)$

的亚高斯随机变量。具体地，就是使用

随机版本的 Babai nearest-plane 算法

，给定格

⊥

(

)

{

∈

⟨

⟩

≡

∈

}

\Lambda^\perp(g^t) := \{z \in Z^l: \langle g,x \rangle \equiv 0 \in Z_q\}

$Λ^{⊥} (g^{t}) := {z \in Z^{l} : ⟨ g, x ⟩ \equiv 0 \in Z_{q}}$

的一组 “好” 的基底

S

$S$

，每次迭代中第

i

$i$

次个基向量对应的系数服从中心零的

−

}

∈

∩

[

)

\{c_i-1,c_i\},\,c_i \in \frac{1}{q} Z \cap [0,1)

${c_{i} - 1, c_{i}}, c_{i} \in \frac{1}{q} Z \cap [0, 1)$

上二值分布。

对于向量和矩阵，定义 gadget matrix

⊗

∈

G = g^t \otimes I_n \in Z_q^{n \times nl}

$G = g^{t} \otimes I_{n} \in Z_{q}^{n \times n l}$

，对应的

−

→

G^{-1}: Z_q^{n \times m} \to Z_q^{nl \times m}

$G^{- 1} : Z_{q}^{n \times m} \to Z_{q}^{n l \times m}$

就是对于每个 entry 独立的使用

−

g^{-1}

$g^{- 1}$

算法。那么给定

⋅

A = G \cdot X

$A = G \cdot X$

，

←

−

(

)

X \leftarrow G^{-1}(A)

$X \leftarrow G^{- 1} (A)$

是一个参数

(

)

O(1)

$O (1)$

的亚高斯随机向量（与任意的固定单位向量的内积是亚高斯的）。

在 GSW 中，密文

∈

{

}

C \in \{0,1\}^{nl \times nl}

$C \in {0, 1}^{n l \times n l}$

是二元方阵，秘密

∈

s \in Z_q^{nl}

$s \in Z_{q}^{n l}$

是

结构化向量

（有个 “big coefficient”），它是个近似特征向量

≈

(

)

s^tC \approx \mu s^t \pmod q

$s^{t} C \approx μ s^{t} (mod q)$

。本文中的 GSW 变体，密文

∈

C \in Z_q^{n \times nl}

$C \in Z_{q}^{n \times n l}$

是长矩阵，秘密

∈

s \in Z^{n}

$s \in Z^{n}$

是

非结构化的短向量

，关系为

≈

⋅

(

)

s^tC \approx \mu \cdot s^tG \pmod q

$s^{t} C \approx μ \cdot s^{t} G (mod q)$

。两者是等价的。

对称的 GSW 变体：

$GSW.Gen(1^n) GS W . G e n ( 1 n ) ：采样 s ˉ ← R χ n − 1 \bar s \leftarrow_R \chi^{n-1} s ˉ ← R χ n − 1 ，输出 s : = ( s ˉ , 1 ) s := (\bar s,1) s := ( s ˉ , 1 )$
$GSW.Enc(s,\mu \in \mathbb Z) GS W . E n c ( s , μ ∈ Z ) ：采样 C ˉ ← R Z q ( n − 1 ) × n l \bar C \leftarrow_R Z_q^{(n-1)\times nl} C ˉ ← R Z q ( n − 1 ) × n l 和 e ← χ m e \leftarrow \chi^m e ← χ m ，计算 b t = e t − s t C ˉ b^t = e^t – s^t \bar C b t = e t − s t C ˉ ，输出 C = ( C ˉ , b t ) t + μ G ∈ C C = (\bar C,b^t)^t + \mu G \in \mathcal C C = ( C ˉ , b t ) t + μ G ∈ C （而原始 GSW 中是 F l a t t e n ( μ I n l + G − 1 ( R A ) ) = G − 1 ( μ G + R A ) Flatten(\mu I_{nl}+G^{-1}(RA)) = G^{-1}(\mu G+RA) Fl a tt e n ( μ I n l + G − 1 ( R A )) = G − 1 ( μ G + R A ) ，两者等价）$
$\in \mathcal C) GS W . Dec ( s , C ∈ C ) ：由于 s t C = e t + μ ⋅ s t G s^tC = e^t + \mu \cdot s^t G s t C = e t + μ ⋅ s t G ，因此取出倒数第二列 c c c （ G G G 的倒数第二列是 [ 0 , ⋯ , 0 , 2 l − 2 ] [0,\cdots,0,2^{l-2}] [ 0 , ⋯ , 0 , 2 l − 2 ] ），计算出 2 l − 2 ⋅ μ ≈ ⟨ s , c ⟩ 2^{l-2} \cdot \mu \approx \langle s,c \rangle 2 l − 2 ⋅ μ ≈ ⟨ s , c ⟩ ，输出 μ \mu μ$

在

−

LWE_{n-1,q,\chi}

$L W E_{n - 1, q, χ}$

假设下，上述方案是 IND-CPA 安全的。

同态加法
$C_1 \boxplus C_2:= C_1 + C_2 C 1 ⊞ C 2 := C 1 + C 2 ，噪声 e 1 t + e 2 t e_1^t+e_2^t e 1 t + e 2 t $
同态乘法
$C_1 \boxdot C_2:= C_1 \cdot X C 1 ⊡ C 2 := C 1 ⋅ X ，噪声 e 1 t X + μ 1 e 2 t e_1^t X + \mu_1 e_2^t e 1 t X + μ 1 e 2 t ，其中 X ← G − 1 ( C 2 ) X \leftarrow G^{-1}(C_2) X ← G − 1 ( C 2 )$

由于同态乘法的非对称噪声增长，我们令算符

\boxdot

$⊡$

是

右结合

的（ right associative）。对于一个关于密文

⋯

C_i, i=1,\cdots,k

$C_{i}, i = 1, \dots, k$

的

乘法链

，

←

(

⊡

∈

[

]

)

⊡

(

⋯

(

⊡

)

∈

C \leftarrow \left(\boxdot_{i \in [k]} C_i\right) \boxdot G = C_1 \boxdot(\cdots(C_k \boxdot G)) \in \mathcal C

$C \leftarrow (⊡_{i \in [k]} C_{i}) ⊡ G = C_{1} ⊡ (\dots (C_{k} ⊡ G)) \in C$

这里的

⋅

∈

G = \textbf{0}+1 \cdot G \in \mathcal C

$G = 0 + 1 \cdot G \in C$

是个

零噪声的

1

$1$

的密文

。由于

∈

{

}

\mu \in \{0,1\}

$μ \in {0, 1}$

，因此

C

$C$

的噪声为

∈

[

]

\sum_{i \in [k]} e_i^t X_i

$\sum_{i \in [k]} e_{i}^{t} X_{i}$

，这是参数

(

∥

)

O(\|e_i\|)

$O (∥ e_{i} ∥)$

的亚高斯随机变量（

拟加性

）。

HEPerm

现在，我们基于上述的对称 GSW 方案，构造关于对称群

S_r

$S_{r}$

的同态方案（不是 FHE）：

$HEPerm.Gen(1^n) H EP er m . G e n ( 1 n ) ：输出 s k : = G S W . G e n ( 1 n ) sk := GSW.Gen(1^n) s k := GS W . G e n ( 1 n )$
$\pi \in S_r) H EP er m . E n c ( s k , π ∈ S r ) ：找到对应的置换阵 P π = ( p i j ) ∈ { 0 , 1 } r × r P_\pi = (p_{ij}) \in \{0,1\}^{r \times r} P π = ( p ij ) ∈ { 0 , 1 } r × r ，输出 C = ( G S W . E n c ( s k , p i j ) ) ∈ C r × r C = (GSW.Enc(sk,p_{ij})) \in \mathcal C^{r \times r} C = ( GS W . E n c ( s k , p ij )) ∈ C r × r$
$\in \mathcal C^{r \times r}) H EP er m . Dec ( s k , C ∈ C r × r ) ：计算出 P π = ( G S W . D e c ( s k , c i j ) ) ∈ { 0 , 1 } r × r P_\pi = (GSW.Dec(sk,c_{ij})) \in \{0,1\}^{r \times r} P π = ( GS W . Dec ( s k , c ij )) ∈ { 0 , 1 } r × r ，输出对应的置换 π \pi π$

这个方案有如下的同态运算（对于任意的

∈

\pi,\sigma \in S_r

$π, σ \in S_{r}$

，而不仅仅那

r

$r$

个循环置换）：

同态的映射复合

$C^\pi \circ C^\sigma := \left(\boxplus_{k \in [r]} \left(c_{ik}^\pi \boxdot c_{kj}^\sigma\right)\right)_{ij} \in \mathcal C^{r \times r} C π ∘ C σ := ( ⊞ k ∈ [ r ] ( c ik π ⊡ c kj σ ) ) ij ∈ C r × r ，就是一般的矩阵乘法（在同态运算下），噪声 E + P π ⋅ E σ E+P^\pi \cdot E^\sigma E + P π ⋅ E σ ，其中 E E E 的第 i i i 行服从参数 O ( ∥ e i π ∥ ) O(\|e_i^\pi\|) O ( ∥ e i π ∥ ) 的亚高斯分布，这里 e i π e_i^\pi e i π 是指 E π E^\pi E π 的第 i i i 行。$
同态的相等判定

$Eq(C^\pi,\sigma) := \left(\boxdot_{i \in [r]} c_{\sigma(i),i}^\pi\right) \boxdot G \in \mathcal C Eq ( C π , σ ) := ( ⊡ i ∈ [ r ] c σ ( i ) , i π ) ⊡ G ∈ C ，因为置换阵 P π P_\pi P π 的 p π ( i ) , i p_{\pi(i),i} p π ( i ) , i 都是 1 1 1 ，而其他的 entry 都是 0 0 0$

对于同构于

\mathbb Z_r

$Z_{r}$

的循环置换子群

⊆

C_r \subseteq S_r

$C_{r} \subseteq S_{r}$

，可以只对指示向量对应的那一列加密。对于

∈

x,y \in \mathbb Z_r

$x, y \in Z_{r}$

，密文

∈

C^x,C^y \in \mathcal C^r

$C^{x}, C^{y} \in C^{r}$

，此时的

计算复杂度降低了

r

$r$

因子

：

同态加法
$C^x \circ C^y := \left(\boxplus_{k \in [r]} \left(c_{r+i-k}^x \boxdot c_{k}^y \right)\right)_{i} \in \mathcal C^{r } C x ∘ C y := ( ⊞ k ∈ [ r ] ( c r + i − k x ⊡ c k y ) ) i ∈ C r ，计算复杂度从 O ( r 3 ) O(r^3) O ( r 3 ) 降低到了 O ( r 2 ) O(r^2) O ( r 2 )$
同态的相等判定
$Eq(C^x,v) := c_{v}^x \in \mathcal C Eq ( C x , v ) := c v x ∈ C ，计算复杂度从 O ( r ) O(r) O ( r ) 降低到了 O ( 1 ) O(1) O ( 1 )$

类似的，由于同态乘法的非对称噪声增长，我们令算符

\circ

$\circ$

也是

右结合

的（ right associative）。对于一个关于密文

⋯

C_i, i=1,\cdots,k

$C_{i}, i = 1, \dots, k$

的

复合链

，

←

(

◯

∈

[

]

)

∘

(

⋯

(

∘

)

∈

C \leftarrow \left(\bigcirc _{i \in [k]} C_{i}\right) \circ J = C_1 \circ(\cdots(C_k \circ J)) \in \mathcal C^{r}

$C \leftarrow (◯_{i \in [k]} C_{i}) \circ J = C_{1} \circ (\dots (C_{k} \circ J)) \in C^{r}$

这里

∈

J \in \mathcal C^{r}

$J \in C^{r}$

是零噪声的恒等置换

I_{r}

$I_{r}$

的 HEPerm 密文（对角线 entry 是

⋅

1 \cdot G

$1 \cdot G$

，其他的 entry 都是

⋅

0 \cdot G

$0 \cdot G$

，将第一列作为指示向量的密文）。由于

P^\sigma

$P^{σ}$

是置换阵，因此

C

$C$

的噪声矩阵的第

i

$i$

行服从参数

(

∥

)

O(\|e_i\|)

$O (∥ e_{i} ∥)$

的亚高斯分布，其中

∈

e_i \in \mathcal E^{kr}

$e_{i} \in E^{k r}$

是

∣

⋯

∣

]

[E_1|\cdots|E_k]

$[E_{1} ∣ \dots ∣ E_{k}]$

的第

i

$i$

行。

Bootstrapping

现在，我们可以使用 HEPerm 来对

任意的 LWE 方案

执行自举了！

定义群嵌入（group embedding），

(

)

→

(

∏

∘

)

\phi: (\mathbb Z_q,+) \to (S:=\prod_{i=1}^t S_{r_i}, \circ)

$ϕ : (Z_{q}, +) \to (S := i = 1 \prod t S_{r_{i}}, \circ)$

令

\phi_i

$ϕ_{i}$

是它的第

i

$i$

分量。我们为 HEPerm（或者说它的部件 GSW）选取一个足够大的模数

≫

Q \gg q

$Q ≫ q$

，以保证 Bootstrapping 之后的噪声比率很小。

令 LWE 的私钥是

∈

s \in \mathbb Z_q^d

$s \in Z_{q}^{d}$

，密文是二元向量

∈

{

}

c \in \{0,1\}^d

$c \in {0, 1}^{d}$

，解密函数为

(

)

(

⟨

⟩

)

Dec(s,c) := f(\langle s,c \rangle)

$Dec (s, c) := f (⟨ s, c ⟩)$

其中

→

{

}

f:\mathbb Z_q \to \{0,1\}

$f : Z_{q} \to {0, 1}$

是某种解码函数。

令

←

sk \leftarrow \chi^n

$s k \leftarrow χ^{n}$

是 HEPerm 的对称秘钥，自举方案如下：

o

o

t

G

e

n

(

s

,

s

k

)

BootGen(s,sk)

$B oo tG e n (s, s k)$

：将

s

$s$

的每个分量

j

s_j

$s_{j}$

嵌入到

S

$S$

中，然后对每个

r

i

S_{r_i}

$S_{r_{i}}$

上的置换

i

(

s

j

)

\phi_i(s_j)

$ϕ_{i} (s_{j})$

用 HEPerm 加密，作为 bootstrapping key，

k

:

=

{

C

i

j

←

H

E

P

e

r

m

.

E

n

c

(

s

k

,

ϕ

i

(

s

j

)

)

∈

C

r

i

:

i

∈

[

t

]

,

j

∈

[

d

]

}

bk := \{ C_{ij} \leftarrow HEPerm.Enc(sk,\phi_i(s_j)) \in \mathcal C^{r_i}: i \in [t], j \in [d] \}

$bk := {C_{ij} \leftarrow H EP er m . E n c (s k, ϕ_{i} (s_{j})) \in C^{r_{i}} : i \in [t], j \in [d]}$

由于

,

r

i

=

O

(

log

⁡

λ

)

t,r_i = O(\log \lambda)

$t, r_{i} = O (lo g λ)$

且

=

O

~

(

λ

)

d = \tilde O(\lambda)

$d = \tilde{O} (λ)$

，因此

k

∈

(

∏

i

=

1

t

C

r

i

)

d

bk \in \left(\prod_{i=1}^t \mathcal C^{r_i}\right)^d

$bk \in (\prod_{i = 1}^{t} C^{r_{i}})^{d}$

包含

~

(

λ

)

\tilde O(\lambda)

$\tilde{O} (λ)$

个 GSW 密文。
o

o

t

s

t

r

a

p

(

b

k

,

c

∈

{

0

,

1

}

d

)

Bootstrap(bk,c \in \{0,1\}^d)

$B oo t s t r a p (bk, c \in {0, 1}^{d})$

：
- 内积运算
  
  ，转化为 subset-sum，即
  
  s
  
  ,
  
  c
  
  ⟩
  
  =
  
  ∑
  
  j
  
  :
  
  c
  
  j
  
  =
  
  1
  
  s
  
  j
  
  ∈
  
  Z
  
  q
  
  \langle s,c \rangle = \sum_{j:c_j=1} s_j \in \mathbb Z_q
  
  $⟨ s, c ⟩ = \sum_{j : c_{j} = 1} s_{j} \in Z_{q}$
  
  ，在对称群
  
  :
  
  =
  
  ∏
  
  i
  
  =
  
  1
  
  t
  
  S
  
  r
  
  i
  
  S:=\prod_{i=1}^t S_{r_i}
  
  $S := \prod_{i = 1}^{t} S_{r_{i}}$
  
  下的复合链为
  
  i
  
  ←
  
  (
  
  ◯
  
  j
  
  ∈
  
  [
  
  d
  
  ]
  
  s
  
  .
  
  t
  
  .
  
  c
  
  j
  
  =
  
  1
  
  C
  
  i
  
  j
  
  )
  
  ∘
  
  J
  
  ∈
  
  C
  
  r
  
  i
  
  C_i \leftarrow \left(\bigcirc _{j \in [d]\, s.t.\, c_j=1} C_{ij}\right) \circ J \in \mathcal C^{r_i}
  
  $C_{i} \leftarrow (◯_{j \in [d] s . t . c_{j} = 1} C_{ij}) \circ J \in C^{r_{i}}$
  
  回顾下算符
  
  \circ
  
  $\circ$
  
  是右结合的，其中
  
  ∈
  
  C
  
  r
  
  i
  
  J \in \mathcal C^{r_i}
  
  $J \in C^{r_{i}}$
  
  是恒等置换
  
  r
  
  i
  
  I_{r_i}
  
  $I_{r_{i}}$
  
  的无噪声 HEPerm 密文。
- 解码运算
  
  ，转化为 equality test，即
  
  (
  
  x
  
  )
  
  =
  
  ∑
  
  v
  
  :
  
  f
  
  (
  
  v
  
  )
  
  =
  
  1
  
  [
  
  x
  
  =
  
  v
  
  ]
  
  ∈
  
  {
  
  0
  
  ,
  
  1
  
  }
  
  f(x) = \sum_{v:f(v)=1} [x=v] \in \{0,1\}
  
  $f (x) = \sum_{v : f (v) = 1} [x = v] \in {0, 1}$
  
  ，在对称群
  
  :
  
  =
  
  ∏
  
  i
  
  =
  
  1
  
  t
  
  S
  
  r
  
  i
  
  S:=\prod_{i=1}^t S_{r_i}
  
  $S := \prod_{i = 1}^{t} S_{r_{i}}$
  
  下的相等判定为
  
  ←
  
  ⊞
  
  v
  
  ∈
  
  [
  
  q
  
  ]
  
  s
  
  .
  
  t
  
  .
  
  f
  
  (
  
  v
  
  )
  
  =
  
  1
  
  (
  
  (
  
  ⊡
  
  i
  
  ∈
  
  [
  
  t
  
  ]
  
  E
  
  q
  
  (
  
  C
  
  i
  
  ,
  
  ϕ
  
  i
  
  (
  
  v
  
  )
  
  )
  
  )
  
  ⊡
  
  G
  
  )
  
  ∈
  
  C
  
  C \leftarrow \boxplus_{v \in [q]\, s.t.\, f(v)=1} \left(\left(\boxdot_{i \in [t]} Eq(C_i, \phi_i(v))\right) \boxdot G\right) \in \mathcal C
  
  $C \leftarrow ⊞_{v \in [q] s . t . f (v) = 1} ((⊡_{i \in [t]} Eq (C_{i}, ϕ_{i} (v))) ⊡ G) \in C$
  
  回顾下
  
  q
  
  (
  
  C
  
  π
  
  ,
  
  σ
  
  )
  
  ∈
  
  C
  
  Eq(C^\pi, \sigma) \in \mathcal C
  
  $Eq (C^{π}, σ) \in C$
  
  ，算符
  
  \boxdot
  
  $⊡$
  
  是右结合的，而
  
  G
  
  $G$
  
  是整数
  
  1
  
  $1$
  
  的无噪声 GSW 密文。

在自举之前，由于我们的 GSW 对密文格式有要求，因此需要对 LWE 密文做一些预处理，包括：

维度约减

、

模约减

、

二进制分解

。在自举结束后，选取 GSW 密文的倒数第二列作为 LWE 密文（GSW 密文就是由 LWE 密文组成的向量），并做

密钥切换

，从

sk

$s k$

下的 LWE 密文回到

s

$s$

下的 LWE 密文。

FHEW

2015 年，Ducas 等人提出了 FHEW 方案。与上述的 HEPerm 相似，FHEW 采用一个与原始 LWE 方案不同的加密方案，构造出一个

同态累加器

（Homomorphic Accumulator），然后用它来 refresh 密文。另外，FHEW 还提出了一种

新的 NAND 门

，只需要用到加法同态，而不需要乘法同态，噪声增长率较低。

一个重要发现是，实现 Bootstrapping 根本不需要完整的

比较电路

（同态地比较加密的明文是否大于某个阈值

q/2

$q /2$

以提取MSB信息），而只需要一个

同态累加器

，像AP14那样用一系列的判等操作来提取MSB，这就大大简化了自举的复杂度。

另外为了维持 NAND 门的输入密文形式，FHEW 使用的是

Gate Bootstrapping

（而非

Circuit Bootstrapping

），将NAND门输出的密文 refresh 为恰当的密文形式。

Notation

FHEW 定义了一个

randomized rounding

函数

→

\chi:\mathbb R \to \mathbb Z

$χ : R \to Z$

，对于任意的

∈

x \in \mathbb R

$x \in R$

和任意的

∈

n \in \mathbb Z

$n \in Z$

，都有

(

)

(

)

\chi(x+n) = \chi(x)+n

$χ (x + n) = χ (x) + n$

，其中

(

)

−

\chi(x)-x

$χ (x) - x$

叫做

(

)

\chi(x)

$χ (x)$

的

rounding error

。不知道本人理解的对不对，

(

)

\chi(x)

$χ (x)$

是一族关于实数

x

$x$

的噪声分布，对于每个固定的

x

$x$

都有一个固定的分布

(

)

\chi(x \pmod 1)

$χ (x (mod 1))$

；特别当

∈

x \in \mathbb Z

$x \in Z$

时，对应于

(

)

\chi(0)

$χ (0)$

。

我们说实数域

\mathbb R

$R$

上的

随机变量

X

$X$

是参数

\alpha>0

$α > 0$

的

亚高斯

（subgaussian），如果对于任意的

∈

t \in \mathbb R

$t \in R$

都满足

[

exp

⁡

(

)

]

≤

(

)

E[\exp(2\pi tX)] \le exp(\pi \alpha^2 t^2)

$E [exp (2 π tX)] \leq e x p (π α^{2} t^{2})$

进一步地，它的尾部（tail）满足

[

∣

≥

]

≤

exp

⁡

(

−

)

∀

≥

Pr[|X| \ge t] \le 2\exp(-\pi t^2/\alpha^2),\forall t \ge 0

$P r [∣ X ∣ \geq t] \leq 2 exp (- π t^{2} / α^{2}), \forall t \geq 0$

所有的

–

B\text{ -}

$B -$

bounded 对称随机变量

X

$X$

都是参数

B \sqrt{2\pi}

$B 2 π$

的亚高斯。扩展到

随机向量

\bf x

$x$

，如果它的所有 one-dimensional marginals

⟩

\bf \langle u,x \rangle

$⟨ u, x ⟩$

（其中

\bf u

$u$

是单位向量）是参数

\alpha

$α$

的亚高斯。扩展到

随机矩阵

\bf X

$X$

，如果它的所有 one-dimensional marginals

\bf u^tXv

$u^{t} Xv$

（其中

\bf u,v

$u, v$

是单位向量）是参数

\alpha

$α$

的亚高斯。

对于

2

$2$

的幂次

N

$N$

，

(

)

\Phi_{2N}(X)=X^N+1

$Φ_{2 N} (X) = X^{N} + 1$

是分园多项式（cyclotomic

polynomial）。令

[

]

(

)

R = \mathbb Z[X]/(X^N+1)

$R = Z [X] / (X^{N} + 1)$

是分园环（cyclotomic ring），对应的商环

R_q=R/qR

$R_{q} = R / qR$

。对于

⋯

−

∈

a=a_0 + a_1x + \cdots + a_{N-1}x^{N-1} \in R

$a = a_{0} + a_{1} x + \dots + a_{N - 1} x^{N - 1} \in R$

，简记

⃗

[

⋮

−

]

∈

⇒

[

−

⋯

−

⋯

−

⋮

⋯

⋮

−

⋯

]

∈

\vec a := \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{N-1} \end{bmatrix} \in \mathbb Z^N,\, \mathop{a}\limits^{\Rightarrow} := \begin{bmatrix} a_0 & -a_{N-1} & \cdots & -a_1\\ a_1 & a_0 & \cdots & -a_2\\ \vdots & \vdots & \cdots & \vdots\\ a_{N-1} & a_{N-2} & \cdots & a_{0} \end{bmatrix} \in \mathbb Z^{N \times N}

$a := a_{0} a_{1} ⋮ a_{N - 1} \in Z^{N}, a \Rightarrow := a_{0} a_{1} ⋮ a_{N - 1} - a_{N - 1} a_{0} ⋮ a_{N - 2} \dots \dots \dots \dots - a_{1} - a_{2} ⋮ a_{0} \in Z^{N \times N}$

其实

⇒

⋅

⃗

⋅

→

\mathop{a}\limits^{\Rightarrow} \cdot \vec b = \overrightarrow{a \cdot b}

$a \Rightarrow \cdot b = a \cdot b$

，这就是环

R

$R$

上的多项式乘积罢了（文章中使用的全是矩阵乘，却不使用多项式乘积）。扩展到向量和矩阵，对于

∈

A \in R^{w \times k}

$A \in R^{w \times k}$

，令

⇒

∈

\mathop{A}\limits^{\Rightarrow} \in \mathbb Z^{wN \times kN}

$A \Rightarrow \in Z^{wN \times k N}$

就是对于每个 entry 单独地应用

⇒

\mathop{\cdot}\limits^{\Rightarrow}

$\cdot \Rightarrow$

算符。我们说一个

随机多项式

∈

a \in R

$a \in R$

是亚高斯的，如果

⃗

\vec a

$a$

是亚高斯的随机向量。

LWE Symmetric Encryption

我们描述一个基于 LWE 的对称加密方案，它可以用标准的转化技术得到非对称加密。秘钥

∈

(

)

s \in \mathbb Z_q^n,q=n^{O(1)}

$s \in Z_{q}^{n}, q = n^{O (1)}$

，消息

∈

≥

m \in \mathbb Z_t,t \ge 2

$m \in Z_{t}, t \geq 2$

，随机园整函数满足

(

)

−

∣

|\chi(x)-x| < q/2t

$∣ χ (x) - x ∣ < q /2 t$

对称加密方案

：

加密，
$LWE_s^{t/q}(m) := (a,\chi(as+mq/t) \pmod q) \in \mathbb Z_q^{n+1} L W E s t / q ( m ) := ( a , χ ( a s + m q / t ) ( mod q )) ∈ Z q n + 1 ，其中 a ∈ Z q n a \in \mathbb Z_q^n a ∈ Z q n 是均匀随机的$
解密，输入密文
$\leftarrow \lfloor t(b-as)/q \rceil \pmod t \in \mathbb Z_t m ′ ← ⌊ t ( b − a s ) / q ⌉ ( mod t ) ∈ Z t $

Modulus Switching

，从模数

Q

$Q$

到模数

q

$q$

的 (scaled) randomized rounding function

⋅

]

→

[\cdot]_{Q:q}:\mathbb Z_Q \to \mathbb Z_q

$[\cdot]_{Q : q} : Z_{Q} \to Z_{q}$

定义为

]

⌊

⌋

[x]_{Q:q} := \lfloor qx/Q \rfloor + B

$[x]_{Q : q} := ⌊ q x / Q ⌋ + B$

其中

∈

{

}

B \in \{0,1\}

$B \in {0, 1}$

是服从

[

]

−

⌊

⌋

Pr[B=1]=qx/Q-\lfloor qx/Q \rfloor

$P r [B = 1] = q x / Q - ⌊ q x / Q ⌋$

的二值分布，容易看出

(

[

]

)

E([x]_{Q:q})=qx/Q

$E ([x]_{Q : q}) = q x / Q$

，并且园整错误

]

−

[x]_{Q:q}-qx/Q

$[x]_{Q : q} - q x / Q$

是参数

\sqrt{2\pi}

$2 π$

的亚高斯。对于

)

∈

(

)

(a,b) \in LWE_z^{t/q}(m)

$(a, b) \in L W E_{z}^{t / q} (m)$

，计算模

q

$q$

下的新密文

(

)

(

[

]

)

[

]

)

ModSwitch(a,b) := (\left([a_i]_{Q:q}\right)_i,[b]_{Q:q})

$M o d Sw i t c h (a, b) := (([a_{i}]_{Q : q})_{i}, [b]_{Q : q})$

Key Switching

，设置 base 为

B_{ks}

$B_{k s}$

，从密钥

∈

z \in \mathbb Z_q^N

$z \in Z_{q}^{N}$

到密钥

∈

s \in \mathbb Z_q^N

$s \in Z_{q}^{N}$

的 switching key

{

}

\mathfrak R := \{k_{ijv}\}

$R := {k_{ij v}}$

定义为

←

(

)

⋯

−

⋯

−

k_{ijv} \leftarrow LWE_s^{q/q}(vz_iB_{ks}^j),\, i = 1,\cdots,N,\, j=0,\cdots,d_{ks}-1,\, v =0,\cdots,B_{ks}-1

$k_{ij v} \leftarrow L W E_{s}^{q / q} (v z_{i} B_{k s}^{j}), i = 1, \dots, N, j = 0, \dots, d_{k s} - 1, v = 0, \dots, B_{k s} - 1$

其中

⌈

log

⁡

⌉

d_{ks} = \lceil \log_{B_{ks}}q \rceil

$d_{k s} = ⌈ lo g_{B_{k s}} q ⌉$

，并且

t=q

$t = q$

使得

k_{ijv}

$k_{ij v}$

是噪声比率为

1/2

$1/2$

的 not typically decryptable 的密文。对于

)

∈

(

)

(a,b) \in LWE_z^{t/q}(m)

$(a, b) \in L W E_{z}^{t / q} (m)$

，首先做分解

∑

a_i = \sum_j a_{ij} B_{ks}^j

$a_{i} = \sum_{j} a_{ij} B_{k s}^{j}$

，然后计算

s

$s$

下的新密文

(

)

(

)

−

∑

KeySwitch\left((a,b),\mathfrak R\right) := (0,b) – \sum_{i,j} k_{i,j,a_{ij}}

$Key Sw i t c h ((a, b), R) := (0, b) - i, j \sum k_{i, j, a_{ij}}$

可以验证

′

−

′

−

b’=b-az+a’s-E

$b^{'} = b - a z + a^{'} s - E$

，从而

′

−

′

≈

−

≈

b’-a’s \approx b-az \approx mq/t

$b^{'} - a^{'} s \approx b - a z \approx m q / t$

，前后两者加密了同一个明文。

NAND Gate

本文提出了一种新的 NAND 计算方式。思路是，用

\mathbb Z

$Z$

上的

仿射变换来拟合

NAND 运算：

$m_0 m 0 $	$m_1 m 1 $	$m_0+m_1 m 0 + m 1 $	$\dfrac{5}{4}-\dfrac{1}{2}(m_0+m_1) 4 5 − 2 1 ( m 0 + m 1 )$

只需要在就近取整，就可以得到

∧

m_0 \bar\wedge m_1

$m_{0} \overset{ˉ}{\land} m_{1}$

的结果了。将明文空间

\mathbb Z_t

$Z_{t}$

设置为

t=4

$t = 4$

，并设置一个更小的错误界

E = q/16

$E = q /16$

，那么对于

∈

{

}

m_i \in \{0,1\}

$m_{i} \in {0, 1}$

，计算密文

∈

(

)

c_i \in LWE_s^{4/q}(m_i,q/16)

$c_{i} \in L W E_{s}^{4/ q} (m_{i}, q /16)$

，另外计算无噪声密文

)

∈

(

)

(0,\dfrac{5q}{8}) \in LWE_s^{2/q}(\dfrac{5}{4},0)

$(0, \frac{5 q}{8}) \in L W E_{s}^{2/ q} (\frac{5}{4}, 0)$

，并将

(

)

LWE_s^{4/q}(m_i,q/16)

$L W E_{s}^{4/ q} (m_{i}, q /16)$

视为

(

)

LWE_s^{2/q}(\dfrac{1}{2}m_i,q/16)

$L W E_{s}^{2/ q} (\frac{1}{2} m_{i}, q /16)$

计算

∧

−

⌊

−

(

)

⌉

m_0 \bar\wedge m_1 = 1-m_0m_1 = \left\lfloor \dfrac{5}{4}-\dfrac{1}{2}(m_0+m_1) \right\rceil

$m_{0} \overset{ˉ}{\land} m_{1} = 1 - m_{0} m_{1} = ⌊ \frac{5}{4} - \frac{1}{2} (m_{0} + m_{1}) ⌉$

的同态与非门：

(

)

(

)

→

(

∧

)

(

)

←

(

)

(

)

(

−

)

HomNAND: LWE_s^{4/q}(m_0,q/16) \times LWE_s^{4/q}(m_1,q/16) \to LWE_s^{2/q}(m_0 \bar\wedge m_1,q/4)\\ (a,b) \leftarrow HomNAND((a_0,b_0),\, (a_1,b_1)) := (-a_0-a_1,\, \dfrac{5q}{8}-b_0-b_1)

$Ho m N A N D : L W E_{s}^{4/ q} (m_{0}, q /16) \times L W E_{s}^{4/ q} (m_{1}, q /16) \to L W E_{s}^{2/ q} (m_{0} \overset{ˉ}{\land} m_{1}, q /4) (a, b) \leftarrow Ho m N A N D ((a_{0}, b_{0}), (a_{1}, b_{1})) := (- a_{0} - a_{1}, \frac{5 q}{8} - b_{0} - b_{1})$

于是

NAND 门只需要同态加法

，不需要采用同态乘法，因此输入密文的噪声界从以前的

(

)

O(\sqrt q)

$O (q)$

扩大到了

(

)

O(q)

$O (q)$

。可以验证，

−

(

−

)

−

(

−

)

(

−

(

)

−

(

)

(

∧

)

−

(

)

(

∧

)

−

(

)

\begin{aligned} b-as &= \dfrac{5q}{8} – (b_0-a_0s) – (b_1-a_1s)\\ &= \dfrac{q}{2}\left(\dfrac{5}{4}-\dfrac{1}{2}(m_0+m_1)\right) – (e_0+e_1)\\ &= \dfrac{q}{2}\left(m_0 \bar\wedge m_1 \pm \dfrac{1}{4}\right) – (e_0+e_1)\\ &= \dfrac{q}{2}\left(m_0 \bar\wedge m_1\right) \pm \dfrac{q}{8} – (e_0+e_1)\\ \end{aligned}

$b - a s = \frac{5 q}{8} - (b_{0} - a_{0} s) - (b_{1} - a_{1} s) = \frac{q}{2} (\frac{5}{4} - \frac{1}{2} (m_{0} + m_{1})) - (e_{0} + e_{1}) = \frac{q}{2} (m_{0} \overset{ˉ}{\land} m_{1} \pm \frac{1}{4}) - (e_{0} + e_{1}) = \frac{q}{2} (m_{0} \overset{ˉ}{\land} m_{1}) \pm \frac{q}{8} - (e_{0} + e_{1})$

噪声

−

(

)

∣

|\dfrac{q}{8} – (e_0+e_1)| < \dfrac{q}{8} + 2 \times \dfrac{q}{16} = \dfrac{q}{4}

$∣ \frac{q}{8} - (e_{0} + e_{1}) ∣ < \frac{q}{8} + 2 \times \frac{q}{16} = \frac{q}{4}$

，因此可以正确解密。

为了继续进行 NAND 运算，我们需要一个刷新函数：

(

)

→

(

)

Refresh:\, LWE_s^{2/q}(m,q/4) \to LWE_s^{4/q}(m,q/16)

$R e f res h : L W E_{s}^{2/ q} (m, q /4) \to L W E_{s}^{4/ q} (m, q /16)$

这个函数就是 Bootstrapping 的作用，每次 NAND 计算后都立刻刷新密文，因此计算瓶颈在 Refresh 上。

Homomorphic Accumulator

FHEW 选取一个可以与 LWE 加密方案不同的另一个加密方案

(

⋅

)

E(\cdot)

$E (\cdot)$

，要求它对于

)

∈

(

)

(a,b) \in LWE_s^{2/q}(m)

$(a, b) \in L W E_{s}^{2/ q} (m)$

满足如下运算关系

(

−

⋅

(

)

⌉

(

)

(

)

\left\lfloor \dfrac{2}{q}(b-a \cdot E(s))\right\rceil \pmod 2 = E(m)

$⌊ \frac{2}{q} (b - a \cdot E (s)) ⌉ (mod 2) = E (m)$

关键是计算

−

⋅

(

)

(

−

⋅

)

b-a \cdot E(s) = E(b-a \cdot s)

$b - a \cdot E (s) = E (b - a \cdot s)$

，这只是密文的同态数乘，可以被视为一些密文的加法。方案

E

$E$

被用来构造

同态累加器

（Homomorphic Accumulator），它是一个算法四元组

)

(E,Init,Incr,msbExtract)

$(E, I ni t, I n cr, m s b E x t r a c t)$

，

$\mathcal C C 可以与 L W E s t / q LWE_s^{t/q} L W E s t / q 不同。$
$\leftarrow Init(v_0) A CC ← I ni t ( v 0 ) 简记为 A C C ← v 0 ACC \leftarrow v_0 A CC ← v 0 $
$\leftarrow Incr(ACC,E(v_i)) A CC ← I n cr ( A CC , E ( v i )) 简记为 A C C ← + E ( v i ) ACC \overset{+}{\leftarrow} E(v_i) A CC ← + E ( v i ) ，其中 i = 1 , ⋯ , l i=1,\cdots,l i = 1 , ⋯ , l$
$\leftarrow msbExtract(ACC) c ← m s b E x t r a c t ( A CC )$

我们说这个同态累加器是

– correct

\mathcal E\text{ – correct}

$E - correct$

的，如果

∉

(

∑

(

)

c \notin LWE_s^{t/q}(\sum_i v_i, \mathcal E(l))

$c \in / L W E_{s}^{t / q} (\sum_{i} v_{i}, E (l))$

的概率可忽略。对于

t=4

$t = 4$

，要求

(

)

≤

\mathcal E(l) \le q/16

$E (l) \leq q /16$

然后利用上述的同态累加器，可以实现 refresh 函数。首先预计算

refreshing key

{

}

\mathcal K := \{K_{ijc}\}

$K := {K_{ij c}}$

，

(

)

⋯

−

⋯

−

K_{ijc} := E(cs_iB_r^j \pmod q),\, i = 1,\cdots,n,\, j=0,\cdots,d_{r}-1,\, c =0,\cdots,B_{r}-1

$K_{ij c} := E (c s_{i} B_{r}^{j} (mod q)), i = 1, \dots, n, j = 0, \dots, d_{r} - 1, c = 0, \dots, B_{r} - 1$

其中

⌈

log

⁡

⌉

d_{r} = \lceil \log_{B_{r}}q \rceil

$d_{r} = ⌈ lo g_{B_{r}} q ⌉$

，这儿的 LWE 密钥

∈

s \in \mathbb Z_q^n

$s \in Z_{q}^{n}$

的各个系数被 power 为

)

(s_i B_r^j)_j

$(s_{i} B_{r}^{j})_{j}$

，然后枚举了所有的

B_r

$B_{r}$

进制下的所有取值。由于

(

)

⋅

(

)

⋅

Decompose(a_i) \cdot Power(s_i) = a_i \cdot s_i

$Deco m p ose (a_{i}) \cdot P o w er (s_{i}) = a_{i} \cdot s_{i}$

，因此可以根据

∑

a_i = \sum_j a_{ij} B_r^j

$a_{i} = \sum_{j} a_{ij} B_{r}^{j}$

挑选出对应的

K_{i,j,a_{ij}}

$K_{i, j, a_{ij}}$

计算同态加法。

在这里插入图片描述

初始化

b+q/4

$b + q /4$

，这使得循环末尾

−

⋅

(

)

v = q/4 + b-a \cdot s = mq/2 + (e+q/4)

$v = q /4 + b - a \cdot s = m q /2 + (e + q /4)$

由于

∣

|e|<q/4

$∣ e ∣ < q /4$

，因此

′

∈

(

)

e’=e+q/4 \in (0,q/2)

$e^{'} = e + q /4 \in (0, q /2)$

，如果

∈

(

)

v \in (0,q/2)

$v \in (0, q /2)$

那么

m=0

$m = 0$

，如果

∈

(

)

v \in (q/2,q)

$v \in (q /2, q)$

那么

m=1

$m = 1$

，这就把

提取

−

a

s

b-as

$b - a s$

的 MSB 转化为了测试

v

$v$

的范围

（与 HEPerm 类似）。

FHEW 使用 Ring-GSW 来实例化同态累加器。LWE 的模数

q=2^k

$q = 2^{k}$

，消息域大小

t=4

$t = 4$

。GSW 的模数

Q

$Q$

满足

Q=B_g^{d_g}

$Q = B_{g}^{d_{g}}$

，其中 base

B_g

$B_{g}$

是

3

$3$

的幂次（这使得

≥

(

−

)

(

−

)

\forall K \ge 3,N=2^K,X^N+1 = (X^{N/2}+X^{N/4}-1) (X^{N/2}-X^{N/4}-1)

$\forall K \geq 3, N = 2^{K}, X^{N} + 1 = (X^{N /2} + X^{N /4} - 1) (X^{N /2} - X^{N /4} - 1)$

，从而

R_Q

$R_{Q}$

几乎是一个域）。额外设置一个参数

⌊

⌋

u = \lfloor Q/2t \rfloor

$u = ⌊ Q /2 t ⌋$

或者

⌈

⌉

u = \lceil Q/2t \rceil

$u = ⌈ Q /2 t ⌉$

，它们在

\mathbb Z_Q

$Z_{Q}$

中是可逆的，且误差

−

∣

|u-Q/2t|<1

$∣ u - Q /2 t ∣ < 1$

。

设置环

[

]

(

)

R = \mathbb Z[X]/(X^N+1)

$R = Z [X] / (X^{N} + 1)$

，使得

∣

q\mid 2N

$q ∣ 2 N$

，那么它有

q

$q$

次本原单位根

Y := X^{2N/q}

$Y := X^{2 N / q}$

，因此

≅

⟨

⟩

\mathbb Z_q \cong \langle Y \rangle

$Z_{q} ≅ ⟨ Y ⟩$

是单位根循环群

⟨

⟩

≅

G = \langle X \rangle \cong \mathbb Z_{2N}

$G = ⟨ X ⟩ ≅ Z_{2 N}$

的子循环群。消息

∈

m \in \mathbb Z_q

$m \in Z_{q}$

可以

直接编码到指数上

为

∈

Y^m \in R

$Y^{m} \in R$

，其向量表示为

−

}

\{-1,0,1\}^N

${- 1, 0, 1}^{N}$

上的 one-hot 向量。为了提取

m

$m$

的 MSB，我们构造一个

testing vector

−

∑

−

⃗

∈

{

−

}

t := – \sum_{v=1}^{q/2-1} \vec Y^v \in \{-1,0,1\}^N

$t := - v = 1 \sum q /2 - 1 Y^{v} \in {- 1, 0, 1}^{N}$

如果

≤

0 \le m < N

$0 \leq m < N$

那么

⋅

⃗

−

t \cdot \vec Y^m = -1

$t \cdot Y^{m} = - 1$

，如果

≤

N \le m < 2N

$N \leq m < 2 N$

那么

⋅

⃗

t \cdot \vec Y^m = +1

$t \cdot Y^{m} = + 1$

，这其实就是挨个测试了

(

)

∀

(

)

Eq(m,v),\forall MSB(v)=0

$Eq (m, v), \forall MSB (v) = 0$

。为了将它们变换回

0/1

$0/1$

，观察到

⋅

-1 \cdot u + u = 0 \cdot Q/t

$- 1 \cdot u + u = 0 \cdot Q / t$

，

⋅

+1 \cdot u + u = 1 \cdot Q/t

$+ 1 \cdot u + u = 1 \cdot Q / t$

，因此只要在将 GSW 密文的明文空间设为

Z_{2t}

$Z_{2 t}$

（RLWE 就是对于多项式

Y^v

$Y^{v}$

的每个系数分别执行 LWE 加密），最后做一个偏移

u

$u$

就把

∈

\pm 1 \in Z_{2t}

$\pm 1 \in Z_{2 t}$

变换为了

∈

0/1 \in Z_t

$0/1 \in Z_{t}$

的 LWE 密文。

FHEW 的基于 RGSW 的同态累加器（密文的形状略微复杂，竖长，它是若干 RLWE 密文的组合）：

在这里插入图片描述

由于

GSW 密文就是由 LWE 密文组成的向量

，因此提取 MSB 对应的 LWE 密文，就是挑选出对应的列向量：

在这里插入图片描述

Refresh 的主要的计算量集中在累加阶段，可以用 FFT/NTT 来加速：

在这里插入图片描述

原文链接：https://blog.csdn.net/weixin_44885334/article/details/129380618

文章目录

AP14

Embedding

GSW

HEPerm

Bootstrapping

FHEW

Notation

LWE Symmetric Encryption

NAND Gate

Homomorphic Accumulator

你可能也喜欢