Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers
Atsushi Miki, Toshiyasu Matsushima · 2025
Read Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers by Atsushi Miki, Toshiyasu Matsushima (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06003.txt.
Description
Atsushi Miki and Toshiyasu Matsushima pin down exactly when a private information retrieval scheme can be as efficient as theory allows. Private retrieval lets a user download one message from servers without revealing which one. Real servers may collude, go silent, or answer with noise, and schemes exist for each threat.
Upper bounds on download efficiency were known for the robust, Byzantine, and colluding variants. What was missing was a systematic way to build schemes that reach those bounds. The authors prove necessary and sufficient conditions on the queries a scheme sends. Meeting those conditions is exactly what capacity requires. The result gives designers a checklist for building optimal private retrieval under adversarial servers.
Catalog record
| CREATOR | Atsushi Miki, Toshiyasu Matsushima |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06003