Capacity conjecture for symmetric PIR from MDS-coded storage with adversarial servers
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.