Cryptology ePrint Archive: Report 2020/1596

Batched Differentially Private Information Retrieval

Kinan Dak Albab and Rawane Issa and Mayank Varia and Kalman Graffi

Abstract: Private Information Retrieval (PIR) hides access patterns when several clients query a database held by one or more servers. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into a pre-processing stage to reduce online costs, or amortizing costs over a large batch of queries.

In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database, and is the first to scale to more than $10^5$ queries per second deployed on an AWS micro instance. Our protocol also builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.

Category / Keywords: cryptographic protocols / Private Information Retrieval, Secret Sharing, Secure Multiparty Computation, Differential Privacy

Date: received 22 Dec 2020

Contact author: kinan_dak_albab at brown edu, ra1issa@bu edu, varia@bu edu

Available format(s): PDF | BibTeX Citation

Version: 20201224:074020 (All versions of this report)

Short URL: ia.cr/2020/1596