Capacity conjecture for symmetric PIR from MDS-coded storage with adversarial servers

Let an [n,k][n,k] MDS storage code store a database accessed by a Symmetric Private Information Retrieval scheme, with tt-colluding servers, bb Byzantine servers, and rr unresponsive servers. Let MM denote the number of messages. Symmetric PIR capacity conjecture. The capacity is

nr(k+t+2b1)nr.\frac{n-r-(k+t+2b-1)}{n-r}.

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 k+t1k+t-1 in qq-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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.