Coeus: A System for Oblivious Document Ranking and Retrieval
Coeus: A System for Oblivious Document Ranking and Retrieval
复制标题
DOI：
10.1145/3477132.3483586
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Ishtiyaque Ahmad;Laboni Sarker;D. Agrawal;A. E. Abbadi;Trinabh Gupta
中科院分区：
文献类型：
--
作者：
Ishtiyaque Ahmad;Laboni Sarker;D. Agrawal;A. E. Abbadi;Trinabh Gupta
给定私有字符串Q和保存一组公共文档D的远程服务器，在没有任何人(甚至服务器)学习关于Q或文档的任何信息的情况下，如何选择和查看D中与Q最相关的K个文档之一？这就是不经意间的文档排序和检索问题。在本文中，我们描述了一个解决这一问题的系统Coeus。在高层次上，Coeus组成了两个加密原语：安全矩阵-向量积，用于使用广泛使用的术语频率-逆文档频率(TF-IDF)方法来评分文档相关性，以及私有信息检索(PIR)，用于不经意地检索文档。然而，Coeus减少了运行这些协议的时间，从而改善了用户感知的延迟，这是一个关键的性能指标。Coeus首先通过分离私有元数据检索和文档检索来降低PIR开销，然后通过一系列新颖的密码改进将安全矩阵-向量积扩展到具有数千亿个元素的TF-IDF矩阵。对于一个包含500万个文档的英文维基百科语料库，一个包含64K关键字的关键字词典，以及AWS上的143台机器，Coeus使用户能够在3.9秒内对文档进行排序和检索-比基准系统提高了24倍。
Given a private string q and a remote server that holds a set of public documents D, how can one of the K most relevant documents to q in D be selected and viewed without anyone (not even the server) learning anything about q or the document? This is the oblivious document ranking and retrieval problem. In this paper, we describe Coeus, a system that solves this problem. At a high level, Coeus composes two cryptographic primitives: secure matrix-vector product for scoring document relevance using the widely-used term frequency-inverse document frequency (tf-idf) method, and private information retrieval (PIR) for obliviously retrieving documents. However, Coeus reduces the time to run these protocols, thereby improving the user-perceived latency, which is a key performance metric. Coeus first reduces the PIR overhead by separating out private metadata retrieval from document retrieval, and it then scales secure matrix-vector product to tf-idf matrices with several hundred billion elements through a series of novel cryptographic refinements. For a corpus of English Wikipedia containing 5 million documents, a keyword dictionary with 64K keywords, and on a cluster of 143 machines on AWS, Coeus enables a user to obliviously rank and retrieve a document in 3.9 seconds---a 24x improvement over a baseline system.