A Caltech Library Service

Private Information Retrieval is Graph Based Replication Systems

Raviv, Netanel and Tamo, Itzhak (2018) Private Information Retrieval is Graph Based Replication Systems. In: 2018 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 1739-1743. ISBN 978-1-5386-4780-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Replication is prevalent in both theory and practice as a means for obtaining robustness in distributed storage systems. A system in which every data entry is stored on two separate servers gives rise to a graph structure in a natural way, and the combinatorial properties of this graph shed light on the possible features of the system. One possible feature of interest, that has recently gained renewed attention, is private information retrieval (PIR). A PIR protocol enables a user to obtain a data entry from a storage system without revealing the identity of the requested entry to sets of colluding servers. In this paper we suggest a simple PIR protocol for graph based replication systems, which guarantees perfect secrecy against any set of colluding servers that does not induce a cycle. Furthermore, it is shown that the secrecy deteriorates gracefully with the number of cycles in the colluding set, and that the upload complexity can be reduced for graphs of certain specialized structure.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article
Raviv, Netanel0000-0002-1686-1994
Additional Information:© 2018 IEEE. The work of Netanel Raviv was supported in part by the postdoctoral fellowship of the Center for the Mathematics of Information (CMI), Caltech, and in part by the Lester-Deutsch postdoctoral fellowship.
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20181126-141023111
Persistent URL:
Official Citation:N. Raviv and I. Tamot, "Private Information Retrieval is Graph Based Replication Systems," 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, 2018, pp. 1739-1743. doi: 10.1109/ISIT.2018.8437311
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:91183
Deposited By: Tony Diaz
Deposited On:26 Nov 2018 22:40
Last Modified:25 Jun 2020 21:19

Repository Staff Only: item control page