Answers are grounded in this paper and cite their sources.
We present new information-theoretic protocols for s-server, doubly-efficient private information retrieval (PIR) in sublinear server time and one extra bit of space on the servers, for every constant s ≥ 2. On an n-bit database, each of the s PIR servers first builds and stores a preprocessing data structure consisting of $n+1$ bits (which is unique to each server, and after which the server may discard the original database). Then, each server answers a PIR query in time Tₛ(n), by reading at most Tₛ bits of its data structure and sending them to the user. In the two server setting ($s=2$), our PIR protocols achieve T₂ = n0.82, matching the server time of the state-of-the-art schemes of Henzinger and Ragavan (EUROCRYPT 2026) while shrinking their storage from O(n√log n) to $n+1$ bits. With s ≥ 3 servers, our PIR protocols retain the $n+1$ bits of storage and additionally improve on the server time of all prior information-theoretic s-server schemes with n¹⁺ᵒ⁽¹⁾ storage: for example, achieving T₃ = n0.74 and T₁₀ = n0.61 (previously n0.79 and n0.75). Asymptotically, as the server count s grows, we shrink the number of servers required to achieve a given server-work exponent from s3.9 to s. Our results draw inspiration from matching-vector techniques (Efremenko, STOC 2009), which we generalize to handle degree-two computations in the exponent. Using this generalization, we build doubly-efficient PIR from the new intermediate abstraction of Fourier-sparse cone-delta functions. Then, we construct such Fourier-sparse cone-delta functions via a connection to modular forms and complex analysis: if a Fourier-sparse cone-delta function does not exist, then there exists a modular form which has too many roots, contradicting the valence formula.
No takes yet. Share an insight, caveat, or question.
Henzinger et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: