The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and...
summary
Proposes a concrete, indistinguishability-based definition called input indistinguishability (InI) and proves it is equivalent to standard simulation for a class of invertible functionalities that includes PSI and variants. Gives tight, quantitative reductions for a canonical OPRF-based Diffie‑Hellman PSI, showing DDH yields constant-factor tightness while CDH gives quadratic losses that drop to linear with a new salted-DH PSI variant; work assumes semi‑honest, deterministic functionalities and treats random‑oracle programming subtleties.
AI-written summary · about
chapters (7)
- 0:00Concrete security intro
- 4:42Simple security definition
- 8:32Asymptotic vs concrete security
- 17:08Input indistinguishability
- 27:31Diffie-Hellman PSI bounds
- 29:52Theory versus practice
- 33:07Cryptography's societal impact
related talks
18mProtecting User Privacy in Private Set Intersection: A Journey Toward Mitigating User
12mOne-Way Functions Imply Secure Computation in a Quantum World
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
52mIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
01h 08mTutorial: Security
01h 08mTutorial on Proof Systems
01h 08mSecure Computation 1
40mOn the Complexity of Two-Party Differential Privacy