效率比原理论最佳算法高出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