CryptoDB
Kaoru Kurosawa
Publications
Year
Venue
Title
2024
EUROCRYPT
Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database Search
Abstract
Motivated by secure database search, we present secure computation protocols for a function $f$ in the client-servers setting, where a client obtains $f(x)$ on a private input $x$ by communicating with multiple servers each holding $f$. Specifically, we propose generic compilers from passively secure protocols, which only keep security against servers following the protocols, to actively secure protocols, which guarantee privacy and correctness even against malicious servers. Our compilers are applied to protocols computing any class of functions, and are efficient in that the overheads in communication and computational complexity are only polynomial in the number of servers, independent of the complexity of functions. We then apply our compilers to obtain concrete actively secure protocols for various functions including private information retrieval (PIR), bounded-degree polynomials and constant-depth circuits. For example, our actively secure PIR protocols achieve exponentially better computational complexity in the number of servers than the currently best-known protocols. Furthermore, our protocols for polynomials and constant-depth circuits reduce the required number of servers compared to the previous actively secure protocols. In particular, our protocol instantiated from the sparse learning parity with noise (LPN) assumption is the first actively secure protocol for polynomials which has the minimum number of servers, without assuming fully homomorphic encryption.
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
Service
- PKC 2023 Program committee
- Asiacrypt 2018 Program committee
- TCC 2015 Program committee
- Asiacrypt 2015 Program committee
- Crypto 2014 Program committee
- PKC 2014 Program committee
- PKC 2013 Program chair
- Crypto 2012 Program committee
- PKC 2012 Program committee
- PKC 2011 Program committee
- Asiacrypt 2010 Program committee
- Crypto 2009 Program committee
- Eurocrypt 2009 Program committee
- PKC 2008 Program committee
- Asiacrypt 2008 Program committee
- Crypto 2007 Program committee
- Asiacrypt 2007 Program chair
- Asiacrypt 2006 Program committee
- PKC 2005 Program committee
- FSE 2004 Program committee
- PKC 2003 Program committee
- Eurocrypt 2001 Program committee
- Eurocrypt 1993 Program committee
Coauthors
- Masayuki Abe (2)
- Carlo Blundo (1)
- Mike Burmester (1)
- Yvo Desmedt (5)
- Reo Eriguchi (2)
- 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)
- Kaoru Kurosawa (59)
- Shuichi Makishima (1)
- Toshihiki Matsuo (1)
- Masashi Mitomo (1)
- Ryo Nojima (1)
- Koji Nuida (3)
- 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)