安全多方计算MPC学习笔记

参考:http://www.noobyard.com/article/p-duxrwkem-qq.html算法

MPC安全

Secure Multi-Party Computation框架

安全多方计算

一种保护数据安全隐私的多方计算算法。函数

GC

Garbled Circuitui

加密电路

一种经过加密处理电路的方式。加密

OT

Oblivious Transferspa

不经意传输

一种安全的选择、传输协议。.net

一、MPC来源

安全多方计算由我国目前惟一图灵奖得到者姚期智院士提出,其提出场景为百万富翁问题:在没有可信第三方的前提下,两个百万富翁如何不泄露本身的真实财产情况来比较谁更有钱。MPC能够在保证各方数据安全的同时,联合使用各方数据来达到特定的效果,从而充分发挥数据的价值。设计

多个持有各自私有数据的参与方,共同执行一个计算逻辑计算逻辑(如,求最大值计算),并得到计算结果。但过程当中,参与的每一方均不会泄漏各自数据的计算,被称之为MPC计算,MPC计算能够经过对协议的设计而不用依赖于可信第三方。blog

二、问题抽象

安全多方计算能够抽象的理解为:两方分别拥有各自的私有数据,在不泄漏各自私有数据的状况下,可以计算出关于公共函数 的结果。整个计算完成时,只有计算结果对双方可知,且双方均不知对方的数据以及计算过程的中间数据。

三、MPC问题分类

  • 由算法适用性来看,MPC既适用于特定的算法,如加法、乘法、AES,集合交集等;也适用于全部可表示成计算过程的通用算法。
  • 根据计算参与方个数不一样,可分为只有两个参与方的2PC和多个参与方(≥3)的通用MPC
  • 安全两方计算所使用的协议为Garbled Circuit(GC)+Oblivious Transfer(OT);而安全多方计算所使用的协议为同态加密+秘密分享+OT(+承诺方案+零知识证实等)。
  • Garbled Circuits   ||   GMW
  • 在安全多方计算中,安全挑战模型包括半诚实敌手模型恶意敌手模型。市场大部分场景知足半诚实敌手模型,也是JUGO技术产品所考虑的敌手模型。
  • 半诚实敌手模型:计算方存在获取其余计算方原始数据的需求,但仍按照计算协议执行。半诚实关系即参与方之间有必定的信任关系,适合机构之间的数据计算;一个半诚实成员彻底遵照协议的执行过程,中途不退出协议的执行过程,也不篡改协议运行结果,但其能够保留执行协议过程当中的一些中间结果,并经过这些中间结果试图分析推导其余成员的输入数据。
  • 恶意敌手模型:参与方根本就不按照计算协议执行计算过程,可以随意中断协议的运行,破坏协议的正常执行过程,也能随意修改协议的中间结果或者与其余参与方相互勾结。参与方可采用任何(恶意)方式与对方通讯,且没有任何信任关系。结果多是协议执行不成功,双方得不到任何数据;或者协议执行成功,双方仅知道计算结果。更多适用于我的之间、或者我的与机构之间的数据计算。

四、MPC算法基本原理(2PC半诚实模型)

4.一、MPC算法执行过程

  • 先对输入数据作预处理。
  •   遵循原则:一、尽可能少的数据输入;二、尽可能多的数据预处理

    ——数据量太大时会大幅下降算法执行效率。

  • 计算逻辑转化为布尔电路。
  •   遵循原则:尽可能简单的计算逻辑

    ——因为MPC是计算密集型和通讯密集型算法,若计算逻辑很复杂,会对执行效率产生很大影响。

      转化方式:手动/电路编译器Frutta

  • 将输入的布尔电路作GC和OT算法(详细在下面叙述),获得输出结果。

4.二、GC+OT的两方计算基本框架

GC+ OT是在两方semi-honest模型下的通用型算法,便可以支持任意计算逻辑的安全两方计算。

  整体框架以下图:

矩阵云推出JUGO安全多方计算平台,既能保护数据隐私又能实现数据流动起来最大化其价值。

五、个人补充

5.一、OT

OT:指发送方sender传输给接收方receiver n个数据,可是不知道receiver收到了n中的哪个,而receiver也只能解码其中一个。假如须要k个数据,那么至少须要k次interaction。

5.2 2PC

5.三、Secret Sharing