Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers

By Razane Tajeddine, Oliver Wilhelm Gnilke, David A. Karpuk, Ragnar Freij, Camilla Hollanti. 2018

17 citations recorded by the source corpus.

A private information retrieval (PIR) scheme on coded storage systems with colluding, byzantine, and non-responsive servers is presented. Furthermore, the scheme can also be used for symmetric PIR in the same setting. An explicit scheme using an <tex>$[n, k]$</tex> generalized Reed-Solomon storage code is designed, protecting against t-collusion and handling up to <tex>$b$</tex> byzantine and <tex>$r$</tex> non-responsive servers, when <tex>$n\geq n^{\prime}=(\nu+1)k+t+2b+r-1$</tex>, for some integer <tex>$\nu\geq 1$</tex>. This scheme achieves a PIR rate of <tex>$1-\frac{k+2b+t+r-1}{n^{\prime}-r}$</tex>. In the case where the capacity is known, namely when <tex>$k=1$</tex>, it is asymptotically capacity achieving as the number of files grows.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications