## CryptoDB

### Paper: How to Correct Errors in Multi-server PIR

Authors: Kaoru Kurosawa DOI: 10.1007/978-3-030-34621-8_20 Search ePrint Search Google 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)$.
##### BibTeX
@article{asiacrypt-2019-30051,
title={How to Correct Errors in Multi-server PIR},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11922},
pages={564-574},
doi={10.1007/978-3-030-34621-8_20},
author={Kaoru Kurosawa},
year=2019
}