计算机科学家实现密码学的“皇冠上的明珠”

2018年，加州大学洛杉矶分校(University of California，Los Angeles)研究生阿尤什·贾恩(Aayush Jain)前往日本，就他和同事正在开发的一种强大的加密工具进行了演讲。当他详细介绍团队对模糊处理(简称IO)的方法时，一位观众困惑地举起了手。

当时，这种怀疑是普遍存在的。如果能够建立起不可区分混淆，它将不仅能够隐藏数据集合，而且能够隐藏计算机程序本身的内部工作，从而创建一种密码主控工具，几乎所有其他密码协议都可以用它来构建。哈佛大学(Harvard University)的博阿兹·巴拉克(Boaz Barak)说，这是“一个密码原语来统治所有人”。但对于许多计算机科学家来说，正是这种力量让IO看起来太好了，以至于不像是真的。

计算机科学家提出了从2013年开始的iO候选版本。但是，随着其他研究人员想出如何打破这些建筑的安全，这些建筑产生的强烈兴奋逐渐消失了。以色列海法Technion的尤瓦尔·伊沙伊(Yuval Ishai)说，随着袭击事件的不断增加，“你可以看到很多负面的气氛。”他说，研究人员想知道，“谁会赢：制造者还是破坏者？”

加州大学伯克利分校西蒙斯计算理论研究所所长沙菲·戈尔德瓦瑟(Shafi Goldwasser)说：“有些人是狂热分子，他们相信[IO]，并一直在努力。”但随着时间的推移，她说，“这样的人越来越少了。”

现在，贾恩与华盛顿大学的林慧佳以及贾恩在加州大学洛杉矶分校(UCLA)的顾问阿米特·萨海(Amit Sahai)一起为制作人插上了一面旗帜。在8月18日发布在网上的一篇论文中，这三位研究人员首次展示了如何仅使用“标准”安全假设来构建无法区分的模糊处理。

所有的密码协议都建立在假设的基础上--有些协议，比如著名的RSA算法，依赖于一种普遍的信念，即标准计算机永远不可能快速将两个大素数的乘积相乘。密码协议的安全性取决于它的假设，而之前在iO上的尝试都是建立在未经测试且最终不稳固的基础上的。相比之下，新协议依赖于过去被广泛使用和研究的安全假设。

虽然该协议还远未准备好部署到现实世界的应用程序中，但从理论上讲，它提供了一种即时的方式来构建一系列以前遥不可及的加密工具。例如，它支持创建“可否认”加密和“功能性”加密，在“可否认”加密中，您可以可信地使攻击者相信您发送的消息与您实际发送的消息完全不同；在“功能性”加密中，您可以为选定的用户提供不同级别的访问权限，以便使用您的数据执行计算。

伊沙伊说，新的结果应该会让iO怀疑论者安静下来。他说：“现在，人们将不再怀疑模糊处理的存在。”“这似乎是个圆满的结局。”

几十年来，计算机科学家一直在想，是否有任何安全的、包罗万象的方法来混淆计算机程序，允许人们在不弄清自己的内部秘密的情况下使用它们。程序模糊可以启用许多有用的应用程序：例如，你可以使用一个模糊的程序将你的银行或电子邮件账户中的特定任务委托给其他人，而不用担心有人会以不是为你的帐户密码或读取密码的方式使用该程序(除非该程序是为输出密码而设计的)。

但到目前为止，所有建造实用混淆器的尝试都以失败告终。“那些在现实生活中流露出来的东西都坏得离谱，…。通常在放归野外后的几个小时内，“萨海说。他说，充其量，他们给攻击者提供了减速带。

2001年，理论方面也传来了坏消息：最强形式的混淆是不可能的。它被称为黑盒混淆，它要求攻击者除了通过使用程序并看到它的输出来观察到的东西之外，绝对不能了解任何关于程序的信息。巴拉克、萨海和其他五名研究人员展示了一些程序，它们如此坚定地揭示了它们的秘密，以至于它们不可能完全混淆。

然而，这些程序是特意编造的，以对抗混淆，与现实世界的程序几乎没有相似之处。因此，计算机科学家们希望能有其他类型的混淆，它既弱到足以可行，又强到足以隐藏人们真正关心的那类秘密。那些证明黑匣子混淆是不可能的研究人员在他们的论文中提出了一种可能的替代方案：不可区分混淆。

从表面上看，IO似乎不是一个特别有用的概念。它不需要隐藏程序的秘密，只需要对程序进行足够的模糊处理，以至于如果您有两个执行相同任务的不同程序，您就无法区分哪个混淆版本来自哪个原始版本。

但IO比听起来更强大。例如，假设您有一个执行与您的银行帐户相关的任务的程序，但该程序包含您未加密的密码，这使得您很容易受到任何获取该程序的人的攻击。然后--只要有一些程序可以在隐藏密码的同时执行相同的任务--一个难以辨别的混淆器就足够强大，能够成功地屏蔽密码。毕竟，如果它不是，那么如果你把这两个程序通过模糊处理器，你就能分辨出哪个模糊版本来自你的原始程序。

多年来，计算机科学家已经证明，你可以使用IO作为你能想象到的几乎所有密码协议的基础(除了黑匣子混淆)。这既包括传统的加密任务，如公钥加密(用于在线交易)，也包括令人眼花缭乱的新来者，如完全同态加密，在完全同态加密中，云计算机可以在不了解加密数据的情况下对其进行计算。它还包括没人知道如何构建的密码协议，比如可否认加密或功能性加密。

康奈尔大学(Cornell University)的拉斐尔·帕斯(Rafael Pass)表示，这真的是密码协议皇冠上的明珠。“一旦你做到了这一点，我们基本上可以得到一切。”

2013年，萨海和五名合著者提出了一种iO协议，将一个程序分割成类似拼图的东西，然后使用名为多线性地图的密码对象对单个拼图进行篡改。如果这些部分被正确地组合在一起，混淆就会消除，程序就会按预期运行，但每一个单独的部分看起来都没有意义。这一结果被誉为一项突破，并引发了数十篇后续论文。但在几年内，其他研究人员发现，在篡改过程中使用的多线性地图是不安全的。其他iO候选人也加入进来，轮到他们失败了。

巴拉克说：“有些人担心这可能只是一个海市蜃楼，也许IO根本就是不可能得到的。”他说，人们开始感觉到，“也许整个企业注定要失败。”

2016年，林开始探索是否有可能通过简单地减少对多线性地图的要求来绕过它们的弱点。多线性地图本质上只是一种秘密的多项式计算方式--由数字和变量的和与积组成的数学表达式，比如3XY+2 YZ 2。贾恩说，这些地图需要某种类似于多项式计算器的东西，连接到一个包含变量值的秘密储物柜系统。输入机器接受的多项式的用户可以查看最后一个储物柜，以确定隐藏的值是否使多项式的值为0。

为了确保该方案的安全性，用户应该无法弄清楚其他储物柜中的内容或沿途生成的号码的任何信息。“我们希望这是真的，”萨海说。但在人们能想到的所有候选多线型地图中，打开最终储物柜的过程揭示了本应隐藏的计算信息。

由于提议的多线性地图机器都存在安全漏洞，林想知道是否有一种方法可以使用机器来构建IO，而不需要计算许多不同类型的多项式(因此可能更容易安全地构建)。四年前，她想出了如何只使用多线性映射来构建IO，这些多线性映射计算的多项式的“阶数”不超过30(这意味着每个项最多是30个变量的乘积，计算重复次数)。在接下来的几年里，她、萨海和其他研究人员逐渐想出了如何将度数降低到更低的水平，直到他们能够展示如何仅使用3度多线地图来构建iO。

从纸面上看，这似乎是一个巨大的进步。Jain说，只有一个问题：从安全的角度来看，“3次实际上就像能处理每一次多项式的机器一样坏了”。

研究人员知道如何安全构建的唯一多线性地图是那些计算2次或更低阶多项式的地图。林与贾恩和萨海联手，试图找出如何从2阶多线性地图构建IO。但是“我们被困了很长一段时间，”林说。

萨海回忆说：“那是一段令人沮丧的时期。”“这里有一个墓地，里面堆满了所有不起作用的想法。”

然而，最终，他们与加州大学圣巴巴拉分校(University of California，Santa Barbara)的普拉汉扬·阿南斯(Prabhanjan Ananth)和区块链项目协和(Concordium)的克里斯蒂安·马特(Christian Matt)一起想出了一个折衷方案：既然IO似乎需要3度地图，但计算机科学家只有2度地图的安全结构，如果有介于两者之间的某种东西--2.5度地图呢？

研究人员设想了一种系统，其中一些储物柜有清晰的窗户，这样用户就可以看到里面包含的值。这使机器不必保护过多的隐藏信息。为了在高次多线性映射的能力和二次映射的安全性之间取得平衡，机器被允许使用高于2次的多项式进行计算，但有一个限制：关于隐藏变量的多项式必须是2次。林说，“我们试图不像一般的多线性地图那样隐藏太多。”研究人员能够证明，这些混合储物柜系统可以安全地建造。