RSS订阅信息安全技术跟踪与研究:技术、平台、会议、论文、产业
你现在的位置:首页 / 学术研究 / 正文

基于最小假设的快速安全两方函数计算:Fast Two-Party Secure Computation with Minimal Assumptions

0 学术研究 | 2015年3月6日
转载申明:本站原创,欢迎转载。但转载时请保留原文地址。
原文地址:http://www.vonwei.com/post/F2PSwithMinAssump.html

Fast Two-Party Secure Computation with Minimal Assumptions

         这是一个关于安全函数计算的文章,发表在计算机安全领域的顶会CCS2013上,作者团队来自美国弗吉尼亚大学,该大学在安全函数计算方便出了很多成果,看最近几年的顶会上,基本都能看到他们的贡献。比较崇拜的是第一个作者Abhi shelat(其主页为https://www.cs.virginia.edu/~shelat/),崇拜的原因不用多说,看主页就知道,不但科研做的很好,还能分身合伙打造了一个创业性公司,其公司是做360度拍照和摄影的(https://arqspin.com),表面上看与其研究没有多大关系吧。

         现在无论上京东、淘宝还是其他网站购物,我们首先都会看物品的图片,经常看到很多网站从不同的侧面来拍某个物品进行展示,然后上传很多照片在网站上,购买者只能一个一个的看。以前习惯了这种模式,一张一张的看一个产品的不同侧面,来确定这个产品是否是自己需要的。很少有人想到过用一张用户能自己控制的动态3D图来代替这种模式吧,不但在网页上占用空间小,用户自己动态旋转图片,就像在三维空间中操作,看到物品的不同侧面,体验效果会非常好。作者公司的产品就是做这个的,确实效果很好,可以去他们网站观摩一下,先点赞一个。

         废话不多说了,先理解下这篇文章的思路。

         安全函数计算是一个比较重要的密码学安全问题,已经研究几十年了,但一直都没有实用的产品出来。之所以还一直热度不减,可能也在于其实际意义,也就是隐私性和安全性。其解决的一个基本问题是“Alice拥有一个输入xBob拥有一个输入y,它们想要共同计算某个函数f(x,y),计算结束后,Alice能获得计算结果但是不会知道y的任何信息,Bob也类似”。这样一个基本问题扩展开来,可以满足很多有意思的需求。比如,你手机上有个联系人记录,你朋友手机上也有他自己的联系人记录,你们想知道你们共同的联系人,而又不想让对方知道你手机上的其它联系人。再比如,你暗恋某个人,你哥们也暗恋一个人,你们可能想知道是不是同一个,但是又不能把心中暗恋的人透露给对方。接着比如,一群朋友想聚会,想找到一个离大家都最方便的地方,但是又不想让其它人知道自己目前的位置。这些有意思的实际问题,通过安全函数计算就可以解决。

         通常的解决方案是采用混淆电路(Garbled CircuitGC),首先将要计算的函数f(x,y)用布尔电路构造出来。AliceBob想要共同计算一个用布尔电路C表示的函数,计算过程需要保证安全性和隐私性。Alice准备电路C的一个混淆版本(或者加密版本,称为混淆电路Garbled Circuit),并连同相关的随机输入密钥一起发送给Bob。这样,Bob不用知道Alice的任何输入以及中间值,就可以计算出电路的输出,并发送给Alice,作为双方接受的最终计算结果。

         布尔电路的输入\输出线路通常是0或者1的比特串,而对应的混淆电路的线路是随机的密钥值(或者称为混淆值)。每条线路有两个随机密钥值,分别对应01,计算时只能使用其中之一。Alice的隐私输入为x,其构造电路时可以根据x的二进制比特位,选择其输入线路对应的随机密钥值,发送电路计算者Bob;而Bob隐私输入y串对应的随机密钥值,需要通过多次OTOblivious Transfer)协议从Alice处获取对应的随机密钥值,OT协议可以保证不泄露Bob的隐私输入yAliceAlice构造混淆电路时,会采用加密、变换等手段为电路中每个门生成真值表,称为混淆真值表。Bob获得混淆真值表和xy对应的输入随机密钥值后,就可以应用真值表计算混淆电路,获得最终输出,最后使用解密门电路可以得到实际的输出f(x,y)

         如果参与方AliceBob是诚实的,GC可以很好的进行安全计算。但是,在实际应用场景中,特别是在互联网或者移动互联网上进行安全计算,假设一个诚实的参与方是很难的。通常会出现恶意的参与方,如恶意的Alice可能构造错误的电路来欺骗获得Bob的隐私输入,恶意的Bob可能发送错误的输出给Alice

         为了保证混淆电路GC的正确构造,防止恶意攻击者,最常见有效的一种方式是采用“circuit-level cut-and-choose”技术:Alice构造多个混淆电路副本,每个副本拥有独立不同的随机数,并发送给Bob,让Bob随机选择部分电路(称为检测电路);BobAlice打开这些电路,检测是否正确构造,如果Alice有欺骗的意图,Bob就终止协议;如果检测电路验证通过,Bob可以计算其余的电路(称为实际计算电路),对比计算结果,选择大部分电路输出相同的值作为最终计算结果。显然,如果Alice构造了过多的错误欺骗电路,会被发现(通过检测电路);而如果Alice只构造了很小部分的欺骗电路,不会影响最终的结果(计算结果选取的是大部分GC电路计算的相同值,少数不同值被丢弃掉了)。而且该方法可以并行运行,提高计算效率。

         虽然上面的技术能起到一定作用,但还存在几个实际障碍:

         1)在构造的多个不同GC副本中,恶意Alice可能针对不同GC提供不同的隐私输入值。试想,如果f(x,y)是一个线性函数功能,每个GC提供一个方程,通过多个不同的x,是可能计算出y的。这样Alice就很可能获得Bob的隐私信息,破坏安全函数计算的本质。

         2)目标函数f(x,y)计算最后实际上得到两个输出,Bob作为电路计算者能够得到其输出,而Alice作为电路生成者从Bob处能获得输出,如何保证Alice得到输出结果的隐私性和真实性(特别是面对恶意的Bob)?隐私性指“Bob不应该获得Alice的输出值”,真实性指“Alice要么获得一个真实的输出,要么根本获不到输出,这种情况认为Bob在欺骗”。

         3)我们知道GC电路存在混淆真值表,实际上由随机混淆值(或者密钥值)构成;而OT协议也会将Bob输入对应的混淆值发送给Bob。如果恶意的AliceGC电路和OT中使用不同的随机混淆值,就可能破坏Bob的输入隐私。例如,恶意AliceGC电路的一个输入线路上委派值为(K0K1),恶意AliceOT交互中使用(K0K2),K1不等于K2;如果Bob对应的输入比特位为0,那么其能从OT中得到K0,可以顺利完成GC的计算;如果Bob对应的输入比特位为1,那么其从OT得到的是K2,而GC中实际需要的值是K1,这样电路计算就会受阻;Alice可以很容易通过上面的区分来识别Bob的比特位是0还是1

         cut-and-choose技术以及这三个问题,之前有很多文献也提供过解决方案,但是都依赖比较复杂的密码学代数假设,而且计算和通信复杂度都挺高,不适合实际使用。 Fast Two-Party Secure Computation with Minimal Assumptions”这篇文章实际上也是解决这三个问题,不过通过题目可以看到他们的主要贡献点:Fast,即提供安全函数计算的效率;Minimal Assumptions,即尽量使用简单常用的技能解决,减少对复杂难题假设的依赖。

         针对第一个问题,本文采用“2-Universal Hash Function”,即通用的哈希函数,增加辅助电路对Alice的输入值进行哈希,哈希的天然“防碰撞”特性可以保证每个GC电路输入的一致性,Bob可以检查h(x)。如果x所在域的规模很小,Bob通过穷举方法计算x所在域上的所有哈希值是可以找到x的,因此本文并不直接对x进行哈希,而是Alice生成一个随机数r来增加输入的熵值,即h(x||r)。为了方便实现,hash功能是通过一个矩阵来实现的,即hM(x)=M * x M为矩阵),这样实现的好处是,hM(x)对异或操作有同态性质,哈希可以直接在本地计算后发送给Bob

         针对第二个问题,本文采用对称加密以及一个WIWitness-Indistinguishable)证明过程。GC的输出门存在随机混淆值(也是密钥值),用其对Alice的输出结果加密,可以保证Bob无法得到其输出结果;而为了证明该输出结果确实来自Alice构造的某个混淆电路GC,同时不泄露具体使用的那个混淆值加密(可能会泄露Bob的隐私),本文构造了一个WI证明过程,主要使用承诺机制commitment)实现该证明过程。

         针对第三个问题,本文采用“k-probe-resistant Matrix”方法,也是使用矩阵。Bob并不直接输入y,而是输入一个y’,两者之间的关系是:M * y’ = y。构造一个辅助电路将y’变化成真正的y,即可保证正确性。这样,Alice会获得y’的部分比特信息,在M拥有一定的相关安全参数情况下,这些信息不足以泄露y的任何比特信息。实际上,k是安全参数,电路构造者要想学习到Bob输入隐私y的信息,必须至少使用2k次探测输入x

 



  • ------------------分隔线----------------

  • 如果感兴趣,欢迎关注本站微信号,跟踪最新博文信息,手机微信扫一扫下面的二维码,即可关注!
  • 微月信公众号
  • 推荐您阅读更多有关于“ 安全函数计算  安全多方计算  茫然传送  不经意传输  混淆电路  Garbled Circuit  Oblivious Transfer   ”的文章

    请填写你的在线分享代码
    上一篇:信息安全与密码学博士:应该掌握的52个知识点下一篇:52知识点之一:各种处理器的区别

    猜你喜欢

    评论列表:

    发表评论

    必填

    选填

    选填

    必填,不填不让过哦,嘻嘻。

    记住我,下次回复时不用重新输入个人信息

    本站介绍
    最近发表
    本年最热文章
    本月最热文章
    网站分类
    文章归档