优化GSW-FHE中的引导过程与评估大型全同态加密门

### 优化GSW - FHE中的引导过程与评估大型全同态加密门 #### 1. 引导过程概述 引导的目标是对密文进行同态解密。对于在密钥 $s \in Z_q^n$ 下的LWE密文 $(a, b) \in Z_q^{n + 1}$，通过计算 $\tilde{m} = LWE^{-1}_s(a, b) = f([b - \langle a, s \rangle]_q) = [\lfloor \frac{t}{q} \cdot [b - \langle a, s \rangle]_q \rceil]_t$ 来解密。同态解密大噪声密文可以得到噪声更小的新密文。由于解密密文需要密钥 $s$ 的信息，因此需要使用加密算法 $Enc()$ 生成引导密钥 $Enc(s)$。在本文方案中，$Enc()$ 为MatGSW加密。 同态解密有两个过程： - 线性操作：$b - \langle a, s \rangle = b - \sum_{i} a_is_i$。 - 非线性操作：即舍入操作 $f : Z_q \to Z_t$。 线性操作可通过迭代执行引理5中描述的同态矩阵 - 向量乘法来计算，非线性操作可通过消息向量的“循环旋转”属性自动执行。实际上，还可以在 $\tilde{m} \in Z_t$ 上进一步评估已知的任意函数 $func : Z_t \to Z_h$，因此通常可定义 $F = func \circ f$ 作为最终的非线性步骤。 引导过程包括两个步骤： - $BootKeyGen(SK, s)$：输入MatGSW加密的密钥 $SK$ 和待引导密文的密钥向量 $s \in Z_q^n$，输出在 $SK$ 下对 $s$ 进行适当加密的引导密钥 $BootKey$。 - $Bootstrap(BootKey, c)$：输入引导密钥 $BootKey$ 和密文向量 $c = (a, b) \in Z_q^{n + 1}$，该密文在密钥 $s$ 下解密为 $\tilde{m} \in Z_t$，输出在密钥 $sk_1$（噪声更小）下解密为 $F(\tilde{m}) \in Z_h$ 的LWE密文，其中 $sk_1$ 是 $SK$ 的第一行。 #### 2. 具体过程 在本方案中，$Q$ 是一个模，$l = \lceil \log_2 Q \rceil$，$N$ 是MatGSW加密的显式随机向量的维度，消息维度为 $q \times q$，即密文 $MatGSW \in Z_Q^{(N + q) \times (N + q) \cdot l}$。设 $w = \lceil \log_2 q \rceil$，$\varphi : Z_q \to S_q$ 是 $Z_q$ 中元素到对应循环置换的同构。本方案遵循基于RLWE的FHEW和TFHE方案的结构，包括两个算法：$BootKeyGen$ 和 $Bootstrap$，其中 $Bootstrap$ 包含三个步骤。 ##### 2.1 BootKeyGen(SK, s) 对于每个 $i \in [n]$ 和 $k \in [w]$，设 $M_{\varphi([2^{k - 1}s_i]_q)} \in \{0, 1\}^{q \times q}$ 是对应于 $\varphi([2^{k - 1}s_i]_q)$ 的矩阵，并计算： $BK_{i,k} = MatGSW_{SK}(M_{\varphi([2^{k - 1}s_i]_q)}) \in Z_Q^{(N + q) \times (N + q) \cdot l}$ 令 $BootKey = \{BK_{i,k}\}_{i \in [n], k \in [w]}$ 并返回 $BootKey$。 ##### 2.2 Bootstrap(BootKey, c) - **初始化（Initialize）**：对于每个 $i \in [q]$，设置 $m_i = \Delta' \cdot F([b - i + 1]_q) = \Delta' \cdot func(f([b - i + 1]_q)) \in Z_Q$ 其中 $f : Z_q \to Z_t$ 是舍入函数，$func : Z_t \to Z_h$ 是已知的任意函数，$\Delta' = \lfloor \frac{Q}{h} \rfloor$。设置 $acc := (0, m) \in Z_Q^{N + q}$，其中 $m = (m_1, \ldots, m_q)$。 - **增量（Increment）**：对于每个 $i \in [n]$ 和 $k \in [w]$，令 $a'_i = -a_i \bmod q$，并设置 $z_{i,k} = \lfloor \frac{a'_i}{2^{k - 1}} \rfloor \bmod 2$。然后对于每个 $i \in [n]$ 和 $k \in [w]$，如果 $z_{i,k} > 0$，则迭代计算 $acc \leftarrow BK_{i,k} \diamond acc$。 - **提取（Extract）**：如果最终密文为 $acc = (a', b' = (b'_1, \ldots, b'_q))$，则返回 $(a', b'_1)$。 对于最终密文，可以使用模块切换将模从 $Q$ 降回 $q$，并使用密钥切换将输出转换为在 $s$ 下的LWE加密，然后可以对该密文执行额外的操作。 #### 3. 正确性 有以下引理： **引理6（正确性）**：设 $SK$ 是本方案的密钥，$sk_1$ 是 $SK$ 的第一行。设 $c$ 和 $s$ 是本方案中描述的密文和密钥。假设密文 $c$ 在密钥 $s$ 下解密为 $\tilde{m} \in Z_t$。对于 $BootKey \leftarrow BootKeyGen(SK, s)$，刷新后的密文 $c' \leftarrow Bootstrap(BootKey, c)$ 在密钥 $sk_1$ 下解密为 $func(\tilde{m}) \in Z_h$，其中 $func : Z_t \to Z_h$ 是已知的任意函数。 还对 $Bootstrap$ 输出的密文中的误差进行了量化： **引理7**：对于任何 $c \in Z_q^{n + 1}$，刷新后的密文