Cryptography Reference
In-Depth Information
Corollary 21.4.7
LetA
(
κ
)
be an algorithm that outputs triples
(
g,h,r
)
such thatr is aκ-bit
prime, g has order r, r
1
is O
(log(
r
)
2
)
-smooth and h
−
∈
g
. Then DLP
≤
R
Fixed-CDH
for the problem instances output by A.
O
(log(
r
)
2
) into Theo-
rem
21.4.6
gives a reduction with
O
(log(
r
) log log(
r
)) oracle queries and
O
(log(
r
)
3
) group
and field operations.
=
Proof
Suppose one has a perfect Fixed-CDH oracle. Putting
l
The same results trivially hold if one has a perfect CDH oracle.
Exercise 21.4.8
Determine the complexity in Theorem
21.4.6
if one has a Fixed-CDH
oracle that only succeeds with probability
.
Cherepnev [
126
] iterates the den Boer reduction to show that if one has an efficient CDH
algorithm for arbitrary groups then one can solve DLP in a given group in subexponential
time. This result is of a very different flavour to the other reductions in this chapter (which
all use an oracle for a group
G
to solve a computational problem in the same group
G
)so
we do not discuss it further.
21.4.3 The Maurer reduction
The den Boer reduction can be seen as solving the DLP in the algebraic group
G
m
(
F
r
),
performing all computations using implicit representation. Maurer's idea was to replace
G
m
(
F
r
) by any algebraic group
G
(
F
r
), in particular the group of points on an elliptic curve
E
(
F
r
). As with Lenstra's elliptic curve factoring method, even when
r
−
1 is not smooth,
there might be an elliptic curve
E
such that
E
(
F
r
) is smooth.
When one uses a general algebraic group
G
there are two significant issues that did not
arise in the den Boer reduction.
The computation of the group operation in
G
may require inversions. This is true for
elliptic curve arithmetic using affine coordinates.
g
a
one must be able to compute an element
P
Given
h
F
r
), in implicit represen-
tation, such that once
P
has been determined in explicit representation one can compute
a
. For an elliptic curve
E
one could hope that
P
=
∈
G
(
=
(
a,b
)
∈
E
(
F
r
)forsome
b
∈ F
r
.
Before giving the main result we address the second of these issues. In other words, we
show how to embed a DLP instance into an elliptic curve point.
g
a
. Let E
:
y
2
x
3
Lemma 21.4.9
Let g have prime order r and let h
=
=
+
Ax
+
B be
an affine elliptic curve over
F
r
. Given a perfect Fixed-CDH oracle there is an algorithm
that outputs an implicit representation
(
g
X
,g
Y
)
of a point
(
X,Y
)
F
r
)
and some extra
data, and makes an expectedO
(log(
r
))
oracle queries and is expected to performO
(log(
r
))
group operations in
∈
E
(
g
. Furthermore, given the explicit value of X and the extra data, one
can compute a.
