Cryptography Reference
In-Depth Information
probability that a collision leads to a solution of the DLP. Cheon [
122
] suggests using the
Kangaroo method, which is a more natural choice for this application.
Exercise 21.5.5
Design a pseudorandom walk for the Pollard kangaroo method to solve
the DLP in implicit representation arising in the proof of Theorem
21.5.1
.
Brown and Gallant use Theorem
21.5.1
to obtain the following result.
g
a
and supposeAis a
perfect oracle for the static Diffie-Hellman problemwith re
spect to
(
g
,h
)
(i
.e
.,A
(
h
1
)
Theorem 21.5.6
Letg have prime orderr and letd
|
(
r
−
1)
. Leth
=
h
1
).
=
+
√
d
)log(
r
))
group
Then one can comp
ute a usin
g d
or
acle queries, O
((
√
(
r
−
1)
/d
+
√
d
)log(
r
))
multiplications in
operations and O
((
√
(
r
−
1)
/d
F
r
.
g
a
i
until
g
a
d
g
a
and compute the sequence
h
i
+
1
=
Proof
Write
h
1
=
h
=
O
(
h
i
)
=
is
computed. Then apply Theorem
21.5.1
.
Note that the reduction uses a Static-DH oracle with respect to
g
a
to compute
a
.The
reduction does not solve a general instance of the DLP using a specific Static-DH oracle;
hence, it is not a reduction from DLP to Static-DH. Also recall that Exercise
20.4.6
showed
how one can potentially compute
a
efficiently given access to a Static-DH oracle (with
respect to
a
) that does not check that the inputs are group elements of the correct order.
Hence, the Brown-Gallant result is primarily interesting in the case where the Static-DH
oracle does perform these checks.
−
Corollary 21.5.7
Let g have prime order r and suppose r
1
has a factor d such that
d
g
a
and a perfect Static-DH oracle with respect to
(
g,h
)
then one can
compute a in O
(
r
1
/
3
)
oracle queries and O
(
r
1
/
3
log(
r
))
group operations.
≈
r
1
/
3
. Given h
=
Exercise 21.5.8
Prove Corollary
21.5.7
.
Brown and Gallant use Theorem
21.5.6
to give a lower bound on the difficulty of
Static-DH under the assumption that the DLP is hard.
Exercise 21.5.9
L
et
g
have order
r
. Assume that the best algorithm to compute
a
,given
h
g
a
, requires
√
r
group operations. Suppose that
r
c
1
log(
r
)
2
for
some constant
c
1
. Pr
o
ve that the best algorithm to solve Static-DH with respect to (
g,h
)
=
−
1 has a factor
d
=
requires at least
c
2
√
r/
log(
r
)
2
group operations for some constant
c
2
.
All the above results are predicated on the existence of a suitable factor
d
of
r
−
1. Of
course,
r
2
l
where
l
is prime then we have shown that given (
g,g
a
,g
a
2
) one can compute
a
in
O
(
√
r/
2log(
r
))
group operations, which is no better than general methods for the DLP. To increase the
applicability of these ideas, Cheon also gives a method for when there is a suitable factor
d
of
r
−
1 may not have a factor of the correct size; for example, if
r
−
1
=
+
1. The method in this case is not as efficient as the
r
−
1 case, and requires more
auxiliary data.
