International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kaoru Kurosawa

Publications

Year
Venue
Title
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