ElGamal Encryption
ElGamal encryption is an asymmetric public-key cryptosystem based on the Diffie–Hellman key exchange and the discrete logarithm problem that provides semantic security and multiplicative homomorphic operations.
ElGamal Encryption is an asymmetric public-key cryptosystem in computation and algorithms based on the algebraic structure of Diffie–Hellman key exchange. Introduced in 1985 by Egyptian cryptographer Taher ElGamal, the scheme demonstrated how the ephemeral key agreement mechanism of Diffie and Hellman could be converted into a full public-key encryption and digital signature system.
Within computational complexity theory, the security of ElGamal encryption is established on the computational intractability of the Computational Diffie–Hellman (CDH) and Decisional Diffie–Hellman (DDH) problems over finite cyclic groups. Because ElGamal encrypts plaintext by incorporating an independent random ephemeral scalar in every encryption operation, it is an intrinsically probabilistic encryption scheme that achieves semantic security against chosen-plaintext attacks while preserving a natural multiplicative homomorphic structure.
Algebraic Framework and Cryptosystem Mechanics
The cryptosystem operates within a finite cyclic group G of prime order q generated by element g, where the group operation is denoted multiplicatively.
1. Key Generation Protocol
- The domain parameters (G, q, g) are established, typically using a Schnorr subgroup of ℤp× or the group of points on an elliptic curve over a finite field.
- The recipient samples a private key x uniformly at random from the integers modulo q:
x ∈ {1, 2, ..., q − 1}
- The recipient computes their public key h by evaluating group exponentiation:
h = gx
The public key is the tuple (G, q, g, h), while the private decryption key is x.
2. Encryption Operation
To transmit a plaintext message encoded as a group element m ∈ G to the recipient:
- The sender samples a secret ephemeral scalar y uniformly at random from ℤq.
- The sender computes the ephemeral public share c1:
c1 = gy
- The sender computes the masked message component c2 using the recipient's public key h:
c2 = m · hy = m · (gx)y
The resulting ciphertext is the pair of group elements c = (c1, c2). Notice that encryption expands the data size by a factor of two, as two group elements are transmitted for each plaintext element.
3. Decryption Operation
Upon receiving the ciphertext (c1, c2), the recipient uses their private key x to recover the original message m:
- The recipient computes the shared secret s by raising c1 to the private exponent x:
s = c1x = (gy)x = gxy
- The recipient evaluates the group inverse of s and multiplies it into c2:
m = c2 · s−1 = (m · gxy) · (gxy)−1 = m
Because computing modular inverses in finite fields or elliptic curve groups is efficient via the extended Euclidean algorithm or Fermat's Little Theorem (s−1 = sq−2), decryption requires only a single group exponentiation and one group multiplication.
Semantic Security and the Decisional Diffie–Hellman Assumption
Unlike deterministic textbook RSA, ElGamal is an inherently randomized cryptosystem. Encrypting the identical plaintext message m multiple times produces completely different ciphertexts (gy, m · hy) because a fresh ephemeral scalar y is generated for each transmission.
Formally, ElGamal encryption achieves Indistinguishability under Chosen-Plaintext Attack (IND-CPA) if and only if the Decisional Diffie–Hellman (DDH) assumption holds in the underlying group G. The DDH assumption asserts that given (g, ga, gb), it is computationally intractable for any polynomial-time algorithm to distinguish the actual Diffie–Hellman value gab from a uniformly random group element gc.
If an adversary cannot distinguish gxy from random noise, the term m · hy acts as an information-theoretically secure one-time pad over the group, guaranteeing that the ciphertext leaks no information about m. However, basic ElGamal is malleable and does not achieve security against adaptive chosen-ciphertext attacks (IND-CCA2), prompting the development of the Cramer–Shoup cryptosystem in 1998, which introduced hash commitments to achieve provable IND-CCA2 security under standard DDH assumptions.
Multiplicative Homomorphic Property and Applications
ElGamal encryption exhibits an intrinsic multiplicative homomorphic property. Consider two ciphertexts (c1, c2) and (c'1, c'2) encrypting plaintexts m1 and m2 under the same public key h:
c1 = gy1, c2 = m1 · hy1 c'1 = gy2, c'2 = m2 · hy2
Evaluating component-wise group multiplication across the ciphertexts yields:
Cmult = (c1 · c'1, c2 · c'2) = (gy1 + y2, (m1 · m2) · hy1 + y2)
The resulting tuple is a valid ElGamal ciphertext encrypting the product m1 · m2 under the randomizer y1 + y2.
Additive Variant: Exponential ElGamal
By encoding a message m as an exponent in the base generator (gm), ElGamal is transformed into an additively homomorphic encryption scheme:
c = (gy, gm · hy)
Multiplying two ciphertexts produces an encryption of the sum m1 + m2:
c1 · c2 = (gy1 + y2, gm1 + m2 · hy1 + y2)
Decryption recovers gm, from which m is derived by solving a discrete logarithm. While solving discrete logarithms is intractable in general, if m is constrained to a small known integer range (such as election vote tallies between 0 and 1,000,000), m is recovered in milliseconds using baby-step giant-step algorithms. This property makes Exponential ElGamal the foundational primitive in verifiable electronic voting systems (such as Helios Voting) and cryptographic mixnets.
Comparison of Homomorphic Encryption Schemes
| Cryptosystem | Underlying Hard Problem | Homomorphic Type | Expansion Ratio | IND-CCA2 Secure Variant |
|---|---|---|---|---|
| ElGamal | Decisional Diffie–Hellman (DDH) | Multiplicative (or Additive in exponent) | 2:1 | Cramer–Shoup |
| RSA | Integer Factorization | Multiplicative | 1:1 | RSA-OAEP (loses homomorphism) |
| Paillier | Composite Degree Residuosity | Additive | 2:1 | Pointcheval–Gemmell |
| BFV / BGV | Ring Learning With Errors (RLWE) | Fully Homomorphic (Addition & Multiplication) | Multi-word vectors | Native leveled FHE |
References
- ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4), 469-472.
- Cramer, R., & Shoup, V. (1998). A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. Advances in Cryptology — CRYPTO '98, 13-25.
- Boneh, D. (1998). The decision Diffie–Hellman problem. Algorithmic Number Theory, 48-63.
- Adida, B. (2008). Helios: Web-based open-audit voting. USENIX Security Symposium, 335-348.