共计 3627 个字符，预计需要花费 10 分钟才能阅读完成。
阿里妹导读：近日，阿里安全双子座实验室与马里兰大学等高校合作的论文《Covert Security with Public Verifiability: Faster, Leaner, and Simpler》【1】被欧洲密码年会(Eurocrypt)2019 接收。这是国内公司在安全多方计算领域的第一篇顶会论文（Eurocrypt2018 只有 3 篇大陆作者论文，难度可见一斑）。
今天，我们邀请阿里高级安全专家鸿程，深入解读业界首个“公开可验证(PVC)”的安全两方计算方案。
安全多方计算介绍
安全多方计算（Secure Multi-Party Computation，MPC）于 1986 年由姚期智院士提出【2】。安全多方计算协议允许多个数据所有者在互不信任的情况下进行协同计算，输出计算结果，并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说，MPC 技术可以获取数据使用价值，却不泄露原始数据内容。
互联网已经完成了从 IT 时代向 DT 时代的转变，数据已经成为 DT 时代企业的核心竞争力。数据作为一种新能源，只有流动起来才能产生价值。不过，大多数企业考虑到数据安全和个人隐私等问题，对数据共享都非常谨慎。而 MPC 对打破数据孤岛，实现数据的可控共享，具有重要的理论和现实意义。
MPC 方案主要可分为基于混淆电路 (Garbled Circuit，GC) 和基于秘密共享两种。本文主要关注 GC 类方案。
不经意传输(Oblivious Transfer)
我们首先介绍一种基础的安全多方计算协议：不经意传输(Oblivious Transfer, OT)。
来看一个例子：假设某旅行社拥有 N 个景点的旅游资料，小淘想去其中的 A 景点游玩，希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：
小淘不希望向旅行社泄露“我准备去 A 景点”这一信息；
旅行社只希望出售小淘出钱购买的那份资料，而不泄露小淘未购买的 N - 1 份资料；
粗看起来这种隐私条件似乎是无法满足的：旅行社只要把景点 A 的资料给到小淘，就必然了解了“小淘正在关注 A 景点”这一信息；除非旅行社把所有 N 份资料都给出，但是这又违背了旅行社的利益；
但是神奇的 OT 可以让交易在这种“不可能的条件”下达成。简而言之，在 OT 协议中，旅行社把他拥有的 N 份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给小淘；小淘可以从密文中解密出 A 的资料，而无法解密出其他 N - 1 份资料。
OT 除了可以直接用于构造 MPC 方案之外，也是 GC 等许多 MPC 方案的基石。
混淆电路
我们知道，任意函数最后在计算机语言内部都是由加法器、乘法器、移位器、选择器等电路表示，而这些电路最后都可以仅由 AND 和 XOR 两种逻辑门组成。一个门电路其实就是一个真值表，例如 AND 门的真值表就是：
例如其中右下格表示两根输入线 (wire) 都取 1 时，输出 wire=1：即 1 AND 1 = 1。
假设我们把每个 wire 都使用不同的密钥加密，把真值表变成这样：
例如其中右下格表示如果门的输入是 b 和 d，那么输出加密的 f(密钥是 b 和 d)。这个门从控制流的角度来看还是一样的，只不过输入和输出被加密了，且输出必须使用对应的输入才能解密，解密出的 f 又可以作为后续门的输入。这种加密方式就称为“混淆电路(Garbled Circuit，GC)”。
将电路中所有的门都按顺序进行这样的加密，我们就得到了一个 GC 表示的函数。这个函数接收加密的输入，输出加密的结果。
假设有两个参与方 A 和 B 各自提供数据 a、b，希望安全的计算约定的函数 F(a,b)，那么一种基于 GC 的安全两方计算协议过程可以非正式的描述如下：
细心的同学一定会指出：第 4 步中 A 怎么可以接触 B 的输入 b 呢？这不是违背了安全多方计算的假设吗？这里就需要使用 OT，A 扮演 Sender，B 扮演 Receiver，让 B 从 A 处得到 Encrypt(b)，却不向 A 透露 b 的内容。如图所示：
需要注意的是，上述流程只是最原始的 GC 方法的不严谨描述，GC 后续还有 Point & Permute、Free XOR、Half Gates 等多种细节优化，随着最近几年的研究进展，GC 的性能已经差不多可以实用了。以求两个百万维向量的汉明距离 (Hamming Distance) 为例（应用场景是两份数据求相似度，却互相不泄露数据内容），这样的安全两方计算已经可以在 1.5 秒左右完成。
安全多方计算的安全模型
半诚实行为模型与恶意行为模型
更细心的同学还会进一步提出问题：“怎么确保 A 给 B 的
就是一个正确的 GC 呢？例如 A 和 B 商定要比 a 和 b 的大小，商定了 F(a,b)=a>b?1:0，但是 A 可以制作一个别的函数的 GC，例如 F(a,b)= b 的第 1 个比特，这样显然是会侵害 B 的隐私的，但是由于函数是以 GC 形式发给 B 的，B 是没有办法发现这个问题?”
这确实是一个安全问题，事实上，GC 还存在如 selective failure 等其他更多的安全问题。在介绍解决方案之前，我们需要先定义安全多方计算的安全模型。
安全多方计算的安全模型包含多个角度的内容，在上述上下文中，我们关注的是其中的“行为模型”，即参与方可能进行何种行为以获取其他方的隐私。常见的行为模型包括“半诚实(Semi Honest)”和“恶意(Malicious)”两种。前者假设所有参与方都是忠实的按照协议步骤进行执行，只是想通过协议内容推测其他方的隐私，而后者假设恶意参与方为了获取其他方的隐私可以不遵循协议内容。
用扑克牌打个不严谨的比方，半诚实的牌友会试图从自己的手牌和已经打出的牌来推测他人的手牌，但是还是遵循扑克牌规则的；而一个恶意的牌友则换牌、偷牌等手段无所不用。
可见，本节开始提出的问题属于恶意行为的范畴，而原始的 GC 只能说在半诚实行为模型下是安全的，无法抵御恶意行为攻击。有许多对 GC 方案的改进方案可以达到恶意行为模型下的安全性，但是它们都需要付出很大的性能代价：仍然以求两个百万维向量的汉明距离为例，其中最快的方法也需要 10 秒 +，比同等的半诚实方案慢 7 倍以上。事实上，经过我们的调研，若想真正的实现支持大规模数据的 MPC 产品，基本上只能考虑半诚实方案。这严重影响了安全多方计算的实用性。
公开可验证 (Public Verifiable Covert, PVC) 行为模型
PVC 是在半诚实、恶意之间的一种折中。其主要思想是：每个参与方的所有行为都自动带有类似签名的机制以供其他参与方存证。假设某个参与方实施恶意行为，那么其他参与方可以有
的概率发现（
称为威慑因子，一般 >=50%，不能 100% 发现，因为 100% 那就直接满足恶意行为模型了）这一恶意行为，并将该行为及其签名公开，令作恶者承受名誉损失。考虑到名誉对一个数据所有者的重要性（例如此后可能再也找不到合作），50% 左右的威慑力已经足以让理性者不考虑作恶。
PVC 模型最开始是由学者在 Asiacrypt2012【3】提出，Asiacrypt2015【4】上也有学者提出相关的改进方案，但是这些方案不仅效率较低，而且只有复杂的理论描述，实现可能性低。我们提出的新型 PVC 方案不仅协议简洁，性能有大幅提升，而且首次进行了完整的代码实现。仍然以求两个百万维向量的汉明距离为例，使用我们威慑因子为 50% 的 PVC 方法大概只需要 2.5 秒。
以下仍假设有两个参与方 A 和 B 各自提供数据 a、b，希望安全的计算约定的函数 F(a,b)，以威慑因子
=50% 为例，给出我们的 PVC 方案的非正式描述：
A 选择两个随机种子 s1 和 s2，B 和 A 运行 OT 随机选择其中一个（不妨设 B 获取了 s1）；
A 使用 s1 和 s2 分别生成 GC1 和 GC2；
B 和 A 运行 OT 获取 GC1 中 B 输入 wire 的加密值（我们后面可以看到 GC1 不会真正被使用，因此这里可以不与 b 对应，比如是任意常数值的密文）；
B 和 A 运行 OT 获取 GC2 中 B 输入 wire 对应的 b 的加密值；
A 对 GC1 进行 Hash，并把 Hash 发给 B；
A 对 GC2 进行 Hash，并把 Hash 发给 B；
A 对上述所有流程进行签名，并把签名发送给 B；
B 由于有 s1，因此可以自行生成 GC1，可以自己模拟第 3 步和第 5 步；如果结果与 A 发的不一致，则公布相关签名作为 A 作恶证据。如果一致，就用 GC2 进行真实计算。
可见，A 如果作恶，总有 50% 的概率被 B 抽查到（因为 A 不知道 B 到底掌握了哪个 GC 的随机种子）。因此理性的 A 会选择不作恶，忠实的执行安全多方计算协议。
需要再次强调的是，为便于理解，所有的协议都仅仅是非正式描述，有兴趣进一步研究细节的同学欢迎参阅我们的论文【1】。
总结
我们与马里兰大学等高校合作，首次实现了一种“公开可验证(PVC)”的安全两方计算方案，这种方案的性能接近半诚实方案，同时其 PVC 特性能够对作弊行为形成威慑力，令其具有远强于半诚实模型的安全性，具有很高的实用价值。
本文作者：鸿程阅读原文
本文来自云栖社区合作伙伴“阿里技术”，如需转载请联系原作者。
