crypto-snippets/elgamal

Elgamal Encryption


\(\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\)

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