Paper 2020/1596

Batched Differentially Private Information Retrieval

Kinan Dak Albab, Brown University
Rawane Issa, Boston University
Mayank Varia, Boston University
Kalman Graffi

Private Information Retrieval (PIR) allows several clients to query a database held by one or more servers, such that the contents of their queries remain private. 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 an offline 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 constant client work. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol achieves speed-ups up to and exceeding $10$x in practical settings compared to state of the art PIR protocols, and can scale to batches with hundreds of millions of queries on cheap commodity AWS machines. Our protocol builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2022
Private Informatio Secret Sharing Secure Multiparty Computation Differential Privacyn Retrieval
Contact author(s)
kinan_dak_albab @ brown edu
ra1issa @ bu edu
varia @ bu edu
2022-06-26: last of 3 revisions
2020-12-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kinan Dak Albab and Rawane Issa and Mayank Varia and Kalman Graffi},
      title = {Batched Differentially Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1596},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.