Cryptography Reference
In-Depth Information
g
i
=
j<i
then we respond with the same value as used earlier. If not then
the simulator chooses uniformly at random an element
H
i
∈{
g
j
for some 1
≤
l
,stores(
g
i
,H
i
)inthe
list, and answers the query
H
(
g
i
) with
H
i
. This is a perfect simulation of a random oracle,
at least until the challenge ciphertext is issued below.
At some time
A
outputs a pair of messages
m
0
and
m
1
. The simulator sets
c
1
=
0
,
1
}
g
b
,
l
and responds with the challenge ciphertext
(
c
1
,
c
2
). The adversary
A
may make further hash function queries (which are answered
using the algorithm above) and eventually
A
outputs
b
chooses
c
2
uniformly at random in
{
0
,
1
}
(of course,
A
may crash,
or run for longer than its specified running time, in which case
S
treats this as the
output 0).
The logic of the proof is as follows: if
A
never queries the random oracle
H
on
g
ab
then
A
has no information on
H
(
g
ab
) and so cannot determine whether the answer should be 0
or 1. Hence, for
A
to succeed then one of the queries on
H
must have been on
g
ab
. Once
this query is made then the simulator is seen to be fake, as the adversary can check that
c
2
is not equal to
m
b
⊕
∈{
0
,
1
}
H
(
g
ab
)for
b
. However, the simulator is not concerned with
this issue since it knows that
g
ab
occurs somewhere in the list of hash queries.
The simulator therefore chooses a random index
i
and responds with
g
i
as its solution
to the CDH instance.
∈{
0
,
1
}
Exercise 20.4.12
Fill the gaps in the proof of Theorem
20.4.11
and determine the exact
probability of success in terms of the success of the adversary and the number of queries
to the random oracle.
The power of the random oracle model is clear: we have been able to “look inside” the
adversary's computation.
Exercise 20.4.13
Prove the converse to Theorem
20.4.11
.
Indeed, the same technique leads to a much stronger result.
Theorem 20.4.14
In the random oracle model, semi-textbook Elgamal encryption has
OWE-CPA security if CDH is hard.
Exercise 20.4.15
Prove Theorem
20.4.14
.
20.5 Security of Diffie-Hellman key exchange
A discussion of security models for key exchange is beyond the scope of this topic. We refer
to Bellare and Rogway [
36
], Bellare, Pointcheval and Rogaway [
34
], Bellare, Canetti and
Krawczyk [
30
], Canetti and Krawczyk [
109
], Shoup [
495
], Boyd and Mathuria [
89
] and
Menezes, van Oorschot and Vanstone [
376
] for details. However, as a rough approximation
we can consider three types of adversary:
