Elgamal encryption

The Elgamal algorithm is an asymmetric key encryption algorithm for public key cryptography which is based on Diffie-Hellman key agreement. It was described by Taher Elgamal in 1984. The Elgamal algorithm is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm is a signature scheme is a variant of the ElGamal signature scheme, which should not be confused with the Elgamal algorithm.

Security

Elgamal is a simple example of a semantically secure asymmetric key encryption algorithm (under reasonable assumptions). It is probabilistic, meaning that a single plaintext can be encrypted to many possible ciphertexts, with the consequence that a general Elgamal encryption produces a 2:1 expansion in size from plaintext to ciphertext.

Related Topics:
Semantically secure - Probabilistic - Plaintext

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

ElGamal's security rests, in part, on the difficulty of solving the discrete logarithm problem in G. Specifically, if the discrete logarithm problem could be solved efficiently, then Elgamal would be broken. However, the security of Elgamal actually relies on the so-called Decisional Diffie-Hellman (DDH) assumption. This assumption is often stronger than the discrete log assumption, but is still believed to be true for many classes of groups.

Related Topics:
Discrete logarithm problem - Decisional Diffie-Hellman (DDH) assumption

~ ~ ~ ~ ~ ~ ~ ~ ~ ~