Cryptography Reference
In-Depth Information
g a i
|
+
1) . Given h i =
Theorem 21.5.10 Let g have prime order r and let d
( r
for
2 d the n on e can compute a in O (( ( r
1
i
+
1) /d
+
d )log( r )) g ro up operations,
d ) group elements storage and O (( ( r
d )log( r )) multi-
O ( ( r
+
1) /d
+
+
1) /d
+
plications in
F r .
Proof As in Exercise 21.4.13 , the idea is to work in the algebraic group G 2 ,r , which
has order r
= F r ( θ ) where θ 2
+
1. Write
F r 2
=
t
∈ F r . By Lemma 6.3.10 each element
}⊆F r 2 is of the form α 0 +
α
G 2 ,r −{
1
α 1 θ where
a 2
t
2 a
a 2
α 0 =
t ,
1 =
a 2
+
+
t
for some a
∈ F r . For each d
∈ N
there exist polynomials f d, 0 ( x ) ,f d, 1 ( x )
∈ F r [ x ]ofdegree
2 d such that, for α as above, one has
f d, 0 ( a )
+
θf d, 1 ( a )
α d
=
.
( a 2
+
t ) d
The idea is to encode the DLP instance g a into the element β
G 2 ,r as
a 2
t
2 a
a 2
β
=
t +
θ
t .
a 2
+
+
We do not know β , but we can compute ( a 2
t ) , ( a 2
t ) and 2 a in implicit representation.
Let γ be a generator for G 2 ,r , known explicitly. Then β
+
γ u for some 0
=
u<r
+
1.
It suffices to compute u .
The first step is to project into the s ubgroup o f order ( r
1) /d .Wehave β d
γ du for
+
=
= ( r
some 0
u< ( r
+
1) /d .Let m
+
1) /d
so that u
=
u 0 +
mu 1 for 0
u 0 ,u 1 <
m . Write γ i
θγ i, 1 . Then β d γ u 0
γ du 1
=
γ i, 0 +
=
and so ( f d, 0 ( a )
+
θf d, 1 ( a ))( γ u 0 , 0 +
( a 2
t ) d ( γ du 1 , 0 +
θγ u 0 , 1 )
=
+
θγ du 1 , 1 ). Hence
g f d, 0 ( a ) γ u 0 , 0 g f d, 1 ( a ) γ u 0 , 1
g ( a 2
t ) d γ du 1 , 0
+
=
and similarly for the implicit representation of the coefficient of θ . It follows that one
can perform the baby-step-giant-step algorithm in this setting to compute ( u 0 ,u 1 ) and
hence u (mod ( r
1) /d ). Note that computing g f d, 0 ( a ) ,g f d, 1 ( a )
and g ( a 2
+ t ) d
+
requires 6 d
exponentiations. The stated complexity follows.
For the second stage, we have β
γ u + v ( r + 1) /d where 0
v<d . Giving a baby-step-
giant-step algorithm here is straightforward and we leave the details as an exercise.
=
One derives the following result. Note that it is not usually practical to consider a
computational problem whose input is a O ( r 1 / 3 )-tuple of group elements; hence, this result
is mainly of theoretical interest.
Corollary 21.5.11 Let g have prime order r and suppose r
+
1 has a factor d such that
g a i for 1
r 1 / 3 . Given h i =
2 d then one can compute a in O ( r 1 / 3 log( r )) group
d
i
operations.
Search WWH ::




Custom Search