Symmetric key encryption

A symmetric key encryption (SKE) scheme allows a sender and receiver sharing a secret key to encrypt and decrypt messages. Its security notions specify what an adversary can learn about the message, allowing leakage of its length.

Syntax

A SKE scheme is a tuple of efficient algorithms $\mathsf{SKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to keyspace $\mathcal{K},$ message space $\mathcal{M},$ and ciphertext space $\mathcal{C}$:

• $\mathsf{KeyGen}(1^{\lambda })\to k,$ is a randomized algorithm which samples a key $k\in \mathcal{K}$,
• $\mathsf{Enc}(k,m)\to c,$ is a randomized algorithm which takes a key $k\in \mathcal{K}$ and message $m\in \mathcal{M}$, outputting a ciphertext $c\in \mathcal{C}$,
• $\mathsf{Dec}(k,c)\to m,$ is a deterministic algorithm which takes a key $k\in \mathcal{K}$ and ciphertext $c\in \mathcal{C}$, outputting a message $m\in \mathcal{M}$ or $\perp$ to indicate an invalid ciphertext.

Properties

Correctness

A SKE scheme $\mathsf{SKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ is $(1-\epsilon )$-correct if for all $\lambda \in \mathbb{N}$ and $m\in \mathcal{M}$,

$$\mathrm{Pr}\left[\mathsf{Dec}(k,\mathsf{Enc}(k,m))=m\right]\ge 1-\epsilon ,$$

over the choice of $k\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and randomness of $\mathsf{Enc}.$ When $\epsilon =0$, we say $\mathsf{SKE}$ is perfectly correct.

CPA Security

In the chosen-plaintext attack (CPA) game, the adversary adaptively queries a left-right encryption oracle: it submits message pairs $(m_0,m_1)$ and receives an encryption of $m_b$, where $b$ is a single hidden bit shared by all queries. Each encryption uses fresh randomness. An admissible adversary submits $m_0,m_1\in \mathcal{M}$ with $|m_0|=|m_1|$ on every query; otherwise ciphertext length may reveal $b$. The adversary wins by guessing $b$ — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cpa}}_{\SKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calO_0(m_0, m_1) := \Enc(k, m_0)$
\State $\calO_1(m_0, m_1) := \Enc(k, m_1)$
\Comment{Every query has $m_0,m_1 \in \calM$ and $|m_0|=|m_1|$}
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A SKE scheme $\mathsf{SKE}$ is CPA-secure if for all admissible efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{SKE},\mathcal{A}}^{\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{SKE},\mathcal{A}}^{\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible.

IND$-CPA Security

Indistinguishability from random (IND$-CPA) is a stronger notion where the adversary must distinguish real encryptions from uniformly random strings of the same length. For each security parameter, assume an encryption of $m\in \mathcal{M}$ always has length $\ell (\lambda ,|m|)$, independent of the key and encryption coins. An admissible adversary queries only messages in $\mathcal{M}$. The oracle in world 0 encrypts each query with fresh randomness; in world 1 it returns a fresh uniform string in $\{0,1{\}}^{\ell (\lambda ,|m|)}$, which need not be a valid ciphertext — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{ind\$\text{-}cpa}}_{\SKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calO_0(m) := \Enc(k, m)$
\State $\calO_1(m) \getsr \bits^{\ell(\secpar, |m|)}$
\Comment{Each query has $m \in \calM$; use fresh coins in both worlds}
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A SKE scheme $\mathsf{SKE}$ is IND$-CPA-secure if for all admissible efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{SKE},\mathcal{A}}^{ind\$\text{-}\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{SKE},\mathcal{A}}^{ind\$\text{-}\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible. IND$-CPA implies CPA security, but not vice versa — standard.

CCA Security

In the chosen-ciphertext attack (CCA) game, the adversary additionally has access to a decryption oracle. An admissible adversary submits equal-length messages in $\mathcal{M}$ on every encryption query and may not query $\mathcal{D}$ on any ciphertext already output by the encryption oracle ${\mathcal{O}}_b$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cca}}_{\SKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calO_b(m_0, m_1) := \Enc(k, m_b)$
\Comment{Every query has $m_0,m_1 \in \calM$ and $|m_0|=|m_1|$}
\State $\calD(c) := \Dec(k, c)$
\Comment{$\calA$ may not query $\calD$ on outputs of $\calO_b$}
\State $b' \gets \calA^{\calO_b, \calD}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A SKE scheme $\mathsf{SKE}$ is CCA-secure if for all admissible efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{SKE},\mathcal{A}}^{\mathrm{cca}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{SKE},\mathcal{A}}^{\mathrm{cca}}(\lambda )=1\right]-1\right|$$

is negligible. The admissibility restriction is necessary: without it, $\mathcal{A}$ could query ${\mathcal{O}}_b(0,1)$ and then decrypt the result to trivially learn $b$.

Other results

• OWF ⇒ PRG
• PRF ⇒ CPA-secure SKE
• PRF ⇒ MAC
• SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE

Participates in

Builds on Symmetric key encryption

• CPA-secure SKE ⇒ SKE (via CPA Security)
• IND-CPA KEM + SKE ⇒ IND-CPA PKE
• IND$-CPA Security ⇒ CPA Security (via IND$-CPA Security)
• IND-CCA KEM + CCA-secure SKE ⇒ IND-CCA PKE (via CCA Security)
• SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE (via CPA Security)
• SKE ⇒ OWF (via CPA Security)

Produces Symmetric key encryption

• CPA-secure SKE ⇒ SKE
• IND$-CPA Security ⇒ CPA Security (via CPA Security)
• SUF-CMA MAC + CPA-secure SKE ⇒ CCA-secure SKE (via CCA Security)
• PRC ⇒ SKE
• PRF ⇒ CPA-secure SKE (via CPA Security)

Barriers

• No fixed-construction reduction from CPA Security to IND$-CPA Security (via CPA Security, IND$-CPA Security)