MIT最新论文《亚线性通信的私有近似近邻搜索》，在线推荐时保护隐私的技术

研究人员设计了一个有效的协议，当算法使用用户的私人信息来推荐产品、歌曲或节目时，可以保证其安全。

背景

当我们在网上购物时，算法会推荐产品，或者当我们在流媒体应用程序上听音乐时，算法会推荐我们可能喜欢的歌曲。

这些算法通过使用我们过去的购买和浏览历史等个人信息来生成定制的推荐。这类数据的敏感性质使得保护隐私极为重要，但解决这一问题的现有方法依赖于沉重的加密工具，需要大量的计算和带宽。

麻省理工学院的研究人员可能有一个更好的解决方案。他们开发了一种保护隐私的协议，其效率非常高，可以通过非常低速的网络在智能手机上运行。他们的技术在确保推荐结果准确的同时保护了个人数据。

除了用户隐私，他们的协议还最大限度地减少了数据库中未经授权的信息转移，即所谓的泄漏，即使有恶意代理试图欺骗数据库，使其泄露秘密信息。

在数据泄露可能违反用户隐私法的情况下，新协议可能特别有用，比如当医疗保健提供者使用病人的病史在数据库中搜索其他有类似症状的病人，或者当一家公司根据欧洲隐私法规向用户提供有针对性的广告。

"这是一个非常困难的问题。我们依靠一整串的加密和算法技巧来达成我们的协议，"计算机科学和人工智能实验室（CSAIL）的研究生Sacha Servan-Schreiber说，他也是提出这个新协议的论文的主要作者。

Servan-Schreiber与CSAIL的研究生Simon Langowski以及他们的导师和高级作者Srinivas Devadas（Edwin Sibley Webster电子工程教授）一起撰写了这篇论文。该研究将在 IEEE Symposium on Security and Privacy发表。

近邻数据

算法推荐引擎的核心技术被称为近邻搜索，即在数据库中找到与查询点最接近的数据点。被映射到附近的数据点具有相似的属性，被称为近邻。

这些搜索涉及一个与在线数据库相连的服务器，该数据库包含数据点属性的简明表示。在音乐流媒体服务的案例中，这些属性被称为特征向量，可能是不同歌曲的类型或流行度。

为了找到歌曲推荐，客户端（用户）向服务器发送一个查询，其中包含某个特征向量，如用户喜欢的音乐类型或他们收听习惯的压缩历史。然后，服务器提供数据库中最接近客户端查询的特征向量的ID，而不透露实际的向量。在音乐流媒体的情况下，这个ID可能是一个歌名。客户端在不了解与之相关的特征向量的情况下就能了解到推荐的歌曲名称。

"服务器必须能够在不看到它正在进行计算的数字的情况下进行这种计算。它实际上不能看到这些特征，但仍然需要给你数据库中最接近的东西，"Langowski说。

为了实现这一目标，研究人员创建了一个协议，该协议依赖于两个访问同一数据库的独立服务器。使用两个服务器使这个过程更加有效，并能够使用一种被称为私人信息检索的加密技术。Servan-Schreiber解释说，这种技术允许客户端查询数据库而不透露它正在搜索的内容。

克服安全挑战

但是，虽然私人信息检索在客户端是安全的，但它本身并不能提供数据库隐私。数据库为客户端提供了一组候选向量--可能的近邻，这些候选向量通常是由客户端使用暴力手段筛选出来的。然而，这样做会向客户透露很多关于数据库的信息。额外的隐私挑战是如何防止客户端学习这些额外的向量。

研究人员采用了一种调整技术，首先消除了许多额外的向量，然后使用一种不同的技巧，他们称之为遗忘屏蔽，以隐藏任何额外的数据点，除了实际最近的邻居。这有效地保留了数据库的隐私，所以客户端不会了解到数据库中的特征向量的任何信息。

一旦他们设计了这个协议，他们就在四个真实世界的数据集上用一个非私有的实施方案对其进行了测试，以确定如何调整算法以最大限度地提高准确性。然后，他们用他们的协议在这些数据集上进行私人近邻搜索查询。

他们的技术每次查询只需要几秒钟的服务器处理时间，客户端和服务器之间的通信量不到10兆字节，即使是包含超过1000万个项目的数据库。相比之下，其他安全方法可能需要数千兆字节的通信或数小时的计算时间。对于每次查询，他们的方法都达到了95%以上的准确率（意味着几乎每次都能找到与查询点的实际近似近邻）。

他们用来实现数据库隐私的技术将挫败一个恶意的客户端，即使它发送虚假查询，试图欺骗服务器泄露信息。

"一个恶意的客户端不会比一个遵循协议的诚实的客户端学到更多的信息。而且，它也能防止恶意的服务器。如果一个人偏离了协议，你可能不会得到正确的结果，但他们永远不会知道客户端的查询是什么，" Langowski说。

在未来，研究人员计划调整该协议，以便它能够只使用一个服务器来保护隐私。这可以使它应用于更多的实际情况，因为它将不需要使用两个不相冲突的实体（它们彼此不共享信息）来管理数据库。

"最近的邻居搜索是许多关键的机器学习驱动的应用的基础，从向用户提供内容推荐到对医疗状况进行分类。然而，它通常需要与一个中央系统共享大量数据，以汇总和启用搜索，"Capital One公司应用机器学习研究主管Bayan Bruss说，他没有参与这项工作。"这项研究提供了一个关键步骤，确保用户从最近的邻居搜索中获得好处，同时相信中央系统不会将他们的数据用于其他目的。"

论文

最近邻搜索是一个广泛的应用的基本构件。一个保护隐私的近邻搜索协议涉及一组客户，他们向远程数据库发送查询。每个客户端在不透露任何查询信息的情况下，在数据库中检索与其查询最接近的邻居（s）。为了确保数据库的私密性，客户必须尽可能少地了解查询答案以外的信息，即使是通过偏离协议的方式进行恶意行为。

现有的私有近邻搜索协议需要沉重的加密工具，导致高计算和带宽的开销。在本文中，我们提出了第一个用于私有近邻搜索的轻量级协议。我们的协议使用两个无冲突的服务器进行实例化，每个服务器持有一个数据库的副本。我们的设计支持任意数量的客户通过这两个服务器同时查询数据库。每个查询都是由客户和两个服务器之间的单轮通信组成。服务器之间不需要通信来回答查询。

如果至少有一个服务器是不结盟的，我们确保（1）客户的查询没有信息被泄露，（2）客户和服务器之间的总通信量是数据库大小的次线性，（3）每个查询答案只向客户泄露少量的、有界限的数据库信息，即使客户是恶意的。

我们实现了我们的协议并报告了它在真实世界数据上的表现。我们的结构在10M特征向量的大型数据库上需要10到20秒的查询延迟。客户端的开销保持在每次查询处理时间10ms以下，通信量小于10MB。