Elgamal encryption scheme

From CRYPTUTOR

Jump to: navigation, search

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.

Contents

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.

References

Personal tools