Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al

By Hua Sun, Syed Ali Jafar. 2017

123 citations recorded by the source corpus.

A (K, N, T, Kc) instance of the MDS-TPIR problem is comprised of K messages and N distributed servers. Each message is separately encoded through an (N, Kc) 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 Kc 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, Kc) = (2,4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Lifting Private Information Retrieval from Two to any Number of Messages (2018, background): “6This conjecture was disproven in [15] for some parameters.”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, methodology): “The capacity of coded PIR with colluding servers is known when m = 2 and k = n − 1 by [14], but no general result is known for k > 1 and t > 1.”