# 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.

## Definition

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 $a \gets \mathbb{Z}_p$ for a private key. Let A = ga be the corresponding public key.
• Encryption: To encrypt $m \in G$ with public key A, choose a random $b \gets \mathbb{Z}_p$ and output the pair (gb,mAb).
• Decryption: $\mathsf{Dec}_a(B,C) = C/B^a$.

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:

$\mathsf{Dec}_a(\mathsf{Enc}_A(m)) = \mathsf{Dec}_a( g^b, m (g^a)^b) ) = m (g^a)^b / (g^b)^a = m$

The security parameter of the scheme is $\lceil\log p\rceil$, the number of bits needed to represent elements from the cyclic group G.

## Proofs of Security

### CPA 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.
1. Give A to V as the public key.
2. When V outputs a challenge (m0,m1), we pick a random β and give (B,mβC) as the response.
3. 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 $\mathcal{A}$:

$\Pr_{m,PK}\Big[ \mathcal{A}( PK, \mathsf{Enc}(m) ) = m \Big]$ is negligible in the security parameter.

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 $\mathcal{A}$. 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.
1. Give A to V as the public key.
2. Pick a random $Z \in G$ and give (B,Z) to V as the ciphertext.
3. 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.

## Malleability

The Elgamal encryption scheme is malleable. For instance, $\mathsf{Dec}(B,tC) = t \cdot \mathsf{Dec}(B,C)$ and $\mathsf{Dec}(B^k,C^k) = (\mathsf{Dec}(B,C))^k$. 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.