TFHE-rs repo

TFHE-rs深度解析之三：密文操作和可编程自举

Chuck Chen
 · 
分类： [密码学]
标签： #全同态加密 #隐私保护 #TFHE
TFHE-rs系列

有限级密文操作

TFHE 支持在密文上直接进行线性运算（加法、减法、常数乘法），这些操作被称为“有限级（Leveled）”操作，因为它们不需要自举（Bootstrapping），但会增加密文中的噪声。

密文加法 (GLWE 同态加法)

给定两个分别加密消息 MM 和 M′M' 的 GLWE 密文 CC 和 C′C'（使用相同的密钥 S⃗\vec{S}），它们的同态加法可以通过将两个密文的对应分量相加来完成。结果密文 C⊞C^{\boxplus} 加密了和 M+M′M + M'，密钥保持不变，但噪声水平会增加（两个输入密文噪声之和）。

数学表达如下：

C⊞=C+C′=(A0+A0′,…,Ak−1+Ak−1′,B+B′)∈GLWES⃗(Δ(M+M′))\begin{align*} C^{\boxplus} =& C + C' \\ =& (A_0 + A'_0, \dots, A_{k-1} + A'_{k-1}, B + B') \in \mathsf{GLWE}_{\vec{S}}(\Delta(M + M')) \end{align*}

简化示例（GLWE 同态加法）

假设参数为：q=64,p=4q = 64, p = 4 (即 Δ=16\Delta = 16), N=4,k=2N = 4, k = 2。 密钥 S⃗=(X+X2,1+X2+X3)\vec{S} = (X + X^2, 1 + X^2 + X^3)。

两个消息分别为：

M=−2+X−X3M′=X+X2−2X3M = -2 + X - X^3 \\ M' = X + X^2 - 2X^3

它们的和为

M⊞=M+M′=−2−2X+X2+X3∈RqM^{\boxplus} = M + M' = -2 - 2X + X^2 + X^3 \in \mathcal{R}_q

假设加密后的密文分量如下（包含噪声）：

  • C=(A0,A1,B)C = (A_0, A_1, B)，其中

    A0=17−2X−24X2+9X3A1=−14−X2+21X3B=−31+5X−21X2+30X3\begin{align*} A_0 &= 17 - 2X - 24X^2 + 9X^3 \\ A_1 &= -14 - X^2 + 21X^3 \\ B &= -31 + 5X - 21X^2 + 30X^3 \end{align*}

  • C′=(A0′,A1′,B′)C' = (A'_0, A'_1, B')，其中

    A0′=−8+15X+3X2−30X3A1′=23−16X+27X2−4X3B′=−25+12X2−12X3\begin{align*} A'_0 &= -8 + 15X + 3X^2 - 30X^3 \\ A'_1 &= 23 - 16X + 27X^2 - 4X^3 \\ B' &= -25 + 12X^2 - 12X^3 \end{align*}

  • 最终得到的密文C⊞=(A0⊞,A1⊞,B⊞)C^{\boxplus} = (A_0^{\boxplus}, A_1^{\boxplus}, B^{\boxplus})。密文加法操作即对应多项式的加法：

    A0⊞=A0+A0′=9+13X−21X2−21X3A1⊞=A1+A1′=9−16X+26X2+17X3B⊞=B+B′=8+5X−9X2+18X3\begin{aligned} A_0^{\boxplus} &= A_0 + A'_0 = 9 + 13X - 21X^2 - 21X^3 \\ A_1^{\boxplus} &= A_1 + A'_1 = 9 - 16X + 26X^2 + 17X^3 \\ B^{\boxplus} &= B + B' = 8 + 5X - 9X^2 + 18X^3 \end{aligned}

    解密后即为 M⊞M^{\boxplus}。

密文乘法 (GLWE 同态标量乘法)

注意：这里的“乘法”特指密文与一个已知的“小”常数多项式（或整数）相乘。如果是两个密文相乘，通常涉及更复杂的外部积（External Product）或需要自举。

给定 GLWE 密文 CC 和一个小常数多项式 Λ\Lambda，同态乘法是将密文的每个分量都乘以 Λ\Lambda。结果 C⋅C^{\cdot} 是加密了积 Λ⋅M\Lambda \cdot M 的新密文。噪声方差会随着 Λ\Lambda 系数的大小放大。

数学表达如下：

C⊠=Λ⋅C=(Λ⋅A0,…,Λ⋅Ak−1,Λ⋅B)C^{\boxtimes} = \Lambda \cdot C = (\Lambda \cdot A_0, \dots, \Lambda \cdot A_{k-1}, \Lambda \cdot B)

简化示例（GLWE 同态标量乘法）

沿用上述参数和密文 CC。我们选择一个小常数多项式 Λ=−1+2X2+X3\Lambda = -1 + 2X^2 + X^3。 我们的目标是计算积 M⊠=Λ⋅M=1+X+X2+X3M^{\boxtimes} = \Lambda \cdot M = 1 + X + X^2 + X^3。

运算过程如下（多项式乘法在模 XN+1X^N+1 下进行）：

A0⊠=Λ⋅A0=(−1+2X2+X3)⋅(17−2X−24X2+9X3)=−31+8X−15X2+4X3A1⊠=Λ⋅A1=(−1+2X2+X3)⋅(−14−X2+21X3)=16+23X+16X2+29X3B⊠=Λ⋅B=(−1+2X2+X3)⋅(−31+5X−21X2+30X3)=4+20X−7X2+13X3\begin{aligned} A_0^{\boxtimes} = \Lambda \cdot A_0 &= (-1 + 2X^2 + X^3) \cdot (17 - 2X - 24X^2 + 9X^3) \\ &= -31 + 8X - 15X^2 + 4X^3 \\ A_1^{\boxtimes} = \Lambda \cdot A_1 &= (-1 + 2X^2 + X^3) \cdot (-14 - X^2 + 21X^3) \\ &= 16 + 23X + 16X^2 + 29X^3 \\ B^{\boxtimes} = \Lambda \cdot B &= (-1 + 2X^2 + X^3) \cdot (-31 + 5X - 21X^2 + 30X^3) \\ &= 4 + 20X - 7X^2 + 13X^3 \end{aligned}

密钥切换 (Key Switching)

密钥切换（Key Switching）是所有基于 (R)LWE 的同态加密方案中的核心操作。它的目标是将一个在一个密钥 S⃗\vec{S} 下加密的密文，同态地转换为在另一个密钥 S⃗′\vec{S}' 下加密同一消息的密文。

原理解析

给定一个 GLWE 密文 C=(A0,…,Ak−1,B)C = (A_0, \dots, A_{k-1}, B)，它在密钥 S⃗\vec{S} 下加密了消息 MM。根据定义：

B−∑i=0k−1Ai⋅Si≈ΔMB - \sum_{i=0}^{k-1} A_i \cdot S_i \approx \Delta M

密钥切换的核心思想是“同态地”计算上述解密公式。具体来说，我们保留 BB（常数项），并试图减去 ∑Ai⋅Si\sum A_i \cdot S_i。由于我们不能直接知道 SiS_i，我们需要提供 SiS_i 在新密钥 S⃗′\vec{S}' 下的加密版本，称为密钥切换密钥 (Key Switching Key, KSK)。

利用前面提到的密文与常数乘法（这里 AiA_i 视为常数，SiS_i 的密文视为密文），我们可以计算出 ∑Ai⋅Si\sum A_i \cdot S_i 的密文，然后从 BB 中减去它。

数学公式

假设 KSK 包含了旧密钥分量 SiS_i 在新密钥 S⃗′\vec{S}' 下的 GLev 加密（GLev 是 GLWE 的一种分解形式，类似于 GGSW 之于 RLWE，用于控制噪声增长）。

KSKi∈GLevS⃗′(Si)\mathsf{KSK}_i \in \text{GLev}_{\vec{S}'}(S_i)

密钥切换操作如下：

C′=(0,…,0,B)−∑i=0k−1⟨Decomp(Ai),KSKi⟩C' = (0, \dots, 0, B) - \sum_{i=0}^{k-1} \langle \mathsf{Decomp}(A_i), \mathsf{KSK}_i \rangle

其中 ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle 表示分解后的向量与 GLev 密文向量的内积（本质上是外部积的变体）。 结果 C′C' 即为在新密钥 S⃗′\vec{S}' 下加密 MM 的 GLWE 密文。

应用场景

密钥切换不仅用于更改密钥，还常用于：

  1. 参数切换：从一组 LWE 参数（如大维度、小模数）切换到另一组（如小维度、大模数）。
  2. LWE 到 RLWE 转换：将 LWE 密文“打包”进 RLWE 密文的系数中。
  3. 自举的最后一步：在 TFHE 自举中，盲旋转后的密文通常具有较大的 LWE 维度（由 RLWE 维度决定），需要通过密钥切换转换回原始的 LWE 维度，以便进行下一轮运算。

有限级密文乘法与外部积

在全同态加密中，两个密文直接相乘通常会导致噪声呈现“二次方”增长，这会迅速消耗噪声预算并导致解密失败。为了解决这个问题，TFHE 引入了 外部积 (External Product) 的概念。

外部积的概念

外部积是一种非对称的乘法运算，记为 ⊡\boxdot。它涉及两种不同类型的密文：

  1. GGSW 密文 CGGSWC_{GGSW}：通常加密一个“小”整数或多项式（例如密钥位或控制位）。这种密文结构较大，包含了消息在不同缩放因子下的多份副本。
  2. GLWE 密文 CGLWEC_{GLWE}：标准的同态密文。

运算结果是一个新的 GLWE 密文：

Cres=CGGSW⊡CGLWEC_{res} = C_{GGSW} \boxdot C_{GLWE}

其核心优势在于：输出噪声的增长是加性的（Additive），而不是乘性的（Multiplicative）。这使得我们可以进行多次连续的乘法运算而不用立刻进行自举。

分解技术 (Decomposition)

为了实现低噪声增长，TFHE使用了**分解（Decomposition）**技术。 给定一个大常数（或 GLWE 密文的分量），我们将其按基数 β\beta 分解为一系列“小”分量：

γ=∑j=1ℓγjqβj\gamma = \sum_{j=1}^{\ell} \gamma_j \frac{q}{\beta^j}

其中 γj\gamma_j 很小。 在计算外部积时，我们不直接用大数相乘，而是将 GLWE 密文分解，然后与 GGSW 密文中预计算好的、对应于 qβj\frac{q}{\beta^j} 的加密部分进行组合。

应用：CMUX 门

外部积最著名的应用是 CMUX (Controlled Multiplexer) 门，它是自举的核心组件。

CMUX(Csel,C0,C1)=Csel⊡(C1−C0)+C0\text{CMUX}(C_{sel}, C_0, C_1) = C_{sel} \boxdot (C_1 - C_0) + C_0

这里，CselC_{sel} 是一个 GGSW 密文（加密了 0 或 1），用于在两个 GLWE 密文 C0C_0 和 C1C_1 之间进行选择。得益于外部积的低噪声特性，我们可以在盲旋转中连续执行数百次 CMUX 操作。

可编程自举 (Programmable Bootstrapping)

自举（Bootstrapping）是全同态加密中的圣杯，它允许我们在加密状态下刷新密文的噪声，从而支持无限深度的电路计算。在 TFHE 中，自举不仅能降噪，还能同时计算一个查表（Look-Up Table, LUT）函数，因此被称为“可编程自举”（PBS）。

TFHE 的自举过程主要由三个核心步骤组成：模数切换 (Modulus Switching)、盲旋转 (Blind Rotation) 和 样本提取 (Sample Extraction)。

模数切换 (Modulus Switching)

模数切换是将密文从一个大模数 qq 转换到一个较小的模数 2N2N（其中 NN 是多项式的度数）的过程。这一步是为了适应后续多项式乘法的需求。

原理与公式

给定一个 LWE 密文 c=(a0,…,an−1,b)∈Zqn+1c = (a_0, \dots, a_{n-1}, b) \in \mathbb{Z}_q^{n+1}，我们将其分量缩放并四舍五入到新的模数 2N2N：

a~i=⌊2N⋅aiq⌉∈Z2N\tilde{a}_i = \lfloor \frac{2N \cdot a_i}{q} \rceil \in \mathbb{Z}_{2N}

结果是一个新的 LWE 密文 c~∈Z2Nn+1\tilde{c} \in \mathbb{Z}_{2N}^{n+1}。这个操作会丢弃低位信息（即噪声的一部分），但保留了消息所在的最高有效位（MSB）。虽然这引入了额外的舍入误差，但对于 LWE 密文来说，只要噪声足够小，消息就能被正确保留。

简单示例（模数切换）

假设 q=64,p=4q = 64, p = 4 (Δ=16\Delta = 16), n=4n = 4。密钥 s⃗=(0,1,1,0)\vec{s} = (0, 1, 1, 0)。 加密消息 m=1m = 1，得到密文 c=(−25,12,−3,7,26)∈Z645c = (-25, 12, -3, 7, 26) \in \mathbb{Z}_{64}^5。 我们将其切换到模数 2N=322N = 32：

c~=(−13,6,−2,4,13)∈Z325\tilde{c} = (-13, 6, -2, 4, 13) \in \mathbb{Z}_{32}^5

新密文解密后 b~−∑a~isi=13−(6−2)=9\tilde{b} - \sum \tilde{a}_i s_i = 13 - (6 - 2) = 9。 缩放回消息空间：⌊9/(32/4)⌉=⌊9/8⌉=1\lfloor 9 / (32/4) \rceil = \lfloor 9/8 \rceil = 1。消息保持不变。

盲旋转 (Blind Rotation)

这是自举中最昂贵但也最关键的一步。它的目标是将 LWE 密文中的相位（包含消息和噪声）转移到一个多项式的指数上。

核心思想

我们需要计算 X−φ~X^{-\tilde{\varphi}}，其中 φ~=b~−∑a~isi\tilde{\varphi} = \tilde{b} - \sum \tilde{a}_i s_i 是模数切换后的近似相位。 由于 sis_i 是加密的（作为自举密钥 BK 提供），我们不能直接计算 ∑a~isi\sum \tilde{a}_i s_i。 我们从一个包含了查表函数的多项式 V(X)V(X) 开始，计算：

ACC=V(X)⋅X−b~⋅∏i=0n−1Xa~isi\text{ACC} = V(X) \cdot X^{-\tilde{b}} \cdot \prod_{i=0}^{n-1} X^{\tilde{a}_i s_i}

这里 Xa~isiX^{\tilde{a}_i s_i} 的计算依赖于密钥位 sis_i。如果 si=0s_i=0，我们乘 11；如果 si=1s_i=1，我们乘 Xa~iX^{\tilde{a}_i}。 这正是 CMUX 门的作用！对于每个 ii，我们执行：

ACC←CMUX(BKi,ACC⋅Xa~i,ACC)\text{ACC} \leftarrow \text{CMUX}(\text{BK}_i, \text{ACC} \cdot X^{\tilde{a}_i}, \text{ACC})

经过 nn 次迭代，累加器 ACC\text{ACC} 将变成加密了 V(X)⋅X−φ~V(X) \cdot X^{-\tilde{\varphi}} 的 GLWE 密文。 多项式 V(X)V(X) 的常数项现在包含了 V(X)V(X) 在 −φ~-\tilde{\varphi} 处的取值。通过精心设计 V(X)V(X)，我们可以让这个值等于我们想要的函数输出（例如去噪后的消息）。

样本提取 (Sample Extraction)

盲旋转结束后，我们得到一个 GLWE 密文。我们需要从中提取出常数项，变回 LWE 密文。

过程

给定 GLWE 密文 C=(A0,…,Ak−1,B)∈Rqk+1C = (A_0, \dots, A_{k-1}, B) \in \mathcal{R}_q^{k+1}，它加密了多项式 M(X)M(X)。 我们要提取 M(X)M(X) 的常数项 m0m_0。 构造新的 LWE 密文 c=(a,b)c = (\mathbf{a}, b)：

  • bb 直接取自 BB 的常数项。
  • a\mathbf{a} 的分量来自于 AiA_i 的系数，但顺序和符号需要调整（由于 XN=−1X^N = -1 的性质）。 具体来说，若 Ai=∑ai,jXjA_i = \sum a_{i,j} X^j，则对应的 LWE 密钥部分为 (si,0,…,si,N−1)(s_{i,0}, \dots, s_{i,N-1})。 提取出的 LWE 向量部分为 (a0,0,−a0,N−1,…,−a0,1,… )(a_{0,0}, -a_{0, N-1}, \dots, -a_{0,1}, \dots)。

这个操作是“免费”的（不增加噪声），它仅仅是系数的重排。

自举全流程

  1. 输入：LWE 密文 cc，自举密钥 BK，查表多项式 TVTV。
  2. 模数切换：c→c~c \to \tilde{c}（模数 q→2Nq \to 2N）。
  3. 初始化：ACC=(0,…,0,TV⋅X−b~)\text{ACC} = (0, \dots, 0, TV \cdot X^{-\tilde{b}})（平凡 GLWE 密文）。
  4. 盲旋转循环： For ii from 0 to n−1n-1: ACC=CMUX(BKi,ACC⋅Xa~i,ACC)\text{ACC} = \text{CMUX}(\text{BK}_i, \text{ACC} \cdot X^{\tilde{a}_i}, \text{ACC})
  5. 样本提取：从 ACC\text{ACC} 中提取常数项，得到新的 LWE 密文 c′c'。
  6. 密钥切换（可选但通常需要）：将 c′c' 的密钥从大参数（盲旋转使用的）切换回原始 LWE 密钥，以便进行下一轮运算。

通过这个流程，TFHE 实现了在密文上计算任意函数并同时清除噪声的能力。