Symmetric PIR capacity conjecture for 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 symmetric private information retrieval (SPIR) from an (n,k)(n,k) MDS storage code with tt-collusion, bb Byzantine servers, and rr nonresponsive servers.

Symmetric PIR capacity conjecture. The capacity of SPIR is

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

The conjecture is one of the claims for the known-parameter cases k=1k=1 or t=1t=1, where symmetric capacity is observed to coincide with asymptotic nonsymmetric capacity. The source notes that an earlier formulation used denominator nrn-r because nonresponsive servers were excluded from the download cost; the paper counts them, while stating that the results apply under both conventions. 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.