Elgamal Encryption

Let \(\mathbb{G}\) be a cyclic group with \(g\in \mathbb{G}\) be a generator.

$sk \leftarrow \mathbb{G}$
$pk \leftarrow g^{sk}$

Let \(m \in \mathbb{G}\) be a message.

$r \leftarrow \mathbb{G}$
$c_{1} \leftarrow g^{r}$
$c_{2} \leftarrow m\cdot pk^{r}$
$c := (c_{1}, c_{2})$

Parse $c := (c_{1}, c_{2})$
$dec \leftarrow c_{2} / (c_{1}^{sk})$

• Discrete Log + CDH implies Encryption is One-way.
• Discrete Log + DDH implies CPA Security.

It is not CCA secure as the encryption scheme is malleable. If \(c := (c_{1}, c_{2})\) is the encryption of \(m\), then \(c' := (c_{1}, 2c_{2})\) is the encryption of \(2m\).