Cryptography Reference
In-Depth Information
Fixed-CDH oracle queries. The motivation for this approach is to give tight reductions
between CDH and DLP (i.e., to give a lower bound on the running time for an algorithm for
CDH in terms of conjectured lower bounds for the running time of an algorithm for DLP).
Their results were improved by Bentahar [
39
,
40
]. It turns out to be desirable to have an
auxiliary elliptic curve such that #
E
(
F
r
) is a product of three coprime integers of roughly
equal size
r
1
/
3
. The reduction then requires
O
(log(
r
)) oracle queries but
O
(
r
1
/
3
log(
r
)) field
operations. It is natural to conjecture
8
that suitable auxiliary elliptic curves exist for each
prime
r
. One can construct auxiliary curves by choosing random curves, counting points
and factoring; one expects only polynomially many trials, but the factoring computation is
subexponential. We refer to [
402
,
39
,
40
] for further details.
Exercise 21.4.18
Write down the algorithm for the Muzereau-Smart-Vercauteren reduction
using projective coordinates. Prove that the algorithm has the claimed complexity.
Exercise 21.4.19
Show how to generate in heuristic expected polynomial-time primes
r,p
1is
κ
-smooth, and 2
κ
−
1
2
κ
+
3
.
≡
2 (mod 3) such that
r
|
(
p
+
1),
r
+
≤
r<p
≤
Hence, by Exercise
9.10.4
, taking
E
:
y
2
x
3
=
+
1 then
E
(
F
p
) is a group of order divisible
by
r
and
E
(
F
r
) has
κ
-smooth order and is a suitable auxiliary elliptic curve for the Maurer
reduction.
Finally, we remark that the den Boer and Maurer reductions cannot be applied to
relate CDH and DLP in groups of unknown order. For example, let
N
be composite and
g
)
∗
of unknown order
M
. Given a perfect Fixed-CDH oracle with respect to
g
one can still compute with the algebraic group
G
m
(
∈
Z
Z
(
/N
Z
/M
Z
) in implicit representation
(or projective equations for
E
(
Z
/M
Z
)), but if
M
is not known then the order of
G
=
G
m
(
Z
/M
Z
) (respectively,
G
=
E
(
Z
/M
Z
)) is also not known and so one cannot perform
the Pohlig-Hellman algorithm in
G
.
21.5 Algorithms for static Diffie-Hellman
Brown and Gallant [
104
] studied the relationship between Static-DH and DLP. Their main
result is an algorithm to solve an instance of the DLP using a perfect Static-DH oracle.
Cheon [
122
] independently discovered this algorithm in a different context, showing that a
variant of the DLP (namely, the problem of computing
a
given
g,g
a
and
g
a
d
; we call this
Cheon's variant of the DLP
) can be significantly easier than the DLP. We now present the
algorithm of Brown-Gallant and Cheon, and discuss some of its applications.
g
a
and
Theorem 21.5.1
Let g have prime order
r and let
d
|
(
r
−
1)
. Given h
1
=
+
√
d
)log(
r
))
gro
up
operations,
then
one
c
an compute a in O
((
√
(
r
g
a
d
h
d
=
−
1)
/d
+
√
d
)
group elements of storage and O
(
√
(
r
+
√
d
)
multiplica-
O
(
√
(
r
−
1)
/d
−
1)
/d
F
r
.
9
tions in
8
This conjecture seems to be possible to prove using current techniques, but I am not aware of any reference for it.
9
As usual, we are being careless with th
e
O
(
·
)-no
tation
.
What we mean is that there is a constant
c
independent of
r,d,g
and
a
such that the algorithm requires
≤
c
(
√
(
r
−
1)
/d
+
√
d
) log(
r
) group operations.
