How to Correct Errors in Multi-Server PIR

Kaoru Kurosawa

Paper 2019/531

How to Correct Errors in Multi-Server PIR

Kaoru Kurosawa

Abstract

Suppose that there exist a user and $ℓ$ servers $S_{1}, \dots, S_{ℓ}$ . Each server $S_{j}$ holds a copy of a database $x = (x_{1}, \dots, x_{n}) \in {0, 1}^{n}$ , and the user holds a secret index $i_{0} \in {1, \dots, n}$ . A b error correcting $ℓ$ 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 / (2 k - 1)} \times k ℓ \log ℓ)$ where $k = ℓ - 2 b$ , the decoding algorithm is very inefficient. In this paper, we show an efficient decoding algorithm for this error correcting server PIR scheme. It runs in time .

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in ASIACRYPT 2019
Keywords: Private Information Retrieval information theoretic error correcting
Contact author(s): kaoru kurosawa kk @ vc ibaraki ac jp
History: 2019-09-04: last of 2 revisions; 2019-05-21: received; See all versions
Short URL: https://ia.cr/2019/531
License: 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},
      url = {https://eprint.iacr.org/2019/531}
}