Paper 2024/765

Information-Theoretic Multi-Server PIR with Global Preprocessing

Ashrujit Ghoshal, Carnegie Mellon University
Baitian Li, Tsinghua IIIS and Columbia
Yaohua Ma, Tsinghua IIIS and CMU
Chenxin Dai, Tsinghua IIIS and CMU
Elaine Shi, Carnegie Mellon University

We propose a new unified framework to construct multi-server, information-theoretic Private Information Retrieval (PIR) schemes that leverage global preprocesing to achieve sublinear computation per query. Despite a couple earlier attempts, our understanding of PIR schemes in the global preprocessing model remains limited, and so far, we only know a few sparse points in the broad design space. Our framework not only unifies earlier results in this space, but leads to several new results. First, we can improve the server space of the state-of-the-art scheme by a polynomial factor. Second, we can broaden the parameter space of known results, allowing a smooth tradeoff between bandwidth and computation. Third, while earlier schemes achieve better per-server bandwidth and computation as we add more servers, the server space actually grows w.r.t. the number of servers. We offer a new scalable family of schemes where the per-server bandwidth, computation, and space all decrease as we add more servers. This scalable family of schemes also implies the so-called ``doubly efficient'' PIR scheme with any super-constant number of servers, achieving $n^{1+o(1)}$ server space and preprocessing cost, and $n^{o(1)}$ bandwidth and computation per query.

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrievalglobal preprocessing
Contact author(s)
aghoshal @ andrew cmu edu
lbt21 @ mails tsinghua edu cn
yaohuam @ andrew cmu edu
chenxind @ andrew cmu edu
runting @ gmail com
2024-06-18: revised
2024-05-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ashrujit Ghoshal and Baitian Li and Yaohua Ma and Chenxin Dai and Elaine Shi},
      title = {Information-Theoretic Multi-Server {PIR} with Global Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2024/765},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.