走近隐私计算 | 多方安全计算的发展及应用
前言
隐私计算作为保障数据价值挖掘过程中隐私安全的技术集合，能够在释放数据价值的同时，实现数据处于加密状态或非透明状态下的流通与计算，以达到各参与方隐私保护的目的。
本系列“走近隐私计算”将陆续带来隐私计算的几种技术路径（多方安全计算、同态加密、零知识证明、可信执行环境、联邦学习等）的整体介绍，以及部分经典论文的学术研读。
本期将作为“走近隐私计算”系列的第三期，浅谈多方安全计算的发展及应用。
第一期《走近隐私计算 | 联邦学习中基于隐私集合求交(PSI)的样本对齐》：介绍联邦学习的概念以及三种基本场景。
第二期《走近隐私计算 | 从(全) 同态加密到同态构型》：介绍同态加密的整体发展路径，到“同态构型”的技术突破。
第一个多方安全计算协议：百万富翁问题最早由姚期智在1982 年提出问题 [1]可以描述为
有两个富翁，他们想要比较一下谁更有钱，但是又不想让另外一 方知道自己到底有多少财产。
为了解决这个问题，姚期智提出了第一个两方安全计算模型，即两个参与方协商一个电路，并将电路混淆，利用各种密码学原语在混淆电路中完成计算，得到最后的计算结果，这个两方安全计算模型也称为混淆电路。
多方安全计算 (MPC) 是在没有可信第三方的前提下，计算一个约定函数的问题。在多方安全计算的场景中，每个参与方只能得到约定函数的输出，且不能得到输出外的其他参与方的隐私信息 (如其他各个参与方的隐私输入等)。接下来将主要介绍多方安全计算的执行过程：
图2 多方安全计算的执行过程
全体参与方选择公开参数和需要一起计算的函数，部分场景下各参与方需要对各自的输入进行秘密分享，并完成系统初始化；
电路生成方根据需要计算的函数生成布尔电路，并利用混淆技术对电路进行混淆，得到混淆电路，并公开混淆电路的部分参数；
全体参与方输入计算数据/计算得到的秘密分享值，根据混淆电路的部分参数，逐个逻辑门 (异或门和与门) 完成函数运算，其中在计算过程中大规模会使用不经意传输 (OT 协议)；
全体参与方在协议执行完毕后得到最后的输出/全体参与方给出自己的秘密分享值，重构输出。
其中秘密分享 (secret sharing) 和不经意传输 (OT) 是构建 GC 混淆电路的两大重要原语。
我们知道，异或门和与门可以表示任意的布尔逻辑电路，当需要计算一个函数时，我们通常是让所有参与方确定一个计算电路，随后将该计算电路的每个逻辑门进行混淆 (对异或门和与门进行混淆)，并生成混淆电路。
所有参与方在生成的混淆电路上完成多方安全计算，而执行混淆电路协议等主要开销在于传输加密门所需等带宽以及生成和计算加密表所需的资源，带宽是执行混淆电路协议的主要代价，由此可以看出，优化异或门和与门的性能变得至关重要。
表 1 给出了异或门和与门的主要优化技术。在最早的姚氏电路中，单个异或门和单个与门都分别需要传递四条数据，通信和计算开销太大，后期通过不断的优化，做到了全部的异或操作在本地就可以实现，而与门的计算只需要两条数据量 (使用 half gate) 技术。
▼表1 异或门/与门优化
同时因为GRR3 方案与 half gates 方案具有非常好的兼容性，half gates 结合 GRR3 方案可以让各用户在计算与门时，将两条数据集缩减为一条。这样一来全部的异或门可以不需要交互，所有参与方本地就可以计算，而与门的计算中通信和计算开销也将大大降低。
姚氏混淆电路 (GC) 被认为是 MPC 的主要技术，但是最早提出的混淆电路技术的开销过大，同时也仅支持两个参与方的计算，无法很好地扩展到多方环境并应用于实际中，目前大部分的方案都是在混淆电路的基础上进行优化升级的。
目前大部分的工作主要集中在将两方扩展到多方环境，并提高效率 (降低通信轮数，减少通信开销)，如表 2，是目前半诚实模型下已经提出的多方安全计算模型。
▼表2 多方安全计算传统方案
其中通信轮数表示各个参与方在执行多方安全计算协议时需要交互的次数，常轮数指各个参与方可以在规定的轮数下完成协议的执行，和电路深入，用户输入等指标均无关。
目前最佳的多方安全计算模型是多个用户可以通过两轮的交互完成最后的计算，得到最后的计算结果。著名的方案主要在图1中进行了呈现，其中 GMW 和 BGW 在 Yao 电路的两方计算基础上扩展到多方计算，并将 Yao 中仅支持布尔函数扩展到了同时支持布尔函数和算术电路运算，但是需要有一定额外的通信开销，后来 BMR 在 GMW 与 BGW 的基础上优化了布尔函数的轮数，也是目前使用最广泛的多方安全计算，可以实现在规定轮数的交互内完成函数的安全计算。
隐私集合求交(PSI)是多方安全计算研究中的热点之一，与其他多方安全计算协议相比，使用通用型算法实现PSI与现有PSI协议性能上差距较大，且PSI产生了许多实际落地应用。在往期【走近隐私计算 | 联邦学习中基于隐私集合求交(PSI)的样本对齐】中，有介绍PSI的定义、实际应用和具体方案。感兴趣的小伙伴可以戳上方链接查看。
图3 集合交集
目前有很多科技公司提出了适应于不同场景下的PSI协议，比如微众FATE 提出了基于隐私保护的样本ID匹配，同盾提出了基于布隆过滤器的样本过滤协议，百度提出了基于MesaTEE的PSI协议等。
大部分的PSI协议目前广泛应用于数据库中的数据搜索中，根据隐私保护需求，可以分为数据源隐私保护 (保护参与方的原始数据集) 和查询条件保护 (保护查询请求方发起的对特定数据库的查询请求) 等。
在多方安全计算提出的后来二十年中，多方安全计算仅仅只是停留在理论应用层面。随着二十一世纪计算机计算性能的提升，使得构建一个可用的多方安全计算协议变得可行。
2004 年 Fairplay [2] 给出了第一个通用安全多方计算系统的实现，但是该安全多方计算系统的可扩展性极差。
在文献 [2] 的实验报告中最多测试的计算两个已排序数组的中位数，其中每个参与方的输入是十个已经完成排序的十六位数字，需要执行4383个门电路，执行时间超过7秒，其中两个参与方通过局域网方式连接。
”
与此同时，在后面几十年的技术发展中，多方安全计算技术已经在实验和使用方面已经取得了重大成功，目前已经有许多公司专注于提供基于多方安全计算的解决方案，下面将列举多方安全计算的几个应用领域：
一、拍卖过程
拍卖过程中对隐私的需求是众所周知的，实际上对于所有的参与者 (包括投标人和卖家) 而言，投标的隐私是非常重要的。
在拍卖过程中，需要遵循的几个要求：
◎ 首先投标人的投标价值必须对其他几个潜在投标人保密，以防止其他投标人在拍卖过程中作弊，让整体出价流程不公平
◎ 其次每个拍卖人的出价应该得到保密
◎ 最后拍卖本身必须正确进行，同时将物品卖给出价最高的投标人。
以上一些特性都可以使用多方安全计算技术来进行设计，多方安全计算不但可以保护每个拍卖人的隐私，还可以保证拍卖人在拍卖过程中的各个行为的合法性，最后多方安全计算会通过每个拍卖人的输入来完成计算，并输出最高投标人的信息。
二、安全的机器学习
多方安全计算技术在机器学习的推理和训练阶段也同样可以用来保护隐私数据， 主要集中在两个方面的研究，主要是模型参数的保护和训练过程中每个参与方数据的保护。
■ 第一个方面是不经意的模型推理，允许客户端向已经完成模型训练的服务器提交请求，同时对服务器保持请求隐私，对客户端保持模型隐私，在这种情况下，多方安全计算的输入是来自服务器的私人模型和来自客户端的私有测试输入，而输出是对模型的预测。最近的工作主要有 MiniONN(Liu 等人)[8]。
目前，常见的基于安全多方计算的隐私保护机器学习解决策略有：◎ 基于混淆电路、不经意传输等技术的隐私保护机器学习协议, 并执行两方安全多方计算协议来完成激活函数等非线性操作计算。典型的两方隐私保护机器学习协议包括TASTY[10]，ABY[11]，SecureML[12]，MiniONN [13]， DeepSecure [14]和GAZELLE [15]等。
图4 基于两方∕安全多方计算的隐私保护机器学习发展历程[25]
图5 多方参与的隐私保护机器学习相关方案的发展历程[25]
三、其他研究领域
除了以上的几个应用外，用多方安全计算技术来实现隐私的应用还有很多。比如保护隐私的网络安全监控[3]，被加密的电子邮件的垃圾邮件清理过滤[4]，基因的隐私保护[5]，广告转换[6] 等。
多方安全计算完美地解决了一组互不信任的参与方之间协同计算且保护隐私的问题，它确保了输入的独立性和隐私性，计算的正确性，已悄然成为隐私计算中的主要技术之一。
多方安全计算最早仅停留在理论研究阶段，随着计算机算力和运行效率的显著性加强，多方安全计算技术也逐渐被部署到各种服务中，为保护数据的安全自由流通和开放共享提供了一条重要的技术路径。
参考文献
[1] Yao, A. C.-C. 1982. “Protocols for Secure Computations (Extended Ab- stract)”. In: 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press. 160–164.
[2] Malkhi, D., N. Nisan, B. Pinkas, and Y. Sella. 2004. “Fairplay-Secure Two- Party Computation System”. In: USENIX Security Symposium.
[3] Burkhart, M., M. Strasser, D. Many, and X. Dimitropoulos. 2010.“SEPIA: Privacy-preserving aggregation of multi-domain network events and statis- tics”. In: Proceedings of the 19th USENIX Security Symposium. Washing- ton, DC, USA: USENIX Association.
[4] Gupta, T., H. Fingler, L. Alvisi, and M. Walfish. 2017. “Pretzel: Email en- cryption and provider-supplied functions are compatible”. In: Proceedings of the Conference of the ACM Special Interest Group on Data Communica- tion (SIGCOMM). ACM. 169–182.
[5] Wang, X. S., Y. Huang, Y. Zhao, H. Tang, X. Wang, and D. Bu. 2015a. “Efficient Genome-Wide, Privacy-Preserving Similar Patient Query based on Private Edit Distance”. In: ACM CCS 15: 22nd Conference on Computer and Communications Security. Ed. by I. Ray, N. Li, and C. Kruegel: ACMPress. 492–503.
[6] Kreuter, B. 2017. “Secure MPC at Google”. Real World Crypto.
[7] Huang, Y., D. Evans, and J. Katz. 2012a. “Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?”In: ISOC Network and Distributed System Security Symposium –NDSS 2012. The Internet Society.
[8] Liu, J., M. Juuti, Y. Lu, and N. Asokan. 2017. “Oblivious Neural Net- work Predictions via MiniONN Transformations”. In: ACM CCS 17: 24th Conference on Computer and Communications Security. Ed. by B. M. Thu- raisingham, D. Evans, T. Malkin, and D. Xu. ACM Press. 619–631.
[9] Evans. 2017. “Privacy-Preserving Distributed Linear Regression on High- Dimensional Data”. Proceedings on Privacy Enhancing Technologies. 2017(4): 248–267.
[10] HeneckaW,KöglS,SadeghiAR,etal．TASTY:Toolfor automatingsecuretwoＧpartycomputations[C]∕∕Procofthe 17thACMConfonComputerandCommunicationsSecurity． NewYork:ACM,2010:451462
[11] DemmlerD,SchneiderT,ZohnerM．ABYＧaframeworkfor efficient mixedＧprotocol secure twoＧparty computation [C∕OL]∕∕ProcofNetworkandDistributedSystemSecurity Symp．Reston,VA:InternetSociety,2015:115．DOI: 10．14722∕ndss．2015．23113
[12] MohasselP,Zhang Y．SecureML:A system forscalable privacyＧpreserving machinelearning [C]∕∕Proc of2017 IEEESymponSecurityandPrivacy(SP)．Piscataway,NJ: IEEE,2017:1938
[13] LiuJian,JuutiM,LuYao,etal．Obliviousneuralnetwork predictionsvia minionntransformations[C]∕∕Procofthe 2017ACMSIGSACConfonComputerandCommunications Security．NewYork:ACM,2017:619631
[14] RouhaniB D,Riazi M S,Koushanfar F．DeepSecure: ScalableprovablyＧsecuredeeplearning [C]∕∕Procofthe55thAnnualDesign AutomationConf．New York:ACM, 2018:16
[15] JuvekarC,VaikuntanathanV,ChandrakasanA．GAZELLE: Alowlatencyframeworkforsecureneuralnetworkinference [C]∕∕Procofthe27th USENIX ConfonSecuritySymp． Berkeley,CA:USENIXAssociation,2018:16511668
[16] DeanJ,CorradoG,MongaR,etal．Largescaledistributed deep networks [C] ∕∕Proc of Advances in Neural Information Processing Systems．Cambridge, MA: MIT Press,2012:12231231
[17] AbadiM,Barham P,ChenJianmin,etal．Tensorflow:A systemforlargeＧscale machinelearning [C]∕∕Procofthe12th USENIX Conf on Operating Systems Design and Implementation．Berkeley, CA: USENIX Association, 2016:265283
[18] MohasselP,RindalP．ABY３:A mixedprotocolframework formachinelearning[C]∕∕Procofthe2018ACM SIGSAC Confon Computer and Communications Security．New York:ACM,2018:3552
[19] WaghS,GuptaD,Chandran N．SecureNN:Efficientand
privateneuralnetworktraining [J∕OL]．IACR Cryptology ePrintArchive,2018[2020Ｇ08Ｇ29]．https:∕∕eprint．iacr．org∕ 2018∕442
[20]ChaudhariH,ChoudhuryA,PatraA,etal.ASTRA:High throughput ３PC over rings with application to secure prediction[C]∕∕Procofthe2019ACM SIGSAC Confon CloudComputingSecurity Workshop．New York:ACM, 2019:81922084计算机研究与发展2020,57(10)
[21]ByaliM,ChaudhariH,PatraA,etal.FLASH:Fastand robustframeworkforprivacyＧpreserving machinelearning [J].ProceedingonPrivacyEnhancingTechnologies,2020, 2020(２):459480
[22]ChaudhariH,RachuriR,SureshA．Trident:Efficient４PC frameworkforprivacypreserving machinelearning [C]∕∕ Procofthe27th AnnualNetworkandDistributedSystem SecuritySymp(NDSS2020)．SanDiego,CA:ISOC,2020: 2326
[23]PatraA,SureshA.BLAZE:BlazingfastprivacyＧpreserving machinelearning [J].arXivpreprint,arXiv:2005.09042, 2020[2020Ｇ07Ｇ20].https:∕∕arxiv.org∕abs∕2005.09042
[24] Wagh S, Tople S,Benhamouda F,et al．FALCON: HonestＧmajority maliciouslysecureframeworkforprivate deeplearning [OL]．arXivpreprint,2020 [2020G07G20].https:∕∕arxiv.org∕abs∕2004.02229
[25] 魏立斐, 陈聪聪, 张蕾, 李梦思, 陈玉娇, 王勤. 机器学习的安全问题及隐私保护[J]. 计算机研究与发展, 2020, 57(10): 2066-2085.
—END—
排版 | 李福玲 图片 | 杨雅清
点击名片关注我👇