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

CREATORAtsushi Miki, Toshiyasu Matsushima
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06003

Browse the full library · About the Tower of Babel