@ 2021.08.29 , 10:57

效率比原理论最佳算法高出25% 安全计算领域大突破

俄勒冈州立大学的研究人员开发了一种安全计算协议,其效率比原本的理论最佳算法还高25%,这意味着对于需要合作计算的团体来说,未来可以节省时间和能源成本,同时保持他们个人数据的安全。

OSU工程学院计算机科学副教授Mike Rosulek和研究生Lance Roy在本月虚拟的第41届国际密码学年会(即Crytpo 2021)上介绍了他们的发现。该会议由国际密码学研究协会组织。

22岁的Roy在科瓦利斯长大,18岁时进入俄勒冈州立大学的计算机科学博士课程,直接从家庭学校的高中进入俄大研究生院。他在12岁时就开始在俄勒冈州立大学旁听本科课程。

安全计算可以用 "姚氏百万富翁问题" 作为示例,这是一个由计算机科学家和计算理论家安德鲁·姚(姚期智)提出并以其名字命名的问题,即两个富人想确定谁更富有,但都不想向对方透露她/他有多少钱。

"在现实生活中,公司和其他团体会商定要运行的计算,然后他们做一些加密的魔术,使所有人只知道计算的最终结果——输入和中间结果仍然是私有的。"Rosulek说,"我最喜欢的一个例子是,波士顿市想要回答该市科技部门是否存在基于性别的工资差距问题。科技公司集体计算了他们的综合工资数据的相关汇总,但没有任何公司需要透露其工资数据。"

安全计算协议中的一项标准技术是混淆电路,它可以有多种结构。混淆电路是实现通用安全计算协议的少数方法之一,只需在相关各方之间进行几轮通信,Rosulek解释道。

"混淆电路的最有效构造来自我以前的一篇论文,在2015年,"Rosulek说(Twitter账号是@GarbledCircus0,"在那篇论文中,我们也给出了一些很好的证据,证明这是你能得到的最有效的方法。我真的相信不可能做得更好,自2015年以来,我一直试图确凿地证明不可能做得更好。这个最新的结果是一个很大的惊喜,因为我们展示了如何突破既有理论。"

Rosulek将Roy描述为更有效的混淆电路背后的 "策划者",这涉及他们称之为 "切片和切块"的思想。

"我已经不再试图证明现有理论的最优性了。"Rosulek说,"Lance对这个问题很熟悉,但这并不是我们共同的工作。当Lance带着出格的想法来找我时,我非常怀疑,但事实证明,他的直觉是正确的,他很快就说服了我,他这个疯狂的新想法是可行的。"

Roy解释说,一个正常的计算机电路包含对数据进行基本计算的门。在一个混淆电路中,这些门被修改过——乱码——所以流经它们的数据被加密了。

在试图证明2015年的混淆电路技术不能被改进时,Roy发现,如果一个门使用输入的所有信息,或者不使用任何信息,他的证明想法是有效的,但如果它使用其中的一些信息,则不成立。这个概念,即切片,使他的思维转向试图改进2015年的技术,而不是证明它不可能被做得更好。

"然而,我也有一个新问题,切片的工作方式,会泄露太多的信息,使混乱的电路变得(不)安全。"

一年多后,在2020年夏末,他想出了一个解决方案:切块。

"如果构建混淆电路的方式是随机的——即通过掷骰子和其他一些信息被保密,切片的想法可以变得安全。"当我把它展示给Mike时,他真的很兴奋,在2021年冬季,我们完善了这项技术并写出了结果。"

https://techxplore.com/news/2021-08-osu-cryptography-huge-efficiency-gain.html


支付宝打赏 [x]
您的大名: 打赏金额:

赞一个 (8)