1---2name: simulation-security-proofs3description: Use when proving security of MPC protocols, zero-knowledge proofs, oblivious transfer, commitment schemes, garbled circuits, or any protocol whose security is argued by comparing a real execution against an ideal functionality, in standalone simulation-based or UC frameworks. Covers simulator construction, hybrid arguments, corruption models, composition theorems, and writing the proof section of a cryptographic paper so the ideal-versus-real argument is complete and checkable.4---56# Simulation-Based and UC Security Proofs78## Overview910Simulation-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.1112## When to Use This Skill1314- Proving security of two-party or multi-party computation protocols15- Constructing zero-knowledge proof systems16- Analyzing oblivious transfer, commitment schemes, or coin-tossing protocols17- Working with semi-honest or malicious adversary models18- Proving security in the CRS model or Random Oracle model19- Establishing UC (Universally Composable) security20- Writing hybrid-model proofs with ideal functionalities as subroutines2122## Quick Reference: The Three Tasks of a Simulator2324| Task | Description |25|------|-------------|26| Generate view | Simulated transcript must be computationally indistinguishable from real execution |27| Extract inputs | Determine the effective inputs used by the adversary |28| Ensure consistency | Make the generated view consistent with outputs based on extracted inputs |2930## Quick Reference: Simulation Strategies by Protocol Type3132| Protocol Type | Key Challenge | Simulation Strategy |33|--------------|---------------|---------------------|34| Semi-honest OT | Generate view without knowing other input | Use trapdoor to compute both values |35| Zero-knowledge | Generate accepting view without witness | Rewind to guess challenge |36| Coin-tossing | Force output to specific value | Rewind until XOR matches |37| Malicious OT | Extract sender's inputs | CRS trapdoor or DDH tuple |38| Commitment | Equivocate or extract | Trapdoor commitment or rewinding |39| MPC (malicious) | Extract all inputs, ensure consistency | Hybrid model with ZK subprotocol |4041## References4243- **references/core_concepts_and_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 checklist44- **references/hybrid_arguments.md**: Hybrid lemma, types of hybrid arguments, systematic construction of hybrid sequences45- **references/simulator_constructions.md**: Detailed patterns for constructing simulators (OT, commitment, coin-tossing, etc.)46- **references/uc_framework.md**: UC execution model, UC security definition, impossibility results, UC with CRS47- **templates/latex_proof_templates.md**: LaTeX templates for semi-honest proofs, malicious adversary proofs, and zero-knowledge proofs4849## Key References50511. Lindell (2025), "How To Simulate It", a tutorial on the simulation proof technique522. Goldreich (2004), Foundations of Cryptography Vol. II533. Canetti (2001), "Universally Composable Security" (FOCS 2001)544. Goldreich, Micali, Wigderson (1991), "Proofs that Yield Nothing but their Validity" (JACM)
sipengxie2024