The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs

Mihir Bellare, Rishabh Ranjan, Doreen Riepel, Ali Aldakheel

TL;DR

This paper introduces a new, simple definition for two-party computation (2PC) security called "input indistinguishability" (InI) that is more amenable to concrete security analysis than traditional simulation-based definitions. They demonstrate that InI is equivalent to standard security definitions for practical functionalities like Private Set Intersection (PSI) and Oblivious Pseudorandom Functions (OPRFs), and provide tight security proofs for these protocols.

What Problem Does This Paper Address?

The field of secure two-party computation (2PC) has historically relied on asymptotic security definitions. While these definitions are foundational, they offer little guidance for practitioners trying to choose concrete security parameters (like key lengths or computational budgets) to achieve a desired level of security in real-world applications. This paper aims to bridge this gap by developing a concrete security framework for 2PC, focusing on achieving tight reductions and practical efficiency for important functionalities like PSI and OPRFs.

Methods

The core of this paper lies in its novel definitional framework. They introduce Input Indistinguishability (InI), a single-quantifier, indistinguishability-based definition of security. This contrasts with the traditional double-quantifier simulation-based definitions (SIM and SIM-np). A key contribution is proving that for a class of functionalities they call "invertible" (which includes PSI and OPRFs), InI is equivalent in strength to the standard simulation-based definitions. This allows for simpler, more concrete security proofs without sacrificing security guarantees. They also explicitly incorporate the Random Oracle Model (ROM) into their definitions, addressing a subtle issue related to functionality queries to the RO.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Concrete Security is Crucial for Practice: The paper argues that for real-world applications, concrete security definitions and tight reductions are essential for parameter selection and efficiency. Asymptotic security alone is insufficient.
  • InI: Simplicity Meets Power: The proposed InI definition is simpler and more "concrete-security friendly" than simulation-based definitions. Crucially, it's shown to be as powerful as simulation-based security for practical functionalities.
  • Invertibility is Key: The equivalence between InI and simulation-based security hinges on the "invertibility" of the target functionality. This property, which is met by PSI and OPRFs, allows for efficient inversion of functionality outputs, enabling simulators to construct realistic execution traces.
  • Tightness Matters: The paper emphasizes the importance of tight reductions. This means that the security of a protocol is directly related to the hardness of the underlying assumption, allowing for more efficient parameter choices.
  • ROM Nuances: The authors highlight a subtle but important issue in defining simulation-based security in the ROM, specifically concerning how functionality queries to the random oracle are handled. Their approach aims to resolve this.

Key Results

  • InI Definition: A new, concrete-security friendly definition for 2PC security.
  • InI Equivalence: For invertible functionalities (like PSI and OPRFs), InI is equivalent to standard simulation-based security (SIM and SIM-np).
  • Tight Proofs for PSI: They provide tight InI security proofs for an OPRF-based PSI protocol, reducing its security to the underlying OPRF's security.
  • Tight Bounds for OPRFs: They analyze the security of the 2H-DH OPRF under various computational assumptions, demonstrating how different assumptions lead to different degrees of tightness in the security bounds.
  • New Salted-DH PSI Protocol: A new PSI protocol is introduced that offers tighter security proofs compared to the standard DH-PSI, while maintaining similar efficiency.

Limitations and Future Work

  • Invertibility Assumption: The equivalence between InI and simulation-based security relies on the "invertibility" of the functionality. While they show this holds for PSI and OPRFs, it's an open question whether all "natural" or "practical" functionalities are invertible.
  • SIM vs. SIM-np: The paper leaves open the question of whether SIM implies SIM-np, conjecturing that a separation exists.
  • Malicious Security: The current work focuses on the semi-honest (honest-but-curious) model. Extending these concrete security definitions and results to the malicious model is a significant area for future work.
  • General Composition: While they provide a general composition result, achieving tight security for multiple executions without the linear degradation of the hybrid argument remains an area for further investigation for specific protocols.

Summary updated

Abstract

This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.
BibTeX
@article{bellare2024concrete,
  author = {Mihir Bellare and Rishabh Ranjan and Doreen Riepel and Ali Aldakheel},
  title = {{The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
}
Figure