荐读丨密码学家设计出私密信息检索技术

我们都知道要小心对待我们在网上分享的细节信息，其实我们搜寻的内容也可能会暴露信息。如搜索驾驶路线，我们的位置就会变得极容易猜到；在大量被泄露的数据中查找密码，我们就面临自己泄露密码的风险。

这些情况引出了密码学领域的一个关键问题：如何从公共数据库中提取信息，又不暴露访问内容的任何信息？这就相当于从图书馆借了一本书，而图书管理员不知道是哪一本书。

美国得克萨斯大学奥斯汀分校的密码学家David Wu表示，制定一种解决这个问题的策略（即所谓的私密信息检索）是“许多保护隐私的应用程序中一种非常有用的基本模块”。

自20世纪90年代以来，研究人员一直在努力解决这个问题——改进私密访问数据库的策略。一个主要的目标（对于大型数据库来说仍然不可能实现）相当于私密谷歌搜索，即你可以匿名筛选一大堆数据，无需进行任何繁重的计算操作。

现在，三位研究人员精心设计出一种私密信息检索技术，并在此基础上制定了一种更通用的隐私策略。这项研究在今年6月的年度计算理论研讨会上获得了最佳论文奖，它扫除了通往真正私密的搜索道路上的一大理论上的障碍。

麻省理工学院的密码学家Vinod Vaikuntanathan表示：“这是里程碑式的重大成果。”

私密数据库访问的问题在20世纪90年代形成。起初，研究人员以为唯一的解决办法是在每次搜索时扫描整个数据库，这就好比检索你要找的书时，图书管理员把每个书架都翻遍一样。毕竟，如果搜索跳过了任何部分，图书管理员就会知道你要找的书不在图书馆的那个对应区。

规模比较小时 ，这种方法的效果足够好，但是随着数据库日益庞大，扫描数据库所需的时间至少会成比例地增长。当从更大的数据库中读取时（互联网是个庞大的数据库），这个过程就变得非常低效。

在21世纪初，研究人员开始觉得他们可以通过“预处理”数据库来避开全面扫描这个障碍。粗略地说，这意味着将整个数据库编码为一个特殊的结构，这样服务器就可以通过读取该结构的仅仅一小部分来回答查询。从理论上讲，足够仔细的预处理可能意味着，一台托管信息的服务器只需要经历一次这个过程，允许所有未来的用户无需花更大的精力就可以私密获取信息。

2017年，两组研究人员编写出首批可以进行这种私密信息检索的程序，但他们无法证明这些程序是安全的。（密码学家通过证明破解一个系统就像解决某个难题一样困难来证明系统的安全性。研究人员无法将其与标准的难题进行比较。）

在他们研究的方法中，数据库中的信息可以转换成一个数学表达式，服务器可以对其进行计算以提取信息。论文作者认为，可以使这个评估过程更有效。他们尝试了2011年的一个想法，当时其他研究人员发现了一种方法，可以通过预处理来快速评估这样一种表达式，创建特殊的紧凑值表，以便略过正常的评估步骤。

这种方法没有带来任何改进，研究小组差点就要放弃，直到他们想搞清楚这个工具在单服务器情况下是否果真可以适用。他们发现，只要足够小心地选择一个多项式，单单一台服务器就可以根据2011年的结果对其进行预处理，从而获得了Wichs已思考多年的安全高效的查找方案。

Wichs表示，在设计了秘密查找方案之后，论文作者转向了私密互联网搜索的实际目标，这比从数据库中提取信息要复杂得多。私密查找方案本身确实允许类似谷歌的秘密搜索，但它非常耗费人力：你自己运行谷歌的算法，并在必要时从互联网上秘密提取数据。真正的搜索（你发出请求，然后静等服务器收集结果）实际上是同态加密这种更广泛的方法力求实现的目标，这种方法掩盖数据，以便其他人可以在一无所知的情况下操纵数据。

典型的同态加密策略会遇到与私密信息检索同样的障碍，每次搜索都要长时间地搜索互联网上的所有内容。但是使用私密查找方法作为基本框架，论文作者设计出了一种新的方案，该方案运行的计算更像我们每天使用的程序，在不搜遍整个互联网的情况下秘密提取信息。

这将为互联网搜索和任何需要快速访问数据的程序提高效率。

Ishai表示，虽然同态加密是私密查找方案的一种实用扩展，但他认为私密信息检索是更为根本性的问题。论文作者的解决方案是“神奇的构建模块”，他们的同态加密策略是自然而然的后续策略。

目前，这两种方案都没有实际用途。幸运的是，Vaikuntanathan表示，未来从大型数据库中进行私密查找将触手可及。