ElGamal cryptosystem

The ElGamal cryptosystem was first proposed by Taher ElGamal in 1984 [DBLP:conf/crypto/Gamal84]. It is defined over a (sub)group \(\mathbb{G}\) in which the DDH assumption is assumed to hold.

• Setup:
• KeyGen\((\lambda) \mapsto \langle \mathit{pk}, \mathit{sk} \rangle\):
• Encrypt\((m, \mathit{pk}) \mapsto c\):
• Decrypt\((c, \mathit{pk}) \mapsto m\):

Symbol definitions

• \(q\) - the order \(|\mathbb{G}|\) of the (sub)group
• \(\lambda\) - security parameter
• \(\mathit{pk} \in \mathbb{G}\) - public key
• \(\mathit{sk} \in \mathbb{Z}_q\) - secret key
• \(m \in \mathbb{G}\) - plaintext
• \(c \in \mathbb{G}\) - ciphertext