§15 Public Key Encryption, CCA Security, and El Gamal Encryption

Public-Key Encryption

• A public-key encryption scheme is a triple of probabilistic polynomial-time algorithms $(Gen, Enc, Dec)$ such that:
  • $Gen$ is the key generation algorithm that takes as input the security parameter $1^n$ and outputs the public-private key pair $(pk, sk)$. We assume that $pk$ and $sk$ each have length $\ge n$, and that $n$ can be determined from $pk, sk$.
  • $Enc$ is the encryption algorithm that takes as input a public key $pk$ and a message $m \in \mathscr{M}$. It outputs a ciphertext $c$, we write this as $c \leftarrow Enc_{pk}(m)$.
  • $Dec$ is the decryption algorithm that takes as input a private key $sk$ and a ciphertext $c$, and outputs a message $m$ or $\perp$. We write this as $m := Dec_{sk}(c)$.

Eavesdropping Indistinguishability Experiment $\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)$

• Given a public-key encryption scheme $\Pi = (Gen, Enc, Dec)$ and an adversary $\mathscr{A}$, we define the eavesdropping indistinguishability experiment $\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)$ as follows:
  1. $Gen(1^n)$ is run to obtain keys $(pk, sk)$.
  2. Adversary $\mathscr A$ is given $pk$, and outputs a pair of equal-length messages $m_0, m_1$ belonging to the message space $\mathscr{M}$.
  3. A uniform bit $b \in \{0,1\}$ is chosen, and a ciphertext $c \leftarrow Enc_{pk}(m_b)$ is computed and given to $\mathscr{A}$. We call $c$ the challenge ciphertext.
  4. $\mathscr{A}$ outputs a bit $b'$. The output of the experiment is $1$ if $b' = b$, and $0$ otherwise. If $b' = b$, we say that $\mathscr{A}$ succeeds.

Computational (EAV) Security in the Public Key setting

• Definition. A public-key encryption scheme $\Pi = (Gen, Enc, Dec)$ has indistinguishable encryptions in the presence of an eavesdropper if for all probabilistic polynomial-time adversaries $\mathscr{A}$, there is a negligible function $\epsilon$ such that

  $$\Pr\left[\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{eav}}(n)=1\right] \le \frac{1}{2}+\epsilon(n)$$

CPA Security in the Public Key setting

• Proposition. If a public-key encryption scheme has indistinguishable encryptions in the presence of an eavesdropper, then it is CPA-secure.

Insecurity of Deterministic Public-Key Encryption

• Theorem: No deterministic public-key encryption scheme is CPA-secure.

Impossibility of Perfectly Secret Public-Key Encryption

• Prop. There is no perfectly secret public-key encryption. Unbounded attackers can always figure out $m$ given $c, pk$.

Multiple message security

• Theorem. If a public-key encryption scheme $\Pi$ is CPA-secure, then it also has indistinguishable multiple encryptions.

CCA Security

CCA Indistinguishability Experiment $\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{cca}}(n)$

• Given a public-key encryption scheme $\Pi = (Gen, Enc, Dec)$ and an adversary $\mathscr{A}$, we define the CCA indistinguishability experiment $\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{cca}}(n)$ as follows:

  1. $Gen(1^n)$ is run to obtain keys $(pk, sk)$.

  2. Adversary $\mathscr{A}$ is given $pk$, and access to a decryption oracle $Dec_{sk}( \cdot )$.

     It outputs a pair of messages $m_0, m_1$ of the same length, belonging to the message space $\mathscr{M}$.

  3. A uniform bit $b \in \{0,1\}$ is chosen, and then a ciphertext $c \leftarrow Enc_{pk}(m_b)$ is computed and given to $\mathscr{A}$. We call $c$ the challenge ciphertext.

  4. $\mathscr{A}$ continues to interact with the decryption oracle, but may not request a decryption of $c$ itself. Finally, $\mathscr{A}$ outputs a bit $b'$.

  5. $\mathscr{A}$ succeeds and the output of the experiment is $1$ if $b' = b$, and $0$ otherwise.

CCA Security in the Public Key setting

• Definition. A public-key encryption scheme $\Pi = (Gen, Enc, Dec)$ has indistinguishable encryptions under a chosen-ciphertext attack, or is CCA-secure, if for all probabilistic polynomial-time adversaries $\mathscr{A}$, there exists a negligible function $\epsilon$ such that

  $$\Pr\left[\operatorname{PubK}_{\mathscr{A}, \Pi}^{\mathrm{cca}}(n)\right] \le \frac{1}{2}+\epsilon(n)$$

El Gamal Encryption

Lemma underlying El Gamal encryption

• Lemma. Let $\mathbb{G}$ be a finite group, and let $m \in \mathbb{G}$ be arbitrary. Then, choosing uniform $k \in \mathbb{G}$, and setting $c := k \cdot m$ gives the same distribution for $c$ as choosing uniform $c \in \mathbb{G}$. That is, for any $\hat{g} \in \mathbb{G}$, we have $\displaystyle \Pr [k ⋅ m = \hat{g}] = \frac{1}{ |\mathbb{G}|}$ where the probability is over uniform choice of $k \in \mathbb{G}$.

El Gamal Encryption Scheme

1. $Gen(1^n)$: On input $1^n$, run $\mathscr{G}(1^n)$ to obtain $(\mathbb{G}, q, g)$. Choose uniform $x \in \mathbb{Z}_q$, compute $h := g^x$

   The public key is $\langle \mathbb{G}, q, g, h \rangle$, and the secret private key is $\langle \mathbb{G}, q, g, x \rangle$.

   The message space is $\mathbb{G}$.

2. $Enc_{pk}(m)$: Given as inputs the public key $pk = \langle \mathbb{G}, q, g, h \rangle$, and message $m \in \mathbb{G}$, choose uniform $y \in \mathbb{Z}_q$.

   Output the ciphertext $\langle c_1, c_2 \rangle = \langle g^y, h^y \cdot m\rangle$.

3. $Dec_{sk}(c_1, c_2)$: Given as inputs the private key $sk = \langle \mathbb{G}, q, g, x \rangle$, and ciphertext $\langle c_1, c_2 \rangle$.

   Output $\displaystyle \hat{m}:=\frac{c_2}{c^x_1}$.

Security of El Gamal encryption scheme

• Theorem. If the DDH problem is hard relative to $\mathscr{G}$, then the El Gamal encryption scheme is CPA-secure.

— Mar 28, 2023

§15 Public Key Encryption, CCA Security, and El Gamal Encryption by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.