Asymptotic capacity conjecture for PIR from MDS-coded colluding and adversarial servers

Assume n>k+t+2b+r1n>k+t+2b+r-1, where tt, bb, and rr are the numbers of colluding, Byzantine, and nonresponsive servers, respectively. Consider PIR from an (n,k)(n,k) MDS storage code with tt-collusion, bb Byzantine servers, and rr nonresponsive servers.

Asymptotic PIR capacity conjecture. The asymptotic capacity as the number of files mm tends to infinity is

1k+t+2b+r1n.1-\frac{k+t+2b+r-1}{n}.

This conjecture concerns the cases in which the relevant parameters are known, namely k=1k=1 or t=1t=1, where the symmetric capacity coincides with the asymptotic nonsymmetric capacity. Its resolution is not established in the supplied text.

Sources & referencesView supporting material

Primary source

Lukas Holzbaur, Ragnar Freij-Hollanti, Jie Li and Camilla Hollanti, “Towards the Capacity of Private Information Retrieval from Coded and Colluding Servers”, arXiv:1903.12552 (2021).

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.