True or false: "ElGamal encryption guarantees data integrity."
False — ElGamal provides NO integrity protection. An attacker can modify the ciphertext in a meaningful way without being detected, thanks to the homomorphic (multiplicative) property.
Integrity and confidentiality are separate guarantees, and ElGamal only buys the second. Because the ciphertext is just the message times a mask, anyone can multiply it by a factor and the decrypted plaintext shifts by that exact same factor — with nothing in the scheme to signal that the message was touched. Confidentiality without integrity is precisely why ElGamal must be paired with a signature or MAC in practice.
How the attack works:
- ElGamal ciphertext: $(k_E, y) = (g^i, x \cdot K_M \mod p)$
- Eve wants to change $x$ to $s \cdot x$ (multiply by a factor $s$)
- Eve simply sends $(k_E, s \cdot y \mod p)$ to Bob
- Bob decrypts: $s \cdot y \cdot K_M^{-1} = s \cdot x \mod p$ → tampered message!
This is even easier than RSA's homomorphic attack:
- In RSA, Eve needs to compute $s^e \mod N$ (requires the public key exponent)
- In ElGamal, Eve just multiplies $y$ by $s$ directly — no exponentiation needed
Other integrity failures:
- Insertion: Eve can encrypt and send her own messages using Bob's public key
- No authentication: Without signatures or MACs, Bob cannot verify who sent the message
The lesson: ElGamal (like schoolbook RSA) provides confidentiality only, never integrity. Always combine with authentication (digital signatures, MAC, or authenticated encryption).
Go deeper:
Malleability (cryptography) — Wikipedia — the property that breaks ElGamal integrity.- Authenticated encryption — Wikipedia — how to add the integrity ElGamal lacks.
- Homomorphic encryption — Wikipedia — the multiplicative property seen as a feature.