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.
Search WWH ::




Custom Search