THE GARDEN

Semantic Security

Updated 11 Aug 2026

• •

  What it is

  • •

    the practical, computationally-bounded relaxation of Perfect Security — a cipher is semantically secure if no efficient adversary can distinguish which of two chosen messages was encrypted, except with negligible advantage

• •

  Defined via an Attack Game

  • •

    the adversary picks two equal-length messages $m_0, m_1$; the challenger encrypts one of them (Experiment 0 encrypts $m_0$​, Experiment 1 encrypts $m_1$​) and returns the ciphertext; the adversary outputs a guess bit

  • •

    the adversary's SS advantage is $\mathrm{SSadv}[A, \mathcal{E}] := |\Pr[W_0] - \Pr[W_1]|$, where $W_b$​ is the event the adversary outputs 1 in Experiment $b$

• •

  Definition

  • •

    a cipher is semantically secure if $\mathrm{SSadv}[A, \mathcal{E}]$ is negligible for every efficient adversary $A$

• •

  Key property: equal-length requirement

  • •

    the two chosen messages must be the same length — this is how the definition allows a cipher to leak message length (usually unavoidable in practice) while still requiring everything else to stay hidden

• •

  Why weaker definition fail

  • •

    "attacker can't recover the key" is not enough — the absurd cipher $E(k, m) := m$ (just output the plaintext) satisfies this, since the attacker never learns $k$, yet the cipher is obviously broken

  • •

    "attacker can't recover the entire message" is not enough — a cipher that sends $m_0$​ in the clear concatenated with a secure encryption of $m_1$ satisfies this (the whole plaintext is never fully recoverable) while leaking half the message outright

• •

  Example: any single leaked bit breaks semantic security

  • •

    suppose adversary $A$ can always deduce the least-significant bit of the plaintext from a ciphertext; build SS adversary $B$: submit $m_0$​ ending in 0 and $m_1$​ ending in 1, forward the challenge ciphertext to $A$, output whatever bit $A$ recovers

  • •

    this $B$ has SS advantage exactly 1 — so if any adversary can extract even one bit of information about the plaintext (LSB, MSB, XOR-of-all-bits, anything), semantic security is broken; conversely, semantic security guarantees no bit of information leaks

• •

  The one-time pad is semantically secure (trivially — even against unbounded adversaries)

  • •

    for any $m_0, m_1$​: $k \oplus m_0$​ and $k \oplus m_1$​ are identically distributed (both uniform, by the XOR Uniformity Lemma) — so any adversary, however powerful, is handed the exact same distribution regardless of which message was encrypted, giving it zero advantage

• •

  Related

  • •

    Perfect Security

  • •

    Attack Game

  • •

    Negligible Function

  • •

    Bit-Guessing Game

  • •

    XOR Uniformity Lemma

◌ Explore connections in Graph view