Paper 2022/500

Multi-Server PIR with Full Error Detection and Limited Error Correction

Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida

Abstract

An $\ell$-server Private Information Retrieval (PIR) scheme allows a client to retrieve the $\tau$-th element $a_\tau$ from a database $\bm{a}=(a_1,\ldots,a_n)$ which is replicated among $\ell$ servers. It is called $t$-private if any coalition of $t$ servers learns no information on $\tau$, and $b$-error correcting if a client can correctly compute $a_\tau$ from $\ell$ answers containing $b$ errors. This paper concerns the following problems: Is there a $t$-private $\ell$-server PIR scheme with communication complexity $o(n)$ such that a client can detect errors with probability $1-\epsilon$ even if $\ell-1$ servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of $(1-\epsilon)$-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most $t$ queries, which reflects $t$-privacy. We then prove an impossibility result that there exists no $1$-fully error detecting (i.e., $\epsilon=0$) PIR scheme with $o(n)$ communication. Next, for $\epsilon>0$, we construct $1$-private $(1-\epsilon)$-fully error detecting and $(\ell/2-O(1))$-error correcting PIR schemes which have $n^{o(1)}$ communication, and a $t$-private one which has $O(n^{c})$ communication for any $t\geq2$ and some constant $c<1$. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Keywords
Private Information Retrieval
Contact author(s)
reo-eriguchi @ g ecc u-tokyo ac jp
History
2022-04-28: received
Short URL
https://ia.cr/2022/500
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/500,
      author = {Reo Eriguchi and Kaoru Kurosawa and Koji Nuida},
      title = {Multi-Server PIR  with Full Error Detection and Limited Error Correction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/500},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/500}},
      url = {https://eprint.iacr.org/2022/500}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.