{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}