Paper 2023/1552

Doubly Efficient Batched Private Information Retrieval

Xiuquan Ding, KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, School of Mathematical Sciences, University of Chinese Academy of Sciences
Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy
Tianwei Zhang, Max Planck Institute for Security and Privacy, Ruhr University Bochum

Private information retrieval (PIR) allows a client to read data from a server, without revealing which information they are interested in. A PIR is doubly efficient if the server runtime is, after a one-time pre-processing, sublinear in the database size. A recent breakthrough result from Lin, Mook, and Wichs [STOC’23] proposed the first-doubly efficient PIR with (online) server computation poly-logarithmic in the size of the database, assuming the hardness of the standard Ring-LWE problem. In this work, we consider the problem of doubly efficient batched PIR (DEBPIR), where the client wishes to download multiple entries. This problem arises naturally in many practical applications of PIR, or when the database contains large entries. Our main result is a construction of DEBPIR where the amortized communication and server computation overhead is $\tilde{O}(1)$, from the Ring-LWE problem. This represents an exponential improvement compared with known constructions, and it is optimal up to poly-logarithmic factors in the security parameter. Interestingly, the server’s online operations are entirely combinatorial and all algebraic computations are done in the pre-processing or delegated to the client.

Available format(s)
Cryptographic protocols
Publication info
Ring-LWEbatched PIRHomomorphic EncryptionFast Polynomial Eval with preprocessingAmortized Efficiency
Contact author(s)
dingxiuquan @ amss ac cn
giulio malavolta @ hotmail it
zhangtianwei1015 @ gmail com
2023-10-11: approved
2023-10-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiuquan Ding and Giulio Malavolta and Tianwei Zhang},
      title = {Doubly Efficient Batched Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1552},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.