Symmetric key encryption

A symmetric key encryption (SKE) scheme allows a sender and receiver sharing a secret key to encrypt and decrypt messages, such that an adversary who does not know the key cannot learn anything about the plaintext from the ciphertext.

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 algorith 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 hidden bit. The adversary wins by guessing $b$.

\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)$
\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 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 ciphertexts, rather than encryptions of two chosen messages. The oracle in world 0 encrypts the query; in world 1 it returns a fresh uniform random ciphertext regardless of the input.

\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 \calC$
\Comment{Each $m$ is a uniform random ciphertext}
\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 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\$cpa}(\lambda )=1\right]-1\right|$$

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

CCA Security

In the chosen-ciphertext attack (CCA) game, the adversary additionally has access to a decryption oracle. To avoid a trivial win, $\mathcal{A}$ is admissible: it may not query $\mathcal{D}$ on any ciphertext 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)$
\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

• (Both CPA and CCA) SKE can be built in a black-box way from a OWF — Folklore?
• CPA-secure SKE can be boosted to CCA-secure SKE using a MAC