International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

How to Correct Errors in Multi-server PIR

Authors:
Kaoru Kurosawa
Download:
DOI: 10.1007/978-3-030-34621-8_20
Search ePrint
Search Google
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 $$\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
}