Private Information Retrieval in Graph-Based Replication Systems
- Creators
- Raviv, Netanel
- Tamo, Itzhak
- Yaakobi, Eitan
Abstract
In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called t-private if the identity of the file remains concealed even if t of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases.
Additional Information
© 2019 IEEE. Manuscript received March 4, 2019; revised September 12, 2019; accepted November 9, 2019. Date of publication November 22, 2019; date of current version May 20, 2020. The work of N. Raviv was supported in part by the Post-Doctoral Fellowship of the Center for the Mathematics of Information (CMI), California Institute of Technology. The work of I. Tamo was supported in part by the Israel Science Foundation (ISF) under Grant 1030/15 and Grant NSF-BSF 2015814. The work of E. Yaakobi was supported in part by the Israel Science Foundation (ISF) under Grant 1817/18. This work was presented in part at the International Symposium on Information Theory (ISIT), Vail, CO, USA, 2018.Attached Files
Submitted - 1812.01566.pdf
Files
Name | Size | Download all |
---|---|---|
md5:ff0cfc267ca401fd8ef9e30c5749f722
|
285.4 kB | Preview Download |
Additional details
- Eprint ID
- 104051
- Resolver ID
- CaltechAUTHORS:20200625-112850096
- Center for the Mathematics of Information, Caltech
- 1030/15
- Israel Science Foundation
- 2015814
- Binational Science Foundation (USA-Israel)
- 1817/18
- Israel Science Foundation
- Created
-
2020-06-25Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field