Capacity conjecture for symmetric PIR from MDS-coded storage with adversarial servers
Capacity conjecture for symmetric PIR from MDS-coded storage with adversarial servers
Let an MDS storage code store a database accessed by a Symmetric Private Information Retrieval scheme, with -colluding servers, Byzantine servers, and unresponsive servers. Let denote the number of messages. Symmetric PIR capacity conjecture. The capacity is
Moreover, the symmetrization of the current scheme is capacity-achieving, and the minimum shared randomness entropy per round required among the servers to guarantee symmetry is in -ary units. This conjecture concerns both the symmetric PIR capacity and the required shared randomness; the supplied text gives no resolution status.
Sources & referencesView supporting material
Primary source
Razane Tajeddine, Oliver W. Gnilke, David Karpuk, Ragnar Freij-Hollanti and Camilla Hollanti, “Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers”, arXiv:1806.08006 (2018).
Additional references
3 papers in this index state this conjecture (2016–2018). The statement above is taken from the most recent of them; the others are arXiv:1802.03731, arXiv:1611.02062.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.