×

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].

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
PDFBibTeX XMLCite
Full Text: DOI