Cryptography Reference
In-Depth Information
to a DHP oracle
O
DHP
. The DHP oracle, in turn, takes as input
g
a
and
g
b
,and
returns as output
g
ab
for all
a, b
∈
G
:
O
DHP
(
g
a
,g
b
)=
g
ab
The adversary can use this oracle to break the ElGamal system—that is,
to decrypt a given ciphertext (
c
1
,c
2
) that is encrypted for user A. Therefore, the
adversary must invoke the DHP oracle with
y
A
=
g
x
A
and
c
1
=
g
k
,andwaitfor
the oracle to respond with
g
x
A
k
(i.e.,
O
DHP
(
g
x
A
,g
k
)=
g
x
A
k
). Then he or she
must compute the inverse element of this result and use
g
−x
A
k
to recover message
m
according to the following formula:
m
=
g
−x
A
k
c
2
Consequently, the adversary can decrypt a given ciphertext if he or she is given
access to a DHP oracle. This means that one can break the ElGamal system if one
can solve the DHP.
For direction (b) we must show that somebody who can break the ElGamal
system can also solve the DHP. We therefore assume an adversary who has an
ElGamal oracle
O
ElGamal
that takes as input
g
a
,
g
b
,and
g
ab
m
, and that returns
as output
m
:
O
ElGamal
(
g
a
,g
b
,g
ab
m
)=
m
The adversary can use this oracle to solve the DHP (i.e., to compute
g
ab
from
g
a
and
g
b
). He or she must therefore invoke the ElGamal oracle with
y
A
=
g
x
A
,
c
1
=
g
k
,and
c
2
=
g
x
A
k
m
, and wait for the oracle to respond with
m
(i.e.,
O
ElGamal
(
y
A
,c
1
,c
2
)=
m
). The adversary now knows
m
and can compute
m
−
1
modulo
p
. Because
c
2
=
g
x
A
k
m
, he or she can finally determine
g
x
A
k
according to
the following formula:
g
x
A
k
=
c
2
m
−
1
Consequently, the adversary can solve the DHP if he or she is given access to
an ElGamal oracle.
