Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912839741997056 |
|---|---|
| author | Miki, Atsushi Matsushima, Toshiyasu |
| author_facet | Miki, Atsushi Matsushima, Toshiyasu |
| contents | Private information retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index of the desired message secret from the servers. PIR schemes have been extended to various scenarios with adversarial servers: PIR schemes where some servers are unresponsive or return noisy responses are called robust PIR and Byzantine PIR, respectively; PIR schemes where some servers collude to reveal the index are called colluding PIR. The information-theoretic upper bound on the download efficiency of these PIR schemes has been proved in previous studies. However, systematic ways to construct PIR schemes that achieve the upper bound are not known. In order to construct a capacity-achieving PIR schemes systematically, it is necessary to clarify the conditions that the queries should satisfy. This paper proves the necessary and sufficient conditions for capacity-achieving PIR schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06003 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers Miki, Atsushi Matsushima, Toshiyasu Information Theory Private information retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index of the desired message secret from the servers. PIR schemes have been extended to various scenarios with adversarial servers: PIR schemes where some servers are unresponsive or return noisy responses are called robust PIR and Byzantine PIR, respectively; PIR schemes where some servers collude to reveal the index are called colluding PIR. The information-theoretic upper bound on the download efficiency of these PIR schemes has been proved in previous studies. However, systematic ways to construct PIR schemes that achieve the upper bound are not known. In order to construct a capacity-achieving PIR schemes systematically, it is necessary to clarify the conditions that the queries should satisfy. This paper proves the necessary and sufficient conditions for capacity-achieving PIR schemes. |
| title | Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Adversarial Servers |
| topic | Information Theory |
| url | https://arxiv.org/abs/2511.06003 |