Cryptography Reference
In-Depth Information
=
i
=
1
l
e
i
Write
r
−
1
where the
l
i
are prime. The PH method involves projecting
a
i
F
r
of order
l
e
i
. In other words, we must compute
and
γ
into the subgroup of
g
a
(
r
−
1)
/l
e
i
h
i
=
i
for 1
n
. Using the Fixed-CDH oracle to perform computations in implicit represen-
tation, Algorithm
4
computes all the
h
i
together in
O
(log(
r
)loglog(
r
)) oracle queries.
4
≤
i
≤
A
further
O
(log(
r
)) oracle queries are required to compute all
g
a
(
r
−
1)
/l
i
where 0
≤
f<e
i
.
γ
(
r
−
1)
/l
e
i
i
in
O
(log(
r
) log log(
r
)) multiplications in
Similarly, one computes all
x
i
=
F
r
.We
then have
g
x
u
(mod
l
e
i
i
.
Following Section
13.2
one reduces these problems to
i
=
1
e
i
instances of the DLP in
groups of prime order
l
i
. This requires
O
(log(
r
)
2
) group operations and field operations
overall (corresponding to the computations in line 6 of Algorithm
12
).
For the baby-step-giant-step algorithm suppose we wish to solve
g
a
h
i
=
g
γ
u
(whe
r
e, for
simplicity, we redefine
a
and
γ
so that they now have order
l
modulo
r
). Set
m
=
=
√
l
and
write
u
=
u
0
+
mu
1
where 0
≤
u
0
,u
1
<m
.From
g
γ
u
g
γ
u
0
+
mu
1
g
γ
u
0
(
γ
m
)
u
1
g
a
=
=
=
(21.6)
one has
(
g
a
)
(
γ
−
m
)
u
1
g
γ
u
0
.
=
(21.7)
We compute and store (in a sorted structure) the baby steps
g
γ
i
for
i
=
0
,
1
,
2
,...,m
−
1
(this involves computing one exponentiation in
G
at each step, as
g
γ
i
+
1
(
g
γ
i
)
γ
, which is
=
at most 2 log
2
(
r
) operations in
G
).
We then compute the giant steps (
g
a
)
γ
−
mj
. This involves computing
w
0
=
γ
−
m
(mod
r
)
γ
−
mj
(mod
r
)as
w
j
+
1
=
and
then
the
sequence
w
j
=
w
i
w
0
(mod
r
);
this
requires
F
r
. We also must compute (
g
a
)
w
j
, each of which requires
O
(log(
m
)
+
m
) multiplications in
≤
2log
2
(
r
) operations in
G
.
When we find a match then we have solv
e
d the DLP in the subgroup of order
l
.
T
heBSGS
algorithm for each prime
l
requires
O
(
√
l
log(
r
)) group operations and
O
(
√
l
+
log(
r
))
operations in
F
r
. There are
O
(log(
r
)) primes
l
for which the BSGS must be run, but a careful
analysis of t
h
e cost (using the result of Exercise
13.2.7
) gives a
n
overall running time of
O
(log(
r
)
2
√
l/
log(
l
)) group operations and
O
(log(
r
)
2
log(
r
)
√
l/
log(
l
)) multiplications
+
in
F
r
. Note that the CDH oracle is not required for the BSGS algorithm.
Once
u
is determined modulo all prime powers
l
e
|
(
r
−
1) one uses the Chinese remain-
γ
u
(mod
r
). These
der theorem to compute
u
∈ Z
/
(
r
−
1)
Z
. Finally, one computes
a
=
final steps require
O
(log(
r
)) operations in
F
r
.
4
Remark
2.15.9
does not lead to a better bound, since the value
n
(which is
m
in the notation of that remark) is not necessarily
large.