Coeus
Open Access
- 26 October 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM
Abstract
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.Keywords
Funding Information
- NSF (National Science Foundation) (CNS-1703560, CNS-1815733)
- Defense Advanced Research Projects Agency (HR001118C0060)
This publication has 49 references indexed in Scilit:
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVPLecture Notes in Computer Science, 2012
- Privacy-Preserving Queries over Relational DatabasesLecture Notes in Computer Science, 2010
- On Ideal Lattices and Learning with Errors over RingsLecture Notes in Computer Science, 2010
- h(k)‐private information retrieval from privacy‐uncooperative queryable databasesOnline Information Review, 2009
- Space-Efficient Private Search with Applications to Rateless CodesLecture Notes in Computer Science, 2007
- Keyword Search and Oblivious Pseudorandom FunctionsLecture Notes in Computer Science, 2005
- Automated empirical optimizations of software and the ATLAS projectParallel Computing, 2001
- Reducing the Servers Computation in Private Information Retrieval: PIR with PreprocessingLecture Notes in Computer Science, 2000
- Exploring the similarity spaceACM SIGIR Forum, 1998
- Principles of quantizationIEEE Transactions on Circuits and Systems, 1978