Symmetric Encryption (SE)

A Symmetric Encryption (SE) scheme is a primitive that allows someone to encrypt plaintext into a ciphertext under a key and then to decrypt the ciphertext under the same key. It is a widely used primitive with many formal definitions of strengths.

Formal Definition

Syntax

A Symmetric Encryption (SE) scheme is a tuple of efficient functions $({\mathsf {Gen}},{\mathsf {Enc}},{\mathsf {Dec}})$, with respect to a keyspace ${\mathcal {K}}$, plaintext space ${\mathcal {M}}$, and ciphertext space ${\mathcal {C}}$, such that:

• ${\mathsf {Gen}}(1^{\lambda })\to k$, is a randomized function that takes a security parameter, and outputs a key $k\in {\mathcal {K}}$,
• ${\mathsf {Enc}}_{k}(m)\to c$, is a randomized function that takes a key $k\in {\mathcal {K}}$ and plaintext message $m\in {\mathcal {M}}$, and outputs a ciphertext $c\in {\mathcal {C}}$,
• ${\mathsf {Dec}}_{k}(c)\to m$, is a deterministic function that takes a key $k\in {\mathcal {K}}$ and ciphertext $c\in {\mathcal {C}}$, and outputs a plaintext message $m\in {\mathcal {M}}$.

Correctness

A SE scheme is correct if for all $m\in {\mathcal {M}}$, there exists a negligible function $\nu$, such that

$\Pr[{\mathsf {Dec}}_{k}({\mathsf {Enc}}_{k}(m))=m]\geq 1-\nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$.

Chosen Plaintext Attack (CPA) Security

A SE scheme is CPA-secure if for all efficient adversaries $A$, there exists a negligible function $\nu$, such that

${\big |}\Pr[A^{{\mathsf {LR}}_{k,b}}(1^{\lambda })=b]-1/2{\big |}\leq \nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$, $b$ is a uniformly random bit, and ${\mathsf {LR}}_{k,b}(m_{0},m_{1})={\mathsf {Enc}}_{k}(m_{b})$.

Chosen Ciphertext Attack (CCA) Security

A SE scheme is CCA-secure if for all admissible efficient adversaries $A$, there exists a negligible function $\nu$, such that

${\big |}\Pr[A^{{\mathsf {LR}}_{k,b},{\mathsf {Dec}}_{k}}(1^{\lambda })=b]-1/2{\big |}\leq \nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$, $b$ is a uniformly random bit, and ${\mathsf {LR}}_{k,b}(m_{0},m_{1})={\mathsf {Enc}}_{k}(m_{b})$. Further, we say an adversary is admissible if it never queries ${\mathsf {Dec}}_{k}$ on an output of ${\mathsf {LR}}_{k,b}$.

The difference in this definition is that we additionally give the adversary access to a decryption oracle. This is a strictly stronger definition than SE#CPA-security.

Indistinguishable from Random CPA (IND-CPA) Security

A SE scheme is IND-CPA-secure if for all efficient adversaries $A$, there exists a negligible function $\nu$, such that

${\big |}\Pr[A^{{\mathsf {Enc}}_{k}}(1^{\lambda })=1]-A^{R}(1^{\lambda })=1]{\big |}\leq \nu (\lambda ),$

where $k\gets {\mathsf {Gen}}(1^{\lambda })$ and $R$ is a random function from ${\mathcal {M}}\to {\mathcal {C}}$.

This security definition is also a stronger definition than CPA-security as it additionally restricts the distribution of ciphertexts produced by an encryption algorithm.

Relationship to other primitives

• PRFs imply the existence of CPA-secure SEs folklore

Sufficient assumptions

See the sufficient assumptions for OWFs.

Variations

• Authenticated Encryption
• Public Key Encryption (PKE)

Other Notes

• Other security definitions, named CCA1 and CCA2, exist and have historically been confused with the CCA notion outlined above