### How to Correct Errors in Multi-Server PIR

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)$.

Available format(s)
Publication info
A minor revision of an IACR publication in Asiacrypt 2019
Keywords
Private Information Retrievalinformation theoreticerror correcting
Contact author(s)
kaoru kurosawa kk @ vc ibaraki ac jp
History
2019-09-04: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/531

CC BY

BibTeX

@misc{cryptoeprint:2019/531,
author = {Kaoru Kurosawa},
title = {How to Correct Errors in Multi-Server PIR},
howpublished = {Cryptology ePrint Archive, Paper 2019/531},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/531}},
url = {https://eprint.iacr.org/2019/531}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.