Public Key Encryption (PKE)

A Public Key Encryption (PKE) scheme is a primitive that allows someone to publish a public key that can be used to encrypt plaintext. Then, the generator of the key can use a secret key to decrypt the ciphertext. It is a critical notion for the modern public-key infrastructure and was famously made possible by [RSA78] and [Elg85].

Formal Definition

Syntax

A Public Key Encryption (PKE) scheme is a tuple of efficient functions $({\mathsf {Gen}},{\mathsf {Enc}},{\mathsf {Dec}})$, with respect to a keyspace ${\mathcal {K}}={\mathcal {K}}_{\text{pub}}\times {\mathcal {K}}_{\text{sec}}$, plaintext space ${\mathcal {M}}$, and ciphertext space ${\mathcal {C}}$, such that:

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

Correctness

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

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

where $(pk,sk)\gets {\mathsf {Gen}}(1^{\lambda })$.

Chosen Plaintext Attack (CPA) Security

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

${\big |}\Pr[A(\sigma ,{\mathsf {Enc}}_{pk}(m_{b}))=b:(m_{0},m_{1},\sigma )\gets A(pk)]-1/2{\big |}\leq \nu (\lambda ),$

where $(pk,sk)\gets {\mathsf {Gen}}(1^{\lambda })$, $b$ is a uniformly random bit, and $\sigma$ represents the state of the adversary after the first phase.

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 {Dec}}_{sk}}(\sigma ,{\mathsf {Enc}}_{pk}(m_{b}))=b:(m_{0},m_{1},\sigma )\gets A^{{\mathsf {Dec}}_{sk}}(pk)]-1/2{\big |}\leq \nu (\lambda ),$

where $(pk,sk)\gets {\mathsf {Gen}}(1^{\lambda })$, $b$ is a uniformly random bit, and $\sigma$ represents the state of the adversary after the first phase. Further, we say an adversary is admissible if it never queries ${\mathsf {Dec}}_{sk}$ on the ciphertext given to $A$ in the second phase of the game.

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

Relationship to other primitives

• TDPs imply the existence of CPA-secure PKEs

Sufficient assumptions

See the sufficient assumptions for TDPs.

Variations

• Symmetric Encryption (SE)
• Identity-Based Encryption (IBE)
• Registration-Based Encryption (IBE)

Other Notes

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