Computational ciphers, semantic security, and reductions

Updated 06 Nov 2026

• •

  Computational ciphers and effciency bounds

  • •

    Definition

    • •

      a computational cipher is a pair of efficient algorithms $(E, D)$ defined over $(K, M, C)$

      • •

        E(k, m)$ -> deterministic or probabilistic polynomial-time (PPT) algorithm.

      • •

        $D(k, c)$ -> deterministic polynomial-time algorithm.

      • •

        correctness -> for all $k \in K$ and $m \in M$: $D(k, E(k, m)) = m$.

  • •

    Paradigm shift -> we abandon unbounded adversaries and restrict the attacker to realistic, computationally bounded polynomial-time algorithms

• •

  Attack games and distinguishing advantage

  • •

    Attack Game methodology

    • •

      formal protocol between a Challenger (executes a fixed, simple verification procedure) and an Adversary $A$ (arbitrary PPT algorithm)

    • •

      Two-experiment model

      • •

        experiment 0 -> challenger executes scenario under condition $b=0$

      • •

        experiment 1 -> challenger executes scenario under condition $b=1$

      • •

        adversary outputs bit $\hat{b} \in \{0, 1\}$

      • •

        let $W_b$ denote the event that Adversary outputs 1 in Experiment $b$

    • •

      Distinguishing advantage -> measures how effectively adversary $A$ distinguishes Experiment 0 from Experiment 1:

      • •
        $$\mathbf{Adv}[A] := |\Pr[W_0] - \Pr[W_1]|$$
    • •

      a cryptographic primitive is secure if $\mathbf{Adv}[A]$ is negligible for every PPT adversary $A$

  • •

    Bit-Guessing Game equialence

    • •

      reformulates the two experiments into a single unified game:

      1. 1.

         challenger samples random bit $b \xleftarrow{R} \{0, 1\}$

      2. 2.

         challenger executes Experiment $b$

      3. 3.

         adversary guesses bit $\hat{b}$

    • •

      Bit-guessing advantage -> $\mathbf{Adv}^*[A] := |\Pr[\hat{b} = b] - 1/2|$

    • •

      Conversion formula -> $\mathbf{Adv}[A] = 2 \cot \mathbf{Adv}^*[A]$

    • •

      both formulations are mathematically equivalent up to a factor of 2

• •

  Negligible functions and security paramters

  • •

    Asymptotic definition

    • •

      a function $\epsilon(\lambda)$ of security parameter $\lambda$ is negligible (denoted $\operatorname{negl}(\lambda)$) if for every positive constat $c > 0$, there exists an integer $\lambda_0$ such that for all $\lambda > \lambda_0$:

      • •
        $$\epsilon(\lambda) < \frac{1}{\lambda^c}$$
    • •

      a negligible function asymptotically vanishes faster than the reciprocal of any polynomial

  • •

    Concrete engineering framing

    • •

      in deployed protocols, values $\le 2^{-80}$ or $2^{-128}$ are treated as negligible (zero practical probability of occurrence over the lifetime of a key)

    • •

      probabilities $\ge 2^{-30}$ (e.g., 1 event per gigabyte of traffic) are non-negligible

  • •

    Algebraic closure properties

    • •

      sum of two negligible functiosn is negligible: $\operatorname{negl}_1 + \operatorname{negl}_2 = \operatorname{negl}$

    • •

      product of a polynomial-bounded function and a negligible function is negligible: $\operatorname{poly}(\lambda) \cdot \operatorname{negl}(\lambda) = \operatorname{negl}(\lambda)$.

    • •

      sum or product of polynomial functions remains polynomial

• •

  Semantic security (IND-CPA eavesdropper security)

  • •

    The Semantic Security Game

    1. 1.

       challenger samples secret key $k \xleftarrow{R} K$

    2. 2.

       adversary $A$ computes and submits two challenge plaintexts $m_0, m_1 \in M$ with the strict condition that $|m_0| = |m_1|$

    3. 3.

       challenger samples secret bit $b \xleftarrow{R} \{0, 1\}$, computes challenge ciphertext $c \leftarrow E(k, m_b)$, and returns $c$ to $A$

    4. 4.

       adversary $A$ outputs guess bit $\hat{b} \in \{0, 1\}$

  • •

    Definition -> a cipher $\mathcal{E}$ is semantically secure if for every efficient adversary $A$:

    • •
      $$\mathrm{SSadv}[A, \mathcal{E}] := |\Pr[A(E(k, m_0)) = 1] - \Pr[A(E(k, m_1)) = 1]| \le \operatorname{negl}$$
  • •

    The equal-length requirement -> ciphertext is permitted to leak message length; enforcing equal length $|m_0|=|m_1|$ isolates confidentiality of content from length leakage

  • •

    Why naive security definitions fail

    • •

      "Attacker cannot recover the key" -> trivially satisfied by the insecure cipher $E(k, m) = m$ (transmits plaintext in the clear; key is never exposed, yet secrecy is zero)

    • •

      "Attacker cannot recover the entire plaintext" -> satisfied by $E(k, m) = (m_0 \text{ in clear}, E'(k, m_1))$, which exposes half the message while preventing full recovery

  • •

    Leakage of any single bit breaks semantic security

    • •

      if an adversary can determine any single predicate of the plaintext (e.g., LSB, parity, or header bit) with non-negligible advantage:

      • •

        construct adversary $B$: submit $m_0$ with LSB $= 0$ and $m_1$ with LSB $= 1$

      • •

        examine challenge $c$; output $A$'s predicted LSB

      • •

        adversary $B$ achieves advantage $\mathrm{SSadv} \approx 1$

    • •

      semantic security guarantees that no single bit of plaintext information is leranable

  • •

    One-Time Pad security status

    • •

      the One-Time Pad is semantically secure even against computationally unbounded adversaries, because $k \oplus m_0$ and $k \oplus m_1$ are identically distributed by the XOR Uniformity Lemma

  • •

    

• •

  Security reductions and message recovery

  • •

    

  • •

    Security reduction methodology

    • •

      standard proof technique in theoretical cryptography

    • •

      to prove that breaking property X is computationally hard based on the hardness of primitive Y:

      1. 1.

         assume an efficient adersary $A$ exists that breaks property X with non-negligible advantage $\epsilon$

      2. 2.

         construct an efficient adversary $B$ (the reduction wrapper) that uses $A$ as a black-box subroutine to break primitive Y

      3. 3.

         conclude that since no efficient algorithm can break Y, no efficient adversary $A$ can exist

  • •

    Message Recovery Attack Game

    • •

      challenger samples $k \xleftarrow{R} K$ and $m \xleftarrow{R} M$

    • •

      adversary $A$ receives challenge $c = E(k, m)$ and outputs a guess $m'$

    • •

      Advantage -> $\mathrm{MRadv}[A, \mathcal{E}] := |\Pr[A(E(k, m)) = m] - 1/|M||$.

  • •

    Theorem: Semantic Security implies Message Recovery Security

    • •

      if cipher $\mathcal{E}$ is semantically secure, then $\mathrm{MRadv}[A, \mathcal{E}]$ is negligible for all efficient adversaries

    • •

      Reduction construction

      • •

        build SS adversary $B$: sample two independent uniform messages $m_0, m_1 \xleftarrow{R} M$.

      • •

        submit $(m_0, m_1)$ to SS challenger; receive $c = E(k, m_b)$.

      • •

        run message recovery adversary $A(c)$ to obtain output $m'$.

      • •

        if $m' = m_0$, output 0; if $m' = m_1$, output 1; otherwise, output a uniform random bit.

      • •

        analysis shows $B$'s distinguishing advantage is bounded below by $A$'s message recovery advantage:

        • •
          $$\mathrm{SSadv}[B, \mathcal{E}] \ge \mathrm{MRadv}[A, \mathcal{E}] \cdot \left(1 - \frac{1}{|M|}\right)$$
      • •

        Since $\mathrm{SSadv}$ is negligible, $\mathrm{MRadv}$ must also be negligible.

  • •

◌ Explore connections in Graph view