安全多方计算技术与框架预研

MPC framework WIKI

安全多方计算框架简介

安全多方计算框架通用结构

  • 上层安全多方计算编译器

    • 可迁移性
    • 灵活性
    • 对非密码学专家卡安全多方计算开发者友好
  • 底层安全多方计算密码学协议

    • 高度优化

安全多方计算框架通用模式如下图:

安全多方计算框架通用模式
安全多方计算框架通用模式

安全多方计算框架详细介绍

前言

Fairplay第一个开源安全多方计算编译器,该编译器将高级语言(函数定义语言)源文件编译成可以由两个参与方共同安全性计算的混淆电路形式。Fairplay随后扩展为FairplayMP,采用的底层MPC协议为BMR协议。
FairPlay让安全多方计算协议可以真正实用化,并且,现代化的MPC协议实现能够很好的计算以大量数据集为输入的复杂函数,例如上千数据的回归分析计算等。

安全多方计算密码学基础

  • 混淆电路

    • 布尔电路
    • 算术电路
  • 秘密分享(Secret Sharing)

    • Shamir 秘密分享
  • 不经意传输(Oblivious Transfer)

    • 两值不经意传输
    • 多值不经意传输
    • 不经意传输扩展方法

安全多方计算协议

基于混淆电路的MPC协议(GC)

  • 以姚氏混淆电路为代表:

    • 两个参与方:一个电路混淆方,一个电路计算方。
    • 用布尔电路表示一个函数,通过AES等非对称密码体系混淆布尔电路。
协议主要特点
  • 电路混淆祝需要一个常数通信轮数,该轮数独立于电路深度。
  • 非对称加密操作次数依赖于输入数据大小。

    • OT是一次公钥加密操作
  • 对称加密操作次数取决于电路门的数量。
  • 总通信量与电路规模成比例。
  • 因为算术电路的混淆导致电路规模增长过快,隐私电路混淆方法主要针对布尔电路。

基于秘密分享的MPC协议(SS)

  • 任意个数计算参与方安全计算一个用电路表示的函数
  • 参与方通过线性秘密分享方法分享各自输入,然后个参与方同时计算电路结构得到电路输出的秘密分享值。

    • 其中电路中的AND门可以本地计算,MUL门需要参与方通信。
    • 因为计算MUL门具体方法的存在差异而衍生出多种基于多方电路的MPC协议。
GMW协议

GMW

  • 可计算布尔电路或者算术电路
  • 对于MUL门,在布尔电路计算中采用OT的方法,在算术电路计算中采用OPE(Oblivious Polynomial Evaluation)或是OLE(Oblivious Linear Evaluation)方法。针对MUL门的不同计算方法总结见Secure Arithmetic Computation with No Honest Majority

在GMW协议中,针对计算MUL门过程中的Oblivious通信占据电路计算消耗的主要部分。所有基于GMW协议的实用性MPC协议的实现都在减少这一部分的消耗作为主要优化方向。而这一优化方向主要实现方式为:在离线预计算阶段,参与方或者一些可信辅助计算方生成一些相关随机数,并且在出于在线阶段时,参与方使用这些相关随机数作为掩码或是一次密钥,辅助计算MUL门输出的分享值。

计算布尔电路的GMW类协议通常使用OT extension与计算ROT 相关随机数,然后于在线计算阶段消耗这些随机数。而计算算术电路的GMW类协议则采用Beaver Multipication Triples(随机元组$(a,b,a\cdot b)$的秘密分享值,其中$a,b$为域中的元素)的方法生成这些相关随机数。

BGW协议以及CCD协议

BGW和CCD两种协议是基于信息论的安全多方计算协议。这两种协议基于一种支持强乘法的秘密分享模式而不是建立在公钥密码学操作的基础上。这类协议因为不需要进行公钥计算而计算更快,但是这类协议需要保证大部分计算参与方是诚实的。因此,这类协议无法从协议的预计算过程中获益。

协议主要特点
  • 可以支持任意多个参与方
  • 通信轮数与乘法电路的深度成比例
  • 总通信量仅与MUL门的数量有关

安全多方计算协议类型分析总结

  • 安全多方计算协议类型主要分为两类:

    • 以混淆电路以及不经意传输为基础的安全双方计算协议
    • 以秘密分享以及不经意传输为基础的安全多方计算协议
  • 其他类型安全多方计算协议(非主流):

    • 混合模型协议:支持多种安全计算模型,秘密分享方法可以切换

安全多方计算框架

框架名称参与方协议族安全级别实现语言
ABY2PCGC&SSSHC++
ABY33PCSS&MLSHC++
CrypTenMPCSSSHPython
EMP-toolkit2PC&MPCGCSH&MalC++
Fancy-Garbling2PCarithmetic GCSHRust
FRESCOMPCTinyTables or SPDZ protocolsSH&MalJava
MOTIONMPCfull-threshold boolean and arithmetic GMW and BMRSHC++
MP-SPDZMPCGC&SSMal&SHC++&Python
Rosetta3PCSSSHC++&Python

2PC:安全两方计算. MPC: 安全多方计算
GC:基于混淆电路的安全双方计算协议,SS:支持秘密分享的安全多方计算协议
SH:抵御半诚实安全模型,安全级别较低,Mal:能够抵御恶意安全模型,安全级别较高

框架协议族示意图:

框架协议族
框架协议族

结论

从项目维护状态,项目文档支持,框架性能以及EPCS目前需求(支持基于混淆电路以及多方计算电路的安全双方计算协议)等角度综合比较得出两个较优的安全多方计算框架,ABY框架以及MP-SPDZ框架

  • ABY:提供了一个强大的底层加密接口,使开发者对性能有显著的控制。ABY针对的是熟悉MPC协议和计算的电路模型的用户。并且ABY框架文档支持最完备。

    • 缺点:没有持续的维护,在一些功能实现上存在一些未被修复的BUG。并且该框架编译环境仅支持Linux操作系统。
  • MP-SPDZ:是一套用于基准测试的MPC协议实现,带有各种有用的构建模块。它是一个成熟的框架,由经验丰富的开发人员实现;该框架效率高,架构良好(模块化),并得到了开发团队的持续的维护。MP-SPDZ是SPDZ-2(Keller等人,CCS'13)的分支,SPDZ是多方计算(MPC)协议SPDZ(Damgård等人,Crypto'12)的实现。MP-SPDZ将SPDZ-2扩展到了二十多种MPC协议,所有这些协议都可以用同一个基于Python的高级编程接口来使用。这大大简化了不同协议和安全模型的成本比较。这些协议涵盖了所有常用的安全模型(诚实/不诚实的多数人和半诚实/恶意模型),以及二进制和算术电路的计算(后者的模数为素数和二次幂)。所采用的基本基元包括秘密共享、不经意传输、同态加密和混淆电路。

其他较完备的安全多方计算框架都没有完全开源,这些框架是由各自开发公司内部实习开发并推广。例如RosettaSharemind