Welcome to the resource topic for 2025/2008
Title:
Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space
Authors: Alexandra Henzinger, Seyoon Ragavan
Abstract:We build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of n > 10^6 bits, the servers store a preprocessed data structure of size 1.5 \sqrt{\log_2 n} \cdot n bits and then answer each PIR query by probing 12 \cdot n^{0.82} bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage n^{1+o(1)} and polynomially sublinear server time n^{1-\Omega(1)}.
Our work builds on the PIR-with-preprocessing protocol of Beimel, Ishai, and Malkin (CRYPTO 2000). The insight driving our improvement is a compact data structure for evaluating a multivariate polynomial and its derivatives. Our data structure and PIR protocol leverage the fact that Hasse derivatives can be efficiently computed on-the-fly by taking finite differences between the polynomial’s evaluations. We further extend our techniques to improve the state-of-the-art in PIR with three or more servers, building on recent work by Ghoshal, Li, Ma, Dai, and Shi (TCC 2025).
On a 55 GB database with 64-byte records, our two-server PIR encodes the database into a 1 TB data structure – which is 1,600,000$\times$ smaller than that of prior two-server PIR-with-preprocessing schemes, while maintaining the same communication and time per query. To answer a PIR query, the servers probe 102 MB from this data structure, requiring 550$\times$ fewer memory accesses than linear-time PIR. The main limitation of our protocol is its large communication complexity, which we show how to shrink to n^{0.31} \cdot \mathsf{poly}(\lambda) using compact linearly homomorphic encryption.
ePrint: https://eprint.iacr.org/2025/2008
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .