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

Reo Eriguchi, Kaoru Kurosawa, Koji Nuida

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivated by secure database search, we present secure computation protocols for a function f in the client-servers setting, where a client can obtain 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 multivariate 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 multivariate polynomials which has the minimum number of servers, without assuming fully homomorphic encryption.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings
EditorsMarc Joye, Gregor Leander
PublisherSpringer Science and Business Media Deutschland GmbH
Pages92-121
Number of pages30
ISBN (Print)9783031587399
DOIs
Publication statusPublished - 2024
Event43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 - Zurich, Switzerland
Duration: May 26 2024May 30 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024
Country/TerritorySwitzerland
CityZurich
Period5/26/245/30/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database Search'. Together they form a unique fingerprint.

Cite this