Elgamal encryption scheme

From CRYPTUTOR

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.

[edit]

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 = g a$ 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 $(g b, m A b)$ .
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$ .

[edit]

Proofs of Security

[edit]

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 $g a b$ is pseudorandom given $g a$ and $g b$ , so masking the message $m$ with $g a b$ 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 = g a, B = g b, C = g c)$ , we must decide whether $c = a b$ or $c$ is randomly distributed.
Give $A$ to $V$ as the public key.
When $V$ outputs a challenge $(m 0, m 1)$ , we pick a random $β$ and give $(B, m β C)$ as the response.
If $V$ guesses $β$ correctly, output 1, otherwise output 0.

When $c = a b$ , 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.

[edit]

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 = g a, B = g b)$ , we must output $g a b$ .
Give $A$ to $V$ as the public key.
Pick a random $Z \in G$ 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 = m g a b$ ). 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.

[edit]

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.