快速的口令电路入门指南

加密电路简介

加密电路简介

特别感谢 Dankrad Feist 的审阅

加密电路是一种相当古老且令人惊讶的简单的密码学原语；它们可能是最简单的一种通用“多方计算”（MPC）形式，便于理解。

这是该方案的常见设置：

• 假设有两个参与方，Alice 和 Bob，他们想要计算某个函数 f(alice_inputs, bob_inputs)，该函数接受两个参与方的输入。Alice 和 Bob 都希望了解计算 f 的结果，但Alice 不想让 Bob 知道她的输入，而 Bob 不想让 Alice 知道他的输入。理想情况下，他们只希望学习 f 的输出，而不获取其它信息。
• Alice 进行一个特殊的过程（“加密”）来加密一个电路（即一组与或门...），以求值函数 f。她将与加密电路兼容的输入，也进行加密，传递给 Bob。
• Bob 使用一种称为“1-of-2 遗忘传输”的技术来学习其自身输入的加密形式，而不让 Alice 知道他获得了哪个输入。
• Bob 在加密数据上运行加密电路并获得答案，并将其传递给 Alice。

可以使用额外的密码学封装来保护该方案，以防止 Alice 和 Bob 发送错误信息并相互给出错误答案；不过，为了简单起见，这里不做进一步探讨，只需说“在所有内容周围封装一个 ZK-SNARK”是一个（相当笨重且不够理想的）有效解决方案。

那么基本方案是如何工作的呢？让我们从一个电路开始：

这是一个非常简单的、非完全琐碎的电路示例，它实际上做了一些事情：它是一个两个比特加法器。它接受两个二进制数字作为输入，每个有两个比特，并输出三个比特二进制数作为和。

现在，让我们对电路进行加密。首先，对于每个输入，我们随机生成两个“标签”（想想看：256位数字）：一个代表该输入为 0，另一个代表该输入为 1。然后，对于每个中间电线也执行相同操作，但不包括输出电线。请注意，这些数据并不是 Alice 发送给 Bob 的“加密”部分；到目前为止，这只是设置。

现在，对于电路中的每个门，我们执行以下操作。对于每个输入组合，我们在 Alice 提供给 Bob 的“加密”中包含输出的标签（或如果输出标签是“最终”输出，则直接输出）加密，与由输入标签哈希得到的密钥一起加密。为了简单起见，我们的加密算法可以设为 enc(out, in1, in2) = out + hash(k, in1, in2)，其中 k 是门的索引（它是电路中的第一扇门、第二扇门还是第三扇门？）。如果你知道两个输入的标签，并且你有加密形式，那么你可以知道相应输出的标签，因为你可以计算相应哈希并将其减去。

这是第一个 XOR 门的加密：

请注意，我们直接包含（加密形式的）0 和 1，因为这个 XOR 门的输出直接是程序的最终输出。现在，让我们看一下最左侧的 AND 门：

这里，门的输出只是被用作其他门的输入，因此我们使用标签而不是比特来隐藏这些中间比特，防止逐步求值。

Alice 提供给 Bob 的“加密”仅需将每个门的第三列的所有内容发送给他，同时对每个门的行进行重新排序（以避免揭示给定行是否对应于任何电线上的 0 或 1）。为了帮助 Bob 查找要解密的每个门对应的值，我们使用特定的顺序：对于每个门，第一行变成两个输入标签都是偶数的行，第二行是第二个标签是奇数的行，第三行是第一个标签是奇数的行，第四行是两个标签都是奇数的行（我们故意选择标签，以便每个门都有一个输出的偶数标签和一个输出的奇数标签）。我们用相同的方法对电路中的每个其他门进行加密。

总的来说，Alice 向 Bob 发送每个门四个约 ~256 位的数字。结果发现，四个数字远非最优；见这里关于如何将其降低到三个甚至两个数字（对于 AND 门甚至零！！）和 XOR 门的最优解决方案。请注意，这些优化确实依赖于一些更改，例如，使用 XOR 而不是加法和减法，尽管这应该出于安全性原因无论如何都会被执行。

当 Bob 收到电路后，他向 Alice 请求对应其输入的标签，并使用一种名为“1-of-2 遗忘传输”的协议，向 Alice 请求对应其自身输入的标签，而不透露给 Alice 他输入的是什么。然后他逐个检查电路中的门，揭示每个中间门的输出电线。

假设 Alice 的输入是最左边的两个电线，她给出了 (0, 1)，而 Bob 的输入是最右边的两个电线，他给出了 (1, 1)。这是带标签的电路：

• 一开始，Bob 知道标签 6816、3621、4872、5851
• Bob 评估第一个门。他知道 6816 和 4872，因此可以提取输出值对应于 (1, 6816, 4872)（见上表），提取第一个输出比特 1
• Bob 评估第二个门。他知道 6816 和 4872，因此可以提取输出值对应于 (2, 6816, 4872)（见上表），提取标签 5990
• Bob 评估第三个门（XOR）。他知道 3621 和 5851，并学习到 7504
• Bob 评估第四个门（OR）。他知道 3621 和 5851，并学习到 6638
• Bob 评估第五个门（AND）。他知道 3621 和 5851，并学习到 7684
• Bob 评估第六个门（XOR）。他知道 5990 和 7504，并学习到第二个输出比特 0
• Bob 评估第七个门（AND）。他知道 5990 和 6638，并学习到 8674
• Bob 评估第八个门（OR）。他知道 8674 和 7684，并学习到第三个输出比特 1

因此 Bob 学到的输出是：101。在二进制表示中，10 + 11 实际上等于 101（输入和输出比特都以从小到大的顺序在电路中给出，这就是为什么 Alice 的输入 10 在电路中表示为 (0, 1)），所以运作正常！

请注意，加法是加密电路的一个相当无意义的用途，因为 Bob 知道 101 只是减去他自己的输入，即可得到 101 - 11 = 10（Alice 的输入），从而破坏隐私。然而，通常情况下，加密电路可以用于不可逆的计算，因此不会以这种方式破坏隐私（例如，可以想象一个计算，其中 Alice 的输入和 Bob 的输入是他们对个性测试的答案，输出是一个单独比特，决定算法是否认为他们兼容；那一个比特信息不会让 Alice 或 Bob 知道彼此的单独测试答案）。

1 of 2 遗忘传输

现在让我们更深入地讨论 1-of-2 遗忘传输，这项 Bob 用来从 Alice 获取与其输入相关的标签的技术。问题在于这里。关注 Bob 的第一个输入比特（第二个输入比特的算法是相同的），Alice 有一个与 0 相对应的标签（6529），和一个与 1 相对应的标签（4872）。Bob 有他想要的输入比特：1。Bob 想了解正确的标签（4872），而不让 Alice 知道他的输入比特是 1。显而易见的解决方案（Alice 直接将 6529 和 4872 都发送给 Bob）无法实现，因为 Alice 只想放弃两个输入标签中的一个；如果 Bob 收到两个输入标签，这可能泄露 Alice 不想泄露的数据。

下面是 一种相当简单的协议，使用椭圆曲线：

1. Alice 生成一个随机的椭圆曲线点 H。
2. Bob 生成两个点 P1 和 P2，要求 P1 + P2 和为 H。Bob 选择 P1 或 P2 为 G * k（即，他知道对应私钥的点）。请注意，P1 + P2 = H 的要求确保 Bob 无法生成 P1 和 P2，让他知道对应私钥。这是因为如果 P1 = G * k1 和 P2 = G * k2，那么 Bob 知道 k1 和 k2，则 H = G * (k1 + k2)，这意味着 Bob 可以提取出 H 的离散对数（或“对应私钥”），这意味着所有的椭圆曲线密码学都被破解了。
3. Alice 确认 P1 + P2 = H，并在 P1 下加密 v1，在 P2 下加密 v2，使用某种标准的公共密钥加密方案（例如，El-Gamal）。Bob 只能解密两个值中的一个，因为他知道与最多一个 （P1, P2） 对应的私钥，但 Alice 不知道是哪一个。

这样解决了问题；Bob 学到两个线标签之一（6529 或 4872），具体取决于他的输入比特，而 Alice 不知道 Bob 学到了哪个标签。

应用

加密电路可能对许多事情都非常有用，而不仅仅是 2-of-2 计算。例如，你可以使用它们进行任意复杂性和任意参与者提供输入的多方计算，这可以在固定的交互轮数中进行。生成加密电路是完全可并行化的；你不需要在对一个门进行加密之前完成加密另一个依赖于它的门。因此，你可以简单地让一个大规模的多方计算，参与者计算出所有电路门的加密，并发布与其输入对应的标签。这些标签本身是随机的，因此不会揭示输入的信息，但任何人都可以执行发布的加密电路并“明文”学习输出。见这里了解有关使用加密电路作为成分的 MPC 协议的最新示例。

多方计算并不是唯一一个利用将计算拆分为可并行化部分、在秘密数据上运行的上下文，后面是可以明文运行的顺序部分是有用的，且加密电路不是实现这一目标的唯一技术。通常，关于 随机编码 的文献包含了很多更复杂的技术。这一数学分支在 功能加密 和 模糊化 等技术中也很有用。

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