MPC-in-the-Head转换入门 - ZKSECURITY

在这篇文章中，我们将研究构建零知识证明最有趣的方法之一：MPC-in-the-Head 转换。 这最初是在 2007 年的论文 Zero-knowledge from secure multiparty computation 中提出的，它通常被称为 IKOS 转换，由论文作者的姓名首字母组成。

该转换允许我们从任何 MPC 协议构建零知识证明系统，该协议被视为黑盒。 我们将探讨 MPC 协议背后的直觉和原始转换技术，并讨论如何应用此构造来开发后量子签名方案。

什么是 MPC？

安全多方计算 (MPC) 是一种密码学技术，允许多方安全地集体计算一个函数。 每个参与方都拥有自己的私有输入，目标是计算所有私有输入的指定函数。 在协议结束时，每个参与方应仅了解函数的输出，而不能了解其他任何内容。

一个简单的协议

用于说明 MPC 协议的一个常见示例是：假设一家公司的员工想知道公司的平均工资，而不透露自己的工资。 在这种情况下，每个员工都拥有一个私有输入 Si，代表他们的工资。 假设所有计算都是在某个素数域 Fp 上执行的：我们想要构建一个协议，计算所有员工的私有输入在域 Fp 上的总和。 然后可以通过将总和除以员工人数来清楚地计算平均工资。

该协议分为三个步骤：输入共享、本地累积和重建。

输入共享

考虑持有其私人工资 S1 的 1 号员工。 他们首先计算 S1 的加法秘密共享，这意味着该值被“拆分”为 n 个份额 [S1]1,[S1]2,…,[S1]n， 它们只是字段元素，选择使得它们的和等于原始值 S1。 S1=[S1]1+[S1]2+…+[S1]n

在实践中，这可以通过从 Fp 中随机均匀地采样前 n−1 个份额来计算，然后将最后一个份额计算为 [S1]n=S1−∑i=1n−1[S1]i 很容易看出，如果前 n−1 个份额是从 Fp 中均匀随机选择的，那么最后一个份额也均匀分布在 Fp 上（事实上，如果至少前 n−1 个份额中的一个是从均匀随机选择的，这也将成立）。 这是一种实现完美隐私的简单方法：如果攻击者看到最多 n−1 个份额，他们就无法了解有关原始值 S1 的任何信息。

本地累积

在此步骤中，每个员工将其生成的第 i 个份额发送给第 i 方。 将注意力集中在 1 号员工身上，他们会将 [S1]2 发送给 2 号员工，将 [S1]3 发送给 3 号员工，依此类推。 然后 1 号员工将收到来自其他员工的以下份额 [S2]1,[S3]1…,[Sn]1 此外，他们可以访问自己生成的份额 [S1]1。

他们现在可以在本地累积每个份额 [S]1=[S1]1+[S2]1+…+[Sn]1 然后将 [S]1 发送给其他每位员工。

重建

最后，每位员工都可以访问其他每位员工累积的份额 [S]1,[S]2,…,[S]n 因此，每位员工都可以通过将所有份额相加来独立重建最终输出 S=[S]1+[S]2+…+[S]n 这对应于所有私有输入的总和。 要了解为什么这有效，请注意，在这种秘密共享方案中，份额是加法同态的：如果我们将两个秘密的两个份额相加，我们就会得到秘密之和的份额。

在这种特定情况下，可以采用这种非常简单的协议，因为我们想要集体计算的函数在私有输入中是线性的。 通常，MPC 协议可用于计算任何函数，但它们需要更复杂的技术。 要了解有关 MPC 构造的更多信息，一个很好的起点是 Y. Lindell 的这篇评论文章。

MPC 协议的属性

MPC 协议应满足两个主要属性：

• 正确性：协议的输出应该是函数的正确输出，与各方在清楚的情况下计算的输出相同。
• 隐私性：各方不应了解其他各方的私有输入，而应仅了解函数的输出。

一般来说，我们假设某些方可能被破坏，这意味着攻击者可能会看到他们交换的输入和消息。 我们说 MPC 协议是 t-私有的，如果即使最多 t 方被破坏，它也能满足隐私性；如果 t+1 方被破坏，则可能会泄露有关诚实方私有输入的一些信息。 在这个基本转换中，我们只需要 2-隐私——这意味着即使最多两方被破坏，也能保持隐私。

此外，MPC 协议仅需要在半诚实模型中是安全的，这意味着假定各方诚实地遵循协议，但在这样做时可能会尝试尽可能多地学习信息。 此模型中的各方通常被称为诚实但好奇。 例如，上面描述的简单协议实际上假定各方诚实地遵循协议：如果一方偏离协议，则输出的计算可能不正确。

最初的 IKOS 转换将底层 MPC 协议视为黑盒，但我们应该指出的是，在更高效的方案中，MPC 协议经过专门设计，以便在应用转换时产生高效的零知识证明方案。

The MPC-in-the-Head transformation

此转换的目标是采用任何具有上述属性的 MPC 协议，并使用它为 NP 中的关系 R 构建零知识证明方案。 在这个新设置中，有两个参与方：证明者和验证者。 证明者想要说服验证者他们知道一个见证 w 使得 (x,w)∈R，其中 x 是一个公共输入。 例如，R 可以是 SHA-256 哈希函数的前像关系： R={(x,w)∣SHA-256(w)=x}

证明者将见证 w 拆分为加法共享 w1,w2,…,wn，使得份额之和等于原始见证： w1+w2+…+wn=w 然后，证明者“在其头脑中”模拟 MPC 协议：将其想象成指导 n 个袜子木偶之间的一场小戏，其中每个角色代表一个参与方。 这些木偶通过遵循脚本对话进行交互，该对话反映了 MPC 协议的步骤。 第 i 方持有 wi 作为其私有输入，并且所有各方都持有公共输入 x。 模拟方计算的函数仅在满足关系时返回 1，否则返回 0： f(x,w1,w2,…,wn)={1if R(x,w1+w2+…+wn)0otherwise 请注意，由于关系 R 位于 NP 中，因此它允许多项式时间验证算法。 因此，函数 f 可以有效地计算，因为它只是对局部见证求和，然后检查关系。 为了给出一个具体的例子，MPC 协议为 SHA-256 前像关系计算的函数如下：

def f(x, w_1, w_2, ..., w_n):
    w = w_1 + w_2 + ... + w_n
    if SHA256(w) == x:
        return 1
    else:
        return 0

在实践中，此函数通常表示为某个有限域上的算术电路 C。

在模拟 MPC 协议后，证明者为每个参与方生成一个视图，其中每个视图都包含参与方的私有输入以及参与方在协议的模拟执行期间发送和接收的消息。 例如，如果第 i 方将消息 m 发送给第 j 方，则

• 第 i 方的视图将包含一个向外消息 out(j,m)，并且
• 第 j 方的视图将包含一个向内消息 in(i,m)。

现在，证明者将所有参与方视图的承诺发送给验证者。 承诺方案是一种密码学原语，允许参与方承诺一个值而不透露它，并在以后打开承诺以显示该值。 承诺 Comm(x) 应该是隐藏的，这意味着它不透露有关 x 的任何信息，并且是绑定的，这意味着以后揭示另一个值 y≠x 并说服验证者它是 Comm(x) 的有效打开在计算上是不可行的。 作为一个具体的例子，一个简单的承诺方案可以从一个抗冲突哈希函数实现，如下所示。

def commit(x: bytes) -> bytes:
   nonce = random(16)
   return sha256(x + nonce)

def verify_opening(x: bytes, nonce: bytes, commitment: bytes) -> bool:
   return len(nonce) == 16 and sha256(x + nonce) == commitment

一旦证明者向每个视图发送了承诺，验证者会随机选择两个参与方，比如 i 和 j，并要求打开他们的视图。 然后，证明者清楚地将选择的视图发送给验证者。

此时，验证者可以了解两个输入 wi 和 wj，以及参与方 i 和 j 发送和接收的消息的完整记录。 验证者检查以下内容：

• 这些视图是对应承诺的有效打开。
• 参与方 i 和 j 诚实地遵循了协议。
• 这两个视图是一致的，这意味着对于两个参与方之间交换的每条消息，两个记录都同意其内容。
• 打开的视图同意该函数的输出为 1。

该方案的可靠性直接基于底层 MPC 协议的正确性。 假设 MPC 协议满足完美的正确性，如果证明者诚实地模拟该协议，则输出将是正确的。 但是，如果证明者试图作弊，那么它必须至少在一个参与方中这样做，因此将至少有一对视图与诚实执行不一致。 验证者选择不一致对的概率为 1/(n2)，这意味着证明者可以成功作弊的概率为 ε=1−1/(n2) 像处理零知识证明时一样，在进行了足够的重复操作后，就可以使健全性误差呈指数级小。

相反，零知识直接基于底层 MPC 协议的隐私性。 足以看到验证者最多知道两个参与方的视图，并且由于假定底层 MPC 协议是 2-私有的，因此验证者无法了解其他参与方的私有输入。 另请注意，了解 wi 和 wj 不会向验证者提供有关 w 的任何信息。

Removing interaction

此协议有一个非常好的属性，即它是公开抛币的，这意味着验证者没有任何主动作用，只是对随机挑战进行采样并将其发送给证明者。 这意味着可以使用标准 Fiat-Shamir 转换使协议变为非交互式的。

改进

尽管上述协议在实践中效率不高，但后来的具体实例化已大大改进了这一基本思想。 效率低下的原因之一是，实际上，证明者必须执行许多轮才能获得合理低的可靠性误差。 这是因为一轮的可靠性误差很高，因为验证者一次只打开两个视图。 作为一个具体的例子，如果 n=8，那么证明者在一轮中成功作弊的概率为 1−1/(82)≈96.4%

通过构建 (n−1)-私有 MPC 协议可以立即进行改进，这样证明者可以安全地向除一个之外的所有参与方打开，而不会丢失零知识。 在这种情况下，验证者只需选择一个参与方来保持私有，并且证明者将所有其他参与方的视图的打开发送出去。 这大大提高了可靠性误差，变为 ε=1n 因为证明者只能在验证者选择的参与方中作弊，这种情况发生的概率为 1/n。 与之前一样，当 n=8 时，成功作弊的概率为 18≈12.5%

应用于后量子签名

由此产生的零知识证明方案具有一些有趣的特性：

• 如果我们使用后量子安全的 MPC 协议，那么由此产生的零知识证明方案也将是后量子安全的，因为转换仅依赖于简单的密码学承诺，而这些承诺可以使用抗冲突哈希函数（例如 SHA3）进行实例化。
• 证明大小与电路大小成线性关系，并且具有非常小的常数，这使得它在实践中对于具有少量门的电路来说是有效的。
• 证明者和验证者的时间复杂度都与电路的大小成线性关系，并且本质上他们做的工作量是相同的。

这使得该方案对于构建后量子签名尤为有趣。 一般来说，要从零知识证明构建签名方案，我们选择一个单向函数 H，该函数是一种容易计算 H(x) 的函数，但是给定输出 y，很难找到输入 x 使得 H(x)=y。 标准示例是将 H 作为密码学哈希函数，然后将关系 R 作为 H 的前像关系。

• 要生成密钥对，随机采样私钥 x，并将公钥计算为哈希值 y=H(x)。

• 要签名消息 m，签名者会使用零知识证明方案证明他们知道一个私有 x 使得 H(x)=y，其中 y 是公钥。 我们可以通过利用 Fiat-Shamir 转换来有效地将消息 m 包含在证明中。 我们让证明者发送给验证者的第一条消息是消息 m，然后像以前一样继续进行正常协议。 通过这种方式，我们获得了一种“依赖于消息的知识证明”，其中签名者证明他们知道公钥的前像，但该证明仅对特定消息 m 有效。 请注意，验证者采样的每个挑战都取决于第一条消息 m，因此该签名不能重复用于其他消息。

• 最后，要验证消息 m 的签名，验证者首先检查证明中包含的消息是否与 m 匹配，然后验证相关的零知识证明。

已经提出了几种具体的签名方案，例如 ZKBoo、Picnic、KKW18 和 FAEST。 值得注意的是，Ligero 零知识证明方案也可以看作是优化后的 Head 中 MPC 转换的实例化，并且可以使用对主动攻击者安全的 MPC 协议来实现亚线性证明大小。

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