Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems
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_ | 1866918134738321408 |
|---|---|
| author | Meel, Shreya Ulukus, Sennur |
| author_facet | Meel, Shreya Ulukus, Sennur |
| contents | We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17736 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems Meel, Shreya Ulukus, Sennur Information Theory Cryptography and Security Databases Networking and Internet Architecture Signal Processing We introduce the problem of symmetric private information retrieval (SPIR) on replicated databases modeled by a simple graph. In this model, each vertex corresponds to a server, and a message is replicated on two servers if and only if there is an edge between them. We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph, and we call this as message-specific common randomness. In this setting, we establish a lower bound on the SPIR capacity, i.e., the maximum download rate, for general graphs, by proposing an achievable SPIR scheme. Next, we prove that, for any SPIR scheme to be feasible, the minimum size of message-specific randomness should be equal to the size of a message. Finally, by providing matching upper bounds, we derive the exact SPIR capacity for the class of path and regular graphs. |
| title | Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems |
| topic | Information Theory Cryptography and Security Databases Networking and Internet Architecture Signal Processing |
| url | https://arxiv.org/abs/2507.17736 |