Cryptography Reference
In-Depth Information
Maurer and Wolf [
368
] (also see Section 3.5 of [
369
]) claim this gives a non-uniform
reduction from DLP to CDH, however the validity of this claim depends on the DLP
instance generator.
7
In other words, if one believes that there does not exist a non-uniform polynomial-time
algorithm for DLP in
G
(for certain instance generators) and if one believes the conjecture
that the Hasse interval around
r
contains a polynomially smooth integer then one must
believe there is no polynomial-time algorithm for CDH or Fixed-CDH in
G
. Hence, one
can use the results to justify the assumption that CDH is hard. We stress that this is purely
a statement of existence of algorithms; it is independent of the issue of whether or not it is
feasible to write the algorithms down.
A second interpretation is that CDH might be easy and that this reduction yields the
best algorithm for solving the DLP. If this were the case (or if one wants a uniform
reduction) then, in order to solve a DLP instance, the issue of how to implement the DLP
algorithm becomes important. The problem is that there is no known polynomial-time
algorithm to construct auxiliary elliptic curves
E
(
F
r
) of smooth order. An algorithm to
construct smooth curves (based on the CM method) is given in Section 4 of [
365
] but it has
exponential complexity. Hence, if one can write down an efficient algorithm for CDH then
the above ideas alone do not allow one to write down an efficient algorithm for DLP.
Boneh and Lipton [
78
] handle the issue of auxiliary elliptic curves by giving a
subexponential-time reduction between Fixed-CDH and DLP. They make the natural
assumption (essentially Conjecture
15.3.1
, as used to show that the elliptic curve factoring
method is subexponential-time) that, for sufficiently large
p
rimes, the p
ro
bability that a
randomly chosen integer in the Hasse interval [
r
2
√
r
]is
L
r
(1
/
2
,c
)-
smooth is 1
/L
r
(1
/
2
,c
) for some constants
c,c
>
0 (see Section
15.3
for further discussion
of these issues). By randomly choosing
L
r
(1
/
2
,c
) elliptic curves over
2
√
r,r
+
1
−
+
1
+
F
r
one therefore
expects to find one that has
L
r
(1
/
2
,c
)-smooth order. One can then perform Algorithm
26
to
solve an instance of the DLP in subexponential-time and using polynomially many oracle
queries. We refer to [
78
] for the details.
Maurer and Wolf extend the Boneh-Lipton idea to genus 2 curves and use results of
Lenstra, Pila and Pomerance (Theorem 1.3 of [
342
]) to obtain a reduction with proven
complexity
L
r
(2
/
3
,c
) for some constant
c
(see Section 3.6 of [
369
]). This is the only
reduction from DLP to CDH that does not rely on any conjectures or heuristics. Unfortu-
nately, it is currently impractical to construct suitable genus 2 curves in practice (despite
being theoretically polynomial-time).
Muzereau, Smart and Vercauteren [
402
] go even further than Boneh and Lipton. They
allow an exponential-time reduction, with the aim of minimising the number of CDH or
7
An instance generator for the DLP (see Example
2.1.9
) outputs a quadruple (
G,r,g,h
) where
G
is a description of a group,
g
∈
G
has order
r
,
h
∈
g
and
r
is prime. The size of the instance depends on the representation of
G
and
g
, but is at least
2 log
2
(
r
) bits since one must represent
r
and
h
. If one considers the DLP with respect to an instance generator for which
r
is constant over all instances of a given size
n
, then a single auxiliary curve is needed for all DLP instances of size
n
and so
Corollary
21.4.14
gives a non-uniform reduction. On the other hand, if there are superpolynomially many
r
among the outputs
of size
n
of the instance generator (this would be conjecturally true for the instance generator of Example
2.1.9
) then the amount
of auxiliary data is not polynomially bounded and hence the reduction is not non-uniform.
