Finite-file PIR rate upper-bound conjecture for coded colluding servers

Let C{\mathcal{C}} be an [n,k,d][n,k,d] code with generator matrix G{\mathbf{G}}, storing mm files through the distributed storage system

Y=XG.{\mathbf{Y}}={\mathbf{X}}\cdot{\mathbf{G}}.

Fix 1tnk1\leq t\leq n-k, and let RmR_m denote the rate of a PIR scheme for Y{\mathbf{Y}} protecting against any tt colluding servers.

Finite-file PIR rate conjecture. Any such PIR scheme has rate at most

Rm1k+t1n1(k+t1n)mm1k+t1n.R_m\leq\frac{1-\frac{k+t-1}{n}}{1-\left(\frac{k+t-1}{n}\right)^m} \mathrel{\xrightarrow[m\rightarrow\infty]{}}1-\frac{k+t-1}{n}.

For finitely many files, this conjectured upper bound is motivated by the capacity expressions known when either k=1k=1 or t=1t=1, and its limiting value agrees with the corresponding asymptotic 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.