ElGamal encryption

tl;dr: ElGamal public key encrypting $\approx$ Using an ephemeral Diffie-Hellman exchanged key as a one-time pad.

Preliminaries

• We assume a group $\Gr$ where Decisional Diffie-Hellman (DDH) is hard
• We use additive group notation for $\Gr$

ElGamal

$\mathsf{E}.\mathsf{KGen}(1^\lambda) \rightarrow (\dk, \ek)$

• $\dk \randget \F$
• $\ek \gets \dk \cdot H$

Can this be $G$, or must it be a different $H$?

$\mathsf{E}.\mathsf{Enc}(\ek, m; r) \rightarrow (C, D)$

• $C \gets m \cdot G + r\cdot \ek$
• $D \gets r \cdot H$

$\mathsf{E}.\mathsf{Dec}(\dk, (C,D)) \rightarrow m\cdot G$

• return $C - \dk \cdot D$

Twisted ElGamal

References

For cited works, see below 👇👇