安全多方计算通用编译器

一：Abstract摘要

      1.安全多方计算功能:Secure multi-party computation (MPC) allows a group of mutually distrustful parties to compute a joint function on their inputs without revealing any information beyond the result of the computation（安全的多方计算（MPC）允许
一组互不信任的各方，可以根据其输入来计算一个联合函数，而不会透露任何超出计算结果的信息）

      2.文章工作:We consider eleven systems: EMP-toolkit, Obliv-C, ObliVM, TinyGarble, SCALE-MAMBA (formerly SPDZ), Wysteria, Sharemind, PICCO, ABY, Frigate and CBMC-GC（调查了11个安全多方计算的框架，进行了一些对比(language expressibility, capabilities of the cryptographic back-end, and accessibility to developers)语言的可表达性，加密后端的功能以及
开发人员可访问性。）

      3.文章工作2:for each system, we also provide a complete virtual environment (Docker container) with all the necessary dependencies to run the compiler and our example programs.(创建了一个github资源库，里面有这11个框架的代码、有样例还有相关的文档信息)

二：INTRODUCTION引言

      第一段介绍了MPC的一个功能。第二段介绍了MPC的应用。第三段介绍了一下MPC技术主要是因为计算和通信复杂度的效率太低而无法在工业中使用。第四段介绍了对于特定内容所设计的高效MPC协议不能成为可扩展的解决方案。第五段介绍了通用MPC编译器可以减轻设计多个自定义协议和让非专业人员使用。第六段介绍了MPC编译器遇到的挑战:1.分布式效率本身就很难，2.编译器和密码方案的优化3.可用性:灵活，直观，简单 4.电路优化:有浮点计算，协议选择:选择最佳协议用于特定计算。第七段介绍了第一个MPC编译器:Fairplay。基本架构高级语言编写--转换为电路格式--使用安全协议执行电路。第8，9段介绍了一下努力的结果。第9段介绍了本文的目的是为新的mpc编译器提供指南和适用的读者(开发安全计算人员,了解最新实用技术的密码学家,了解现有技术局限性并确定新研究方向的编译器设计师,公司决策人员)。第10段介绍它们做了哪些工作（1.mpc必要技术，2.最新mpc框架+评估(更注意可用性而不是性能)3.每个案例做了三个小实验,4.提出了未来mpc编译器的研究方案）。第11段介绍了为了使其他人简单尝试创建了了俩个github库(1.一组Docker容器，每个容器提供一个开发环境，该环境配置了每个MPC框架所需的软件基础结构，以及我们的测试用例的可执行示例2.一个Wiki页面，该页面收集了此处提供的大部分评估以及有关每个框架的其他文档)

     准备工作:1.调查安全计算工具，定义一个度量方法(a maturity taxonomy)

                      2.调查不同威胁模型，外包计算技术

                     3.mpc框架调查

                      4.Drago Rotaru. awesome-mpc. https://github.com/rdragos/awesome-mpc 2018.：mpc信息库提供了最新的编译器，后端和专用协议列表，其中包含简短的内容每个的描述。

作者创建的  https://github.com/MPC-SoK/frameworks

三：CRYPTOGRAPHIC BUILDING BLOCKS

          本章简单的描述了一下共有的密码学技术

         1.Secret Sharing(秘密共享)：

                 有关秘密共享的调查看这篇论文：Amos Beimel. Secret-Sharing Schemes: A Survey. In YeowMeng Chee, Zhenbo Guo, San Ling, Fengjing Shao, Yuansheng Tang, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology, volume 6639 of Lecture Notes in Computer Science, pages 11–46. Springer Berlin Heidelberg, 2011.

                 大多数MPC协议都利用的简单的秘密分享协议：: either simple, additive secret sharing or Shamir sharing。

【这里简单的补充一下秘密分享的知识:

           秘密分享基本思想：将数字x拆分成多个x1,x2,..xn并将这些数分发给多个参与方s1,s2…sn. 只有大家把各自的数据凑到一起时才能还原真实数据。所以关键就是要设计好秘密分配算法和秘密重构算法，使他们能满足安全的要求，这里简单说一下shamir1979年设计的(t,n)门限秘密共享机制.

密钥分配算法：将主秘密赋值给a0,再随机生成t-1个数：a1,a2,a3,a4……at-1 再生成一个t-1次随机多项式： 将f(1),f(2),f(3),,,,f(n)分别分发给p1,p2,p3….pn. 密钥重构算法：运用了比较通俗的解法，也就是t个未知数，有t个方程就可以解出。这就是(t,n)秘密分享机制。】

             2. Oblivious Transfer (OT）不经意传输协议

主要介绍了一下从OT协议到ROT到OT-extension

OT：bob从alice手中拿一个数据，不想让alice知道拿的是什么，alice也确保bob只能从他那里拿一个数据OT协议:bob从alice手中拿一个数据，不想让alice知道拿的是什么，alice也确保bob只能从他那里拿一个数据

四：SECURE MULTI-PARTY COMPUTATIN(安全多方计算)

         怎么才能认为一个协议是安全的：如果敌手攻击实际协议所得与攻击理想模型所得相当。(理想模型:存在一个所有参与方共同信任的可信方，在可信方的帮助下计算出的协议的功能函数)

            【解释一下：先看一下理想模型的执行过程：参与方将自己的输入传输给可信方--可信方计算功能函数--将计算结果返回给相应的参与方。可见敌手攻击理想模型无可得，攻击实际模型也就无所得了】

接下来介绍支持现代MPC系统的主要协议系列的关键设计特征

1.. Garbled Circui

      关于姚的混淆电路就不再介绍，需要补充这部分知识的请参考我的MPC系列。

     关于混淆电路实现的程序请参考:Mihir Bellare, Viet T. Hoang, and Phillip Rogaway. Foundations of Garbled Circuits. In CCS ’12, CCS ’12, pages 784–796, New York, NY, USA, 2012. ACM.

      混淆电路俩个关键技术的提升:free xor,该门不需要加密也就是不需要任何代价就能保证安全性。Half-Gates(半门):减少与门的密文数量，将AES-NI指令集合加入现代程序极大减少计算量。

       混淆电路特点:固有的俩方安全协议，仅需要常数轮的交换。昂贵的公密钥计算只与输入大小有关。私钥的计算取决于门的数量。通讯费与电路大小成正比。

2.Multi-party circuit-based protocols(多方电路协议)

        GMW(基于混淆电路的)，BGW(基于秘密分享的)

        关于乘法门的方法可以看Ishai的论文:Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Secure Arithmetic Computation with No Honest Majority. In TCC, pages 294–314, March 2009.（遗忘乘法门的通信主导了电路花费的评估）

        布尔电路由异或门和与门组成。算数电路由加法门和乘法门组成。

        信息理论协议:秘密共享方案比基于密码学方案快。但是它们必须保证诚实者占多数。

3.Hybrid models（混合模型）

        将功能函数编译为一组可优化的子协议用于常规操作(原语的建立)。将信息理论(如秘密分享)和密码学协议(如混淆电路)混合。

3.Alternative methods(代替的方法)

        全同态加密方案(FHE),实现全同态加密的库：HElib,PALISADE,SEAL。该文没有将FHE与其他方案进行比较。

Shai Halevi and Victor Shoup. Helib: Implementing homomorphic encryption. http://shaih.github.io/HElib/index.html, 2015.

Kurt Rohloff and Gerard Ryan. The PALISADE lattice cryptography library. https://git.njit.edu/palisade/PALISADE, 2016.

Microsoft Research. Simple encrypted arithmetic library (SEAL). https://www.microsoft.com/en-us/research/project/ simple-encrypted-arithmetic-library/, 2016

四.FRAMEWORKS SURVEY(框架调查)

        调查的11种方法都遵循相同的一般方法：1.编译器将高级语言编写的程序转换为中间表示形式(通常为电路)2.将电路作为输入，执行MPC协议，产生输出。(只有Frigate和CBMC-GC没运行时组件)。

工程挑战:

            所以电路表示功能函数的优点:输入独立，因此不会泄露输入信息。

                                                     挑战与局限性:需预先设置有限域，不支持非算数操作如比较和相等检测。boolean电路需要重新定义位宽，对此没有一个标准，导致不支持任意位宽操作。将程序转换为电路需要展开它的循环和递归，但是大多数编译器不支持静态分析来终止递归，需要程序员设置一个时间来中断。大多数语言不支持私有数组索引。如有i，数组v但是v[i]不能索引。平衡透明性和灵活度是MPC编译器的一个重要挑战，自动选择最优MPC协议也是一件困难的事情，

五.EVALUATION CRITERIA(评价标准)

         1.易用性:是否有工具文档说明。

          2.Sample Programs(样例程序):使用三个简单的程序来体系可用性，表达性，结构与密码设计。在附录A中包含了示例代码。(Multiply Three：三方输入计算，测试整数输入输出和安全类型计算的能力。Inner Product:测试与阵列相关的功能。Crosstabulation:按类别计算平均数，这里直接返回汇总清单。)

         3.Functionality(功能性):定义安全功能的高级语言的表达能力。(1.数据类型:2，运算3，语法)

         4.Implementation Criteria(实施标准)：定义框架和密码的标准。开发语言,AES-NI提供GC性能,X86扩展加速加解密。

Architecture:(结构)：独立框架：开发新的语言和编译器。第二种是对现有框架的扩展。第三种是完全以现有的语言实行（定义一个类和方法对协议进行执行）

Computation Model(计算模型):算数电路，布尔电路，及时生成电路(在运行之前生成电路，减少资源消耗，允许动态数组和循环界限，减少整体运行时间)

I/O：Arbitrary Formatting，Different Input types from each party，Array Output，Multiple Output

         5.Performance（性能）：在这篇论文中更专注可用性，对性能并不评价测试。理论效率指标在实际的mpc框架中并不适用。例如电路的大小和深度在GC和SS中的含义并不一样。协议的变化和威胁模型意味着我们不能直接的进行比较。(为什么不讨论性能的原因)

 六.FRAMEWORKS（框架）

         接下来将详细介绍每个框架的详细限制和主体可用性。并对每个框架的适用情况提出建义。

1.EMP-toolkit：Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMPtoolkit: Efficient MultiParty computation toolkit. https://github. com/emp-toolkit, 2016           

                      基于混淆电路的MPC，核心组成(oblivious transfer library, secure type classes, and several custom protocol implementations)

                      使用这个框架完成的俩个测试:半诚实下姚的混淆电路协议（发现代码直观易懂，允许使用数组和结构来保存安全值，可即时生成电路，支持任意大小的整型和浮点型，），恶意下的authenticated garbling（支持功能有限，在使用半诚实库之前必须将功能函数转换为电路，将i/o编码转换为boolean数组）(Xiao Wang, Samuel Ranellucci, and Jonathan Katz. Authenticated garbling and efficient maliciously secure two-party computation. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, pages 21–37, New York, NY, USA, 2017. ACM.)

建议：我们推荐使用EMP工具包半诚实库。由于现有的电路生成和密码库，整个平台非常适合希望实现基于电路的新协议的学者，但是我们注意到端到端的流不是无缝的.

2.Obliv-C

               基于混淆电路,在C库上添加了遗忘限定符(遗忘功能和条件中的代码无法修改公共数据)，

建议：Obliv-C是一个鲁棒GC框架，我们向一般用途的开发人员和希望实现和优化有用库（如ORAM）的学者推荐它。

3.ObliVM

             类Java语言被叫做ObliVM-lang，执行俩方GC协议。目的为非专业人员提供直观的编程以提高性能。

            允许自定义数据类型和类型推断，实现了built-in的高效ORAM方案。但是文件有限，I/O受限:不可读，无法返回复杂类型如数组。

建议:ObliVM实现了高级密码学结构，但它在实际应用中的可用性却受到其最小文档和受限的I/O功能的极大限制。

4.TinyGarble

            利用硬件电路生成工具去优化GC协议(三步:1.将定义在verilong的函数转换为网格2.将网格转换为自定义电路描述3.使用GC协议安全评估boolean电路)

建议：TinyGarble旨在为生产硬件电路而开发的强大的电路优化器。从可用性角度来说，目前还是是很弱的。不幸的是，从可用性的角度来看，Verilog编译器缺乏兼容性，netlist格式缺乏标准，这意味着我们无法使用TinyGarble框架编译或运行任何新的示例。然而，我们相信，MPC社区可以通过利用现有电路优化器的能力而受益匪浅。

5.

Aseem Rastogi, Matthew Hammer, and Michael Hicks. Wysteria: A Programming Language for Generic, Mixed-Mode Multiparty Computations. In Security and Privacy (SP), 2014 IEEE Symposium on, pages 655–670. IEEE, May 2014

                  支持任意数量的参与方，软件的贡献:前端语言,类型检测器，执行GMW协议的运行解释器。局限：仅支持除以2，没有在boolean上使用逻辑运算符的方法。

建议：对复杂数据类型支持有限，缺乏发展，过时的电路解释器。但是Wysteria是这11个系统里唯一旨在提供一种系统的系统编译器，该系统可自动验证底层多方计算是否具有与开发人员实现的整体程序相同的功能。也是唯一一个函数式的编译器。所以我们建议使用Wysteria的类型正确性和安全性保证作为模型。

6.ABY

     Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY - a framework for efficient mixed-protocol secure two-party computation. In NDSS, February 2015. 

      ABY:使用C++库实现的俩方计算混合协议，旨在提供一个混合协议的机制，为开发人员提供效率，ABY在三种协议间进行交换:基于GMW的算术电路协议,在算数电路上具有乘法三元组的共享方案。   boolean电路的实现使用原始的GMW协议和基于XOR的共享方案。 姚协议使用优化版本的姚混淆电路协议。

       ABY:有大量的文档为理解框架的功能提供有用的框架。(包括:开发人员指南，扩展的README文件以及各种带有注释的示例)

      ABY仅支持无符号的C整型类型。它支持一些浮点运算，并正在积极开发此功能，ABY可以将安全数据存储在C结构中，

基于ABY的几种安全协议:

Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, and Thomas Schneider. Towards securing internet exchange points against curious onlookers. In ANRW, pages 32–34, New York, NY, USA, 2016. ACM

Schapira, and Thomas Schneider. SIXPACK: Securing Internet eXchange Points Against Curious onlooKers. In 13. International Conference on emerging Networking EXperiments and Technologies (CoNEXT’17), pages 120–133. ACM, 2017.

Daniel Demmler, Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, and Shaza Zeitouni. Automated synthesis of optimized circuits for secure computation. In 22. ACM Conference on Computer and Communications Security (CCS’15), pages 1504–1517. ACM, 2015

Agnes Kiss, Jian Liu, Thomas Schneider, N Asokan, and Benny ´ Pinkas. Private set intersection for unequal set sizes with mobile applications. Proceedings on Privacy Enhancing Technologies, 2017(4):177–197, 2017.

Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient circuit-based psi via cuckoo hashing. In EUROCRYPT, pages 125–157. Springer, 2018.

建议:ABY提供了一个强有力，低级密码接口，给开发者很好的控制。我们推荐给具有足够加密背景的开发人员。

7.SCALE-MAMBA

      SCALE-MAMBA:实现了恶意的俩方安全协议取代了SPDZ方案。MAMBA是一个类python语言可以编译成字节码。将所有的公钥处理转到了预处理阶段。

      SCALE-MAMBA:允许开发者自定义I/O类。

建议：推荐SCALE-MAMBA有多种用途:很灵活，支持任意数量的参与者，有很强的安全证明，但是可能需要大量的计算资源。

8.Sharemind MPC

        Sharemind：一个安全的数据处理平台，框架执行三方混合协议使用一个附加的秘密共享方案。

        Sharemind MPC明确了三个参与方:客户方(输入)，服务器(定义和安全计算)，接收者(接受计算的输出)。

        Sharemind MPC在固定大小的环上实现了自定义加性秘密共享方案。

建议：推荐给希望实施安全计算的公司，以及需要MPC作为工作项目的学者。

9.PICCO

Yihua Zhang, Marina Blanton, and Ghada Almashaqbeh. Implementing support for pointers to private data in a generalpurpose secure multi-party compiler. ACM Trans. Priv. Secur., 21(2):6:1–6:34, December 2017.

          通用编译器：使用自定义秘密共享协议。包括三个主要的软件贡献:将扩展C转化为本地C的安全协议，一个i/o实用协议，产生并重建秘密共享的输入和输出，启动计算的工具。支持任意数的参与方但是需要诚实的占多数。

建议:建议给真正实现俩方的开发者和学者,在配置计算方面有很大的灵活性。

10.Frigate

 B. Mood, D. Gupta, H. Carter, K. Butler, and P. Traynor. Frigate: A validated, extensible, and efficient compiler and interpreter for secure computation. In 2016 IEEE European Symposium on Security and Privacy (Euro S&P), pages 112–127, March 2016.

Frigate编译器是类C语言开发的用于任意输入的自定义boolean电路，包含测试工具，电路格式最大程度减小，

系统只有3个本地类型:有符号，无符号，结构。编译器能提供有用的错误提醒。

建议:提供一个类C语言快速生成电路,好的方式评估给定计算的电路大小。但是，即使我们提供一个转化工具，MPC端到端的计算用户都需要一个频繁的操作。

11.CBMC-GC

Schallhart, and Helmut Veith. CBMC-GC: An ANSI C Compiler for Secure Two-Party Computations. In Albert Cohen, editor, Compiler Construction, volume 8409 of Lecture Notes in Computer Science, pages 244–249. Springer Berlin Heidelberg, 2014.

从ANSI-C产生子集，基于CMBC框架，有界模型检查器(将C程序转化为boolean约束,调整该输入的输出,以生成用于mpc计算的优化电路)，该编译器可以优化到最小尺度或深度的电路,

建议:CBMC-GC是一个强大的工具可以去优化电路，但是我们不能去成功的执行它产生任何电路。

七.DISCUSSION（讨论）

1.利用现有的编译器研究:很少有mpc研究利用这些技术，Wysteria是一个例外，但存在工程空白，无法实际使用。关于编译器改进领域是值得关注的，

2.我们机构用数千小时对上面框架进行文档说明。http://www.texample.net

3.标准化和基准: