| Paper ID | D4-S6-T4.2 |
| Paper Title |
Bounds on the Capacity of PIR over Graphs |
| Authors |
Bar Sadeh, Tel-Aviv University, Israel; Yujie Gu, Kyushu University, Japan; Itzhak Tamo, Tel-Aviv University, Israel |
| Session |
D4-S6-T4: Private Information Retreival II |
| Chaired Session: |
Thursday, 15 July, 23:40 - 00:00 |
| Engagement Session: |
Friday, 16 July, 00:00 - 00:20 |
| Abstract |
In the private information retrieval (PIR) problem a user wants to retrieve a file from a database without revealing any information about the identity of the desired file to the servers that store the database. In this paper we study the PIR capacity of a graph based replication system, in which each file is stored on two distinct servers according to an underlying graph. The main goal of this paper it to provide upper and lower bounds to the PIR capacity of graphs via various graph properties. In particular, we provide several upper bounds on the PIR capacity that apply to all graphs. We further improve the bounds for specific graph families (which turn out to be tight in certain cases) by utilizing the underlying graph structure. For the lower bounds, we establish optimal rate PIR retrieval schemes for star graphs via edge-coloring techniques. Lastly, we provide an improved PIR scheme for complete graphs, which then imply an improved general lower bound on the PIR capacity for all graphs.
|
