Public key encryption (PKE)

Public key encryption (PKE) is a central cryptographic primitive in theory and in practice. It is centrally important in communicating over untrusted channels where parties cannot share a key in advance, in which case SE is sufficient.

Definition

A public key encryption (PKE) scheme is a tuple of efficient algorithms $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$, with respect to key space $\mathcal{K}={\mathcal{K}}_{\mathrm{priv}}\times {\mathcal{K}}_{\mathrm{pub}}$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$ such that

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

Correctness

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

Chosen Plaintext Attack (CPA) Security

The CPA advantage of an adversary $\mathcal{A}$ that outputs messages $m_0$ and $m_1$ is defined as ${\text{Adv}}_{\mathcal{A}}^{\text{cpa}}(\lambda )\le 2\left|\mathrm{Pr}[\mathcal{A}(1^{\lambda },pk,c)=b]-\frac{1}{2}\right|,$ where $(sk,pk)\leftarrow \mathsf{Gen}(1^{\lambda })$, $b\leftarrow \{0,1\}$, and $c\leftarrow {\mathsf{Enc}}_{pk}(m_b)$.

An PKE 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 )$.

Chosen Plaintext Attack (CCA) Security

The CCA advantage of an adversary $\mathcal{A}$ that outputs messages $m_0$ and $m_1$ is defined as ${\text{Adv}}_{\mathcal{A}}^{\text{cca}}(\lambda )\le 2\left|\mathrm{Pr}[{\mathcal{A}}^{{\mathsf{Dec}}_{sk}(\cdot )}(1^{\lambda },pk,c)=b]-\frac{1}{2}\right|,$ where $(sk,pk)\leftarrow \mathsf{Gen}(1^{\lambda })$, $b\leftarrow \{0,1\}$, $c\leftarrow {\mathsf{Enc}}_{pk}(m_b)$, and ${\mathsf{Dec}}_{sk}(\cdot )$ is a decryption oracle.

An PKE scheme is CCA-secure if for all admissible $\mathcal{A}$, there exists a negligible function $\nu$, such that: ${\text{Adv}}_{\mathcal{A}}^{\text{cpa}}(\lambda )\le \nu (\lambda )$. An adversary is admissible if it is efficient and never queries $\mathsf{Dec}$ on the input $c$, i.e., it never decrypts the given ciphertext with 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{Dec}}_{sk}(c)$ to see if it is $m_0$ or $m_1$.

Variations

• Key-hiding
• CCA1

Other results

• PKE implies OWF
• TDF implies PKE

Candidate Public-key Encryption

• PKE can be built assuming DDH is hard — DH76
• PKE can be built assuming mid-noise LPN