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)
- 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
-
CC BY