Cryptography Reference
In-Depth Information
The reduction is conceptually the same as the den Boer reduction. One difference is
that elliptic curve arithmetic requires inversions (which are performed using the method of
Lemma
21.1.13
and Lemma
21.1.14
) and hence the number of Fixed-CDH oracle queries
must increase. A sketch of the reduction in the case of exhaustive search is given in
Algorithm
26
.
ThefirststepistouseLemma
21.4.9
to associate with
h
the implicit representations of a
point
Q
F
r
). This requires an expected
O
(log(
r
)) oracle queries and
O
(log(
r
)) group
operations for all four variants. Then
Q
∈
E
(
∈
P
where
P
is the generator of the cyclic group
E
(
F
r
).
The idea is again to use Pohlig-Hellman (PH) and baby-step-giant-step (BSGS) to solve
the discrete logarithm of
Q
with respect to
P
in
E
(
F
r
). If we can compute an integer
u
such that
Q
[
u
]
P
(with computations done in implicit representation) then computing
[
u
]
P
and using Lemma
21.4.9
gives the value
a
explicitly.
First, we consider the PH algorithm. As with the den Boer reduction, one needs to com-
pute explicit representations (i.e., standard affine coordinates) for [
N/l
e
i
]
P
and implicit
representations for [
N/l
e
i
]
Q
. It is possible that [
N/l
e
i
]
Q
=
=
O
E
so this case must be han-
dled. As in Section
2.15.1
, computing these points requires
O
(log(
r
) log log(
r
)) elliptic
curve operations. Hence, for the multiples of
P
we need
O
(log(
r
)loglog(
r
)) operations
in
F
r
, while for the multiples of
Q
we need
O
(log(
r
)
2
log log(
r
)) Fixed-CDH oracle
queries and
O
(log(
r
) log log(
r
)) group operations. (If a CDH oracle is available then this
stage only requires
O
(log(
r
)loglog(
r
)) oracle queries.) Computing the points [
N/l
i
]
P
for 1
f<e
i
and all
i
requires at most a further 2
i
=
1
e
i
log
2
(
l
i
)
=
O
(log(
r
)) group operations. Similarly, computing the implicit representations of the
remaining [
N/l
i
]
Q
requires
O
(log(
r
)
2
) Fixed-CDH oracle queries and
O
(log(
r
)) group
operations.
The computation of
u
i
P
0
in line 8 of Algorithm
26
requires
O
(log(
r
)) operations in
≤
=
2log
2
(
N
)
F
r
followed by
O
(1) operations in
G
and oracle queries.
The exhaustive search algorithm for the solution to the DLP in a subgroup of prime order
l
i
is given in lines 9 to 16 of Algorithm
26
. The point
P
0
in line 8 has already been computed,
and computing
Q
0
requries only one elliptic curve addition (i.e.,
O
(log(
r
)) Fixed-CDH
oracle queries). The while loop in line 12 runs for
≤
B
iterations, each iteration involves a
+
constant number of field operations to compute
T
P
0
followed by two exponentiations
in the group to compute
g
x
T
and
g
y
T
(an obvious improvement is to use
g
x
T
only). The
complexity of lines 9 to 16 is therefore
O
(
B
log(
r
)) group operations and
O
(
B
) field
operations.
If one uses BSGS the results are similar. Suppose
Q
and
P
are points of order
l
,
where
P
is known
e
xplicitly, while we only have an implicit representation (
g
x
Q
,g
y
Q
)
for
Q
.Let
m
=
√
l
and
P
1
=
[
m
]
P
so that
Q
=
[
u
0
]
P
+
[
u
1
]
P
1
for 0
≤
u
0
,
u
1
<m
.
One computes a list
o
f baby steps [
u
0
]
P
in implicit representation using
O
(
√
B
) field
operations and
O
(
√
B
log(
r
)) group operations as above. For the giant steps
Q
[
u
1
]
P
1
one is required to perform elliptic curve arithmetic with the implicit point
Q
and the
explicit point [
u
1
]
P
1
, which requires an inversion of an implicit element. Hence, the giant
−
