利用KHE与FHE构造电路特定解密密钥

如何为全同态加密构造电路特定的解密密钥？：第二部分

2026-05-10

FHE 与 KHE——公钥的同态性质

在引入密钥同态编码（KHE）的形式化定义之前，我们强调 FHE 和 KHE 之间的相似性和差异。为简化起见，在下面的讨论中，我们将可信委员会替换为单个可信方。

• 在 FHE 和 KHE 中，密钥对（私钥和公钥）都由可信方采样生成。然而，在 FHE 中，所有密文都与同一个私钥（解密密钥）和同一个公钥（加密密钥）相关联；而在 KHE 中，每个编码与同一个私钥相关联，但各自拥有不同的公钥。
• 每个 FHE 密文和每个编码都与某个明文相关联。但是，FHE 密文总是隐藏其明文，而编码原则上对无权限服务器是公开的，除了后面讨论的特殊情况。
• FHE 和 KHE 都支持同态电路求值：也就是说，通过同态求值一个电路得到的密文/编码是一个有效的密文/编码，其明文就是该电路的输出。此外，KHE 支持公钥的同态求值。也就是说，与电路输出的编码相关联的公钥，可以根据与电路输入的编码相关联的公钥以及电路描述，独立于输入明文而确定性地推导出来。 这一特性允许可信方在初始设置阶段，预先为给定电路准备一个电路特定的解码密钥。

BGG+ 编码

在下文中，我们将 Boneh 等人的 BGG+ 编码 [ BGG+14] 作为 KHE 的具体实例，即第一个基于格（lattice）的实例。

符号和定义。 我们简要总结本文所用的符号。令 $\mathbb{Z}_q$ 表示模 $q$ 的整数环。向量和矩阵用粗体字母表示，除非另有说明，向量为行向量。带下划线的项表示添加了小范数误差项。

BGG+ 编码的核心特征可以简洁地表述如下：给定在相同私钥但不同公钥下对 $L$ 个不同输入 $x:=(x_1,\ldots,x_L)$ 的编码，对于电路 $C$，可以公开地且仅公开地计算对应于电路输出 $C(x)$ 的输出编码。此外，还可以公开地且仅公开地推导出对应于输出编码的公钥；该输出公钥仅取决于用于输入编码的公钥，而与具体的输入值 $x$ 无关。

设 $n$ 为 LWE 维度，并令 $m:=n\lceil\log_2 q\rceil$。直观地说，BGG+ 编码将整数 $x\in\mathbb{Z}_q$ 相对于私钥 $s\in\mathbb{Z}_q^n$ 和公钥 $A\in\mathbb{Z}_q^{n\times m}$ 进行编码。除非知道私钥 $s$，否则无法将编码与它所编码的整数 $x$ 分离；也就是说，无法将同一编码重新解释为在相同私钥和相同公钥下对另一个不同值 $x'\neq x$ 的编码。

形式上，BGG+ 编码定义如下：

$$c_x := s(A - xG) + e,$$

其中 $e\in\mathbb{Z}_q^m$ 是 LWE 误差，其范数（向量中元素的最大大小）有界，$G\in\mathbb{Z}_q^{n\times m}$ 是一个称为 gadget 矩阵的固定矩阵，具体为：

$$G := I_n \otimes (1,\ldots,2^{\lceil\log_2 q\rceil-1}) = \begin{pmatrix} (1,\ldots,2^{\lceil\log_2 q\rceil-1}) & \ldots & 0 \ \vdots & \ddots & \vdots \ 0 & \ldots & (1,\ldots,2^{\lceil\log_2 q\rceil-1}) \end{pmatrix}.$$

BGG+ 编码的密钥同态性质提供了确定性的公开算法，允许无权限服务器在公钥和编码上求值电路，其语法如下：

• $\text{EvalPK}(C,(A_1,\ldots,A_L)) \to A_C$：给定一个具有 $L$ 个输入和 $1$ 个输出的电路 $C$，以及 $L$ 个输入公钥 $(A_1,\ldots,A_L)\in\mathbb{Z}_q^{n\times Lm}$，返回一个输出公钥 $A_C$。
• $\text{EvalEnco}(C,(A_1,\ldots,A_L),x,(c_{x1},\ldots,c_{xL})) \to c_{C(x)}$：给定一个具有 $L$ 个输入和 $1$ 个输出的电路 $C$，$L$ 个输入公钥 $(A_1,\ldots,A_L)\in\mathbb{Z}q^{n\times Lm}$，输入整数 $x\in\mathbb{Z}q^{L}$，以及 $L$ 个输入编码 $(c{x1},\ldots,c{xL})\in\mathbb{Z}q^{Lm}$，返回一个输出编码 $c{C(x)}$。

正如我们稍后更详细解释的那样，在我们构建电路特定 FHE 解密密钥的场景中，要求值的电路是代表 FHE 同态求值和解密的电路。

这些输出满足以下方程：

$$c_{C(x)} = s(A_C - C(x)G) + e_{C(x)},$$

其中 $e_{C(x)}\in\mathbb{Z}_q^m$ 是某个范数有界的误差。这些同态求值是通过在公钥和编码上定义布尔门操作（例如 NAND），然后将目标电路表示为布尔电路来实现的。

直观上，可以发现第二项中的电路输出 $C(x)$ 被第一项中的掩码 $\underline{sA_C}$ 隐藏（现在，请忽略 $C(x)$ 也乘以了私钥 $s$ 和 gadget 矩阵 $G$，并且添加了误差 $e_{C(x)}$ 这一事实）。由于该掩码与特定电路 $C$ 相关，但与输入 $x$ 无关，如果持有私钥 $s$ 的可信方预先将相应的掩码 $\underline{sA_C}$ 作为针对电路 $C$ 的解码密钥发布，那么执行同态求值的无权限服务器可以非交互地恢复输出 $C(x)$。即使恶意服务器试图解码通过对与 $C$ 不同的电路 $C'$ 求值得到的输出编码，解码密钥 $\underline{sA_C}$ 也是无用的，因为该输出编码被 $sA_{C'}\neq sA_C$ 掩码。

不幸的是，故事并没有这么简单地结束。事实上，正如 $x$ 作为 $\text{EvalEnco}$ 的参数出现所暗示的那样，编码的同态求值只能处理公开输入，因此我们不能简单地将 BGG+ 编码视为 FHE 的直接替代品。更准确地说，对于编码之间的乘法，两个输入中至少有一个必须对服务器已知。因此，简单的 BGG+ 编码原生仅支持至少一个乘数为公开的乘法。注意，将私有输入乘以公开输入仍然是可能的，我们稍后将利用这个性质。

对 BGG+ 编码进行 FHE 求值和解密

一种已知的允许对 BGG+ 编码进行私有乘法的方法是将它们与 FHE 结合 [ GVW15, BTW+17, HLL23, AKY24]。具体来说，将私有输入在 FHE 下加密，并将 FHE 密文作为公开输入在 BGG+ 编码下编码。然后，在这些编码上求值的电路 $C$ 被定义为模拟 FHE 的同态求值。更正式地说，当 $x:=\operatorname{fhe}(z)$ 表示私有输入 $z$ 的 FHE 加密时，并且 $F$ 是在 FHE 下求值的应用特定电路，$C_F(x)$ 将是 $F(z)$ 的 FHE 加密，即 $C_F(x)=\operatorname{fhe}(F(z))$。更具体地说，$\operatorname{fhe}(F(z))$ 是通过将每个 FHE 原语操作（例如加法和乘法）的同态求值算法表示为布尔电路，然后根据电路 $F$ 的门结构组合它们来实现的。

我们强调，这种方法仍然处于 BGG+ 编码的限制之内，因为电路 $C_F$ 的输入 $x$ 是服务器可用的公开 FHE 密文。同时，这也是一个主要的实际瓶颈，因为在这种 BGG+ 编码上求值这样的电路实际上将编码的开销乘以了 FHE 的开销。

上述描述仍然面临与 FHE 相同的基本限制。也就是说，将输出密文 $\operatorname{fhe}(F(z))$ 转换为明文 $F(z)$ 需要 FHE 解密密钥，但如果我们直接发布解密密钥 $d$，对手也能够解密输入密文 $\operatorname{fhe}(z)$。相反，可信方向服务器提供一个 $d$ 的编码，并强制服务器在编码上执行 FHE 解密过程，而不泄露 $d$ 本身。

回想一下，BGG+ 编码仍然原生支持私有输入和公开输入之间的同态乘法。因此，如果解密过程可以写成关于解密密钥 $d$ 的线性多项式，其中系数来自被解密的密文，那么服务器可以通过将 $d$ 视为私有输入、将密文视为公开输入，在编码上求值解密过程，而无需访问解密密钥 $d$。幸运的是，大多数基于格的 FHE 方案满足这个性质，因为它们的解密过程（忽略用于去除小误差的最终舍入步骤）可以表示为解密密钥向量 $d$ 与密文向量之间的内积。因此，大多数基于格的 FHE 密文可以在 BGG+ 编码上解密。

总结上述讨论，为了支持多个私有输入之间的乘法，服务器对输入 BGG+ 编码（这些编码了 1）FHE 解密密钥向量 $d$ 和 2）私有输入 $z$ 的 FHE 密文 $\operatorname{fhe}(z)$）求值以下电路 $C_F$：

1. 对输入密文 $\operatorname{fhe}(z)$ 求值应用特定电路 $F$，得到输出密文 $\operatorname{fhe}(F(z))$。
2. 计算 $d$ 与 $\operatorname{fhe}(F(z))$ 的内积，得到一个带噪声的解密结果 $\underline{F(z)}$。
3. 输出 $\underline{F(z)}$。

在实践中，还需要额外的步骤——例如，确保可以从带噪声的解密结果中可靠地提取 $F(z)$，以及为了安全性而隐藏添加到 $F(z)$ 的误差——但我们在此省略这些细节 [ AKY24]。

与电路特定解密密钥的联系

回想一下，在使用电路特定解密密钥的机密投票示例中，无权限服务器在设置阶段从可信方接收合法电路 $F$ 的解密密钥，并在投票阶段从用户接收 FHE 加密的选票。在计票阶段，服务器同态求值电路 $F$ 以获得投票总数的加密，然后使用提供的解密密钥进行解密，而无需与可信方或用户交互。

在这个例子中，针对 $F$ 的电路特定解密密钥使得服务器能够获得 1）FHE 解密密钥 $d$ 和加密选票 $\operatorname{fhe}(z)$ 的输入 BGG+ 编码，即 $\underline{s((A_1,\ldots,A_L)-(d,\operatorname{fhe}(z))\otimes G)}$，以及 2）针对上述电路 $C_F$ 的解码密钥，即 $\underline{sA_{C_F}}$。利用这些数据，服务器可以通过在输入编码上求值 $C_F$，得到输出编码 $\underline{sA_{C_F}+F(z)}$，然后从输出编码中移除解码密钥，从而非交互地恢复明文形式的投票总数。

然而，上述构造仍然缺少一个环节：由于服务器不知道私钥 $s$，它无法创建输入 BGG+ 编码。可信方也无法向服务器提供这样的编码，因为它必须在设置阶段、用户提供 $\operatorname{fhe}(z)$ 之前准备好所有数据。

在最后一篇文章中，我们将解释如何填补这个缺失的环节。事实上，这正是将 BGG+ 编码与 FHE 的结合升级为不可区分混淆（indistinguishability obfuscation）的关键。

附录：BGG+ 编码的密钥同态加法和乘法

回忆一下，$\text{EvalPK}$ 和 $\text{EvalEnco}$ 算法是由公钥和编码上的加法和乘法操作构建的。下面，我们具体展示这些操作是如何实例化的。

设 $c_1:=s(A_1-x_1G)+e_1$ 和 $c_2:=s(A_2-x_2G)+e_2$ 分别是 $x_1$ 和 $x_2$ 的输入编码。它们的密钥同态加法很简单：

$$c_{1+2}:=c_1+c_2=s((A_1+A_2)-(x_1+x_2)G)+(e_1+e_2).$$

可以发现，$c_{1+2}$ 中的公钥，即 $A_{1+2}:=A_1+A_2$，可以仅从输入公钥 $A_1$ 和 $A_2$ 公开推导出来。因此，对于加法门，我们可以让 $\text{EvalPK}$ 和 $\text{EvalEnco}$ 算法输出 $A_{1+2}$ 和 $c_{1+2}$。

密钥同态乘法稍微复杂一些。令 $G^{-1}(A_2)\in{0,1}^{m\times m}$ 为 $A_2$ 的比特分解矩阵，满足

$$GG^{-1}(A_2)=A_2.$$

值得注意的是，$G^{-1}(A_2)$ 的范数很小，因为其元素是比特。

那么，编码 $c_1$ 和 $c_2$ 之间的乘法定义如下：

$$c_{1\times2}:=c_1G^{-1}(A_2)+x_1c_2=(sA_1G^{-1}(A_2)-x_1sA_2+e_1G^{-1}(A_2))+(x_1sA_2-x_1x_2G+x_1e_2)=s(A_1G^{-1}(A_2)-x_1x_2G)+(e_1G^{-1}(A_2)+x_1e_2).$$

相应的公钥定义为 $A_{1\times2}:=A_1G^{-1}(A_2)$，这也是仅从输入公钥 $A_1$ 和 $A_2$ 公开推导出来的。此外，误差项 $(e_1G^{-1}(A_2)+x_1e_2)$ 的范数有界，只要 $x_1$ 很小。实际上，这种由 $x_1$ 引起的误差增长造成了一个限制：BGG+ 编码只能在实际参数下求值布尔电路，而不能求值大型算术电路。

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