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

DOI10.1109/TIT.2017.2779454MaRDI QIDQ4566682zbMATH OpenOpenAlexWikidataFDO

Authors Hua Sun, Syed A. Jafar

Publication date 27 June 2018

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

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)

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.

Cited in

(5)

• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private information retrieval from locally repairable databases with colluding servers
• Private information retrieval from coded databases with colluding servers
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• 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)