Paper 2022/154
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-02-12: received
- Short URL
- https://ia.cr/2022/154
- License
-
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},
url = {https://eprint.iacr.org/2022/154}
}