Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.

DOI10.1109/TIT.2017.2779454zbMATH Open1390.94887arXiv1701.07807OpenAlexW2774968492WikidataQ122909915 ScholiaQ122909915MaRDI QIDQ4566682FDOQ4566682

Authors: Hua Sun, Syed A. Jafar 

Publication date: 27 June 2018

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

Abstract: A $(K,N,T,K_c)$ instance of the MDS-TPIR problem is comprised of $K$ messages and $N$ distributed servers. Each message is separately encoded through a $(K_c,N)$ MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to $T$ servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either $T$ or $K_c$ belongs to $1,N$. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting $(K,N,T,K_c)=(2,4,2,2)$, which achieves the rate $3/5$, exceeding the conjectured capacity, $4/7$. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR including all cases with $(K,N,T,K_c)=(2,N,T,N-1)$, where $N$ and $T$ can be arbitrary.

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

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05) Applications to coding theory and cryptography of arithmetic geometry (14G50) Distributed systems (68M14) Authentication, digital signatures and secret sharing (94A62) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Cited In (5)

• Private information retrieval from coded databases with colluding servers
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private information retrieval from locally repairable databases with colluding servers
• Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers

This page was built for publication: Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.

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