Elgamal Encryption

crypto-snippets/elgamal

Elgamal Encryption

#encryption #instantiation

$\gdef\system{\mathsf{Enc}}$ $\gdef\systemprefix{}$ $\gdef\keygen{\mathsf{\systemprefix{}KGen}}$ $\gdef\msgspace{\mathcal{M}}$

$\gdef\enc{\mathsf{\systemprefix{}Enc}}$ $\gdef\dec{\mathsf{\systemprefix{}Dec}}$ $\gdef\msgspace{\mathcal{M}}$ $\gdef\group{\mathbb{G}}$ $\gdef\generator{g}$ $\gdef\modulo{q}$ $\gdef\rgets{\stackrel{\$}{\gets} }$

For a group $\group$ with generator $g$ and modulo $\modulo$, Elgamal encryption scheme for message space $\msgspace{} = \group$ is the tuple $(\keygen, \enc, \dec)$ defined as follows:

$\keygen(1^n) \to (pk, sk)$

$x \rgets \mathbb{Z}_q$
$X = g^x$
return $(pk := X, sk = x)$

$\enc(pk, m) \to c$

$y \rgets \mathbb{Z}_q$
$c_1 := g^y$
$c_2 := X^y \cdot m$
return $c := (c_1, c_2)$

$\dec(sk, c) \to m$

$x := sk$
$(c_1, c_2) := c$
$m := c_2 \cdot c_1^{-x}$
return $m$

References

ElGamal, Taher. "A public key cryptosystem and a signature scheme based on discrete logarithms." IEEE transactions on information theory 31.4 (1985): 469-472.

Last modified June 22, 2025, 11:14 a.m.