安全多方计算相关技术原理

安全多方计算,Secure Multiparty Computation,简称MPC。概念不多说了,百度一大堆,涉及的密码学知识比较多,但大多数网上的资料讲解起来都比较抽象,本文希望从一个密码学初级学者角度(入门还谈不上,本人就是)用比较易懂的方式讲解一下自己对这些相关技术原理的理解。题外话,个人认为,数据孤岛是目前阻碍行业发展的一个比较打的问题,社会资源整合共享是一项非常大的事业,所以非常看好MPC的前景,结合区块链和人工智能,这项技术会越来越多地出现在人们的视野里。

(文中部分参考Youtube的视频讲解,个人认为讲得比较形象的,可以翻墙看一下,加深理解,最近墙比较牢,可以暂时先看看鄙人的讲解)

密钥分享相关视频: https://youtu.be/kkMps3X_tEE https://youtu.be/iFY5SyY3IMQ

不经意传输相关教学视频: https://youtu.be/HP0HnVmBs3g https://youtu.be/h6iiaAv_K0A

混淆电路相关教学视频: (ps. udacity对于密码学这一块的整个教学内容都值得一看) https://classroom.udacity.com/courses/cs387/lessons/48725342/concepts/486838550923

密钥分享(Secret Sharing)

密钥分享即把一个密钥数字拆分成多个部分,分发给多个参与方,满足一定条件的多个参与方联合起来可以重构该密钥数字。

在最初,密钥分享是所有人都掌握一份完整的密钥的备份,这种方式在传输过程中非常不安全,恶意窃听者可以很轻松地在通信信道中窃取密钥。人们便尝试将密钥按位划分成几部分,然后分发给合作的各方,每一方只知道密钥的几个位的数字,只有当各方将各自的数字联合拼接起来才能得到完整的密钥。这种方式对于网络窃听者起到了很好的防护作用,但后来人们又发现,知道密钥的几位数字还是可以利用穷举法得到最终完整的密钥,因此有人提出了模仿图片加噪声的方式,把分享的图片与一个噪声图片相加得到噪声合成图片,然后一方拿到噪声图片,另一方拿到的是噪声合成图片,双方要想知道原图需要结合双方,将噪声合成图片减去噪声图片。在密钥数字上体现为,把密钥加上一个随机数,得到一个随机密钥,一方拿到随机数,另一方拿到随机密钥。由于添加了一个随机数,双方要想单独破解密钥难度非常大。

这个时候,又出现了另外一个问题,如果各方中有一方缺失了,那么将无法还原密钥。著名密码学家Shamir在1979年发表的论文中提出了解决方案[1]。他利用几何学知识,将密钥表示为二维空间中的一个点坐标(x轴坐标值为0,y轴的值为密钥数字),然后随机生成一些空间中的点,将这些点和密钥表示的点生成一条曲线,随机生成的点即为分享给各参与方的密钥合成成分,理论上,该曲线上的点都可以作为分享成分,恢复密钥只要获取足够的点然后计算出曲线方程,再令x=0,计算y值也即密钥数字。

曲线方程取决于至少需要几个参与方才能恢复密钥(利用特性:两点可以确定唯一直线,三点可以确定一元二次函数曲线等),比如要求需要至少2个参与方便能恢复密钥,那曲线方程其实就是直线方程:y=bx+c,而密钥数字就是该直线与y轴交点的y坐标值,要计算直线方程,只需要得出b和c即可,直线上的点(除密钥点外)可以分发给n个参与方,但只要其中两方使用彼此拿到的点计算直线方程,即可成功恢复密钥。

若要求需要至少3个参与方才能恢复密钥,那么可以构造一元二次函数,曲线方程:y=ax2+bx+c,求解该曲线方程需要知道a和b和c,同样令x=0即可求得密钥。随机生成两个点坐标与密钥点坐标构建曲线,而求解这样的一元二次函数需要至少三个点坐标,也即n个参与方里必须有3个才能成功恢复密钥。

对于要求至少4、5、6或更多的参与方时,同样可以构造三次、四次、五次曲线等。一般地,假设要求至少t个参与方才能恢复密钥,那么构造多项式

对于要求至少4、5、6或更多的参与方时,同样可以构造三次、四次、五次曲线等。一般地,假设要求至少t个参与方才能恢复密钥,那么构造多项式

f(0)=a0即为原始密钥,可用拉格朗日插值法或变量消除法求解该多项式

在实际应用上,大部分的密钥分享协议都是类似上述的(t, n)密钥分享,即在n个持有密钥分享成分的参与方中,少于t个参与方是无法获取任何信息的,只有大于等于t个参与方才可以重构密钥数字,同时这些协议都满足线性特性。线性特性是密钥分享可以用于安全多方计算的关键要素。

关于密钥分享多项式的线性特性(可以认为是加法同态性):

假设有多项式g和h,它们的最高次幂相同,则有f=g+h,满足: (1)f的最高次幂与g、h相同 (2)f(x)=g(x)+h(x)

下面通过一个简单的例子说明密钥分享如何运用在安全多方计算。假设有一个投票系统S,接收来着A、B和C的赞成或者反对投票,用1和0分别表示赞成和反对,A、B、C的投票结果分别为1、1、0,在安全多方计算的概念里,S只能知道ABC最终的投票结果,即有2票赞成1票反对,但是不知道ABC分别的投票结果,而对于ABC而言,他们每个人都无需上传自己的投票选择,同时对于其他人的投票选择也无从所知。从密钥分享的角度分析,ABC的投票综合结果即为密钥,对于S来说,ABC三人一起才能解开密钥,即这是一个(3, 3)密钥分享问题,需要构建二次多项式方程。

首先构建二次多项式

A:fA(x)=1+a1x+a2x2, B:fB(x)=1+b1x+b2x2, C:fC(x)=0+c1x+c2x2,

则S需要的密钥:

fS(0)=fA(0)+fB(0)+fC(0)=2,

安全多方计算要求S不能知道ABC的具体投票是什么,S必须找到三个满足的点然后恢复投票结果密钥,那么根据多项式的线性特性,S的多项式可以为:

fS(x)=fA(x)+fB(x)+fC(x)=s0+(a1+b1+c1)x+(a2+b2+c2)x2

注意,a1b1c1a2b2c2对于S和ABC而言,除了知道自己各自的系数,对于其他人的系数都是无从所知的,需要依据线性特性来得到S的三个密钥成分。

由于ABC彼此之间都不知道对方的投票结果,但又需要联合计算得出总的投票结果,所以ABC各自都构建了各自的多项式,并且将自己的密钥成分分发给其他两方。在这里,对于a1b1c1a2b2c2其实无需考虑具体的值,这些由ABC决定,但有一点需要约定,在进行密钥分享时,ABC选取的点横坐标必须是一致的,比如选取x=1,x=2和x=3这三个点。

假设A的密钥成分为:

fA(1)=0,fA(2)=1,fA(3)=-1, A保留x=1,把x=2,x=3的结果分别发给B和C;

B的密钥成分为:

fB(1)=1,fB(2)=-1,fB(3)=0, B保留x=2,把x=1,x=3的结果分别发给A和C;

C的密钥成分为:

fC(1)=-1,fC(2)=0,fC(3)=3, C保留x=3,把x=1,x=2的结果分别发给A和B。

ABC中任意两方想要联合恢复另一方是不可能的。ABC在收集到各自发来的密钥成分后,先做加法,然后再发送给S:

A:fA(1)+fB(1)+fC(1)=0 B:fA(2)+fB(2)+fC(2)=0 C:fA(3)+fB(3)+fC(3)=0

对于S,实际收到的信息为:

f(1)=0, f(2)=0, f(3)=2

三点坐标满足,求解多项式:fS(x)=2-3x+x2,2为最终投票结果。在整个计算过程中,S、A、B、C都不知道各自的投票结果。

以上是安全多方计算利用密钥分享的一个简单应用实例,实际上,该模型并不是一个绝对安全的模型,称为半诚实模型,原因在于它要求各自上传的信息都是可靠的,如果有一方上传假消息,便会导致最终计算结果错误。同时,该模型也不支持乘法操作,Ben-Or, Goldwasser and Wigderson在1989年提出BGW协议,使得密钥分享可以支持乘法操作。

不经意传输(Oblivious Transfer,OT)

不经意传输协议[2],一种具有隐私保护功能的通信协议,能使通信双方以一种选择模糊化的方式在彼此之间传送消息。OT是密码学的一个基本协议,他使得服务的接收方以不经意的方式得到服务发送方输入的某些消息,这样就可以保护接收者的隐私不被发送者所知道,同时接收者也不知道发送者具体发送了什么消息。

OT协议的实现与对称加密算法AES和非对称加密算法RSA相关,下面以2取1位OT协议为例说明OT协议的基本原理。

假设有A和B双方,B需要从A那获取一些信息,在2取1位OT协议里,A为B提供了两个选择,但是A不知道B选择了什么,而B只能查看B选择的信息,另一个选择对B不可见。具体执行步骤如下:

A有数据(m0,m1),B只能选择查看其中之一; A通过RSA算法将公钥(n,e)发送给B,然后A再随机生成两个数字(x0,x1)发送给B,(m0,m1)和(x0,x1)没有任何联系; B收到(x0,x1),选择其中一个,假设B选择x1,然后B随机生成一个数字r,利用A的公钥对r进行加密,再加上x1生成一个新的值v并将其发送给A: v=x1+re mod n

A收到B发送的v,使用自己的私钥(n,d)根据(x0,x1)对v分别解密,得到两个密钥k0,k1: k0=(v-x0)d mod n=(x1+re mod n-x0)d mod n

k1=(v-x1)d mod n=(x1+re mod n-x1)d mod n=r

A通过AES算法使用密钥k0,k1对(m0,m1)进行加密,得到(Ek0(m0), Ek1(m1)),并发送给B; B收到(Ek0(m0),Ek1(m1)),由步骤4可知密钥k1就是步骤3中B生成的随机数r,B通过AES算法使用r对Ek1(m1)进行解密得到DrEk1(m1)=m1。

至此,B成功获取A的数据m1,但B不知道密钥k0,所以无法读取到m0的内容。除2取1位OT协议外,还有n取1、n取m位的OT协议。OT协议在执行过程中需要多次通信且公钥算法也会消耗部分性能,在后来又出现了随机OT协议,通过事先产生随机数和密钥批量生成等预处理操作,可以有效地提高算法的执行效率。

从理论角度上,MPC协议可以单独由OT协议实现,OT协议也非常适合用于构建更加高效的MPC协议。大部分的MPC协议都基于OT协议设计,OT协议也常应用在混淆电路协议中。

混淆电路(Garbled Circuits,GC)

早期的MPC协议都是基于电路模型,其中最为典型的就是混淆电路协议。混淆电路是一种两方安全计算方法,最早由姚期智先生提出[3],为此,他还提出了经典的百万富翁问题:在双方不透露任何资产的情况下比较谁更富有。参与的双方分别是电路生成者和电路执行者,首先双方达成一致地将要执行的联合函数转换成布尔电路。通常地,生成者使用对称加密算法(AES等)对每个门电路进行加密。对电路上的每一条线路的可能输入(输出)值,生成者选取对等个数的随机数分别进行一一替换,这些随机数被称为混淆密钥。生成者再利用这些混淆密钥,对电路里的每个门的输出的混淆密钥进行加密,得到混淆电路的真值表。

以简单的与门电路为例,假设有输入x,y,输出为z,则有真值表:

首先,x和y不能公开(也不能全部发送给执行者),可以用随机数表示,执行者拿到的是z的相关信息。而z的信息也不能完全透露,如果采用简单的编码替换z的结果,很容易便可以推出z的输入信息,因此,需要真值表中z的四个结果都使用不一样的表示,也可采用随机数,同时,z的随机数可以由某一组的xy解得,因此可以使用对应的xy来对z进行加密。整个过程就是混淆真值表生成的过程,最终的混淆真值表:

生成者将混淆真值表的z顺序打乱后连同自己的输入随机数发送给执行者(注意:前提是生成者与执行者共同约定执行电路),执行者接受到消息后开始执行电路。一般地,生成者提供自己的x输入后,执行者在和之间选择自己的输入便可解得z,和同样由生成者提供,但是生成者不能都发送给执行者,同时,执行者也不想让生成者知道自己选择了哪个,这时,OT协议就起作用了,混淆电路正是使用了OT协议解决这个问题。最终,执行者使用生成者提供的x输入和自己的输入依次解密z,解密成功的z即为最终结果(注意:结果有且只有一个,并且只是解密得到z的混淆密钥)。执行者再将结果也即混淆密钥发送给生成者,生成者对照真值表把密钥对应的真实z的输出结果发送给执行者,至此,双方便完成了一次混淆电路计算。

混淆电路的前提是需要双方彼此事先约定好执行电路,并且双方都能诚实地把结果发送给对方,这是一半诚实模型。最初的混淆电路协议可以对抗半诚实攻击,经过后续的许多改进和优化,也可以对抗完全恶意攻击。在实际应用过程中,还存在复杂运算逻辑的表示和电路生成计算的性能问题。

下面的内容大部分来自一篇论文的翻译,推荐一位知乎牛人,论文内容主要关于MPC的一些开源框架,计划会在接下来更新开源框架的教程博客

https://zhuanlan.zhihu.com/p/72119587

基于电路的多方协议(Multi-party circuit-based protocols)

GC+OT的协议模型只能进行两方计算,无法满足更多的应用场景。于是,开始涌现出基于电路的支持多反计算的协议,如GMW[4]、BGW[5]和CCD[6]等协议,它们允许任意数量的参与方安全地执行联合函数转化而成的电路。这些协议中,每一位参与方都采用线性密钥分享将各自的输入分享出去,所有参与方按电路门逐个计算结果。每个门将密钥分享输入得到同样为密钥分享的输出,对于加法性质的门运算,依据加法线性性质可以得到同样的密钥输出结果。但是对于乘法运算门,则有些不同。

GMW协议支持布尔电路也支持算术电路,对于布尔电路依旧使用OT协议,而对于算术电路则使用不经意多项式估值协议(Oblivious Polynomial Evaluation)[7]或不经意线性估值协议(Oblivious Linear Evaluation)[8]。

电路执行的资源消耗大部分来自乘法门运算中的不经意传输通信(例如随机数传送等),在实际应用中,大部分基于GMW协议的MPC都会采取一些措施来减少这部分的损耗。无论是布尔电路还是算术电路,都使用同样的方法,在线下预处理阶段,由参与方们或可信第三方先生成相关随机数,在线上执行电路的时候,参与方们使用这些事先生成好的随机数进行相关操作。基于GMW的布尔电路协议通常使用扩展OT[9]协议来预生成随机OT相关系数,而算术电路则是使用Beaver乘法三元组[10]。

信息论协议如BGW[11]和CCD[12],依赖于它们的密钥分享协议对乘法操作具有较强的支持,而不是公钥原语。这些协议具有更高的效率,因为它们不需要进行耗费计算资源的公钥操作,但是,要求大多数的参与方必须诚实。

总体而言,基于电路的多方协议可以支持任意数量的参与方进行安全计算,同时,协议通信的次数与电路中乘法的深度成正比,而通信的总量则取决于电路中乘法门的个数。这些协议还允许独立计算方接收输入并传送输出给其他参与方,而不影响安全性。

混合模型(Hybrid models)

经过近几年的发展,MPC协议系统已经不再使用严格的电路表示,而是使用混合模型,在混合模型中,函数被编译成一组优化的子协议函数,用于公共操作。这组原语可以包括传统的基于电路的协议模型,可以在单个协议中被无缝地描述。混合模型系统通常将中间值表示为一个大的有限域上的密钥分享。它们可以使用信息论和密码协议的混合,因此,计算参与方的数量和威胁模型都不同。

与严格的基于电路的模型相比,混合模型允许存在非常不同的性能特性。例如,在有限域中,比较、位移和相等性测试等操作作为算术电路表示代价高昂。然而,操作密钥分享的专用子协议在共享计算结果方面却非常高效。

全部评论(0)
给作者留言