On the Asymptotic Capacity of X-Secure T-Private Information Retrieval With Graph-Based Replicated Storage

DOI10.1109/TIT.2020.3011053MaRDI QIDQ5138809zbMATH OpenOpenAlexFDO

Authors Zhuqing Jia, Syed A. Jafar

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.05906

zbMATH Keywords

private information retrievalasymptotic capacitygraph-based replicated storage

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Applications of graph theory to circuits and networks (94C15) Informational aspects of data analysis and big data (94A16) Privacy of data (68P27)

Abstract: The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi. Its capacity remains open in almost all cases. In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary $T$-privacy and $X$-security constraints, where the privacy of the user must be protected against any set of up to $T$ colluding servers and the security of the stored data must be protected against any set of up to $X$ colluding servers. A general achievable scheme for arbitrary storage patterns is presented that achieves the rate $(h{o}_{min}-X-T)/N$, where $N$ is the total number of servers, and each message is replicated at least $h{o}_{min}$ times. Notably, the scheme makes use of a special structure inspired by dual Generalized Reed Solomon (GRS) codes. A general converse is also presented. The two bounds are shown to match for many settings, including symmetric storage patterns. Finally, the asymptotic capacity is fully characterized for the case without security constraints $(X=0)$ for arbitrary storage patterns provided that each message is replicated no more than $T+2$ times. As an example of this result, consider PIR with arbitrary graph based storage ($T=1,X=0$) where every message is replicated at exactly $3$ servers. For this $3$-replicated storage setting, the asymptotic capacity is equal to $2/u_2(G)$ where $u_2(G)$ is the maximum size of a $2$-matching in a storage graph $G[V,E]$. In this undirected graph, the vertices $V$ correspond to the set of servers, and there is an edge $uvinE$ between vertices $u,v$ only if a subset of messages is replicated at both servers $u$ and $v$.

This page was built for publication: On the Asymptotic Capacity of X-Secure T-Private Information Retrieval With Graph-Based Replicated Storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138809)