ElGamal encryption

ElGamal encryption is a probabilistic public-key scheme whose security is related to the difficulty of discrete logarithms and the Decisional Diffie–Hellman problem.¹ Taher ElGamal introduced it in a 1985 paper that also described a related signature scheme; the encryption construction should not be confused with ElGamal signatures, which have different algorithms and security considerations.

In its original form, a user chooses a cyclic group with a generator g, a private exponent x, and publishes h = g^x. A message is represented as a group element m. The sender chooses fresh random k and transmits the pair (g^k, m·h^k), while the recipient recovers m using the private exponent.²

The scheme works because the recipient can reconstruct the shared group element without learning the sender’s random exponent: raising the first ciphertext component to x yields g^xk, which can be removed from the second component.¹ Correctness therefore depends on the chosen group, message encoding, and arithmetic being implemented consistently.

Fresh randomness is essential. Reusing k links ciphertexts and can expose relationships between their plaintexts; weak or predictable randomness can be catastrophic. In common formalizations, ElGamal provides semantic security under an appropriate Decisional Diffie–Hellman assumption in suitable groups, but its basic version is malleable: multiplying a ciphertext by an encryption of a chosen factor produces a ciphertext related to the original plaintext.² Consequently, unauthenticated ElGamal is generally described as IND-CPA secure rather than secure against adaptive chosen-ciphertext attacks.

Modern deployments normally wrap ElGamal in a larger hybrid-encryption design rather than encrypting arbitrary files directly. Public-key operations establish or protect a session key, and a symmetric authenticated-encryption scheme then handles the bulk data; standardized cryptographic guidance treats key establishment, authentication, and key management as separate engineering requirements.⁴

ElGamal ciphertexts are relatively large because each encryption contains two group elements, and the plaintext must usually be encoded as a valid element of the selected group. Implementations must validate public parameters and ciphertext components, avoid small-subgroup and invalid-element problems, and use a cryptographically secure random source. OpenPGP historically specified an ElGamal encryption option, but contemporary protocol profiles distinguish legacy public-key algorithms from newer preferred constructions and require careful algorithm negotiation.³ These operational concerns explain why textbook ElGamal is mainly a foundational construction, a compatibility mechanism, or a component of specialized protocols rather than a default general-purpose cipher.

ElGamal has a useful multiplicative homomorphic property: multiplying two ciphertexts yields a ciphertext of the product of the corresponding plaintext group elements.² This feature can support specialized applications such as verifiable or privacy-preserving computation, but it also creates the malleability that makes unauthenticated ciphertexts dangerous.

The construction is not tied exclusively to one finite-field group. Related variants use elliptic-curve groups, where the underlying operation is written additively and the security assumption is expressed through elliptic-curve discrete-logarithm problems; these variants are often called elliptic-curve ElGamal. Parameter selection is therefore part of the security definition, not a cosmetic implementation choice. A further subtlety is that the encryption scheme and the signature scheme share historical origins but do not share a single security theorem: a safe deployment must analyze the exact variant, encoding, randomness generation, and protocol context.

Discrete logarithm problem

The problem of recovering an exponent x from g and g^x in a specified group.

Decisional Diffie–Hellman

The problem of distinguishing a genuine Diffie–Hellman shared value from a random group element.

Malleability

The ability to transform a ciphertext into another ciphertext whose plaintext has a predictable relation to the original.

IND-CPA

A security notion requiring that encryptions hide which of two chosen plaintexts was encrypted when the adversary may obtain encryptions of chosen messages.

Hybrid encryption

A design that uses public-key cryptography for a key or small secret and symmetric cryptography for the main data.