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

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

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

相关文章

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用

Java实现Excel与HTML互转

《Java实现Excel与HTML互转》Excel是一种电子表格格式,而HTM则是一种用于创建网页的标记语言,虽然两者在用途上存在差异,但有时我们需要将数据从一种格式转换为另一种格式,下面我们就来看看... Excel是一种电子表格格式,广泛用于数据处理和分析,而HTM则是一种用于创建网页的标记语言。虽然两

Java中Springboot集成Kafka实现消息发送和接收功能

《Java中Springboot集成Kafka实现消息发送和接收功能》Kafka是一个高吞吐量的分布式发布-订阅消息系统,主要用于处理大规模数据流,它由生产者、消费者、主题、分区和代理等组件构成,Ka... 目录一、Kafka 简介二、Kafka 功能三、POM依赖四、配置文件五、生产者六、消费者一、Kaf

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS?优势:应用场景:DFS配置步骤什么是DFS?DFS指的是分布式文件系统(Distr

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端:安装nfs-utils2、服务端:创建共享目录3、服

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作(适用于大文件)四、使用 pand

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一