Game-Based Security Proof Methodology

Overview

This skill provides systematic guidance for constructing security proofs using the sequence-of-games technique. The methodology transforms complex security arguments into manageable sequences of small, analyzable transitions between games.

Core Principle: Security proofs proceed by constructing Game 0 (original attack game), then transforming it through Games 1, 2, ..., n until reaching a game where the target probability is easily computed. Each transition changes only one aspect, making analysis tractable.

When to Use This Skill

• Proving semantic security (IND-CPA, IND-CCA) of encryption schemes
• Proving unforgeability (EUF-CMA) of signatures/MACs
• Proving pseudorandomness of PRFs/PRPs
• Reducing security to computational assumptions (DDH, CDH, RSA, LWE)
• Writing formal proofs for cryptography papers

Proof Structure Template

1. Setup Phase