全同态加密、零知识证明和多方计算

介绍

云计算和存储已经改变了企业和人们使用、存储和管理数据的方式。数据通常使用对称密钥加密方案（如 AES 或 ChaCha20）以加密形式安全地存储。但是，为了执行数据分析，我们必须要么将密钥提供给服务器以便它可以解密数据，要么我们必须下载数据、解密数据并在我们自己的机器上运行计算，这可能会非常昂贵，需要大量的时间或内存。全同态加密 (FHE) 允许我们将涉及加密数据的计算委托给不受信任的第三方，而无需先解密它们。

即使这是一种非常强大的密码学原语，我们仍然面临着一个巨大的挑战：我们如何知道第三方执行了它应该执行的计算？这就是零知识证明 (ZKP) 发挥作用的地方。ZKP 允许我们证明给定计算的完整性，而无需重新执行它。zk-SNARKs（简洁的非交互式知识论证）产生可以在非常短的时间内验证的简短证明，并且在去中心化账本（解决隐私和可扩展性问题）和去中心化私有计算中具有应用。它们也面临着一些挑战：为任意计算生成证明的成本可能很高，并且设备功能较弱的用户可能无法生成它们。许多 zk-SNARK 需要可信设置，这些设置应由诚实的一方生成，以确保没有人可以作弊并生成伪造的证明。

这两者都可以通过多方计算 (MPC) 来解决。在这个方案中，证明的生成或可信设置的建立委托给各个方，这些方可能对数据具有部分访问权限。在设置仪式的情况下，只要所涉及的一方之一是诚实的，该设置就是安全的。MPC 还可以与去中心化账本一起使用，以确保任何人都可以参与设置仪式并防止恶意方阻止诚实的参与者，使用具有透明设置的证明（例如 STARK - 可扩展的透明知识论证）。

证明生成可以由多个服务器执行，每个服务器都具有关于秘密输入的部分信息。每一方都可以提交证明，证明证明生成协议的正确性。多方计算还可以用于在不同方之间执行计算，每一方都具有与问题相关的不同信息，例如银行之间的财务信息或医疗服务提供商的健康相关信息。FHE 帮助各方共享信息并进行计算，而无需泄露信息，或者在不损害敏感数据的情况下训练机器学习模型。

从以上所有内容中可以清楚地看出，FHE、ZKP 和 MPC 有许多共同点，并且每一个都可以为其他方面提供一些东西。ZKP 可以提供计算的完整性，FHE 允许数据共享和计算而不损害它，并且 MPC 使我们能够将昂贵的计算委托给其他方。这些为金融、健康和医疗领域中许多新的、令人兴奋的应用打开了大门，重点在于数据隐私和去中心化。

我们现在将解释这些原语背后的基本思想。

全同态加密

全同态加密是一种加密形式，我们可以在加密数据上执行操作，并且这些操作的结果是涉及密文的操作的加密形式。例如，在 RSA 密码系统 中，我们使用公钥通过以下方式加密消息 $m$

$E(m)=m^e$ (mod n)

现在假设我们有 $m_1$，$m_2$ 两个数，我们想要计算它们的乘积 $m_1 \times m_2$。我们可以看到，如果我们执行乘积然后对其进行加密，我们会得到

$E(m_1 \times m_2)=( m_1 \times m_2)^e$  (mod   $n$)

如果我们取 m1,m2 加密形式的乘积，那么

$E(m_1) \times E(m_2)= m_1^e \times m_2^e =( m_1 \times m_2)^e$   (mod $n$)

这与先计算乘积然后再加密相同。加密空间中的操作不必与原始空间中的操作相同。鉴于 RSA 密码系统的这一特性，许多研究人员开始怀疑是否有可能构建一种全同态加密方案。第一个 FHE 方案于 2009 年由 Craig Gentry 提出。

数学插曲：同态

更准确地说，同态是两个代数结构（例如两个群、两个环、两个向量空间）之间的函数，并保留它们的结构。如果你上过线性代数课程，那么线性变换就是同态的例子。在群的上下文中，假设我们有两个群 ($\mathbb{G}_1,\cdot$) 和 ($\mathbb{G}_2,\oplus$)，每个群都有它们的二元运算（它可以是乘法、加法、椭圆曲线加法、函数组合等）。函数 $f:\mathbb{G}_1\rightarrow\mathbb{G}_2$ 是一个同态，如果给定 $\mathbb{G}_1$ 中的 $x$，$y$，我们有

$f(x\cdot y) = f(x) \oplus f(y)$

请注意，图像 $f(x),f(y)$ 之间的运算是 $\mathbb{G}_2$ 上的运算。当我们定义模算术时，我们还看到了环之间的同态的例子：我们有一个从具有通常运算的整数集合 ($\mathbb{Z},+,\times$) 到整数模 $p$ 的环 ($\mathbb{Z}/ p \mathbb{Z},\oplus,\cdot$) 的保持加法和乘法的函数（我们使用不同的加法和乘法符号来记住这些是模 $p$）。例如，如果我们取 $p = 7$，我们得到 $\mathbb{Z}/ p \mathbb{Z}={0,1,2,3,4,5,6}$。我们可以看到： −5+3=−2。这与 2 ⊕ 3 ≡ 5 (mod7) 相关，其中 2 是 $\mathbb{Z}/ p \mathbb{Z}$ 中对应于 −5 的元素，3 对应于它本身，而 5 全等于 −2。−3×4=−12，这与 4⋅4≡2(mod7) 的关系与之前相同。

重要的是要看到同态不一定是单射函数（最后一个环同态显示了一个清晰的例子）。如果同态是双射函数，则称为同构。以下是从具有加法的实数 ℝ 到配备有乘法的正实数 ℝ + 的同构示例，ℝ +,  $f$ : ℝ→ℝ+, $f (x)$ = exp $(x)$ ，及其逆函数，$f^{-1}$ : ℝ+→  ℝ,  $f^{-1}$ ( $z$) = ln( $z$)。你可以很容易地检查 $f  (x + y )=f (x) \cdot f (y)$

在密码学的上下文中，我们希望有保留一些操作的加密或承诺方案。例如，Kate-Zaverucha-Goldberg (KZG) 承诺方案是加性同态的。该承诺接受多项式（我们可以将其视为具有普通多项式加法的组 (ℙ,+)）并将它们映射到椭圆曲线点（它们也具有组结构，具有椭圆曲线加法 (𝔾,⊕)）。我们可以验证

cm( $p_1 (x)  +  p_2(x))  =  cm( p_1 (x))  \oplus  cm(p_2(x))$

此属性对于证明聚合和折叠方案很有用。椭圆曲线配对还提供了一些方法来计算承诺形式的多项式之间的乘法（使用 KZG）。

为了能够构建 FHE 方案，我们不仅需要保留操作，还需要有一种方法来解密结果。

FHE 基础知识

现在有很多用于 FHE 的库，例如 OpenFHE、Microsoft SEAL、Λ∘λ 和更多。使用 FHE，你可以对搜索引擎或页面（例如 Wikipedia）进行私有查询；请参见此处。

FHE 方案基于格密码学。格由一些基向量的整数系数的线性组合给出。为了固定概念，假设我们有两个向量 $e_x = (1,0)$ 和 $e_y = (0,1)$，我们考虑所有可能的组合 $p = xe_x + ye_y$，其中 $x$, $y$ 在 ℤ 中，产生空间中的点 (0,0),(1,0),(1,1),(−1,−2),.... 一个格子看起来像这样。理想格对应于多项式环中的理想，继承了环的自然加法和乘法运算（理想概括了整数的某些子集背后的思想，例如偶数。任意两个偶数的加法总是偶数，并且每当我们用偶数乘以任何整数时，结果也是偶数 - 一种吸收特性 - ）。

为了构建 FHE 方案，我们可以想象有一个带有一些小噪声的密文，这样只要噪声低于某个阈值，解密就可以工作。如果我们有同态地乘法和加法密文的方法，但代价是相应地增加噪声参数，也就是说，$E(a + b) =E (a) \oplus E (b)$ 和 $E(a\times b)=E(a)\cdot E(b)$。我们称之为半同态加密方案 (SHE)。如果我们能添加一个“重加密”算法，它可以接受给定的密文 $E(m)$ 并降低其噪声，从而获得一个新的密文 $E'(m)$，该密文也加密 $m$，那么我们可以获得一个 FHE 方案。

SHE 方案可以处理具有一定深度的电路（想象一下这是在噪声变得太大之前你可以乘法或加法的次数）。可以修改 SHE，使其解密电路具有较低的乘法深度，使其“可引导”，从而将其转换为 FHE 方案。

一些常见的 FHE 方案是：

• 用于整数算术的 Brakerski-Fan-Vercauteren (BFV) 和 Brakerski-Gentry-Vaikuntanathan (BGV)。
• 用于实数算术的 Cheon-Kim-Kim-Song (CKKS)。
• 用于布尔电路和使用查找表的任意函数的 Ducas-Micciancio (DM) 和 Chillotti-Gama-Georgieva-Izabachene (CGGI)。

许多密码学原语（例如公钥密码学）都基于数学问题的难度或难解性，例如整数分解 (RSA) 或离散对数问题（椭圆曲线密码学）。这些问题无法通过当前的计算机有效地解决（至少，前提是所涉及的整数足够大或群具有大量元素）。但是，如果满足某些条件，量子计算机可以通过 Shor 算法 轻松处理这些问题。FHE 基于最短向量问题或带错误的环学习 (RLWE) 问题，这是一个 NP 难问题，无法用 Shor 算法解决（FHE 被认为是抗量子的）。

零知识证明

零知识证明 (ZKP) 在过去十年中受到了越来越多的关注，尤其是在第一个高效的 SNARK 构造出现之后。ZKP 在去中心化账本中两个主要挑战的解决方案中发挥着重要作用：可扩展性和隐私。为了验证交易，节点必须重新执行它们，从而导致瓶颈。此外，账本中的所有信息都是公开的，这可能会泄露有关个人和组织的敏感信息。

zk-SNARK 允许一方证明一个语句，而无需透露除该语句的有效性之外的任何内容。例如，我们可以证明我们拥有给定的密钥，而无需透露它。我们还可以证明我们已经执行了某些交易或计算，而无需暴露秘密或敏感信息。SNARK 的一个重要属性是它们的简洁性，这意味着证明：

• 很短（占用很少的内存，对于某些 SNARK 约为 1 kB）。
• 验证速度快（通常在毫秒级）。

以太坊最近一直在添加零知识证明技术来解决可扩展性问题。Zcash 实施了 ZKP 来提供私有交易，而 Aleo 使用它们来以去中心化的方式运行私有计算。

SNARK 在底层是如何工作的？即使有许多不同的构造（例如 Marlin、Plonk、Halo 和 STARK），它们也有一个共同的配方。SNARK 的构建块是多项式交互预言证明 (PIOP) 和多项式承诺方案 (PCS)。根据所做的选择，生成的 SNARK 具有不同的属性和要求。例如，它可以是透明的（不需要可信设置）、后量子安全的、需要特殊的（配对友好的）椭圆曲线、需要更长的时间来生成证明、具有更短的证明（小于 1 kB）、允许轻松递归等。此处显示了不同多项式承诺方案之间的比较。

为了能够构造证明，我们首先需要将我们的计算转换为一些 SNARK 友好的格式。我们可以通过将其简化为某种 NP 完全问题（例如图着色或电路可满足性）来证明我们执行的正确性。我们将使用算术电路，并且将程序转换为电路的过程被称为算术化。有不同的形式或策略来进行这种转换；此处概述了最常用的方法。

多方计算

在安全的多方计算中，一组参与者 $p_1,p_2,...,p_m$，每个参与者都拥有一​​些秘密信息 $s_1,s_2,...s_m$，想要计算一个需要了解该秘密信息的特定函数。例如，我们可能有 $m$ 个员工想要知道他们的平均工资，而无需透露他们的收入。一种简单的方法是他们都信任另一方，并且每个人都发送他们的秘密信息，然后由“受信任”的一方计算平均值。缺点： “受信任的”一方会了解所有信息，并可能利用它。或者也许他是诚实的，但他被黑客入侵了，攻击者获取了一切。

幸运的是，有一种有用的密码学原语可以处理这种情况：加性秘密共享。每个参与者都可以将其秘密 $s_k$ 分解为 $m$ 份，这样任何股东都不能单独了解该秘密。为了能够重建秘密，所有其他方都必须勾结并分享他们的部分。在上面的例子中，每个员工都可以将他的工资，$sk$ 分解成 $m$ 个不同的随机份额。例如，如果我们有 4 个员工，并且员工 A 赚取 4500，那么他可以拥有 4 个份额，$s{Ai}$：-1200、1500、3600、600，这样 $\sum{i} s{Ai} = 4500$。他保留一份份额，并将剩余的份额分发给 B、C 和 D。反过来，其余人会分解他们的秘密并将其分开。之后，每个参与者将他拥有的所有份额相加，获得一个部分和，$s{p,A} = \sum{k} s_{k,A}$，然后分享这些部分和以计算最终平均值。

当知道最多 $m − 1$ 的各方所拥有的信息不超过任何没有份额的人的信息时，秘密共享是安全的。

现在，我们如何确保每个参与者都做他应该做的事情？ ZKP 让我们能够通过提交证明正确执行的证明来保证每个参与者都按预期进行计算。如果他作弊，证明应该失败，他可能会受到惩罚。早期的 MPC 协议具有显着的开销；过去十年已经取得了许多进展，使其高效并导致了许多应用。

总结

全同态加密、零知识证明和多方计算是重要的密码学原语，近年来随着去中心化账本的引入以及对数据隐私的日益关注，它们越来越受到关注。每一个都具有其独特的功能和应用，并且能够为其他原语提供一些东西。FHE 允许我们对加密数据进行云端计算，而无需将我们的密钥交给服务器，这可以防止第三方访问数据的具体内容。ZKP 允许我们通过提交一个可以快速验证的简短证明来证明给定计算的正确性。这被认为是解决去中心化账本的隐私和可扩展性问题的最伟大的工具之一。多方计算可以帮助我们以安全的方式分配复杂的计算或在所有输入都在多个参与者之间分配时计算某些内容；它在投票、私人拍卖、竞标等方面有应用。FHE 可以帮助我们改进现有的 ZKP，而 ZKP 反过来可以使多方计算更简单、更安全。反过来，zk-SNARK 的设置仪式也需要 MPC，并且 MPC 还可以帮助证明者通过将证明生成委托给不受信任的强大服务器来减少他们的证明生成时间。ZKP 还可以帮助我们确保涉及加密数据的计算能够正确执行。所有这些领域在过去十年中都取得了巨大的进步，并且每一个都将帮助其他领域取得进步，从而带来新的有趣的应用，更加注重去中心化和隐私。在接下来的文章中，我们将更深入地介绍 FHE 的数学基础以及 MPC 和 ZKP 的进一步应用。

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