安全多方计算新突破！阿里首次实现“公开可验证” 的安全方案

2019 年 3 月 12 日 阿里技术

阿里妹导读：近日，阿里安全双子座实验室与马里兰大学等高校合作的论文《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景点游玩，希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：

1. 小淘不希望向旅行社泄露“我准备去A景点”这一信息；
2. 旅行社只希望出售小淘出钱购买的那份资料，而不泄露小淘未购买的N-1份资料；

粗看起来这种隐私条件似乎是无法满足的：旅行社只要把景点A的资料给到小淘，就必然了解了“小淘正在关注A景点”这一信息；除非旅行社把所有N份资料都给出，但是这又违背了旅行社的利益；

但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之，在OT协议中，旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给小淘；小淘可以从密文中解密出A的资料，而无法解密出其他N-1份资料。

以下以N=2为例，基于Diffie-Hellman密钥交换协议，给出一种1 of 2 OT实现方法的非正式描述；其中S（Sender）=旅行社，R（Receiver）=小淘，S拥有两份资料，R希望取得其中的；

1. S秘密生成随机数a; R秘密生成随机数b；
2. S将发送给R; R将发送给S；

3. S计算；

4. S以为密钥加密, 以k1为密钥加密,将和发送给R；

5. 由于, 因此R可以计算出，并解密出，但R无法计算，因此无法解密出。

如果R希望取得，只需把第2步中的改为即可。

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的安全两方计算协议过程可以非正式的描述如下：

1. A把F进行加密，得到GC表示的函数; （注意这里A是电路的生成者，所以他了解每根wire的密钥）；

2. A把自己的输入a使用第1步中对应的wire密钥加密，得到Encrypt(a)；
3. A将Encrypt(a)、发送给B；

4. A将B的输入b使用第1步中对应的wire密钥加密，得到Encrypt(b)，并将Encrypt(b)发送给B；
5. B拥有完整的GC和输入，因此可以运行电路得到加密的输出；
6. A把输出wire的密钥发给B，B解密得到最终结果F(a,b)；
7. 如果A需要的话，B再把(a,b)发给A；

细心的同学一定会指出：第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方案的非正式描述：

1. A选择两个随机种子s1和s2， B和A运行OT随机选择其中一个（不妨设B获取了s1）；
2. A使用s1和s2分别生成GC1和GC2；
3. B和A运行OT获取GC1中B输入wire的加密值（我们后面可以看到GC1不会真正被使用，因此这里可以不与b对应，比如是任意常数值的密文）；
4. B和A运行OT获取GC2中B输入wire对应的b的加密值；
5. A对GC1进行Hash，并把Hash发给B；
6. A对GC2进行Hash，并把Hash发给B；
7. A对上述所有流程进行签名，并把签名发送给B；
8. B由于有s1，因此可以自行生成GC1，可以自己模拟第3步和第5步；如果结果与A发的不一致，则公布相关签名作为A作恶证据。如果一致，就用GC2进行真实计算。

可见，A如果作恶，总有50%的概率被B抽查到（因为A不知道B到底掌握了哪个GC的随机种子）。因此理性的A会选择不作恶，忠实的执行安全多方计算协议。

需要再次强调的是，为便于理解，所有的协议都仅仅是非正式描述，有兴趣进一步研究细节的同学欢迎参阅我们的论文【1】。

总结

我们与马里兰大学等高校合作，首次实现了一种“公开可验证(PVC)” 的安全两方计算方案，这种方案的性能接近半诚实方案，同时其PVC特性能够对作弊行为形成威慑力，令其具有远强于半诚实模型的安全性，具有很高的实用价值。

参考资料：

[1] https://eprint.iacr.org/2018/1108

[2] Yao.A.C. How to Generate and Exchange Secrets. FOCS 1986: 162-167

[3] Asharov G , Orlandi C . Calling Out Cheaters:Covert Security with Public Verifiability, Advances in Cryptology – ASIACRYPT 2012. Springer Berlin Heidelberg, 2012.

[4] Kolesnikov V , Malozemoff A J . PublicVerifiability in the Covert Model (Almost) for Free, Advances in Cryptology – ASIACRYPT 2015. Springer Berlin Heidelberg, 2015.