密码学家设计了一种全面搜索隐私的方法广达杂志

我们都知道要小心我们在网上分享的细节，但我们寻求的信息也可能会泄露信息。 搜索行车路线，我们的位置就变得更容易猜测。 在大量泄露的数据中检查密码，我们自己就有泄露密码的风险。

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

制定解决这个问题的策略（称为私人信息检索）是“许多隐私保护应用程序中非常有用的构建块，”说。 吴大卫，德克萨斯大学奥斯汀分校的密码学家。 自 1990 世纪 XNUMX 年代以来，研究人员逐渐解决了这个问题，改进了私下访问数据库的策略。 一个主要目标（对于大型数据库来说仍然是不可能的）相当于私人谷歌搜索，您可以在其中匿名筛选大量数据，而无需进行任何繁重的计算工作。

现在，三位研究人员 精雕细琢 一个长期寻求的私人信息检索版本，并将其扩展以构建更通用的隐私策略。 该作品获得了 最佳论文奖 六月在年度 计算理论研讨会，推翻了真正私人搜索道路上的一个主要理论障碍。

“[这是]密码学中的东西，我想我们都想要但不太相信它存在，”说 维诺德·维昆塔纳森是麻省理工学院的密码学家，他没有参与这篇论文。 “这是一个具有里程碑意义的结果。”

私有数据库访问问题在 1990 世纪 XNUMX 年代初露端倪。 起初，研究人员认为唯一的解决方案是在每次搜索时扫描整个数据库，这就像让图书管理员在带书回来之前搜索每个书架一样。 毕竟，如果搜索跳过任何部分，图书馆员就会知道您的书不在图书馆的该部分。

这种方法在较小规模下效果很好，但随着数据库的增长，扫描数据库所需的时间至少成比例增长。 当你从更大的数据库中读取数据时——互联网是一个相当大的数据库——这个过程变得极其低效。

2000 年代初，研究人员开始怀疑他们可以通过“预处理”数据库来避开全扫描障碍。 粗略地说，这意味着将整个数据库编码为特殊结构，因此服务器可以通过读取该结构的一小部分来回答查询。 从理论上讲，足够仔细的预处理可能意味着托管信息的单个服务器本身只经历一次该过程，从而允许所有未来的用户无需更多努力即可私下获取信息。

针对 丹尼尔·威克斯东北大学的密码学家、这篇新论文的合著者，这似乎好得令人难以置信。 2011年左右，他开始尝试证明这种方案是不可能的。 “我确信这是不可能做到的，”他说。

但在 2017 年，两组研究人员 出版 结果 这改变了他的想法。 他们构建了第一个可以进行此类私人信息检索的程序，但他们无法证明这些程序是安全的。 （密码学家通过证明破解系统与解决某些难题一样困难来证明系统的安全性。研究人员无法将其与规范的难题进行比较。）

因此，即使怀有新的希望，威克斯认为这些程序的安全版本仍然还有很长的路要走。 相反，他和他的合著者—— 林伟凯，现在在弗吉尼亚大学，并且 伊森·莫克同样在东北大学 - 致力于解决他们认为更容易的问题，其中涉及多个服务器托管数据库的情况。

在他们研究的方法中，数据库中的信息可以转换为数学表达式，服务器可以评估该数学表达式以提取信息。 作者认为，或许可以提高评估过程的效率。 他们考虑了 2011 年的一个想法，当时其他研究人员找到了一种通过预处理来快速评估此类表达式的方法，创建特殊、紧凑的值表，使您可以跳过正常的评估步骤。

这种方法没有产生任何改进，该小组几乎放弃了——直到他们想知道这个工具是否真的可以在令人垂涎的单服务器情况下工作。 他们发现，只要足够仔细地选择一个多项式，一台服务器就可以根据 2011 年的结果对其进行预处理，从而产生 Wichs 多年来思考的安全、高效的查找方案。 突然间，他们终于解决了更难的问题。

起初，作者们并不相信。 “让我们弄清楚这到底出了什么问题，”威克斯回忆道。 “我们一直试图找出它的故障所在。”

但解决方案仍然成立：他们确实发现了一种安全的方法来预处理单服务器数据库，以便任何人都可以秘密提取信息。 “这确实超出了我们的预期，”说 尤瓦尔·伊沙伊（Yuval Ishai）是以色列理工学院的密码学家，他没有参与这项工作。 他说，这是“我们甚至没有勇气去要求的”结果。

威克斯说，在建立了秘密查找方案后，作者转向私人互联网搜索的现实目标，这比从数据库中提取信息更复杂。 私人查找方案本身确实允许类似谷歌的私人搜索版本，但它是极其劳动密集型的：您自己运行谷歌的算法，并在必要时秘密地从互联网上提取数据。 Wichs 表示，真正的搜索，即您发送请求并在服务器收集结果时坐下来，实际上是一种更广泛的同态加密方法的目标，这种方法可以伪装数据，以便其他人可以在不知道任何信息的情况下操纵它。

典型的同态加密策略会遇到与私人信息检索相同的障碍，每次搜索都会缓慢地浏览所有互联网内容。 但是，作者使用他们的私有查找方法作为脚手架，构建了一个新方案，该方案运行的计算更像我们每天使用的程序，秘密地提取信息而无需席卷整个互联网。 这将为互联网搜索和任何需要快速访问数据的程序提供效率提升。

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

目前，这两种方案都没有实际用处：当数据库大小膨胀到无穷大时，预处理目前在极端情况下会有所帮助。 但实际部署它意味着这些节省无法实现，而且这个过程会消耗太多的时间和存储空间。

Vaikuntanathan 表示，幸运的是，密码学家长期以来一直在优化最初不切实际的结果。 如果未来的工作能够简化该方法，他相信从大型数据库中进行私人查找可能是可以实现的。 “我们都以为我们被困在那里了，”他说。 “丹尼尔的结果带来了希望。”

广达 正在进行一系列调查，以更好地为我们的观众服务。 就拿我们的 计算机科学读者调查 您将有机会免费赢取 广达 商品。