CaltechAUTHORS
  A Caltech Library Service

Private Information Retrieval in Graph-Based Replication Systems

Raviv, Netanel and Tamo, Itzhak and Yaakobi, Eitan (2020) Private Information Retrieval in Graph-Based Replication Systems. IEEE Transactions on Information Theory, 66 (6). pp. 3590-3602. ISSN 0018-9448. https://resolver.caltech.edu/CaltechAUTHORS:20200625-112850096

[img] PDF - Submitted Version
See Usage Policy.

278Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200625-112850096

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/tit.2019.2955053DOIArticle
https://arxiv.org/abs/1812.01566arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20181126-141023111Related ItemConference Paper
ORCID:
AuthorORCID
Raviv, Netanel0000-0002-1686-1994
Tamo, Itzhak0000-0002-8000-0419
Yaakobi, Eitan0000-0002-9851-5234
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.
Funders:
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
Israel Science Foundation1030/15
Binational Science Foundation (USA-Israel)2015814
Israel Science Foundation1817/18
Subject Keywords:Private information retrieval (PIR), distributed storage systems
Issue or Number:6
Record Number:CaltechAUTHORS:20200625-112850096
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200625-112850096
Official Citation:N. Raviv, I. Tamo and E. Yaakobi, "Private Information Retrieval in Graph-Based Replication Systems," in IEEE Transactions on Information Theory, vol. 66, no. 6, pp. 3590-3602, June 2020, doi: 10.1109/TIT.2019.2955053
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104051
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:25 Jun 2020 21:21
Last Modified:25 Jun 2020 21:21

Repository Staff Only: item control page