How to Correct Errors in Multi-server PIR

Suppose that there exist a user and \(\ell \) servers \(S_1,\ldots ,S_{\ell }\). Each server \(S_j\) holds a copy of a database \(\mathbf {x}=(x_1, \ldots , x_n) \in \{0,1\}^n\), and the user holds a secret index \(i_0 \in \{1, \ldots , n\}\). A b error correcting \(\ell \) server PIR (Private Information Retrieval) scheme allows a user to retrieve \(x_{i_0}\) correctly even if and b or less servers return false answers while each server learns no information on \(i_0\) in the information theoretic sense. Although there exists such a scheme with the total communication cost \( O(n^{1/(2k-1)} \times k\ell \log {\ell } ) \) where \(k=\ell -2b\), the decoding algorithm is very inefficient.In this paper, we show an efficient decoding algorithm for this b error correcting \(\ell \) server PIR scheme. It runs in time \(O(\ell ^3)\).