Scalable Private Search with Wally

本文介绍了Wally，一种支持对大型数据库进行高效语义和关键字搜索查询的私人搜索系统。当有足够的客户端进行查询时，Wally的性能显著优于以前的系统。在以前的私人搜索系统中，对于每个客户端查询，服务器必须对每个数据库条目执行至少一个昂贵的加密操作。结果，性能随着数据库中条目数量的增加而降低。在Wally中，我们摆脱了这个限制。具体而言，对于每个查询，服务器仅针对少数数据库条目执行加密操作。我们通过要求每个客户端添加一些虚假查询，并通过匿名网络以独立选择的随机时刻发送每个查询，来实现这些结果。此外，每个客户端还使用了某种同态加密（SHE）来隐藏查询是真实的还是虚假的。Wally提供$(\epsilon, \delta)$-差分隐私保证，这是强隐私的公认标准。每个客户端制作的虚假查询数量取决于正在进行查询的客户端数量的倒数。因此，虚假查询的开销随着客户端数量的增加而消失，实现了对数百万个查询和大型数据库的可扩展性。具体而言，Wally可以以每秒3,000个查询的速率处理800万个请求。这大约比最先进的方案高60倍。

解决问题：Wally试图解决私人搜索系统中的性能问题，以及提供强隐私保障。

关键思路：Wally通过要求每个客户端添加一些虚假查询，并通过匿名网络随机发送每个查询来减少服务器的加密操作，从而提高性能。同时，每个客户端还使用了略微同态加密（SHE）来隐藏查询是真实的还是虚假的，并提供了（ε，δ）-差分隐私保障。

其他亮点：Wally可以在大型数据库中支持高效的语义和关键字搜索查询，并且当有足够的客户端进行查询时，其性能显著优于以前的系统。论文还提到，Wally可以处理每秒3000个查询，可以服务于8百万个请求。Wally的亮点之一是其可扩展性，随着客户端数量的增加，虚假查询的开销会消失。论文没有提供开源代码，但提供了数据集。

相关研究：在私人搜索系统方面，最近的相关研究包括“Private Information Retrieval Using Trusted Hardware”和“Private Searching on Streaming Data: Theory and Practice”。