You are looking at a specific version 20201224:074020 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Private Information RetrievalSecret SharingSecure Multiparty ComputationDifferential Privacy
Contact author(s)
kinan_dak_albab @ brown edu
ra1issa @ bu edu
varia @ bu edu
History
2022-06-26: last of 3 revisions
2020-12-24: received
See all versions
Short URL
https://ia.cr/2020/1596
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.