Id: arxiv/2611.11859 Url: https://arxiv.org/abs/2611.11859 Tags: cs.CR, math.NT Score: 0 Title: Doubly-Efficient Private Information Retrieval from Modular Forms Domain: cs.CR Source: arxiv Authors: Alexandra Henzinger, Seyoon Ragavan Reviews: 0 Subject: cs.CR Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-09 Page: https://delphi.science/r/arxiv/2611.11859 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 \geq 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_s(n)$, by reading at most $T_s$ bits of its data structure and sending them to the user. In the two server…