一文带你了解多方安全计算
验“金”室
2019年9月6日，人民银行正式发布了《金融科技（FinTech）发展规划（2019-2021）》。截至2020年3月，人民银行已发布云计算、生物识别、分布式账本等多个金融应用规范。在大数据应用方面，基于大数据的支付风险智能防控技术规范已基本完成，对指导金融机构完善支付风控具有重大价值；多方安全计算金融应用技术规范等技术规范也在研制过程中，为实现数据所有权、管理权、使用权分离，提高数据流通价值提供了技术解决方案。
在大数据时代，数据已经成为企业之间竞争的核心竞争力。而数据作为一种新资源，只有流动起来才能发挥其真正的价值。但在流动的过程中，数据的使用权与所有权之间存在着一个重要的矛盾：服务者必须在得到消费者的数据后才能提供服务，而消费者却不希望公开他们的私密数据。
安全计算的作用就是让人们在保护数据隐私的基础上完成计算任务。当多个参与者希望将各自的数据凑在一起形成大数据集并在此基础上进行一定的计算以得到最后计算结果，而同时这些参与者又不希望他人知道自己的数据时，就需要应用多方安全计算（Secure Muti-Party Computation，MPC）。
1982年，姚期智院士曾提出一个“百万富翁”设想 [1]：有两位百万富翁和，他们想知道谁更富有，但又不想对方知道自己有多少钱。为了解决这一问题，姚期智院士提出建立一个通用的框架处理单向函数所涉及的加密、完整性、智能扑克等系列问题，从中发展出了验证其安全性的通用技术。
1986年，姚期智院士又提出了一种基于混淆电路的通用解决方案[2]，进一步验证了多方安全计算的通用可行性，同时也奠定了现代计算机密码学的理论基础。此后，经诸多学者的进一步的研究和创新，多方安全计算逐渐发展成为现代密码学的一个重要分支。
在实际应用中，通过综合运用密码学中混淆电路、不经意传输、密钥分享、同态加密等多种理论和协议，结合计算机工程技术研发出整套多方安全计算系统，能够使整个信息交互计算的过程全程在密文下进行，并且保证计算结果与明文下计算的结果一致。
姚期智院士解释，初期由于计算机的算力无法实现相应的计算，MPC并没有真正运作起来，但是现在，经过了三十多年的发展，“计算机终于足够快，能够使这三十年大家不断改进的方案开始运作起来”。
一、多方安全计算概念
多方安全计算理论是姚期智院士为解决一组互不信任的参与方之间在保护隐私信息以及没有可信第三方的前提下协同计算问题而提出的理论框架。多方安全计算允许多个数据所有者在互不信任的情况下进行协同计算，输出计算结果，并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说，MPC技术可以获取数据使用价值，却不泄露原始数据内容。
多方安全计算根据参与者的数量分为两方（两者）和多方（三者以上）。主流两方安全计算框架的核心用了不经意传输(Oblivious Transfer)和混淆电路（Garbled Circuit）这两种协议。而多方安全计算所使用的则是同态加密（Homomorphic Encryption）、密钥分享（Secret Sharing）等协议。
协议是指有至少两个参与者参加为完成某一任务而制定的一系列明确且完整的计算步骤，协议的参与者必须知道协议的所有步骤并遵循它。以“百万富翁”假设为例，“百万富翁”假设可以抽象为：
在文献[1]中，姚期智院士就“百万富翁”假设提出了一种解决方案：
具体方案如下：
由此和完成了彼此财产的比较，而双方并不知道彼此的具体财产数量。
这一协议构建了一套基础的框架，为未来更多通用技术建立了基础。进一步的，文献[1]中证明了
1.不经意传输
不经意传输协议[3]是密码学的一个基本协议，它使得服务的接收方以不经意的方式得到服务发送方输入的某些消息，这样就可以保护接受者的隐私不被发送者所知道。
最初，不经意传输协定是对于单一秘密而言的，发送者A以1/2的概率向接受者B发送秘密，B收到秘密的概率为1/2，B自己知道是否收到秘密，而A不知道B是否收到秘密。
随着技术的发展，不经意传输协议逐渐演化为：接受者B希望从发送者A提供的n个秘密中获得其中m个而不希望A知道自己想要哪些秘密，同时A也不希望透露其他秘密。
例如：
由于不经意传输协议能够在保护传输双方隐私的前提下传输数据，因此不经意传输协议常常作为设计其他协议的基本模块。
2.混淆电路
混淆电路[2]是姚期智院士的安全两方计算通用协议中的核心技术，用于构造加密版本的电路，以实现所有非电路输出的线路上信息不泄露。当前，混淆电路已发展成构造上层安全协议的密码学工具，被广泛研究。
我们知道，任意函数最后在计算机语言内部都是由加法器、乘法器、移位器、选择器等电路表示，而这些电路最后都可以仅由AND和XOR两种逻辑门组成。一个门电路其实就是一个真值表，例如AND门的真值表就是：
可以看到，只要有了真值表，我们就有办法计算一个电路，也可以通过电路的输出和自己的输入来猜测对方的输入，于是姚期智院士提出了一种想法：
如AND门的真值表经加密变为：
该表称为“混淆电路的混淆表”，类似的也可对于更加复杂的电路构建混淆表。这里需注意的是表中各行应随机排序后存储，否则将因位置而泄露门电路的输入信息。
假设有两个参与方A和B各自提供数据a、b，希望安全的计算约定的函数F(a,b)，那么一种基于混淆电路的两方安全计算协议过程如下：
A的数据安全由混淆电路保证，而B的数据安全由不经意传输保证。上述协议是两方安全计算设计的通用框架之一，之后许多研究以该协议为基础进行优化改进，以设计高效的多方协议，适应现实世界中各类应用场景的特定需要。如文献[4]中对于性能的优化和文献[5]中对于安全性的优化等等。
3.密钥分享
对于各种纯粹由位运算（AND、OR、XOR等）组成的算法，GC效率是比较高的。但有一个问题是，即便一些常见的算术操作（如乘法、乘方等），电路也非常复杂，以乘法为例，一个2位整数的乘法电路涉及8个门的运算，这对GC而言很吃力。而现实中的算法往往更加复杂，这意味着很多常用的算法纯靠GC是难以指望的。而密钥分享（Secret Sharing）[6]则正好对算术操作比较拿手。
密钥分享是信息安全和数据保密中的一项重要技术，它在重要信息和秘密数据的安全保存、传输及合法利用中起着非常关键的作用。密钥分享最初是被设计用来在RSA加密过程中分配密钥，而在多方安全计算被提出后，它在计算方面的性能才被渐渐发觉[7]。
密钥分享的基本思路是：
这样的话，密钥分享便保证了计算过程中各个参与方看到的都是一些随机数，但最后仍然算出了想要的结果。
最简单的例子：
但有时候我们并不希望必须凑齐n个人才能解开，一方面是因为数据是分散在多个人手里的，要是有一个人的数据缺失，那数据就无法恢复，另一方面我们不需要这么强的安全性，比如我们可以相信10个人里面至少一半是好人，那么我们只需要保证少于4个人时无法将数据解开就行了。这种密钥分享叫做阈值密钥分享（Threshold Secret Sharing）。
此外，在允许一定的信息交换时，这一方案也能够执行乘法等更加复杂的运算。
4.同态加密
严格来说，同态加密并非狭义的安全计算的范畴，只是其所实现的目标与安全计算有诸多类似之处，因此广义上安全计算也可将其囊括在内。相较于混淆电路和秘密分享，同态加密的思路更为直观：直接将原文加密，然后在密文上进行各种运算，最终得到结果的密文。
很多众所周知的公钥加密方案其实都具有同态的性质，只是它们都只支持部分同态，也就是说它们只支持在密文上进行加法或乘法操作，但不能既做加法又做乘法。比如著名的RSA加密方案，支持的是同态乘法；1999年出现的著名的Paillier加密方案支持的是同态加法；上文提到的Shamir的方案也是支持同态加法的。而真正可用的全同态加密直到2009年才被当时的斯坦福博士Gentry提出[8]。
Gentry的全同态加密方案是基于理想格构造的，是一个含有噪音的方案，加密时往里添加噪音，主要是为了进一步提高安全性。而其缺点在于计算量极大，且由于噪声的存在密文会在计算过程中不断膨胀，甚至失真。为解决这些问题，学者们又提出了许多改进方案，目前最为理想的方案以Gentry-Sahai-Waters为代表的、基于带误差学习或环上带误差学习困难问题构造全同态加密方案[9]，该方案具有加密解密复杂度低、密文膨胀率小、不需要运用密钥等优点，但其效率仍未达到实用要求。
目前，部分同态技术已在一些统计类的场景中得到了应用，如计算平均值等，而全同态加密技术目前还处于工程化研究阶段，相信未来会有很多的应用落地。
二、应用场景
不论是在全球范围内流动的资源、货物、资本、技术、人、数据或是观念，还是由于各种现实世界摩擦造成的冲突、监管和制约等，都影响着各方对于经济、文化、教育、医疗、公共管理等各行各业信息的判断和使用。
数据的流动和协同分析在各行业都有着极其重要的价值，也催生了众多的应用需求：
1. 金融业
金融本身就是一个经营风险的行业，风控与征信是金融业管理风险的重要手段。传统数据分析模式面临的难题是，数据采集范围局限、平台上传数据积极性低、更新不及时、接入门槛高等。而MPC征信模式可支持的数据本地采集方式，弥补了传统征信数据老旧、风险评估状况滞后的缺陷，更能支持数据类型多样化的协同计算，将数据分析范围从金融信贷数据，扩展至医疗、保险、交通等行业的征信评价体系中，以获得更为广泛的社会信用评价画像。
2. 制造业
制造业的数字化改造已经为各类制造业企业带来了更精准、更先进的工艺以及更优良的产品。而对行业整体供给数据、生产频度、维修情况等的综合分析，能为行业降本增效提供有力数据支撑，减少产能过剩之“痛”。制造业全球分布的特性以及相对金融业较低的信息技术运用程度，使得数据的流通和共享存在一定阻力。MPC技术在制造业的运用，可以使数据互操作脱离国家边境线的限制，为全球制造供应链优化提供保障；通过对行业整体数据或市场需求情况的深度挖掘和多维护剖析，可以准确地配置全球生产体系，更加灵活地安排各地市场产品的投放，随时把握产业动向。
3. 医疗业
医疗数据的敏感性使得医疗机构、保险、药企、医疗设备供应商之间难以实现低成本、高效的医疗信息数据交换和共享，进而导致行业内大量的数据资源没有得到有效使用和深度分析。MPC技术在医疗行业的应用，可以在相对封闭的医疗数据参与方间建立起安全可信的数据交换网络，实现医疗数据价值的最大效用。
4. 电子政务
以电子选举为例，这是安全多方计算的典型应用，得到了研究者的广泛重视。在电子选举中，通过安全多方计算可以实现：计票的完整性、投票过程的鲁棒性、选票内容的保密性、不可复用性和可证实性。此外，在多方参与需要公正裁判的场景，均可用安全多方计算协议来代替裁判。例如，安全多方计算使网上拍卖成为现实，电子拍卖的大部分方案都采用可验证秘密共享协议或使用其思想，具备灵活性、保密性、鲁棒性和可验证性。
●参考文献 ●
Andrew C. Yao. "Protocols for secure computation." Foundations of Computer Science, 1982. SFCS '08. 23rd Annual Symposium on IEEE, 1982.
Andrew C. Yao. "How to generate and exchange secrets." Foundations of Computer Science, 1986., 27th Annual Symposium on. IEEE, 1986.
S. Even, O. Goldreich, and A. Lempel, “A Randomized Protocol for Signing Contracts.”
Kolesnikov, Vladimir, and Thomas Schneider. "Improved garbled circuit: Free XOR gates and applications." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2008.
《Covert Security with Public Verifiability: Faster, Leaner, and Simpler 》
Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.
Beaver, Donald, and Shaft Goldwasser. "Multiparty computation with faulty majority." Conference on the Theory and Application of Cryptology. Springer, New York, NY, 1989.
Gentry , Craig, and Dan Boneh. A fully homomorphic encryption scheme. Vol. 20. No. 09. Stanford: Stanford University, 2009.
Gentry C, Sahai A, Waters B. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[M]// Advances in Cryptology – CRYPTO 2013. Springer Berlin Heidelberg, 2013.
更多精彩内容
FCC30+
长按左边二维码
关注我们不迷路