Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
本文提出了一种用于十亿级规模全同态加密下最近邻搜索的 GPU 加速系统，该系统通过结合秩缩减（rank reduction）和分层路由技术实现了实际的延迟性能，同时通过种子填充（seeded padding）对相关的几何泄漏进行了量化与缓解。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，你拥有一个包含数十亿张照片的图书馆，你想找到一张与你口袋里照片最相似的照片。通常情况下，计算机需要扫描每一张照片来寻找匹配项，但如果由于照片涉及隐私而无法向计算机展示你的图片怎么办？如果这个图书馆是由一个你不信任的陌生人拥有的呢？这就是研究人员试图解决的问题。他们想要一种方法，让计算机能够在从未看到实际查询内容的情况下，搜索一个庞大的、秘密的数据库。为了实现这一点，他们使用了一种称为全同态加密的方法，这就像是将你的问题放入一个透明的锁闭箱中。计算机可以在不打开箱子的情况下对箱子进行计算，并返回一个仍然处于锁定状态的结果。只有持有钥匙的你，才能打开最终的箱子并看到答案。多年来，这个想法由于维持箱子锁定的数学运算极其沉重，以至于在处理海量数据时速度太慢，无法投入实用。
现在，一组研究人员已经构建了一个系统，使得在单个图形处理器（GPU）上处理十亿级规模的数据成为可能。他们成功地在包含 13.9 亿个条目的数据库中找到了最相似的图像，而服务器从未见过查询内容。该系统通过两个主要技巧来提高速度。首先，它简化了图像。系统不再比较照片的每一个微小细节，而是在搜索开始前，将每张图像的描述简化为更短、更简单的版本。这使得数学运算变得更加轻量。其次，它并不查看每一张照片。相反，它使用了一种层级结构，就像一张地图，首先指向一个大致的社区，然后指向一条特定的街道，最后指向几栋房子。计算机只检查这些选定区域内的照片，从而跳过了其余部分。这使得系统即使在数据被锁在箱子里的情况下，也能快速找到正确答案。
结果表明，这种方法的效果非常出色。在一个拥有 13.9 亿张图像的数据集中，该系统在 90% 的情况下都能在前十个结果中找到正确的匹配项。当研究人员允许考虑“近乎重复”的情况时（因为互联网上充满了略有不同的相同照片副本），成功率跃升至 95%。整个过程在单个图形处理器上每次搜索仅耗时约六秒。这是一种“可部署的速度”，意味着一旦预先准备好数据库，它就足够快，可以用于实际应用。研究人员还在另一个包含 96 维向量的十亿级集合上测试了该系统，实现了在仅 2.3 秒内达到 90% 的成功率。这些数字证明，在单台机器上搜索数十亿个加密项目不再仅仅是一个理论上的梦想。
然而，研究人员非常谨慎地衡量了这种速度在隐私方面付出的代价。虽然服务器从未看到问题或答案，但它确实看到了计算机请求查看哪些数据组。这种访问模式可以揭示关于数据库本身的线索。通过观察哪些组被同时请求，观察者可以重建大约 72% 的显示数据组织方式的地图。他们还可以推测两次不同的搜索是否在寻找相似的东西，如果它们请求了相同的组。为了修复这个问题，研究人员尝试了一种方法，即让计算机在请求真实数据组的同时，也请求额外的、虚假的（伪造的）数据组，以隐藏真实的模式。如果这些虚假组每次都发生变化，聪明的攻击者仍可以通过比较多次搜索来发现真相。但如果这些虚假组是固定且始终不变的，攻击者就无法将其剥离。这种“种子化”（seeded）填充技术将信息泄露减少了约 35 倍，将数据库地图的恢复率从 乘 72% 降低到了仅 2%。
团队还探索了其他使搜索更快速的方法，例如一种称为“乘积量化”（product quantization）的技术，它将数据分解为小的代码。他们发现，在加密环境下，这种方法效果并不理想。它要么无法超越标准的加密搜索，要么会泄露太多关于数据结构的信息。因此，他们决定不使用它，而是坚持使用更简单的方法：即缩小数据描述的大小并使用层级地图。这一选择凸显了一个关键发现：当隐私是首要任务时，有时直接的方法比复杂的方法更好。
该系统的运行流程是：用户向服务器发送一个加密的问题。持有加密数据库的服务器对锁定数据进行数学运算。它首先检查几千个宽泛的类别，然后缩小范围到几千个更具体的组，最后对这些组中的实际图像进行评分。在每一步中，服务器都会返回加密的分数。用户解密分数，决定下一步要查看哪些组，然后发送新的请求。服务器永远不会看到用户的决策或最终答案。这种往返过程会持续进行，直到找到前十个匹配项。研究人员测量了加载数据和执行评分所需的时间，不包括用户解密最终结果或数据在网络上传输的时间。他们发现，时间主要消耗在将加密数据加载到计算机内存中，而不是在数学运算本身。
在对隐私风险的分析中，研究人员表明，泄露是搜索路由本身的一个属性，而非特定被搜索数据本身的属性。无论数据库包含的是人脸还是普通图像，访问模式揭示的结构信息量都是相同的。他们证明了如果没有保护措施，观察者几乎可以完美地恢复数据的分组情况。通过使用固定组填充技术，这种恢复能力显著下降，尽管并未完全消失。其中的权衡是显而易见的：为了隐藏访问模式，系统必须获取比严格需要更多的的数据，这增加了完成搜索的时间。研究人员表明，这种成本是可以管理的，但这需要平衡隐私需求的大小与系统的运行速度。
这项工作在使大规模私密搜索变得实用方面迈出了重要一步。它证明了只要你愿意接受几秒钟的延迟并妥善管理隐私成本，就可以在不泄露意图的情况下搜索十亿个项目。该系统并不依赖于魔法或未经证实的理论；它利用成熟的数学和精巧的工程设计来解决现实问题。研究人员提供了一份关于如何构建和运行该系统的完整指南，包括速度和准确性的精确设置。他们还展示了极限所在，特别是关于通过搜索模式泄露的信息。通过对所隐藏的内容和所揭示的内容保持透明，他们为在隐私日益珍贵的时代进行安全数据搜索提供了一条现实的路径。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。