软文网站发布平台,网页翻译英文,成都做网站的工资多少,正能量视频免费网站免下载阿里妹导读#xff1a;近日#xff0c;阿里安全双子座实验室与马里兰大学等高校合作的论文《Covert Security with Public Verifiability: Faster, Leaner, and Simpler 》【1】被欧洲密码年会(Eurocrypt)2019接收。这是国内公司在安全多方计算领域的第一篇顶会论文#xff…
阿里妹导读近日阿里安全双子座实验室与马里兰大学等高校合作的论文《Covert Security with Public Verifiability: Faster, Leaner, and Simpler 》【1】被欧洲密码年会(Eurocrypt)2019接收。这是国内公司在安全多方计算领域的第一篇顶会论文Eurocrypt2018只有3篇大陆作者论文难度可见一斑。
今天我们邀请阿里高级安全专家鸿程深入解读业界首个“公开可验证(PVC)” 的安全两方计算方案。
安全多方计算介绍
安全多方计算 Secure Multi-Party ComputationMPC于1986 年由姚期智院士提出【2】。安全多方计算协议允许多个数据所有者在互不信任的情况下进行协同计算输出计算结果并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说MPC技术可以获取数据使用价值却不泄露原始数据内容。 互联网已经完成了从IT时代向DT时代的转变数据已经成为DT时代企业的核心竞争力。数据作为一种新能源只有流动起来才能产生价值。不过大多数企业考虑到数据安全和个人隐私等问题对数据共享都非常谨慎。而MPC对打破数据孤岛实现数据的可控共享具有重要的理论和现实意义。
MPC方案主要可分为基于混淆电路(Garbled CircuitGC)和基于秘密共享两种。本文主要关注GC类方案。
不经意传输(Oblivious Transfer)
我们首先介绍一种基础的安全多方计算协议不经意传输(Oblivious Transfer, OT)。
来看一个例子假设某旅行社拥有N个景点的旅游资料小淘想去其中的A景点游玩希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件
小淘不希望向旅行社泄露“我准备去A景点”这一信息旅行社只希望出售小淘出钱购买的那份资料而不泄露小淘未购买的N-1份资料
粗看起来这种隐私条件似乎是无法满足的旅行社只要把景点A的资料给到小淘就必然了解了“小淘正在关注A景点”这一信息除非旅行社把所有N份资料都给出但是这又违背了旅行社的利益
但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之在OT协议中旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密然后发送给小淘小淘可以从密文中解密出A的资料而无法解密出其他N-1份资料。
以下以N2为例基于Diffie-Hellman密钥交换协议给出一种1 of 2 OT实现方法的非正式描述其中SSender旅行社RReceiver小淘S拥有两份资料R希望取得其中的
S秘密生成随机数a; R秘密生成随机数bS将发送给R; R将发送给SS计算S以为密钥加密, 以k1为密钥加密,将和发送给R由于, 因此R可以计算出并解密出但R无法计算因此无法解密出。
如果R希望取得只需把第2步中的改为即可。 OT除了可以直接用于构造MPC方案之外也是GC等许多MPC方案的基石。
混淆电路
我们知道任意函数最后在计算机语言内部都是由加法器、乘法器、移位器、选择器等电路表示而这些电路最后都可以仅由AND和XOR两种逻辑门组成。一个门电路其实就是一个真值表例如AND门的真值表就是 例如其中右下格表示两根输入线(wire)都取1时输出wire1即 1 AND 1 1。
假设我们把每个wire都使用不同的密钥加密把真值表变成这样 例如其中右下格表示如果门的输入是b和d那么输出加密的f(密钥是b和d)。这个门从控制流的角度来看还是一样的只不过输入和输出被加密了且输出必须使用对应的输入才能解密解密出的f又可以作为后续门的输入。这种加密方式就称为“混淆电路(Garbled CircuitGC)”。
将电路中所有的门都按顺序进行这样的加密我们就得到了一个GC表示的函数。这个函数接收加密的输入输出加密的结果。
假设有两个参与方A和B各自提供数据a、b希望安全的计算约定的函数F(a,b)那么一种基于GC的安全两方计算协议过程可以非正式的描述如下
A把F进行加密得到GC表示的函数; 注意这里A是电路的生成者所以他了解每根wire的密钥A把自己的输入a使用第1步中对应的wire密钥加密得到Encrypt(a)A将Encrypt(a)、发送给BA将B的输入b使用第1步中对应的wire密钥加密得到Encrypt(b)并将Encrypt(b)发送给BB拥有完整的GC和输入因此可以运行电路得到加密的输出A把输出wire的密钥发给BB解密得到最终结果F(a,b)如果A需要的话B再把(a,b)发给A
细心的同学一定会指出第4步中A怎么可以接触B的输入b呢这不是违背了安全多方计算的假设吗这里就需要使用OTA扮演SenderB扮演Receiver让B从A处得到Encrypt( b)却不向A透露b的内容。如图所示 需要注意的是上述流程只是最原始的GC方法的不严谨描述GC后续还有Point Permute、Free XOR、Half Gates等多种细节优化随着最近几年的研究进展GC的性能已经差不多可以实用了。以求两个百万维向量的汉明距离(Hamming Distance)为例应用场景是两份数据求相似度却互相不泄露数据内容这样的安全两方计算已经可以在1.5秒左右完成。
安全多方计算的安全模型
半诚实行为模型与恶意行为模型
更细心的同学还会进一步提出问题“怎么确保A给B的就是一个正确的GC呢例如A和B商定要比a和b的大小商定了F(a,b)ab?1:0但是A可以制作一个别的函数的GC例如F(a,b)b的第1个比特这样显然是会侵害B的隐私的但是由于函数是以GC形式发给B的B是没有办法发现这个问题?”
这确实是一个安全问题事实上GC还存在如selective failure等其他更多的安全问题。在介绍解决方案之前我们需要先定义安全多方计算的安全模型。
安全多方计算的安全模型包含多个角度的内容在上述上下文中我们关注的是其中的“行为模型”即参与方可能进行何种行为以获取其他方的隐私。常见的行为模型包括“半诚实(Semi Honest)”和“恶意(Malicious)”两种。前者假设所有参与方都是忠实的按照协议步骤进行执行只是想通过协议内容推测其他方的隐私而后者假设恶意参与方为了获取其他方的隐私可以不遵循协议内容。
用扑克牌打个不严谨的比方半诚实的牌友会试图从自己的手牌和已经打出的牌来推测他人的手牌但是还是遵循扑克牌规则的而一个恶意的牌友则换牌、偷牌等手段无所不用。
可见本节开始提出的问题属于恶意行为的范畴而原始的GC只能说在半诚实行为模型下是安全的无法抵御恶意行为攻击。有许多对GC方案的改进方案可以达到恶意行为模型下的安全性但是它们都需要付出很大的性能代价仍然以求两个百万维向量的汉明距离为例其中最快的方法也需要10秒比同等的半诚实方案慢7倍以上。事实上经过我们的调研若想真正的实现支持大规模数据的MPC产品基本上只能考虑半诚实方案。这严重影响了安全多方计算的实用性。
公开可验证(Public Verifiable Covert, PVC)行为模型
PVC是在半诚实、恶意之间的一种折中。其主要思想是每个参与方的所有行为都自动带有类似签名的机制以供其他参与方存证。假设某个参与方实施恶意行为那么其他参与方可以有的概率发现称为威慑因子一般50%不能100%发现因为100%那就直接满足恶意行为模型了这一恶意行为并将该行为及其签名公开令作恶者承受名誉损失。考虑到名誉对一个数据所有者的重要性例如此后可能再也找不到合作50%左右的威慑力已经足以让理性者不考虑作恶。
PVC模型最开始是由学者在Asiacrypt2012【3】提出Asiacrypt2015【4】上也有学者提出相关的改进方案但是这些方案不仅效率较低而且只有复杂的理论描述实现可能性低。我们提出的新型PVC方案不仅协议简洁性能有大幅提升而且首次进行了完整的代码实现。仍然以求两个百万维向量的汉明距离为例使用我们威慑因子为50%的PVC方法大概只需要2.5秒。
以下仍假设有两个参与方A和B各自提供数据a、b希望安全的计算约定的函数F(a,b)以威慑因子50%为例给出我们的PVC方案的非正式描述
A选择两个随机种子s1和s2 B和A运行OT随机选择其中一个不妨设B获取了s1A使用s1和s2分别生成GC1和GC2B和A运行OT获取GC1中B输入wire的加密值我们后面可以看到GC1不会真正被使用因此这里可以不与b对应比如是任意常数值的密文B和A运行OT获取GC2中B输入wire对应的b的加密值A对GC1进行Hash并把Hash发给BA对GC2进行Hash并把Hash发给BA对上述所有流程进行签名并把签名发送给BB由于有s1因此可以自行生成GC1可以自己模拟第3步和第5步如果结果与A发的不一致则公布相关签名作为A作恶证据。如果一致就用GC2进行真实计算。
可见A如果作恶总有50%的概率被B抽查到因为A不知道B到底掌握了哪个GC的随机种子。因此理性的A会选择不作恶忠实的执行安全多方计算协议。
需要再次强调的是为便于理解所有的协议都仅仅是非正式描述有兴趣进一步研究细节的同学欢迎参阅我们的论文【1】。
总结
我们与马里兰大学等高校合作首次实现了一种“公开可验证(PVC)” 的安全两方计算方案这种方案的性能接近半诚实方案同时其PVC特性能够对作弊行为形成威慑力令其具有远强于半诚实模型的安全性具有很高的实用价值。
原文链接 本文为云栖社区原创内容未经允许不得转载。
