7 min read
On this page

Provable Security

Security Definitions

Provable security provides rigorous mathematical frameworks for analyzing cryptographic constructions. Security is defined relative to an adversary's capabilities and goals.

IND-CPA (Indistinguishability under Chosen Plaintext Attack)

The adversary chooses two messages m_0, m_1. The challenger encrypts m_b for random b in {0,1}. The adversary must guess b.

Advantage: Adv^{IND-CPA}_A = |Pr[A outputs 1 | b=1] - Pr[A outputs 1 | b=0]|

A scheme is IND-CPA secure if Adv^{IND-CPA}_A is negligible for all PPT adversaries A. Deterministic encryption cannot be IND-CPA secure (the adversary can encrypt m_0, m_1 themselves). This necessitates randomized or stateful encryption.

IND-CPA captures semantic security: ciphertexts reveal nothing about plaintexts beyond their length.

IND-CCA and IND-CCA2

IND-CCA1 (lunchtime attack): Adversary gets decryption oracle access before seeing the challenge ciphertext.

IND-CCA2 (adaptive CCA): Adversary gets decryption oracle access both before and after the challenge, except cannot query the challenge ciphertext itself. This is the standard security notion for public-key encryption.

IND-CCA2 prevents malleability: an adversary cannot modify a ciphertext to produce a related plaintext. Achieved by constructions like RSA-OAEP, Cramer-Shoup, and AEAD schemes.

EUF-CMA (Existential Unforgeability under Chosen Message Attack)

For digital signatures. The adversary can request signatures on adaptively chosen messages. Must produce a valid signature on a message not previously queried.

Strong EUF-CMA (sEUF-CMA): The adversary must produce a new (message, signature) pair, even if the message was previously signed (new signature for old message counts).

Other Notions

  • IND-CCA3/RCCA (Replayable CCA): Relaxation of IND-CCA2 allowing re-randomization
  • Key-dependent message (KDM) security: Security when encrypting functions of the secret key
  • Leakage resilience: Security when adversary obtains bounded leakage of secret key
  • Selective vs adaptive security: Whether adversary commits to target before or after seeing system parameters

Reductions

A security reduction shows that breaking a cryptographic scheme implies solving a hard computational problem.

Structure: Given adversary A that breaks scheme S with advantage epsilon in time t, construct algorithm B that solves hard problem P with advantage epsilon' in time t', where epsilon' is polynomially related to epsilon and t' is polynomially related to t.

Tightness: A reduction is tight if epsilon' ~ epsilon and t' ~ t. Loose reductions (epsilon' << epsilon) mean the concrete security guarantee is weaker, requiring larger parameters.

Example (ElGamal): If A breaks ElGamal IND-CPA with advantage epsilon, then B solves DDH with advantage epsilon. This is a tight reduction.

Types of reductions:

  • Black-box reduction: B uses A as an oracle without examining its internals. Most common.
  • Non-black-box reduction: B uses the code of A. Enables stronger results but less modular.
  • Turing reduction: B calls A multiple times (polynomial).
  • Many-one (Karp) reduction: B calls A once, making a single transformation.

Impossibility results: Some natural reductions are impossible. For example, no black-box reduction from one-way permutations to collision-resistant hash functions exists.

Random Oracle Model (ROM)

The random oracle model replaces a hash function H with a truly random function: every new query returns a uniformly random value, repeated queries return the same value.

Advantages:

  • Simplifies proofs dramatically (the reduction can "program" the oracle's responses)
  • Enables efficient constructions (OAEP, Fiat-Shamir, signatures from identification schemes)
  • Provides a useful heuristic for real-world security

Limitations:

  • Canetti-Goldreich-Halevi (1998): There exist schemes provably secure in the ROM but insecure for any concrete hash function instantiation
  • The ROM does not capture hash function structure (length extension, algebraic properties)
  • Proofs in the ROM are not "real" proofs of security in the standard model

Standard model alternatives: The standard model uses only well-defined computational assumptions. Constructions in the standard model are generally less efficient but provide stronger theoretical guarantees. The common reference string (CRS) model and generic group model (GGM) are intermediate abstractions.

Game-Based Proofs

The dominant proof methodology in applied cryptography. Security is defined through a game between a challenger C and adversary A.

Structure:

  1. Define a security game G (initialization, oracle queries, challenge, finalization)
  2. The adversary's advantage is Adv_A = |Pr[A wins G] - trivial_probability|
  3. Show Adv_A is negligible via a sequence of game transformations

Proof technique -- Game Hopping:

  • Game_0: The real security game
  • Game_i -> Game_{i+1}: Make a small modification, bound the difference in adversary's advantage
  • Game_final: A game where the adversary trivially has no advantage

Each hop is justified by one of:

  • Transition based on indistinguishability: Games differ by replacing one distribution with a computationally indistinguishable one (invoke computational assumption)
  • Transition based on failure event: Games are identical unless a bad event occurs; bound its probability
  • Bridging step: Purely syntactic change that does not affect the adversary's view

Advantage bound: Adv_A <= sum of differences across all hops.

Simulation-Based Security

An alternative paradigm where security is defined by comparison to an ideal functionality.

Real/Ideal paradigm:

  • Real world: Parties execute the protocol pi in the presence of adversary A
  • Ideal world: Parties interact with a trusted ideal functionality F, with a simulator S
  • Security: For every real-world adversary A, there exists a simulator S such that no environment Z can distinguish real from ideal execution

Universal Composability (UC) (Canetti 2001): Strongest simulation-based framework. Security guarantees hold even when the protocol is composed with arbitrary other protocols. Key features:

  • Environment Z models all external activity
  • Equational composition theorem: if pi UC-realizes F, replacing F with pi in any larger protocol preserves security
  • Some functionalities are impossible to UC-realize without setup assumptions (e.g., commitment without CRS)

Advantages over game-based: Automatic composition guarantees, models complex multi-party interactions. Disadvantages: More complex proofs, stronger assumptions often needed, simulator must work for all adversaries simultaneously.

Hybrid Arguments

A technique for extending security from single instances to multiple instances.

Standard hybrid argument: To show n ciphertexts are jointly indistinguishable from random, define n+1 hybrid distributions:

  • H_0: all real ciphertexts
  • H_i: first i ciphertexts replaced with random, rest real
  • H_n: all random

If any adversary distinguishes H_i from H_{i+1} with advantage epsilon, it breaks single-instance security. Total advantage: at most n * epsilon.

Applications:

  • Multi-message IND-CPA from single-message IND-CPA (with tight reduction using a reduction that embeds the challenge at a random position)
  • PRF/PRP switching lemma: PRF and PRP are indistinguishable up to birthday bound (advantage <= q^2/2N for q queries to a domain of size N)
  • Leftover hash lemma and randomness extraction

Concrete security implications: Hybrid arguments with n hybrids incur an n-factor loss in tightness. This matters for practice: a 128-bit security level with a reduction losing factor n = 2^30 requires the underlying assumption to be 158-bit hard.

Complexity-Theoretic Foundations

  • One-way functions (OWF): The minimal assumption. Easy to compute, hard to invert. OWF existence is equivalent to P != NP (widely believed but unproven). From OWFs: pseudorandom generators (PRG), pseudorandom functions (PRF), commitment schemes, digital signatures, CCA-secure encryption.
  • Trapdoor one-way functions: OWF with a trapdoor enabling efficient inversion. Basis for public-key encryption.
  • Computational assumptions: Specific hard problems used in reductions -- DDH, CDH, RSA, LWE, factoring. Organized in a hierarchy of implications.
  • Fine-grained cryptography: Based on polynomial hardness gaps rather than super-polynomial hardness. For example, constructions secure against O(n^2) adversaries based on problems requiring Omega(n^3) time.

Asymptotic vs. Concrete Security

Asymptotic security (negligible advantage for PPT adversaries) guides theoretical understanding. Concrete security specifies exact advantage bounds as functions of adversary resources (time, queries, memory).

Modern practice demands concrete security analysis:

  • NIST standards specify security levels (e.g., AES-128 equivalent)
  • Parameter selection requires tight reductions with explicit bounds
  • Multi-user security: advantage may degrade multiplicatively with number of users/keys
  • Quantum security: Grover's algorithm squares the advantage, requiring doubled key lengths for symmetric primitives