Elgamal encryption scheme
The Elgamal encryption scheme (often spelled ElGamal or El Gamal) is a public-key encryption scheme for messages in a cyclic group that achieves IND-CPA security. It is based on the Diffie-Hellman key exchange protocol, and named after its creator, Taher Elgamal.
Let G be a cyclic group of prime order p with generator g. We will write the group operation as multiplication. The Elgamal encryption scheme is defined by the following algorithms:
- Key Generation: Choose a random for a private key. Let A = ga be the corresponding public key.
- Encryption: To encrypt with public key A, choose a random and output the pair (gb,mAb).
- Decryption: .
We assume that the group G and its generator g are publicly known parameters. Alternatively, a description of G and g can be included as part of the public key.
The decryption algorithm is correct because:
The security parameter of the scheme is , the number of bits needed to represent elements from the cyclic group G.
Proofs of Security
We can show that Elgamal encryption is IND-CPA secure as long as the Decisional Diffie-Hellman assumption holds for the underlying cyclic group G. Intuitively, the DDH assumption says that gab is pseudorandom given ga and gb, so masking the message m with gab should be like masking m with a truly random one-time pad.
Proof: Recall the definition of IND-CPA security for public-key encryption. We will use the variant where the adversary only gives one challenge. Consider an adversary V that has advantage ε in the Elgamal IND-CPA experiment. We will show that this quantity is negligible.
We first use V to build an adversary V * for distinguishing the two distributions from the definition of the DDH assumption:
V * : Adversary to distinguish DDH tuples from random tuples:
On input (A = ga,B = gb,C = gc), we must decide whether c = ab or c is randomly distributed.
- Give A to V as the public key.
- When V outputs a challenge (m0,m1), we pick a random β and give (B,mβC) as the response.
- If V guesses β correctly, output 1, otherwise output 0.
When c = ab, the response in step 2 is a correctly distributed ciphertext of mβ, so we perfectly simulate the IND-CPA experiment with V. The probability we output 1 is 1 / 2 + ε.
When c is distributed randomly, the value (B,mβC) is distributed independently of β. Thus the probability we output 1 is exactly 1/2.
This shows that V * can distinguish between the two distributions in the definition of the DDH assumption with probability ε. By our assumption that the DDH assumption holds for the underlying group, ε must be negligible, as desired.
One-wayness of Encryption
Even if the DDH assumption does not hold in its underlying group, it is still possible to prove a weaker level of security for Elgamal if the Computational Diffie-Hellman (CDH) assumption holds. We say that an encryption scheme is one-way if, for any PPT adversary :
Here, the probability is over a random choice of message from the message space, public key (according to KeyGen), and also over the randomness in Enc and . Essentially, the encryption is one-way if it is computationally infeasible to invert the encryption of a random message without the private key.
We can show that Elgamal has this property if the CDH assumption holds in the underlying group.
Proof: Consider an adversary V that can invert random Elgamal encryptions with ε probability. We will show that this quantity is negligible.
We first use V to build an adversary V * for computing the Diffie-Hellman function:
V * : Adversary to compute the Diffie-Hellman function:
On input (A = ga,B = gb), we must output gab.
- Give A to V as the public key.
- Pick a random and give (B,Z) to V as the ciphertext.
- When V outputs m, we output Z / m.
Note that the distribution (A,(B,Z)) does indeed correspond to a random Elgamal public key and encryption of a random message under that key. Thus, with probability ε, V outputs the "correct" plaintext m (that is, m such that Z = mgab). When this is the case, the output of V * matches the Diffie-Hellman function. By our assumption that the CDH assumption holds for the underlying group, ε must be negligible, as desired.
The Elgamal encryption scheme is malleable. For instance, and . Thus, Elgamal encryption does not achieve IND-CCA security. However, the Cramer-Shoup encryption scheme, which is an extension of Elgamal, does achieve IND-CCA security.
- Taher Elgamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO '84, pp10-18.