安全多方计算新突破!阿里首次实现“公开可验证” 的安全方案...

本文主要是介绍安全多方计算新突破!阿里首次实现“公开可验证” 的安全方案...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

image

阿里妹导读:近日,阿里安全双子座实验室与马里兰大学等高校合作的论文《Covert Security with Public Verifiability: Faster, Leaner, and Simpler 》【1】被欧洲密码年会(Eurocrypt)2019接收。这是国内公司在安全多方计算领域的第一篇顶会论文(Eurocrypt2018只有3篇大陆作者论文,难度可见一斑)。

今天,我们邀请阿里高级安全专家鸿程,深入解读业界首个“公开可验证(PVC)” 的安全两方计算方案。

安全多方计算介绍

安全多方计算( Secure Multi-Party Computation,MPC)于1986 年由姚期智院士提出【2】。安全多方计算协议允许多个数据所有者在互不信任的情况下进行协同计算,输出计算结果,并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说,MPC技术可以获取数据使用价值,却不泄露原始数据内容。

image


互联网已经完成了从IT时代向DT时代的转变,数据已经成为DT时代企业的核心竞争力。数据作为一种新能源,只有流动起来才能产生价值。不过,大多数企业考虑到数据安全和个人隐私等问题,对数据共享都非常谨慎。而MPC对打破数据孤岛,实现数据的可控共享,具有重要的理论和现实意义。

MPC方案主要可分为基于混淆电路(Garbled Circuit,GC)和基于秘密共享两种。本文主要关注GC类方案。

不经意传输(Oblivious Transfer)

我们首先介绍一种基础的安全多方计算协议:不经意传输(Oblivious Transfer, OT)。

来看一个例子:假设某旅行社拥有N个景点的旅游资料,小淘想去其中的A景点游玩,希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私,不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件:

  1. 小淘不希望向旅行社泄露“我准备去A景点”这一信息;
  2. 旅行社只希望出售小淘出钱购买的那份资料,而不泄露小淘未购买的N-1份资料;

粗看起来这种隐私条件似乎是无法满足的:旅行社只要把景点A的资料给到小淘,就必然了解了“小淘正在关注A景点”这一信息;除非旅行社把所有N份资料都给出,但是这又违背了旅行社的利益;

但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之,在OT协议中,旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密,然后发送给小淘;小淘可以从密文中解密出A的资料,而无法解密出其他N-1份资料。

以下以N=2为例,基于Diffie-Hellman密钥交换协议,给出一种1 of 2 OT实现方法的非正式描述;其中S(Sender)=旅行社,R(Receiver)=小淘,S拥有两份资料image,R希望取得其中的image

  1. S秘密生成随机数a; R秘密生成随机数b;
  2. S将image发送给R; R将image发送给S;
  3. S计算image
  4. S以image为密钥加密image, 以k1为密钥加密image,将imageimage发送给R;
  5. 由于image, 因此R可以计算出image,并解密出image,但R无法计算image,因此无法解密出image

如果R希望取得image,只需把第2步中的image改为image即可。

image

OT除了可以直接用于构造MPC方案之外,也是GC等许多MPC方案的基石。

混淆电路

我们知道,任意函数最后在计算机语言内部都是由加法器、乘法器、移位器、选择器等电路表示,而这些电路最后都可以仅由AND和XOR两种逻辑门组成。一个门电路其实就是一个真值表,例如AND门的真值表就是:

image

例如其中右下格表示两根输入线(wire)都取1时,输出wire=1:即 1 AND 1 = 1。

假设我们把每个wire都使用不同的密钥加密,把真值表变成这样:

image

例如其中右下格表示如果门的输入是b和d,那么输出加密的f(密钥是b和d)。这个门从控制流的角度来看还是一样的,只不过输入和输出被加密了,且输出必须使用对应的输入才能解密,解密出的f又可以作为后续门的输入。这种加密方式就称为“混淆电路(Garbled Circuit,GC)”。

将电路中所有的门都按顺序进行这样的加密,我们就得到了一个GC表示的函数。这个函数接收加密的输入,输出加密的结果。

假设有两个参与方A和B各自提供数据a、b,希望安全的计算约定的函数F(a,b),那么一种基于GC的安全两方计算协议过程可以非正式的描述如下:

  1. A把F进行加密,得到GC表示的函数image; (注意这里A是电路的生成者,所以他了解每根wire的密钥);
  2. A把自己的输入a使用第1步中对应的wire密钥加密,得到Encrypt(a);
  3. A将Encrypt(a)、image发送给B;
  4. A将B的输入b使用第1步中对应的wire密钥加密,得到Encrypt(b),并将Encrypt(b)发送给B;
  5. B拥有完整的GC和输入,因此可以运行电路得到加密的输出;
  6. A把输出wire的密钥发给B,B解密得到最终结果F(a,b);
  7. 如果A需要的话,B再把(a,b)发给A;

细心的同学一定会指出:第4步中A怎么可以接触B的输入b呢?这不是违背了安全多方计算的假设吗?这里就需要使用OT,A扮演Sender,B扮演Receiver,让B从A处得到Encrypt( b),却不向A透露b的内容。如图所示:

image

需要注意的是,上述流程只是最原始的GC方法的不严谨描述,GC后续还有Point & Permute、Free XOR、Half Gates等多种细节优化,随着最近几年的研究进展,GC的性能已经差不多可以实用了。以求两个百万维向量的汉明距离(Hamming Distance)为例(应用场景是两份数据求相似度,却互相不泄露数据内容),这样的安全两方计算已经可以在1.5秒左右完成。

安全多方计算的安全模型

半诚实行为模型与恶意行为模型

更细心的同学还会进一步提出问题:“怎么确保A给B的image就是一个正确的GC呢?例如A和B商定要比a和b的大小,商定了F(a,b)=a>b?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是在半诚实、恶意之间的一种折中。其主要思想是:每个参与方的所有行为都自动带有类似签名的机制以供其他参与方存证。假设某个参与方实施恶意行为,那么其他参与方可以有image的概率发现(image称为威慑因子,一般>=50%,不能100%发现,因为100%那就直接满足恶意行为模型了)这一恶意行为,并将该行为及其签名公开,令作恶者承受名誉损失。考虑到名誉对一个数据所有者的重要性(例如此后可能再也找不到合作),50%左右的威慑力已经足以让理性者不考虑作恶。

PVC模型最开始是由学者在Asiacrypt2012【3】提出,Asiacrypt2015【4】上也有学者提出相关的改进方案,但是这些方案不仅效率较低,而且只有复杂的理论描述,实现可能性低。我们提出的新型PVC方案不仅协议简洁,性能有大幅提升,而且首次进行了完整的代码实现。仍然以求两个百万维向量的汉明距离为例,使用我们威慑因子为50%的PVC方法大概只需要2.5秒。

以下仍假设有两个参与方A和B各自提供数据a、b,希望安全的计算约定的函数F(a,b),以威慑因子image=50%为例,给出我们的PVC方案的非正式描述:

  1. A选择两个随机种子s1和s2, B和A运行OT随机选择其中一个(不妨设B获取了s1);
  2. A使用s1和s2分别生成GC1和GC2;
  3. B和A运行OT获取GC1中B输入wire的加密值(我们后面可以看到GC1不会真正被使用,因此这里可以不与b对应,比如是任意常数值的密文);
  4. B和A运行OT获取GC2中B输入wire对应的b的加密值;
  5. A对GC1进行Hash,并把Hash发给B;
  6. A对GC2进行Hash,并把Hash发给B;
  7. A对上述所有流程进行签名,并把签名发送给B;
  8. B由于有s1,因此可以自行生成GC1,可以自己模拟第3步和第5步;如果结果与A发的不一致,则公布相关签名作为A作恶证据。如果一致,就用GC2进行真实计算。

可见,A如果作恶,总有50%的概率被B抽查到(因为A不知道B到底掌握了哪个GC的随机种子)。因此理性的A会选择不作恶,忠实的执行安全多方计算协议。

需要再次强调的是,为便于理解,所有的协议都仅仅是非正式描述,有兴趣进一步研究细节的同学欢迎参阅我们的论文【1】。

总结

我们与马里兰大学等高校合作,首次实现了一种“公开可验证(PVC)” 的安全两方计算方案,这种方案的性能接近半诚实方案,同时其PVC特性能够对作弊行为形成威慑力,令其具有远强于半诚实模型的安全性,具有很高的实用价值。

原文发布时间为:2019-03-12
本文作者:鸿程
本文来自云栖社区合作伙伴“ 阿里技术”,了解相关信息可以关注“ 阿里技术”。

这篇关于安全多方计算新突破!阿里首次实现“公开可验证” 的安全方案...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/406987

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影