Paper 2022/154

Coeus: A System for Oblivious Document Ranking and Retrieval

Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 28th ACM SIGOPS Symposium on Operating Systems Principles (SOSP ’21)
secure matrix vector multiplicationprivate keyword searchprivate document ranking
Contact author(s)
ishtiyaque @ ucsb edu
2022-02-12: received
Short URL
Creative Commons Attribution-NonCommercial


      author = {Ishtiyaque Ahmad and Laboni Sarker and Divyakant Agrawal and Amr El Abbadi and Trinabh Gupta},
      title = {Coeus: A System for Oblivious Document Ranking and Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/154},
      year = {2022},
      doi = {10.1145/3477132.3483586},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.