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.