CryptoDB
Kaoru Kurosawa
Publications
Year
Venue
Title
2022
TCC
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$.
2019
ASIACRYPT
How to Correct Errors in Multi-server PIR
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)$$.
2008
ASIACRYPT
2007
PKC
2005
EUROCRYPT
1997
EUROCRYPT
Program Committees
- Asiacrypt 2018
- Asiacrypt 2015
- TCC 2015
- PKC 2014
- Crypto 2014
- PKC 2013 (Program chair)
- PKC 2012
- Crypto 2012
- PKC 2011
- Asiacrypt 2010
- Eurocrypt 2009
- Crypto 2009
- Asiacrypt 2008
- PKC 2008
- Crypto 2007
- Asiacrypt 2007 (Program chair)
- Asiacrypt 2006
- PKC 2005
- FSE 2004
- PKC 2003
- Eurocrypt 2001
- Eurocrypt 1993
Coauthors
- Masayuki Abe (2)
- Carlo Blundo (1)
- Mike Burmester (1)
- Yvo Desmedt (5)
- Reo Eriguchi (1)
- Rosario Gennaro (3)
- Goichiro Hanaoka (1)
- Swee-Huay Heng (4)
- Kazutomo Itoh (1)
- Tetsu Iwata (7)
- Thomas Johansson (2)
- Yutaka Katayama (1)
- Takeshi Koshiba (1)
- Noboru Kunihiro (1)
- Shuichi Makishima (1)
- Toshihiki Matsuo (1)
- Masashi Mitomo (1)
- Ryo Nojima (1)
- Koji Nuida (2)
- Satoshi Obana (2)
- Wakaha Ogata (11)
- Koji Okada (5)
- Tatsuaki Okamoto (1)
- Choonsik Park (2)
- Takeshi Saito (1)
- Keiichi Sakano (2)
- Kouichi Sakurai (1)
- Alfredo De Santis (1)
- Takashi Satoh (4)
- Katja Schmidt-Samoa (2)
- Victor Shoup (2)
- Douglas R. Stinson (2)
- Kazuhiro Suzuki (1)
- Tsuyoshi Takagi (3)
- Shigeo Tsujii (7)
- Takuya Yoshida (2)
- Tomonobu Yoshino (2)
- Tomohiro Yuasa (1)