「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

GMW协议GMW协议由Goldreich等人提出,基于混淆电路(Garbled Circuit),支持多方的半诚实的安全计算协议。

GMW协议

GMW协议由Goldreich等人提出,基于混淆电路(Garbled Circuit),支持多方的半诚实的安全计算协议。和之前所述的姚氏混淆电路估值方案的不同之处在于,GMW混淆电路估值方案不需要使用混淆真值表,因此没用混淆真值表带来的查表和加解密操作,节省了非常大的计算量和通信量。

混淆电路在上次的科普已经介绍过了,在将安全多方计算的目标函数转换为布尔电路后,通过对电路进行混淆(加密)操作来得到混淆电路。

混淆电路通过对电路进行混淆(加密)操作来掩盖电路的输入和电路的结构,以此来实现对各个参与者的隐私信息的保密,再通过电路计算来实现安全多方计算的目标函数的计算。

GMW协议的目标函数由异或门和与门、非门组成。非门的输出值是输入值的反,输入为1则输出为0,反之输入为0则输出为1。与门的真值表如下图所示:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

异或门及其真值表

异或门及其真值表如下图所示:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

与门及其真值表

首先介绍GMW协议的两方情况。首先假设参与者为AliceBob,Alice和Bob的输入均为长为n的比特串,其中 Alice输入为比特串,Bob的输入为比特串b。

对于比特串中的每个比特,Alice都产生一个随机的比特∈ {0,1},1≤≤,并将这n个随机产生的比特,1≤≤发送给Bob。

对于比特串中的每个比特,Bob也都产生一个随机的比特∈ {0,1},1≤≤,并将这n个随机产生的比特发送给Alice。Alice和Bob分别将作为协议输入和b的子秘密。

即Alice掌握了和b的子秘密,Bob掌握了和b的子秘密

若Alice公开其所掌握的,Bob公开其所掌握的,那么Alice和Bob可以共同计算出

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

接着Alice和Bob对布尔电路中的每个门求值,直至完成整个电路的计算。对于非门,由于非门是单输入的,Alice和Bob间无须进行交互,因此直接对输入求反即可。

对于异或门,假设异或门的输入分别为和b,Alice掌握了和b的子秘密Bob掌握了和b的子秘密,因为:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

因此Alice和Bob可以在本地对其所掌握的子秘密进行计算,

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

对于与门,因为,因此Alice和Bob无法只在本地完成与门的计算。

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

因为Alice手中有,因此Alice可以本地计算Bob 手中有,因此Bob可以本地计算。剩下的二者必须协同完成。

的计算可通过四选一不经意传输协议完成。对于Alice来说,Bob掌握的都是单比特值,只有四种情况:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

Alice手中又有,因此Alice可以直接计算出四种情况下的⋀的值,假设分别为,注意这里⋀的值为的值, 对于Alice和Bob来说式子里都只有两个未知数,而这两个未知数一共只有4种可能。

Alice的未知数为Alice可以假设()分别为(0,0)、(0,1)、(1,0)、(1,1),那么根据假设的四种情况,就都确定了,可以据此计算出四个确定的值。因此Alice可以得到下表:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

Alice 再产生一个随机比特,并将计算出的异或上随机比特,将为四选一不经意传输协议的输入,Bob将其所掌握的作为四选一不经意传输协议的输入,双方执行该OT协议,Bob得到对应的

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

Alice将作为该与门的输出的子秘密,Bob将作为该与门的输出的子秘密。

由于Alice和Bob双方间执行的是不经意传输协议,Alice不知道Bob 在中选择了哪个,保证了依旧对Alice保密。

又由于Alice发送的是,Bob不知道随机比特的值,也就不知道的到底是1还是0,只有在最后双方都公布各自手中的计算结果,双方才能合力计算出正确的结果。

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

这里Bob得到的子秘密异或上Alice得到的子秘密即为⋀的值。

将GMW协议扩展到多方情况下:参与者为,假设输入为m个比特,那么每个参与者产生组,每组−1个随机比特,分别将每组的−1个随机比特发送给除了自己之外的n-1个参加者。

假设输入数据为1个比特,那么每个参与者向参与者发送,1≤≤且≠。在所有参与者发送完成后,参与者掌握了。假设的输入为,那么作为的子秘密

对应的收到发送的随机比特的参与者,将当做秘密的子秘密。因此

对于异或门以及非门,和双方情况下相同,每个参与者直接在本地进行计算即可。对于与门,与门的输入为和b,参与者手中掌握了和b的子秘密,因为,可得:

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

这其中,对于来说,每个都可由在本地进行计算。而对于,≠,可由参与者通过上述的两方BGW协议共同计算出的两个子秘密。当电路计算完成,每个参与者公布自己所掌握的子秘密,再将所有的子秘密进行异或,即可得到最后的计算结果。

BGW协议

BGW协议也是支持多方的安全计算协议,BGW协议基于Shamir(t, n)门限秘密共享机制,利用了Shamir秘密共享机制的加法同态和乘法同态的性质。Shamir(t, n)门限秘密共享机制在之前的科普已经进行过介绍了。

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

假设BGW协议的参与者一共有n人,假设参与者需要输入秘密,则参与者首先利用Shamir(t,n)门限秘密共享机制将秘密共享给其他所有参与者,阈值t的选择根据具体使用情景下的安全性要求决定。

当所有参与者的输入都通过Shamir(t, n)门限秘密共享机制分享后,每个参与者都掌握了协议输入的子秘密。假设一个门的输入分别为和,秘密和已经分别由秘密分配函数

分配完成,,参与者掌握和b的子秘密。在布尔电路上,可将异或门和与门分别看成在有限域2上的加法和乘法。将异或用模为2的加法进行计算,与用模为2的乘法进行计算。

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

对于异或门:由于Shamir具有加法同态性,因此

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

假设,则,而都由掌握,因此可以本地计算出。当所有计算完成后,每个参与者公布自己计算出的, 即可恢复出

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

对于与门,和之前叙述过的基于Shamir(t, n)门限共享机制的多方乘法计算相同,只是BGW是在有限域2上。每个参与者计算,接着每个独自选取次数为t次的随机多项式,且满足,1≤≤,</2。

向各个参与者分配,且,1≤,≤。所有参与者分配结束后,掌握了信息,同时再利用公开的重组向量1,…,,计算

此时掌握的子秘密即为的子秘密。当所有计算完成后,每个参与者公开自己的子秘密,再根据之前叙述的Shamir(t, n)门限秘密重构算法即可获得。

「隐私计算笔谈」MPC系列专题(四):GMW协议和BGW协议

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/74493.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信