Symmetric key encryption (SE)

Symmetric key encryption (SE) is a central cryptographic primitive in theory and in practice.

Definition

A symmetric key encryption (SE) scheme is a tuple of efficient algorithms $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$, with respect to key space $\mathcal{K}$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$ such that

• $\mathsf{Gen}(1^{\lambda })\to k$, is a randomized algorithm that takes a security parameter, and outputs a key $k\in \mathcal{K}$,
• ${\mathsf{Enc}}_k(m)\to c$, is a randomized algorithm that takes a key $k\in \mathcal{K}$ and message $m\in \mathcal{M}$, and outputs a ciphertext $c\in \mathcal{C}$,
• ${\mathsf{Dec}}_k(c)\to m$, is a deterministic algorithm that takes a key $k\in \mathcal{K}$ and candidate ciphertext $c\in \mathcal{C}$, and outputs either a message $m\in \mathcal{M}$
  • One may also allow ${\mathsf{Dec}}_k$ to output $\perp$ to indicate that a candidate ciphertext is not a valid encryption

Correctness

A SE scheme is correct if for every $\lambda \in \mathbb{N}$ and message $m\in \mathcal{M}$, $\mathrm{Pr}[{\mathsf{Dec}}_k({\mathsf{Enc}}_k(m)))=m\mid k\leftarrow \mathsf{Gen}(1^{\lambda })]=1$.

Chosen Plaintext Attack (CPA) Security

The CPA advantage of an adversary $\mathcal{A}$ is defined as ${\text{Adv}}_{\mathcal{A}}^{\text{cpa}}(\lambda )\le 2\left|\mathrm{Pr}[{\mathcal{A}}^{{\mathsf{LR}}_{k,b}}(1^{\lambda })=b]-\frac{1}{2}\right|,$ where $k\leftarrow \mathsf{Gen}(1^{\lambda })$, $b\leftarrow \{0,1\}$, and ${\mathsf{LR}}_{k,b}(m_0,m_1)={\mathsf{Enc}}_k(m_b)$ is a left-right oracle, which encrypts either its left or right input based on the input $b$.

An SE scheme is CPA-secure if for all efficient $\mathcal{A}$, there exists a negligible function $\nu$, such that: ${\text{Adv}}_{\mathcal{A}}^{\text{cpa}}(\lambda )\le \nu (\lambda )$.

Indistinguishable from random CPA (IND$-CPA)

The IND$-CPA advantage of an adversary $\mathcal{A}$ is defined as ${\text{Adv}}_{\mathcal{A}}^{\text{ind\$-cpa}}(\lambda )\le \left|\mathrm{Pr}[{\mathcal{A}}^{{\mathsf{Enc}}_k}(1^{\lambda })=1]-\mathrm{Pr}[{\mathcal{A}}^R(1^{\lambda })=1]\right|,$where $k\leftarrow \mathsf{Gen}(1^{\lambda })$ and $R$ is a random response oracle, which on each query gives a uniformly random $n$-bit string (even on the same input, unlike a random oracle).

An SE scheme is IND$-CPA-secure if for all efficient $\mathcal{A}$, there exists a negligible function $\nu$, such that: \text{Adv}^{\text{ind\-cpa}}_{\mathcal{A}}(\lambda)\le \nu(\lambda)$.

Chosen Ciphertext Attack (CCA) Security

The CCA advantage of an adversary $\mathcal{A}$ is defined as ${\text{Adv}}_{\mathcal{A}}^{\text{cca}}(\lambda )\le 2\left|\mathrm{Pr}[{\mathcal{A}}^{{\mathsf{LR}}_{k,b},{\mathsf{Dec}}_k}(1^{\lambda })=b]-\frac{1}{2}\right|,$ where $k\leftarrow \mathsf{Gen}(1^{\lambda })$, $b\leftarrow \{0,1\}$, and ${\mathsf{LR}}_{k,b}(m_0,m_1)={\mathsf{Enc}}_k(m_b)$ is a left-right oracle, which encrypts either its left or right input based on the input $b$.

An SE scheme is CCA-secure if for all admissible $\mathcal{A}$, there exists a negligible function $\nu$, such that: ${\text{Adv}}_{\mathcal{A}}^{\text{cca}}(\lambda )\le \nu (\lambda )$. An adversary is admissible if it is efficient and never queries $\mathsf{Dec}$ with an output of $\mathsf{LR}$, i.e., it never decrypts encryptions from the oracle (but it may query inputs which depend on the outputs given).

• This restriction is necessary, as otherwise $\mathcal{A}$ could trivially discover what $b$ is by querying $\mathsf{LR}(0,1)$ and decrypting the answer.

Other results

• (Both CPA and CCA) SE can be built in a black-box way from a One-way function — Folklore?
• Boosting CPA encryption can be boosted to CCA by using a MAC