Simulation-Based and UC Security Proofs

Overview

Simulation-based security is the gold standard for proving cryptographic protocol security. The paradigm compares a real protocol execution to an ideal world that is secure by definition. A protocol is secure if any real-world attack can be "simulated" in the ideal world, meaning the adversary learns nothing beyond what is inherently leaked by the functionality.

When to Use This Skill

• Proving security of two-party or multi-party computation protocols
• Constructing zero-knowledge proof systems
• Analyzing oblivious transfer, commitment schemes, or coin-tossing protocols
• Working with semi-honest or malicious adversary models
• Proving security in the CRS model or Random Oracle model
• Establishing UC (Universally Composable) security
• Writing hybrid-model proofs with ideal functionalities as subroutines

Quick Reference: The Three Tasks of a Simulator

Quick Reference: Simulation Strategies by Protocol Type

References

• references/coreconceptsand_techniques.md: Computational indistinguishability, ideal/real paradigm, adversary models (semi-honest and malicious definitions), proof techniques (hybrid argument, rewinding, hybrid model, reductions), common pitfalls, special models (CRS, ROM, adaptive), and proof checklist
• references/hybrid_arguments.md: Hybrid lemma, types of hybrid arguments, systematic construction of hybrid sequences
• references/simulator_constructions.md: Detailed patterns for constructing simulators (OT, commitment, coin-tossing, etc.)
• references/uc_framework.md: UC execution model, UC security definition, impossibility results, UC with CRS
• templates/latexprooftemplates.md: LaTeX templates for semi-honest proofs, malicious adversary proofs, and zero-knowledge proofs

Key References

1. Lindell (2025), "How To Simulate It", a tutorial on the simulation proof technique
2. Goldreich (2004), Foundations of Cryptography Vol. II
3. Canetti (2001), "Universally Composable Security" (FOCS 2001)
4. Goldreich, Micali, Wigderson (1991), "Proofs that Yield Nothing but their Validity" (JACM)