安全多方计算之混淆电路

2020-10-11 12:56 栏目:经验之谈 来源:网络整理 查看()

简介:混沌电路,又称姚电路,是教授于1986年为解决百万富翁问题而提出的。

其核心技术是将双方的安全计算函数编译成布尔电路,并对真值表进行加密和加扰,从而实现电路的正常输出而不泄露参与计算双方的隐私信息。由于任何安全计算函数都可以转换成相应布尔电路的形式,相对于其他安全计算方法具有更高的通用性,因此在业界受到了更高的关注。

混乱的电路开发

姚的电路是基于半诚实模型的两方安全计算。

简单来说,整个计算过程可以分为两个阶段:

第一阶段将安全计算函数转化为电路,称为电路生成阶段;

第二阶段使用OT、加密等执行电路,称为执行阶段。

每一级都由参与操作的一方负责,直到电路完成执行并在操作后输出结果。对于参与操作的双方,从参与者的角度来说,可以分为电路发生器和电路评估器。

示意图如下图:所示

安全多方计算之混淆电路

步骤1:电路生成阶段

参与运算的双方首先以安全计算为目的,依靠专有编程语言(SSL)或相关编程语言扩展,然后编译程序实现计算,生成布尔电路文件;

然后根据双方的输入值和中间输出结果随机生成映射标签,然后将这些标签作为密钥,通过分组密码对每个对应的电路输出真值表进行加密,并对真值表值进行加扰。这一步是混淆电路的概念。

步骤2:电路执行阶段

电路执行器执行布尔电路文件,电路生成器在执行时需要将自身输入对应的标签发送给电路执行器;电路执行器根据自己所有的信息通过OT选择自己对应的标签,这样电路发生器和执行器都无法得到对方的输入数据;此时电路执行器获取双方输入的对应标签,将真值表作为密钥的相关信息进行解密,得到真值表的内容,一圈又一圈,直到所有电路执行完毕,输出执行结果。

姚氏电路是第一个安全的两方计算协议,其后大多数用于安全计算布尔电路/算术电路的安全多方计算协议都是在姚氏混淆电路的基础上扩展而来的。

常用的有/CCD/BGW/BMR,将姚协议支持的双方安全计算扩展到多方安全计算。将布尔电路扩展为算术电路;安全模型从半诚实模型扩展到恶意模型,以抵抗一定数量的恶意对手攻击。

在最后一篇文章中,我们介绍了双方安全计算的混淆电路。在此基础上,我们介绍了支持多方安全计算协议的GMW。

《GMW议定书》简介

Goldreich等人提出的GMW协议支持多方(2)安全计算,不仅支持布尔电路,还支持算术电路。但与姚的电路协议略有不同的是,电路评估不再使用混淆真值表,而是直接在本地进行计算,大大节省了混淆真值表带来的解密运算,节省了更多的计算量。

GMW协议(prOTocol)采用了秘密共享和ot等常见的加密原语,可以将整个计算过程分为三个阶段:

秘密分享阶段

参与操作的多方以线性秘密共享的方式共享自己的私有数据,以保证每个参与者都能获得自己的秘密成分。

电路执行阶段

接收到的每个秘密分量输入到and电路中,由and电路在本地逐门执行(AND门需要再次执行OT协议),重复这个过程,直到所有的门都被执行,得到结果的分量。

结果广播重新计算

各方广播最终的执行结果,各参与方获得各参与方的结果成分后获得最终结果。

实例分析

参与行动的两方是爱丽丝和鲍勃:

爱丽丝有私人信息u,加性秘密分享后,[u1][u2]=u,[u1][u2]可视为u的秘密成分,爱丽丝发送[u2]给bob。

Bob拥有秘密信息v,并且在分割秘密后,可以将[v1][v2]=v,[v1][v2]视为v的秘密部分,Bob将秘密部分[v1]发送给Alice。

这样,爱丽丝和鲍勃就有了彼此的秘密成分,如下表:所示

安全多方计算之混淆电路

(1)布尔电路的异或(相当于加法)

爱丽丝和鲍勃安全地计算总和(异或门),用电路形式表示如下:所示

安全多方计算之混淆电路

爱丽丝和鲍勃共享秘密后,爱丽丝和鲍勃获得的秘密分量和计算电路如下:

安全多方计算之混淆电路

爱丽丝和鲍勃分别在本地执行该电路:

安全多方计算之混淆电路

爱丽丝和鲍勃分别执行完电路后广播结果分量,经过局部计算得到最终结果:

安全多方计算之混淆电路

(2)布尔电路的与(相当于乘法)

爱丽丝和鲍勃安全地计算了积(与门),积以电路的形式表示,如下图:所示

安全多方计算之混淆电路

爱丽丝和鲍勃共享秘密后,爱丽丝和鲍勃获得的秘密分量和计算电路如下:

安全多方计算之混淆电路

安全多方计算之混淆电路

三方或多方扩展

(1)异或门

每个参与者获得每个分量后,在本地执行电路,类似于两方的计算,然后广播自己的本地计算结果,然后在收集所有参与者自己的计算结果时计算最终结果。

(2)与门(与)

安全多方计算之混淆电路

摘要

混淆电路的优化可以分为两个方面:

一方面,电路优化主要是减小编译后电路的尺寸,常用的技术有自由异或/乱码降行/电路简化等。

另一方面,常用的技术是快速查表(减少解密和混淆真值表的次数)和流水线电路执行(将原来的电路生成和执行转换成一个阶段,边生成边执行电路,可以提高安全计算的效率)。

基于姚混淆电路的协议和方法大多不再使用混淆真值表,而只保留电路的形式。为了扩展到多方(2)安全计算,秘密共享/无意传输技术被广泛使用。

与其他安全计算方案相比,混淆电路是一种安全性相对较高的通用解决方案,但其性能一般,尤其是当参与方数量超过3个、数据量较大时,安全计算过程中的流量会相对较大(双方各有1000个数据时,PSI流量可以达到GB的数量级),特别不适合带宽受限或WAN网络环境。

所以业界对混淆电路的评价是“高效但昂贵”,有效但计算成本高。

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发