International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kaoru Kurosawa

Publications

Year
Venue
Title
2022
TCC
On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
Reo Eriguchi Kaoru Kurosawa Koji Nuida
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
Kaoru Kurosawa
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)$$.
2015
EUROCRYPT
2010
JOFC
2009
ASIACRYPT
2008
JOFC
2008
EUROCRYPT
2008
ASIACRYPT
2007
PKC
2006
ASIACRYPT
2006
PKC
2006
PKC
2005
EUROCRYPT
2005
EUROCRYPT
2005
FSE
2005
PKC
2004
CRYPTO
2004
PKC
2004
PKC
2003
ASIACRYPT
2003
ASIACRYPT
2003
FSE
2002
ASIACRYPT
2002
FSE
2002
PKC
2002
PKC
2001
FSE
2001
PKC
2001
JOFC
2000
ASIACRYPT
2000
ASIACRYPT
2000
EUROCRYPT
2000
FSE
1999
ASIACRYPT
1999
ASIACRYPT
1999
JOFC
1998
ASIACRYPT
1998
EUROCRYPT
1997
EUROCRYPT
1997
EUROCRYPT
1996
ASIACRYPT
1996
EUROCRYPT
1995
CRYPTO
1995
EUROCRYPT
1994
ASIACRYPT
1994
ASIACRYPT
1994
ASIACRYPT
1994
ASIACRYPT
1994
CRYPTO
1993
EUROCRYPT
1993
EUROCRYPT
1993
EUROCRYPT
1992
AUSCRYPT
1992
AUSCRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1990
CRYPTO
1990
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