International Association
for Cryptologic Research

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.