Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916434405228544 |
|---|---|
| author | Miki, Atsushi Morishita, Yusuke Matsushima, Toshiyasu |
| author_facet | Miki, Atsushi Morishita, Yusuke Matsushima, Toshiyasu |
| contents | Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. Here, PIRs in which servers do not communicate with each other are called standard PIRs, and PIRs in which some servers communicate with each other are called colluding PIRs. The information-theoretic upper bound on efficiency has been given in previous studies. However, the conditions for PIRs to keep privacy, to decode the desired message, and to achieve that upper bound have not been clarified in matrix form. In this paper, we prove the necessary and sufficient conditions for the properties of standard PIR and colluding PIR. Further, we represent the properties in matrix form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13624 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers Miki, Atsushi Morishita, Yusuke Matsushima, Toshiyasu Information Theory Private Information Retrieval (PIR) is a mechanism for efficiently downloading messages while keeping the index secret. Here, PIRs in which servers do not communicate with each other are called standard PIRs, and PIRs in which some servers communicate with each other are called colluding PIRs. The information-theoretic upper bound on efficiency has been given in previous studies. However, the conditions for PIRs to keep privacy, to decode the desired message, and to achieve that upper bound have not been clarified in matrix form. In this paper, we prove the necessary and sufficient conditions for the properties of standard PIR and colluding PIR. Further, we represent the properties in matrix form. |
| title | Necessary and Sufficient Conditions for Capacity-Achieving Private Information Retrieval with Non-Colluding and Colluding Servers |
| topic | Information Theory |
| url | https://arxiv.org/abs/2404.13624 |