New PIR schemes store n+1 bits and answer queries in sublinear time
Original title: Doubly-Efficient Private Information Retrieval from Modular Forms
For two servers, query time is n^0.82, matching prior EUROCRYPT 2026 schemes with far less storage.
Authors present information-theoretic s-server doubly-efficient private information retrieval for every constant s of at least 2. Each server stores a unique n+1-bit preprocessing structure and answers a query by reading at most T_s bits. For two servers, T_2 is n^0.82, matching Henzinger and Ragavan while shrinking storage from O(n sqrt(log n)) to n+1 bits. With more servers they report T_3 of n^0.74 and T_10 of n^0.61.
Unconfirmed: Complexity bounds are author-reported in a preprint and are not independently verified.
- Protocols cover every constant server count s of at least 2.
- Two-server storage falls from O(n sqrt(log n)) to n+1 bits.
- Reported times are n^0.74 for three servers and n^0.61 for ten.
- The construction uses modular forms and Fourier-sparse cone-delta functions.
From the original article
1 min read at arxiv.orgWe 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 \geq 2$.
By Alexandra Henzinger · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.