§2 Perfectly Secret Encryption

Perfect Secrecy

Perfect Secrecy: Threat Model

• In defining the notion of perfect secrecy, we first consider the threat model of a single ciphertext-only attack.

• Adversary knows $(Gen, Enc, Dec)$, and the probability distribution over $\mathscr M$.

  Adversary passively eavesdrops on the communication and is able to get a single ciphertext.

• No assumption is made on the computational power of the adversary.

  Adversary does not know the secret key shared by Alice and Bob.

Perfect Secrecy: Definition

• Definition. An encryption scheme $(Gen, Enc, Dec)$ with message space $\mathscr M$ is perfectly secret if for every probability distribution over $\mathscr M$, every message $m \in \mathscr M$ and every ciphertext $c \in \mathscr C$ for which $\Pr [C = c] > 0$, it holds that

  $$\Pr [M = m|C = c] = \Pr [M = m]$$

Perfect Secrecy: Equivalent Definition

• Lemma. An encryption scheme $(Gen, Enc, Dec)$ with message space $\mathscr M$ is perfectly secret if and only if

  $$\Pr [Enc_K(m) = c] = \Pr [Enc_K(m' ) = c]$$

  or equivalently if

  $$\Pr [C = c|M = m] = \Pr [C = c|M = m']$$

  holds for every $m, m' \in \mathscr M$ and every $c \in \mathscr C$.

Adversarial Indistinguishability Experiment $\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}$

1. The adversary $\mathscr A$ outputs a pair of messages $m_0, m_1 \in \mathscr M$.

2. A key $k$ is generated using $Gen$ and a bit $b \in \{0,1\}$ is chosen uniformly at random.

   The challenge ciphertext $c \leftarrow Enc_k (m_b)$ is computed and given to $\mathscr A$.

3. $\mathscr A$ outputs a guess bit $b' ∈ \{0,1\}$.

4. The adversary succeeds and the output of the experiment is defined to be $1$ if $b' = b$ and $0$ otherwise. We write $\operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}=1$ if the output of the experiment is $1$.

Perfect Indistinguishability

• Definition. An encryption scheme $\Pi = (Gen, Enc, Dec)$ with message space $\mathscr M$ is perfectly indistinguishable if for every $\mathscr A$ it holds that

  $$\Pr \left[ \operatorname{PrivK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}=1 \right] = \frac{1}{2}$$

• Lemma. An encryption scheme $\Pi$ is perfectly secret if and only if it is perfectly indistinguishable.

One-Time Pad: A Perfectly Secret Private-Key Encryption Scheme

One-Time Pad Encryption Scheme

• Fix an integer $l > 0$. The message space, key space and ciphertext space are the set of all binary strings of length $l$, i.e. $\mathscr M = \mathscr K = \mathscr C = \{0,1\}^l$.
• $Gen$: the key-generation algorithm chooses key uniformly at random from the key space i.e., $k \leftarrow \mathscr K$ with $\Pr [K = k] = 2^{-l} \quad \forall k \in \mathscr K$.
• $Enc$ : given inputs $k \in \mathscr K$ and $m \in \mathscr M$, the encryption algorithm outputs $c := m \oplus k$.
• $Dec$ : given inputs $k \in \mathscr K$ and $c \in \mathscr C$, the decryption algorithm outputs $m := c \oplus k$.

One-Time Pad: Bitwise XOR

• Correctness: The One-Time Pad satisfies the correctness criterion, since for every $k, m$ we have

  $$Dec_k (Enc_k (m)) = (m \oplus k) \oplus k = m \oplus (k \oplus k) = m \oplus 0 = m$$

Perfect Secrecy of the One-Time Pad

• Theorem. The One-Time Pad encryption scheme is perfectly secret.

Optimality of the One-Time Pad

• Theorem. If $(Gen, Enc, Dec)$ is a perfectly secret encryption scheme with message space $\mathscr M$ and key space $\mathscr K$, then $|\mathscr K| ≥ |\mathscr M|$.

— Feb 1, 2023

§2 Perfectly Secret Encryption by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.