El Gamal Encryption

El Gamal Encryption

Lemma

Let be a finite group, and let be arbitrary. Then choosing uniform and setting gives the same distribution for as choosing uniform Put differently, for any we have

where the probability is taken over uniform choice of

The El Gamal Encryption Scheme

By Taher El Gamal in 1985

• Gen: on input run to obtain Then choose a uniform and compute The public key is and the private key is The message space is .
• Enc: on input a public key and a message choose a uniform and output the ciphertext

• Dec: on input a private key and a ciphertext ,output

Security

CPA Secure

If the DDH problem is hard relative to then the El Gamal encryption scheme is CPA -secure.

Proof

Let denote the El Gamal encryption scheme. We prove that has indistinguishable encryptions in the presence of an eavesdropper; this implies it is CPA-secure.

: Choosing uniform and outputting the ciphertext

: Given as input, where and is either or .

• set and run to obtain two messages

• Choose a uniform bit and set and

• Give the ciphertext to and obtain an output bit If output otherwise, output 0

Case 1:

Case 2:

Under the assumption that the DDH problem is hard relative to there is a negligible function negl such that

So