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

2017/01/26 by Sun, Hua, Jafar, Syed A. · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1701.07807

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 by

• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems

Related

• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A Capacity-Achieving T-PIR Scheme Based On MDS Array Codes
• Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size