Machina iO: 为全同态加密（FHE）生成电路特定解密密钥的 Part 3

2026-05-10

概览

我们最终讨论实现电路特定解密密钥的最后缺失部分。我们还展示了这如何直接推导出不可区分性混淆（iO）。

回顾一下，这个缺失部分是指允许服务器将新的公共输入（在线投票中即加密的选票）插入到可信方提供的 BGG+ 编码中的过程。为简化起见，我们将该问题形式化如下：给定 $L$ 位公共输入 $x_L \in {0,1}^L$ 和一些依赖于私有输入 $d \in {0,1}^K$ 但与 $x_L$ 无关的辅助数据，服务器应能获得 $(d, x_L)$ 的 BGG+ 编码：

$c_{x_L} := \overline{s(A_{x_L} - (d, x_L) \otimes G)} = (\overline{s(A_{x_L,0} - d \otimes G)}, \overline{s(A_{x_L,1} - x_{L,1} G)}, \dots, \overline{s(A_{x_L,L} - x_{L,L} G)})$，

其中 $A_{x_L} \in \mathbb{Z}q^{n \times (K+L)m}$ 是针对 $d$ 和 $x_L$ 的一组公钥，它可能依赖于 $x_L$，而 $x{L,i}$ 是 $x_L$ 的第 $i$ 位。

一个额外的约束是，可信方应该能够在了解服务器的公共输入 $x_L$ 之前，高效地推导出对应于电路 $C_F$ 的公钥；否则，可信方无法在设置阶段发布 $C_F$ 特定的解码密钥 $\overline{s A_{C_F}}$。然而，这导致输入公钥 $A_{x_L}$ 的定义面临以下张力。

• 如果它们依赖于公共输入 $x_L$，那么电路输出的公钥，即 $A_{C_F}$，不仅依赖于电路，还依赖于输入的公钥。结果，可信方必须为每个可能的公共输入准备一个单独的解码密钥，导致解码密钥总大小增长 $2^L$ 倍。
• 另一方面，如果假设它们独立于公共输入 $x_L$，那么 BGG+ 编码将变得不安全。具体来说，恶意服务器可以获得两个仅在第 $i$ 位上不同的编码，例如 $\overline{s(A - (d,1) \otimes G)}$ 和 $\overline{s(A - (d,0) \otimes G)}$。由于 $A$ 对两个编码是共同的，它们的差会抵消掩码 $sA$，服务器得到 $sG + e$，其中 $e$ 是某个小误差项。这已知是一个容易求解的 LWE 实例，服务器最终可以恢复密钥 $s$。

Diamond iO：输入相关的密钥

Diamond iO 是我们团队提出的一种基于格的 iO 方案 [SBP25]，它通过将输入依赖性嵌入到密钥而非公钥中来解决这一张力。从现在起，我们用 $s_{x_L}$ 表示对应于公共输入 $x_L$ 的密钥，并使用 $A$ 表示输入公钥。那么服务器为公共输入 $x_L$ 获取的输入编码被重新定义如下：

$c_{x_L} := \overline{s_{x_L} (A - (d, x_L) \otimes G)}$

直观地说，这防止了上述差分攻击，因为在该输入位上不同的两个编码的掩码，即 $s_1 A$ 和 $s_0 A$，至少无法以任何明显的方式相互抵消。实际上，如果每个密钥 $s_{x_L}$ 是从对应于所有其他输入的密钥中独立采样的，那么这种直觉将遵循 LWE 假设（的子指数难度）。

然而，出于我们将简要解释的原因，我们实际上以不完全相互独立的方式采样对应于不同输入的密钥。具体来说，我们引入的基于格的 iO 方案 Diamond iO 将输入 $x_L \in {0,1}^L$ 的密钥定义如下：

$s_{x_L} := s_\epsilon \prod_{j \in [L]} S_{j,x_j}$，

其中 $s_\epsilon \in {0,\pm1}^n$ 是一个均匀随机向量，每个 $S_{j,x_j} \in {0,\pm1}^{n \times n}$ 对于每个 $j \in [L]$ 和 $x_j \in {0,1}$ 独立且均匀随机地采样。Diamond iO 引入了一个新的基于格的假设，称为全乘积 LWE，在该假设下，所得构造可以被证明能够抵御差分攻击。

用于输入插入的 GGH15 编码

我们现在转向服务器如何在不了解密钥本身的情况下，作为公共输入的函数采样密钥 $s_{x_L}$ 的问题。一个自然的工具是 GGH15 编码。它的关键特性是，仅需 $O(L)$ 份辅助数据，就可以生成长度为 $L$ 的二分分支过程所有 $2^L$ 种模式对应的编码。在原始 GGH15 图像中，这意味着可以推导出对应于沿二分路径选择的秘密矩阵的所有 $2^L$ 个乘积的编码。我们在此正是使用这个想法，因为我们的输入相关密钥本身被定义为每个输入位一个秘密矩阵的乘积。更具体地说，我们不让服务器显式地学习 $s_{x_L}$，而是让它推导出一个编码，其隐藏的秘密部分随着它逐位插入 $x_L$ 的位而精确地按照这个乘积演变。

为了实现这一点，可信方最初不向服务器提供 BGG+ 编码。相反，它提供一个初始的 GGH15 编码，形式为

$p_\epsilon := \overline{((d, 0^L) \otimes s_\epsilon) B_0}$，

其中 $B_0$ 是由可信方采样的一个公开矩阵。更一般地，在插入前 $i$ 个输入位之后，目标编码是

$p_{x_i} := \overline{((d, x_i, 0^{(L-i)}) \otimes s_{x_i}) B_i}$，

其中 $x_i := (x_1, \dots, x_i)$ 且

$s_{x_i} := s_\epsilon \prod_{j \in [i]} S_{j,x_j}$。

因此，服务器的目标是从 $p_\epsilon$ 开始，逐步更新，直到达到 $p_{x_L}$。

使用原像更新编码

实现这些更新的桥梁是一个称为原像的标准格对象。给定一个公开矩阵 $B$ 和一个目标矩阵 $P$，$P$ 相对于 $B$ 的格原像是一个矩阵 $K$，使得 $BK = P$。

在以下内容中，我们使用 $K \leftarrow B^{-1}(P)$ 来表示生成满足上述方程的原像 $K$ 的过程。值得注意的是，只有拥有与 $B$ 一起采样的陷门的人才能高效地为均匀随机矩阵 $B$ 生成原像。因此，只有可信方才能决定在设置阶段为哪些目标矩阵生成和发布原像，而看到 $B$ 但不知道其陷门的恶意对手无法自行高效地创建这样的原像。

这之所以有用，不仅因为乘以 $K$ 可以以受控方式转换编码的公共部分，而且还因为 $K$ 可以使用 $B$ 的陷门以小范数采样。因此，即使编码包含误差项 $e$，乘法后新误差的大小（即 $eK$）仍然有界，因为 $K$ 的范数有界。

对于每个位置 $i \in [L]$ 和位 $b \in {0,1}$，可信方准备一个原像 $K_{i,b}$。为了定义其目标，设 $U_{i,b}$ 是一个将位 $b$ 写入下一个空输入槽的公开矩阵，即满足

$(d, x_{i-1}, 0^{(L-i+1)}) U_{i,b} = (d, x_{i-1}, b, 0^{(L-i)})$。

然后采样原像 $K_{i,b}$，使得

$B_{i-1} K_{i,b} = (U_{i,b} \otimes S_{i,b}) B_i + E_{i,b}$，

其中 $E_{i,b}$ 是一个小误差矩阵。由于目标同时包含 $U_{i,b}$ 和 $S_{i,b}$，乘以 $K_{i,b}$ 会同时更新可见的输入前缀和隐藏的密钥。

实际上，如果服务器已经持有 GGH15 编码

$p_{x_{i-1}} = \overline{((d, x_{i-1}, 0^{1 \times (L-i+1)}) \otimes s_{x_{i-1}}) B_{i-1}}$，

那么通过将其乘以对应于实际下一个输入位 $x_i$ 的原像，它得到

$p_{x_i} := p_{x_{i-1}} K_{i,x_i} = \overline{((d, x_i, 0^{(L-i)}) \otimes s_{x_i}) B_i}$，

其中

$s_{x_i} = s_{x_{i-1}} S_{i,x_i}$。

因此，每次乘以 $K_{i,x_i}$ 正好执行一步输入插入。从 $p_\epsilon$ 开始，依次乘以 $K_{1,x_1}, K_{2,x_2}, \dots, K_{L,x_L}$，服务器可以为其选择的公共输入 $x_L$ 推导出 $p_{x_L}$，而可信方只需发布 $2^L$ 个原像 ${K_{i,0}, K_{i,1}}_{i \in [L]}$，而不是为所有 $2^L$ 种可能的输入分别准备辅助数据。

一旦得到最终的 GGH15 编码

$p_{x_L} = \overline{((d, x_L) \otimes s_{x_L}) B_L}$，

可信方提供两个额外的原像，将其转换为电路特定解密所需的对象。

首先，它提供一个原像 $K_{\text{att}}$，其目标被选择为使得乘以它可以将 GGH15 编码转换为所需的输入 BGG+ 编码：

$c_{x_L} := p_{x_L} K_{\text{att}} = \overline{s_{x_L} (A - (d, x_L) \otimes G)}$。

因此，$K_{\text{att}}$ 是从 GGH15 世界到 BGG+ 世界的最终投影。

其次，它提供另一个原像，这里记为 $K_C$，其目标被选择为使得乘以它可以提取对应于电路 $C_F$ 输出公钥的掩码：

$v_{C, x_L} := p_{x_L} K_C = \overline{s_{x_L} A_{C_F}}$。

这正是解码在电路 $C_F$ 对输入 BGG+ 编码求值后获得的输出 BGG+ 编码所需的解码密钥。

完整协议流程

将所有内容放在一起，完整过程如下。

1. 可信方发布一个初始 GGH15 编码 $p_\epsilon$，以及后续转换所需的所有原像，即更新原像 ${K_{i,0}, K_{i,1}}{i \in [L]}$ 以及最终转换原像 $K{\text{att}}$ 和 $K_C$。
2. 服务器根据其公共输入位乘以相应的原像，从而执行输入插入并动态生成 $p_{x_L}$。
3. 通过将 $p_{x_L}$ 乘以 $K_{\text{att}}$ 和 $K_C$，服务器动态生成输入 BGG+ 编码和电路特定解码密钥。
4. 然后，服务器在 BGG+ 编码上求值模拟 FHE 求值和 FHE 解密的电路 $C_F$。
5. 这会产出一个解密结果的输出 BGG+ 编码，并由相应的解码密钥掩码。
6. 最后，服务器使用动态生成的解码密钥移除该掩码，并恢复出明文解密结果。

因此，用于输入插入的 GGH15 编码和原像乘积、输入 BGG+ 编码和电路特定解码密钥的动态生成以及在 BGG+ 编码上对 FHE 计算和解密进行求值的组合，正好产生了我们想要的：一个用于 FHE 的电路特定解密密钥。可信方仅在设置时准备辅助数据，而服务器随后可以非交互地恢复合法电路的输出，并且仅针对该电路。

与 iO 的联系

此时，通往 iO 的剩余步骤在概念上很简单。具体来说，我们将固定函数替换为一个通用电路。设 $F$ 是针对将要混淆的 $L$ 位电路类的通用电路。在 iO 设置中，可信方（即混淆器）并不只准备固定的硬编码函数的辅助数据；相反，它还额外提供要混淆的特定 $L$ 位电路 $G$ 的 FHE 加密，记为 $fhe(G)$。相应地，初始 GGH15 编码 $p_\epsilon$ 被定义为将 $fhe(G)$ 作为其公共负载的一部分，与其它硬编码数据一起编码。然后，在求值器通过原像链插入其输入位 $x_L$ 之后，生成的 BGG+ 编码在输入相关密钥 $s_{x_L}$ 下同时包含 $fhe(G)$ 和 $x_L$。

然后在 BGG+ 编码上求值的电路被选为电路 $C_F$，它通过同态求值加密电路 $G$ 在公共输入 $x_L$ 上的结果来模拟通用计算 $F(fhe(G), x_L) = fhe(G(x_L))$。换句话说，一旦输入插入步骤动态生成了 $(d, fhe(G), x_L)$ 的 BGG+ 编码，随后的 BGG+ 编码求值将产生 FHE 密文 $fhe(G(x_L))$ 的编码，然后可以如上所述使用解密密钥 $d$ 同态解密并解码。因此，求值器从混淆器准备的辅助数据开始，插入自己的输入 $x_L$，最终仅恢复输出 $G(x_L)$。

• 原文链接： machina-io.com/posts/cir...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～