Paper 2022/1206
On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
Abstract
An $\ell$-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among $\ell$ servers while hiding the identity of the item. It is called $b$-error-correcting if a client can correctly compute the data item even in the presence of $b$ malicious servers. It is known that $b$-error correction is possible if and only if $\ell>2b$. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-2b)$-server PIR as a function of the database size $n$. Secondly, we formalize a relaxed notion of statistical $b$-error-correcting PIR, which allows non-zero failure probability. We show that as a function of $n$, the minimum communication cost of statistical $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-b)$-server one, which is at most that of $(\ell-2b)$-server one. Our main technical contribution is a generic construction of statistical $b$-error-correcting $\ell$-server PIR for any $\ell>2b$ from regular $(\ell-b)$-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any $\ell>2b$.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in TCC 2022
- Keywords
- Private Information Retrieval
- Contact author(s)
-
reo-eriguchi @ g ecc u-tokyo ac jp
kaoru kurosawa kk @ vc ibaraki ac jp
nuida @ imi kyushu-u ac jp - History
- 2022-09-14: approved
- 2022-09-13: received
- See all versions
- Short URL
- https://ia.cr/2022/1206
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1206, author = {Reo Eriguchi and Kaoru Kurosawa and Koji Nuida}, title = {On the Optimal Communication Complexity of Error-Correcting Multi-Server {PIR}}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1206}, year = {2022}, url = {https://eprint.iacr.org/2022/1206} }