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.