International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database Search

Reo Eriguchi , National Institute of Advanced Industrial Science and Technology (AIST)
Kaoru Kurosawa , Chuo University/AIST
Koji Nuida , Kyushu University/AIST
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
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.
  title={Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database Search},
  author={Reo Eriguchi and Kaoru Kurosawa and Koji Nuida},