New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916712840953856 |
|---|---|
| author | Kong, Xiangliang Meel, Shreya Maranzatto, Thomas Jacob Tamo, Itzhak Ulukus, Sennur |
| author_facet | Kong, Xiangliang Meel, Shreya Maranzatto, Thomas Jacob Tamo, Itzhak Ulukus, Sennur |
| contents | In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at most $r$ files. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20888 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage Kong, Xiangliang Meel, Shreya Maranzatto, Thomas Jacob Tamo, Itzhak Ulukus, Sennur Information Theory Cryptography and Security Combinatorics 68P20, 68P27 H.3.3 In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at most $r$ files. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases. |
| title | New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage |
| topic | Information Theory Cryptography and Security Combinatorics 68P20, 68P27 H.3.3 |
| url | https://arxiv.org/abs/2504.20888 |