Welcome to the resource topic for 2019/531
Title:
How to Correct Errors in Multi-Server PIR
Authors: Kaoru Kurosawa
Abstract:Suppose that there exist a user and \ell servers S_1, \ldots, S_{\ell}. Each server S_j holds a copy of a database 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).
ePrint: https://eprint.iacr.org/2019/531
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .