全同态加密（FHE）简介

简介

最近，云计算和存储改变了企业和个人使用、存储和管理数据的方式。为了保证安全，数据使用安全的密码学方案进行加密，例如 AES，其中需要一个密钥来解密和读取数据。在 2009 年之前，如果我们想在不受信任的服务器上执行数据分析，我们需要以明文形式提供对数据的访问权限，或者将加密数据的密钥交给服务器。这两种选择都有其风险，因为服务器可能会学习到有价值或敏感的信息，而无法完全控制之后的操作。或者，即使对方是诚实的，一些攻击者也可能破坏其安全性，并以明文形式（或密钥）访问我们的私人信息。全同态加密 (FHE) 是一种强大的密码学原语，允许各方使用加密数据进行计算，而无需先解密。它在金融、医疗保健系统、图像和文本分类、机器学习、电子投票和多方计算中都有应用。一个简单的例子是想要计算两个数字 a 和 b 的总和。我们可以加密它们 $E(a)$ 和 $E(b)$，执行一些操作 $E(a) \oplus E(b)$ 并得到 $E(c)=E(a) \oplus E(b)$，其中 $c=a+b$，而不是直接将它们相加。

更正式地说，我们的想法是，我们的数据以明文形式存在，我们想在那个明文空间上计算一些函数（例如，我们可以使用整数，$\mathbb{Z}$，表示个人的工资，并想计算平均函数）。为此，我们将明文转换为密文，并在密文空间上执行操作，从而使生成的密文是应用于明文的函数的加密：$E(f(x))=\hat{f}(E(x))$。在之前的文章中，我们介绍了计算可以表示为算术电路，其中我们有两个运算：加法和乘法。如果我们能让这些操作在密文上工作，那么原则上，我们可以构建更复杂的函数。

同态是相同类型的两个代数结构（例如两个群、环、域或向量空间，仅举几例）之间的函数，它保留了它们的结构。特别是，我们对环同态感兴趣，其中我们有一个具有两个运算的集合。给定环 $(R_1,+,×)$ 和 $(R_2,⊕,⋅)$，如果对于 $R_1$ 中的任何 $x,y$，$f:R_1→R_2$ 是（环）同态，则

• $f(x+y)=f(x)⊕f(y)$。
• $f(x×y)=f(x)⋅f(y)$。

同态的两个常见例子是在具有普通运算的整数 $(\mathbb{Z},+,×)$ 和具有其运算的模 $p$ 的整数 $(\mathbb{Z}/p\mathbb{Z},+,×)$ 之间。另一个例子是当我们使用多项式在某点的值作为同态时，在多项式 $(\mathbb{Z}[X],+,×)$ 和整数 $(\mathbb{Z},+,×)$ 之间。我们可以看到，先对两个多项式求和或相乘，然后在 $x_0$ 点求值，或者先在 $x_0$ 点求值多项式，然后对结果进行加法或乘法运算，效果是一样的。给定多项式 $p(x),q(x)$ 和运算 $∘$（加法或乘法），$(p∘q)(x_0)=p(x_0)∘q(x_0)$。

第一个 FHE 方案是由 Craig Gentry 在 2009 年提出的。为了了解该方案的工作原理，我们可以想象密文包含附加在它的错误或噪声。只要误差不大，我们就可以解密密文并恢复明文。如果我们添加或乘以密文，误差会增加；如果它高于某个阈值，那么解密将无法工作。Gentry 的工作中所介绍的关键点是自举，通过它可以获取密文和公共评估密钥并重新加密消息，从而减少误差。这使得能够计算更深层（执行更多操作）的电路。

尽管 Gentry 的构造证明了 FHE 是可能的，但它的速度非常慢，以至于无法实际应用，对 1 位进行自举需要长达半小时的时间。从那时起，已经有了许多进展，我们已经达到了可以在每位微秒级进行自举 (接近 10 个数量级) 的程度。截至今天，FHE 有 4 代。一些构造是 Brakerski/Fan-Vercauteren (BFV) 和 Brakerski-Gentry-Vaikuntanathan (BGV) 用于整数计算，Cheon-Kim-Kim-Song (CKKS) 用于实数计算，Ducas-Micciancio (DM) 和 Chillotti-Gama-Georgieva-Izabachene (CGGI/TFHE) 用于布尔电路和任意函数。在这篇文章中，我们将重点介绍环面上的全同态加密 (TFHE)。

目前，方案可以分为：

1. 自举方法。这种方法没有深度限制，并且在需要时进行自举以减少噪声。当电路非常深或其深度未知时，它的效果更好。TFHE 就是这种方法的一个例子。
2. 分级方法。这种方法需要预先知道电路，并且当电路的深度小且已知时，它的效果更好。CKKS 是这种策略的一个例子。

许多 FHE 方案的安全性基于带误差环学习 (RLWE) 问题的难度。这与一个著名的困难格问题密切相关，该问题被认为可以防御量子计算机。量子计算机在破解基于阿贝尔群的同态加密方案方面效率很高。

使用 TFHE 加密

TFHE 支持各种方案来加密不同的变量或执行某些操作。

LWE 方案

假设我们要加密一条消息，m，它可以是一个比特或一个模整数。要加密，我们需要两个数 p 和 q，一个密钥 s，s 的长度为 n 比特（取决于安全级别），以及一个误差分布，从中我们将获得误差 e。要加密，我们需要在 $\mathbb{Z}/q\mathbb{Z}$ 中采样一个具有 n 个元素的随机向量 a。$q=2^{n_b}$，其中 $n_b$ 是密文中的比特数，$p=2^{m_b}$，其中 $m_b$ 是明文的比特数。通常，q 的数量级为 $2^{32}$ 到 $2^{64}$。误差 e 应小于 $p/2q$，否则，在加法或乘法时可能会影响消息的比特。

加密 m 得到的密文 c 由下式给出

$E(m,s)=c=(a,b)$

其中 $b=\sum_{k=1}^{n}a_ks_k+e+\Delta m$。这里，$\Delta$ 是 p 和 q 的比率，因此消息被编码在密文的最重要比特中。

要解密，我们必须使用密钥来消除 $\sum_{k=1}^{n}a_ks_k$ 并对结果进行四舍五入（取最重要的比特），

$D(c,s)=round(b-\sum_{k=1}^{n}a_ks_k)$

该方案支持密文加法和乘以常数因子。两个密文的加法，$⊕$，为

$E(m_1,s)⊕E(m_2,s)=(a_1+a_2,b_1+b_2)$

乘以常数因子 $\alpha$ 为

$\alpha E(m,s)=(\alpha a,\alpha b)$

带误差环学习 (RLWE)

在这种情况下，消息是一个多项式 $M(x)$ 模 $x^N-1$，其中包含 $N$ 个系数。密钥 $S(x)$ 是一个系数在 $0,1$ 中的多项式。加密函数为

$E(M(x),S(x))=(A(x),B(x))$

其中 $B(x)=A(x)⋅S(x)+E(x)+\Delta M(x)$。现在，误差也是一个 $N-1$ 次多项式。

该方案支持密文的加法和乘以常数多项式。

环 GSW (RGSW)

该方案支持密文的加法和乘法。消息、密钥和误差与 RLWE 中的相同，但密文不同。我们可以将其视为一个三维矩阵，其中包含 $\ell$ 层

生成的多项式由以下关系给出：

$B_j(x)=A_j(x)S(x)+E_j(x)-M(x)S(x)\frac{q}{\beta_j}$

$$ B{j}^{\star}(x)=A{j}^{\star}(x)S(x)+E_{j}^{\star}(x)+M(x)S(x)\frac{q}{\beta_j} $$

乘以常数多项式的加法和乘法遵循与先前情况相同的规则。要将两个消息相乘，我们需要将第一个术语的每一层分解为 $\ell$ 个较小的多项式，并在此分解与另一个密文的相应层之间执行乘法。

密文总结

下表总结了不同类型的密文和支持的操作。

将私钥转换为公钥方案

Rothblum 定理指出，可以执行模 2 加法的语义安全的私钥同态加密方案可以转换为公钥语义安全同态方案。

外部乘积和受控多路复用器(CMux)门

外部乘积，$×$，是一个涉及 RLWE 密文和 RGSW 密文的运算，输出 RLWE 密文。要执行外部乘积，我们必须分解 RLWE 密文中的 $A(x)$ 和 $B(x)$ 多项式，并在分解与 RSGW 密文的层之间执行矩阵向量积。

外部乘积的一个有趣应用与受控多路复用器门有关，我们在其中根据 if 条件赋值。给定两个值，$y_1,y_2$ 和一个布尔变量 $b$，我们可以构造以下运算

$(y_2-y_1)b+y_1=y$

如果 $b$ 为 $0$，我们得到 $y_1$，如果 $b=1$，我们得到 $y_2$。

这是自举操作的一个重要构建块。

密钥切换

密钥切换操作可用于更改不同参数集中的加密密钥。要实现它，我们需要密钥切换密钥。该过程与自举有一些相似之处，但细微的区别在于它会增加密文中的噪声。密钥切换可用于更改 LWE 和 RLWE 密文中的密钥，但也可用于将 LWE 密文（一个或多个）转换为一个 RLWE。

总结

FHE 是一种重要的密码学原语，允许我们使用加密数据进行计算，而无需先解密，这为许多有趣和新的应用打开了大门。自 2009 年以来，已经提出了四代 FHE 方案，增加了新功能并将性能提高了几个数量级。有两种方法：引导式和分级式。第一个适用于深度深的电路或深度未知的电路，而第二个适用于深度小的电路。许多 FHE 方案的安全性依赖于后量子难题，例如带误差环学习 (RLWE)。一种强大的方案是 TFHE，一种引导式构造，它对不同类型的密文进行操作以实现丰富的功能。在接下来的文章中，我们将介绍其他方案，并且我们将更深入地研究 FHE 的基础知识。

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