### Coeus: A System for Oblivious Document Ranking and Retrieval

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

##### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. 28th ACM SIGOPS Symposium on Operating Systems Principles (SOSP ’21)
DOI
10.1145/3477132.3483586
Keywords
secure matrix vector multiplicationprivate keyword searchprivate document ranking
Contact author(s)
ishtiyaque @ ucsb edu
History
Short URL
https://ia.cr/2022/154

CC BY-NC

BibTeX

@misc{cryptoeprint:2022/154,
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{https://eprint.iacr.org/2022/154}},
url = {https://eprint.iacr.org/2022/154}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.