Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 64, Issue 2, Pages 1000-1022Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2017.2779454
Keywords
Capacity; private information retrieval; colluding servers; MDS coded data
Funding
- NSF [CCF-1617504, CNS-1731384]
- ONR [N00014-16-1-2629, N00014-18-1-2057]
- ARO [W911NF-16-1-0215]
Ask authors/readers for more resources
A (K, N, T, K-c) instance of private information retrieval from MDS coded data with colluding servers (in short, MDS-TPIR), 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available