Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 244

Adversary

Ciphertext
( g r

Plaintext
m

Encryption Decryption

, my r ) ( u , v )

vu − x

Secret key

Public key

y y x

AUTHENTICATED

y = g x

Generator

Figure 9.11. ElGamal Cryptosystem.

g r Problem : compute m such that there exists r such that u = mod p and v =

my r mod p
EGKRP (ElGamal Key Recovery Problem)
Parameters : a prime number p and a generator g of Z p
Input : a public key y
Problem : compute x such that y g x = mod p

We notice that being able to decrypt (i.e. solving EGDP) means being able to compute
v

u − x

v

. This implies being able to compute u x

v/

from u and as m . Obviously, being

able to compute u x from u and g x

is equivalent to the Diffie-Hellman problem as

Z p .

defined on p. 234 DHP with G =

Let us formally prove that given the public parameters p and g , ElGamal decryption
EGDP is equivalent to the Diffie-Hellman DHP problem. First of all, we assume that
we have an oracle which solves the Diffie-Hellman problem: given A g a = mod p and

g b mod p , the oracle computes g ab mod p . We can use this oracle in order to
decrypt ( u

B =

,v ) with the public key y . For this we simply give A = y and B = u to the

oracle. We obtain g xr mod p from the oracle which is u x

mod p , so we can compute

u − x m = v mod p .

Second, we assume that we have a decryptor oracle which given ( u ,v ) and y =

g x u − x mod p . We can use this oracle in order to solve the Diffie-

Hellman problem with A and B : we simply give u

mod p computes v

Z p at

= A , y = B , and take v ∈

A − log B mod p from which we deduce A log B mod p .

random, and we get v

Similarly, we can prove that the ElGamal key recovery EGKRP problem is
equivalent to the discrete logarithm with known order DLP problem as defined
on p. 160 with G Z p .(For G Z p

= = with a prime p , DLP and DLKOP are

equivalent.)