International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Mihir Bellare , University of California San Diego
Rishabh Ranjan , University of California San Diego
Doreen Riepel , University of California San Diego
Ali Aldakheel , King Abdulaziz City for Science and Technology
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: This paper aims to give tight proofs, and thus concrete-security improvements, for protocols for two-party computation. Our first step is to suggest, as target, a simple, indistinguishability-based, concrete-security-friendly definition we call InI. This would of course be a poor choice if InI were weaker than the standard simulation-based definition, but it is not; we show that for functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study 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 one that is tight, for the well-known and efficient 2H-DH OPRF.
BibTeX
@inproceedings{asiacrypt-2024-34693,
  title={The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs},
  publisher={Springer-Verlag},
  author={Mihir Bellare and Rishabh Ranjan and Doreen Riepel and Ali Aldakheel},
  year=2024
}