Public key encryption

A public key encryption (PKE) scheme allows anyone to encrypt a message to a receiver using a public key, while the holder of the corresponding secret key can decrypt. Its security notions specify what an adversary can learn about the message, allowing leakage of its length.

Syntax

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

$KeyGen (1^{λ}) \to (sk, pk),$ is a randomized algorithm which samples a secret key $sk \in K_{sk}$ and public key $pk \in K_{pk}$ ,
$Enc (pk, m) \to c,$ is a randomized algorithm which takes a public key $pk \in K_{pk}$ and message $m \in M$ , outputting a ciphertext $c \in C$ ,
$Dec (sk, c) \to m,$ is a deterministic algorithm which takes a secret key $sk \in K_{sk}$ and ciphertext $c \in C$ , outputting a message $m \in M$ or $⊥$ to indicate an invalid ciphertext.

Properties

Correctness

A PKE scheme $PKE = (KeyGen, Enc, Dec)$ is $(1 - ε)$ -correct if for all $λ \in N$ and $m \in M$ ,

Pr [Dec (sk, Enc (pk, m)) = m] \geq 1 - ε,

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

CPA Security

The CPA game takes the form of a single challenge: the adversary receives $pk$ , submits two messages, and tries to determine which was encrypted. The adversary can encrypt messages with $pk$ . An admissible adversary submits $m_{0}, m_{1} \in M$ with $∣ m_{0} ∣ = ∣ m_{1} ∣$ ; otherwise ciphertext length may reveal the challenge bit — standard.

\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)$
\Comment{$m_0,m_1 \in \calM$ and $|m_0|=|m_1|$}
\State $c^* \gets \Enc(\pk, m_b)$
\State $b' \gets \calA(c^*, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PKE scheme $PKE$ is CPA-secure if for all admissible efficient $A$ ,

Adv_{PKE, A}^{cpa} (λ) := 2 Pr [G_{PKE, A}^{cpa} (λ) = 1] - 1

is negligible.

Semantic security

Semantic security compares predicting a function of the plaintext with and without its ciphertext — GM84. In the following key-dependent, efficiently samplable formulation, the adversary chooses the message distribution after seeing $pk$ — standard.

For an efficient adversary $A = (A_{1}, A_{2})$ , sample $(sk, pk) \leftarrow KeyGen (1^{λ})$ and $(M, f, st) \leftarrow A_{1} (1^{λ}, pk)$ . Here $M$ describes an efficient sampler supported on equal-length messages in $M$ , $f$ describes an efficiently computable function, and $st$ is auxiliary state. Sample $m \leftarrow M$ using fresh coins, and write $z := (1^{λ}, pk, M, f, st, ∣ m ∣)$ for the information available in both experiments.

A PKE scheme $PKE$ is semantically secure in this formulation if for every such $A$ there is an efficient $S$ such that

∣ Pr [A_{2} (z, Enc (pk, m)) = f (m)] - Pr [S (z) = f (m)] ∣

is negligible, over key generation, $A_{1}$ , the fresh draw from $M$ , encryption, and the coins of $A_{2}$ or $S$ . The simulator receives the sampler’s description, not the coins used to draw $m$ . This formulation is equivalent to IND-CPA security — standard.

CCA Security

In the chosen-ciphertext attack (CCA, or IND-CCA2) game, the adversary additionally has access to a decryption oracle $D$ in two phases: before submitting $(m_{0}, m_{1})$ , and after receiving the challenge $c^{*}$ . An admissible adversary submits equal-length messages in $M$ and, after receiving $c^{*}$ , may not query $D$ on $c^{*}$ 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: $\calD$ unrestricted; $m_0,m_1 \in \calM$, $|m_0|=|m_1|$}
\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 $PKE$ is CCA-secure if for all admissible efficient $A$ ,

Adv_{PKE, A}^{cca} (λ) := 2 Pr [G_{PKE, A}^{cca} (λ) = 1] - 1

is negligible. The admissibility restriction is necessary: without it, $A$ trivially wins by querying $D (c^{*})$ to learn $m_{b}$ .

Variations

Perfectly correct CPA-secure PKE

An IND-CPA-secure scheme that is perfectly correct, $ε = 0$ . Constructions of non-malleable and chosen-ciphertext-secure encryption that check a proof of consistency between ciphertext components need decryption to be errorless under all but a negligible fraction of key pairs, which perfect correctness guarantees; DNR04 immunize schemes with decryption errors to meet this weaker condition — DNR04. With negligible decryption error, a scheme may have rare encryption coins whose ciphertexts decrypt to bits of the secret key; a pair of such ciphertexts carries an honest consistency proof, and decryption queries on such pairs leak the key — standard.

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^{*}$ is revealed. CCA1 is strictly weaker than CCA2 and strictly stronger than CPA, assuming CCA2-secure schemes exist — BDPR98.

Key-hiding

TODO

Other results

Participates in

Builds on Public key encryption

Produces Public key encryption

Barriers

Cryptology City

Explorer