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.

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.

Key-hiding

TODO

Other results

• PKE implies OWF
• TDP implies PKE
• PKE can be built assuming DDH is hard — DH76
• PKE can be built assuming Mid-noise LPN