Public key encryption

A public key encryption (PKE) scheme allows anyone to encrypt a message to a receiver using a public key, while only the holder of the corresponding secret key can decrypt. This enables secure communication over untrusted channels without a pre-shared secret, unlike SKE.

Syntax

A PKE scheme is a tuple of efficient algorithms $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ with respect to secret keyspace ${\mathcal{K}}_{\mathrm{sk}}$, public keyspace ${\mathcal{K}}_{\mathrm{pk}}$, message space $\mathcal{M}$, and ciphertext space $\mathcal{C}$:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{sk},\mathsf{pk}),$ is a randomized algorithm which samples a secret key $\mathsf{sk}\in {\mathcal{K}}_{\mathrm{sk}}$ and public key $\mathsf{pk}\in {\mathcal{K}}_{\mathrm{pk}}$,
• $\mathsf{Enc}(\mathsf{pk},m)\to c,$ is a randomized algorithm which takes a public key $\mathsf{pk}\in {\mathcal{K}}_{\mathrm{pk}}$ and message $m\in \mathcal{M}$, outputting a ciphertext $c\in \mathcal{C}$,
• $\mathsf{Dec}(\mathsf{sk},c)\to m,$ is a deterministic algorithm which takes a secret key $\mathsf{sk}\in {\mathcal{K}}_{\mathrm{sk}}$ and ciphertext $c\in \mathcal{C}$, outputting a message $m\in \mathcal{M}$ or $\perp$ to indicate an invalid ciphertext.

Properties

Correctness

A PKE scheme $\mathsf{PKE}=(\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}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},m))=m\right]\ge 1-\epsilon ,$$

over the choice of $(\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and randomness of $\mathsf{Enc}.$ When $\epsilon =0$, we say $\mathsf{PKE}$ is perfectly correct.

CPA Security

The CPA game therefore takes the form of a single challenge: the adversary receives $\mathsf{pk}$, submits two messages, and tries to determine which was encrypted. Note that the adversary themselves can encrypt messages with $\mathsf{pk}.$

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cpa}}_{\PKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $(m_0, m_1, \stA) \gets \calA(1^\secpar, \pk)$
\State $c^* \gets \Enc(\pk, m_b)$
\State $b' \gets \calA(c^*, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PKE scheme $\mathsf{PKE}$ is CPA-secure if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PKE},\mathcal{A}}^{\mathrm{cpa}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PKE},\mathcal{A}}^{\mathrm{cpa}}(\lambda )=1\right]-1\right|$$

is negligible.

Semantic security

A PKE scheme $\mathsf{PKE}$ is semantically secure if for all efficient $\mathcal{A}$ there is an efficient $\mathcal{S}$ such that for every distribution $\mu$ on $\mathcal{M}$ and every function $f$,

$$\left|\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },\mathsf{pk},\mathsf{Enc}(\mathsf{pk},m))=f(m)\right]-\mathrm{Pr}\left[\mathcal{S}(1^{\lambda },\mathsf{pk},|m|)=f(m)\right]\right|$$

is negligible, over $(\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$, $m\leftarrow \mu$, and the coins of $\mathsf{Enc}$, $\mathcal{A}$ and $\mathcal{S}$ — GM84.

CCA Security

In the chosen-ciphertext attack (CCA, or IND-CCA2) game, the adversary additionally has access to a decryption oracle $\mathcal{D}$ in two phases: before submitting $(m_0,m_1)$, and after receiving the challenge $c^{\ast }$. To avoid a trivial win, $\mathcal{A}$ is admissible: it may not query $\mathcal{D}$ on $c^{\ast }$ itself.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{cca}}_{\PKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\calD(c) := \Dec(\sk, c)$
\State $(m_0, m_1, \stA) \gets \calA^{\calD}(1^\secpar, \pk)$
\Comment{Phase 1: $\calA$ may query $\calD$ freely}
\State $c^* \gets \Enc(\pk, m_b)$
\State $b' \gets \calA^{\calD}(c^*, \stA)$
\Comment{Phase 2: $\calA$ may not query $\calD$ on $c^*$}
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PKE scheme $\mathsf{PKE}$ is CCA-secure if for all admissible efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PKE},\mathcal{A}}^{\mathrm{cca}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PKE},\mathcal{A}}^{\mathrm{cca}}(\lambda )=1\right]-1\right|$$

is negligible. The admissibility restriction is necessary: without it, $\mathcal{A}$ trivially wins by querying $\mathcal{D}(c^{\ast })$ to learn $m_b$.

Variations

CCA1 Security

CCA1 (also called the lunchtime attack) is an intermediate notion between CPA and CCA2. The adversary has access to the decryption oracle only in Phase 1, before seeing the challenge ciphertext; no decryption queries are permitted after $c^{\ast }$ is revealed. CCA1 is strictly weaker than CCA2 and strictly stronger than CPA, assuming CCA2-secure schemes exist — BDPR98.

Key-hiding

TODO

Other results

• PKE ⇒ OWF
• TDP ⇒ PKE
• DDH ⇒ PKE
• LWE ⇒ PKE
• Mid-noise LPN ⇒ PKE
• Noisy k-LIN + PC ⇒ PKE

Participates in

Builds on Public key encryption

• CCA Security ⇒ CCA1 Security (via CCA Security)
• CCA1 Security ⇒ CPA Security (via CCA1 Security)
• IND-CPA ⇔ Semantic security (via CPA Security)
• IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto) (via CPA Security)
• PKE ⇒ COM
• PKE ⇒ OWF
• PKE ⇒ KE
• PKE ⇒ KEM

Produces Public key encryption

• CCA Security ⇒ CCA1 Security (via CCA1 Security)
• CCA1 Security ⇒ CPA Security (via CPA Security)
• IND-CPA ⇔ Semantic security (via Semantic security)
• DCR ⇒ PKE
• DDH ⇒ PKE
• OWF + iO ⇒ PKE
• Higher residuosity ⇒ PKE
• IBE ⇒ PKE
• NIKE ⇒ PKE
• KEM + SKE ⇒ PKE
• Lossy trapdoor functions ⇒ IND-CCA PKE (via CCA Security)
• LWE ⇒ PKE
• Mid-noise LPN ⇒ PKE
• Noisy k-LIN + PC ⇒ PKE
• NTRU ⇒ PKE
• PC + Search noisy $k$-LIN ⇒ PKE
• QR ⇒ PKE
• Ring LWE ⇒ PKE (NTRUEncrypt with Gaussian keys)
• RSA ⇒ IND-CCA PKE (RSA-OAEP) (via CCA Security)
• RSA ⇒ PKE
• Subexponential LPN ⇒ IND-CCA PKE (via CCA Security)
• TDP ⇒ PKE

Barriers

• No relativizing reduction from OWF to PKE
• No fixed-construction reduction from HE to IND-CCA2 Security (via CCA Security)
• No fully-black-box reduction from OT to PKE
• No fixed-construction reduction from CCA1 security to CCA2 security (via CCA1 Security, CCA Security)
• No fixed-construction reduction from CPA security to CCA1 security (via CCA1 Security, CPA Security)
• No fully-black-box reduction from PKE to OT
• No fully-black-box reduction from PKE to TDP