一篇文章揭示了跨链、密钥管理和合约隐私背后的技术

出品 | 区块链大本营，ARPA

安全多方计算已被公认为区块链发展过程中重要的密码学技术和工具，在交易或合约隐私保护、钱包密钥管理、跨链交易、区块链扩容等问题上发挥了独特的作用. 影响。

但是由于其具体技术涉及到很多密码算法和数学背景知识，所以在开始学习和发展相应领域的时候会手足无措，毫无头绪。

本文希望在有限的篇幅内，将安全多方计算的概念串联成一个系统，让读者快速学习，搭建知识网络。 同时介绍了安全多方计算应用最广泛的两个分支：“基于混淆电路的安全多方计算”和“基于秘密共享的安全多方计算”。

在安全多方计算（Secure Multi-Party Computation）中，我们已经描述了安全多方计算如何解决数据价值与隐私保护之间的矛盾，以及姚期智先生如何提出这个问题，以及如何它在生活中的实践中发挥作用。

那么在介绍安全多方计算的进一步应用以及如何与区块链相结合之前，我们先开一个“过程”深入安全多方计算技术，对其进行简单明了的演示实施技术。

通过这些例子，我们可以看出安全多方计算与明文计算的区别，这种密码方案是如何实现其声称的功能的，不同实现方式之间的关系和区别，以及安全多方计算与其他密码算法之间的关系。 本文会涉及到一定的密码学基础算法和数学内容，但这并不影响理解安全多方计算本身的思路。

安全多方计算的提议

Andrew C. Yao 先生在 1982 年发表的《安全计算协议》一文中提到“两个百万富翁想知道谁更富有以太坊私钥碰撞软件，但是，他们又不想获得关于对方财富的额外信息。他们应该如何进行这次对话？”。

这种“百万富翁困境”是安全多方计算的一个特例。 广义安全多方计算是 n 方分别持有数据 x1, x2, ... xn 的交互协议。 协议希望在输入上计算函数y1,y2,...,yn=f(x1,x2,...xn)，让第i方只得到yi而没有其他信息。

这个定义似乎并不能带来直观的认知以太坊私钥碰撞软件，我们不妨换个角度思考：在一个理想世界（ideal world paradigm）中，存在一个完全中立、不与任何人合谋的可信第三方。 每个人都把数据给他，然后他进行计算并相应地分配结果。 这样就完成了安全计算。

那么在现实世界（real world paradigm）中，安全多方计算协议就是在没有这个可信第三方的情况下完成同样的任务。 这为人们思考安全多方计算的能力和缺陷提供了更简洁的参考。

例如，它不能保证输入方提供了正确的输入，也不能普遍隐藏函数f的信息（代码混淆）。 但另一方面，是否能保证所有参与者能或不能同时得到计算结果（公平性），以及当参与者中的几方合谋或试图窥探他人的输入信息时，能不能保证？ , 计算还安全吗？ （鲁棒性），这些问题是密码学家在构造不同的安全多方计算协议时关心的重点。

现实中不仅有一个协议，也没有几个相同的类型，而是一系列效率不同、安全模型不同、实现方式不同的密码协议。 这也是安全多方计算中最复杂和最引人注目的部分。 在本文中，我们将首先介绍安全多方计算的两个最常用的分支——“基于混淆电路的安全多方计算”和“基于秘密共享的安全多方计算”。 ”。

基于混淆电路的安全多方计算

姚期智先生在提问的文章中已经给出了解决此类问题的方法：乱码电路与不经意传输的结合。

这个协议主要适用于双方的安全计算，现在有很多工作将这个算法扩展到多方（n>2），但是我们会看到它自然只适用于双方，但是两个-派对计算已经可以帮助我们解决许多具体问题。

这项技术之所以被称为“电路”，是因为它首先将需要计算的函数表达为布尔电路，就像现代集成电路中的逻辑一样，其基本单元是一个逻辑门，每个逻辑门被定义为两个输入输出，但可以有多个扇出（输出可以是下一阶段多个门的输入）。

如果确定了电路的拓扑关系，则可以通过输入输出连接的顺序来实现整个电路的计算。 那么我们将函数的安全多方计算实现为一个门的实现，也就是说我们构建了一个可以等同于现实生活中的理想世界的“安全门”，那么我们就可以泛化整个电路。 改造。

姚芝芝先生提供的布尔电路混淆（Garbling）技术也是采用了不经意的传输。 Oblivious Transfer是一种可以独立使用的加密工具。 我们以1-out-of-2 oblivious transfer为例（如下图所示），其核心目的是接收方（Bob）想要获取发送方指定的两个信息（m1，m2）之一（Alice）（如mb），却无法获取对方的信息。 另一方面，Alice 无法知道 b 的具体值。

无意传播

通过上图，我们可以得出一个结论：任何有效的不经意传输协议都意味着可以基于它构造一个安全的两方计算协议。

然后我们可以观察这是如何实现的。 如果Alice是“电路制造者”，Bob是“电路计算者”，双方想共同计算f(x,y)，其中x来自Alice，y来自Bob。那么Alice负责提供电路生成，不失一般性，我们以一个逻辑与门为例，我们为每个线信号（Wire）选择一对键

, 分别代表该信号的 0 和 1。 之后，我们使用双密钥对称加密函数得到表1，称为混淆门。 至此混淆电路就构建完成了。

与门手势混淆

混淆与门对照表

Alice 将混淆电路传递给 Bob，并将 x 输入对应的密钥值。 这时候Bob可以通过无意的传输获得自己输入的y对应的key值。 然后，经过解密尝试，Bob 得到了相应的结果。 当使用满足 IND-CCA 方案的加密算法时，当 Bob 试图解密错误的密文时，解密算法将拒绝它。

正如第一部分所说，SMC保证的是一方的输入不能被另一方获得，而不是输入不能从输出中推断出来。

安全两方计算

这就是混淆电路的基本流程。 然而，这种结构仍然非常初级且效率低下。 这篇文章发表后，研究工作逐渐提出了很多改进。 该分支机构的技术在安全性和运行效率方面都得到了极大的提升，使实用变得可行。

一些比较重要的技术包括 Free-XOR，Half AND，它降低了特殊逻辑门的成本，以及 Point-and-permute，Row reduction，它降低了循环复杂度。

在应用方面，最先实现的是2004年发布的Fairplay系统，2009年Asiacrypt的一篇文章使用混淆电路实现了AES的安全两方计算版本，使得AES的私钥在使用过程中无需恢复计算过程。 ，这得益于 AES 中的大多数 XOR 门可以使用 Free XOR 技术来减少消耗。