Kurosawa, Kaoru How to correct errors in multi-server PIR. (English) Zbl 1452.68072 Galbraith, Steven D. (ed.) et al., Advances in cryptology – ASIACRYPT 2019. 25th international conference on the theory and application of cryptology and information security, Kobe, Japan, December 8–12, 2019. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 11922, 564-574 (2019). Summary: 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)\).For the entire collection see [Zbl 1428.94009]. Cited in 1 Document MSC: 68P20 Information storage and retrieval of data 68P27 Privacy of data 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) 94A60 Cryptography 94B35 Decoding Keywords:private information retrieval; information theory; error-correcting codes PDFBibTeX XMLCite \textit{K. Kurosawa}, Lect. Notes Comput. Sci. 11922, 564--574 (2019; Zbl 1452.68072) Full Text: DOI