2017/01/26 by Hua Sun, Sun, Hua, Syed A. Jafar +1 · 4 citations
Computer Science · Mathematics · #Automorphism #Combinatorics #Complexity and Algorithms in Graphs #Computer network #Computer science #Conjecture #Counterexample #Cryptography and Data Security #Cryptography and Security (cs.CR) #Discrete mathematics #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Information Theory (cs.IT) #Mathematics #Privacy-Preserving Technologies in Data #Private information retrieval #Programming language #Server #Set (abstract data type) #Statistics #Theoretical computer science #cs.CR #cs.IR #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1701.07807
published in ArXiv.org
openalex publication_date 2017/01/26 · arxiv created 2017/01/30 · arxiv updated 2017/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 a (Kc, 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 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. Insights from the counterexample lead us to capacity characterizations for various instances of MDS-TPIR including all cases with (K, N, T, Kc) = (2,N,T,N-1), where N and T can be arbitrary.