Cryptography Reference
In-Depth Information
Theorem 21.3.8
Fix l
. Let g have prime order r. Let A be a CDH (respectively,
Fixed-CDH) oracle with success probability at least >
log(
r
)
−
l
. Let
(
g,g
a
,g
b
)
be a
CDH instance. Let
1
>
>
1
/r. Then one can obtain an oracle that solves the CDH
(respectively, Fixed-CDH) with probability at least
1
∈ N
−
log(2
r
)
2
/
(
r
2
)
and that makes
−
log(2
/
)
/
at most
2
queries to A (where
log
is the natural logarithm).
log(2
/
)
so that
e
−
c
/
2. First, call the oracle
n
Proof
Define
c
times
on random-self-reduced instances (if the oracle is a CDH oracle then use Lemma
21.3.1
and
if the oracle is a Fixed-CDH oracle then use Exercise
21.3.2
) of the input problem (
g,g
a
,g
b
)
and store the resulting guesses
Z
1
,...,Z
n
for
g
ab
in a list
L
1
. Note that
n
=
∈ R
=
=
c/
O
(log(
r
)
l
+
1
).
=
The probability that
L
1
contains at least one copy of
g
ab
is
)
c/
e
−
c
≥
1
−
(1
−
≥
1
−
=
/
2.
Now choose uniformly at random integers 1
1
−
g
s
1
/
(
g
a
)
s
2
.
≤
s
1
,s
2
<r
and define
X
2
=
g
a
.
Call the oracle another
n
times on random-self-reduced versions of the CDH instance
(
g,X
2
,g
b
) and store the results
Z
1
,...,Z
n
in a list
L
2
.
Hence, with probability
=
and is independent of
X
1
=
One can show that
X
2
is uniformly distributed in
G
g
/
2)
2
there is some
Z
i
∈
L
1
and some
Z
j
∈
≥
(1
−
≥
1
−
L
2
g
ab
and
Z
j
=
g
b
(
s
1
−
as
2
)
. For each 1
such that
Z
i
=
≤
i,j
≤
n
test whether
Z
s
2
i
(
g
b
)
s
1
/Z
j
.
=
(21.2)
If there is a unique solution (
Z
i
,Z
j
) then output
Z
i
, otherwise output
⊥
. Finding
Z
i
can
be done efficiently by sorting
L
1
and then, for each
Z
j
∈
L
2
, checking whether the value
of the right-hand side of equation (
21.2
) lies in
L
1
.
We now analyse the probability that the algorithm fails. The probability there is no
pair (
Z
i
,Z
j
) satisfying equation (
21.2
), or that there are such pairs but none of them has
Z
i
=
g
ab
,isatmost
. Hence, we now assume that a good pair (
Z
i
,Z
j
) exists and we want
to bound the probability that there is a bad pair (i.e., a solution to equation (21.2) for which
Z
i
=
g
ab
). Write
X
1
=
g
a
,
X
2
=
g
a
(where
a
=
g
b
. Suppose (
Z,Z
)
s
1
−
as
2
) and
Y
=
is a pair such that
Z
s
2
Z
=
Y
s
1
.
(21.3)
Y
a
and
Z
=
Y
a
with probability at least 1
We claim that
Z
=
−
1
/q
. Note that if equa-
tion (
21.3
) holds then
Y
a
/Z
.
(
Z/Y
a
)
s
1
=
(21.4)
If precisely one of
Z
=
Y
a
or
Z
=
Y
a
holds then this equation does not hold. Hence,
Z
=
Y
a
and
Z
=
Y
a
, in which case there is precisely one value for
s
1
for which equation (
21.4
)
holds. Considering all
n
2
L
2
it follows there are at most
n
2
values
for
s
1
, which would lead to an incorrect output for the self-corrector. Since
s
1
is chosen
uniformly at random the probability of an incorrect output is at most
n
2
/r
. Since
n
pairs (
Z,Z
)
∈
L
1
×
≤
log(2
r
)
/
one gets the result. Note that log(2
r
)
2
/
(
r
2
)
O
(log(
r
)
2
+
2
l
/r
).
=
