Paper 2023/1552
Doubly Efficient Batched Private Information Retrieval
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Ring-LWEbatched PIRHomomorphic EncryptionFast Polynomial Eval with preprocessingAmortized Efficiency
- Contact author(s)
-
dingxiuquan @ amss ac cn
giulio malavolta @ hotmail it
zhangtianwei1015 @ gmail com - History
- 2023-10-11: approved
- 2023-10-09: received
- See all versions
- Short URL
- https://ia.cr/2023/1552
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1552,
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{https://eprint.iacr.org/2023/1552}},
url = {https://eprint.iacr.org/2023/1552}
}
