Cryptography Reference
In-Depth Information
Proof
First, the case
a
0(mod
r
). The idea is
essentially the same as the den Boer reduction. Let
γ
be a primitive root modulo
r
.
Then
a
≡
0(mod
r
) is easy, so we assume
a
≡
γ
u
(mod
r
)forsome0
1 and it suffices to compute
u
. The den Boer
reduction works by projecting the unknown
a
into prime order subgroups of
=
≤
u<r
−
F
r
using a
Diffie-Hellman oracle. In our setting, we already have an implicit representation of the
projection
a
d
into the subgroup of
F
r
of order (
r
−
1)
/d
.
g
a
d
g
γ
du
Thefirst
stepistosolve
h
d
=
=
for some 0
≤
u
≤
(
r
−
1)
/d
.Let
m
=
√
(
r
u
0
,u
1
<m
. This is exactly the setting
of equations (
21.6
) and (
21.7
) and hence one can compute (
u
0
,u
1
) using a baby-step-
giant-step algorithm. This requires
−
1)
/d
and write
u
=
u
0
+
mu
1
with 0
≤
≤
F
r
and
≤
m
multiplic
ations in
2
m
exponentiations
in th
e group.
Thus the total complexity is
O
(
√
(
r
−
1)
/d
log(
r
)) group operations and
O
(
√
(
r
1)
/d
) field operations.
We now have
a
d
−
γ
u
+
v
(
r
−
1)
/d
for some 0
=
γ
du
and so
a
=
≤
v<d
. It remains to
compute
v
.Let
h
γ
−
u
1
g
aγ
−
u
g
γ
v
(
r
−
1)
/d
.
h
=
=
=
=
√
d
Set
m
v
0
,v
1
<m
. Using the same ideas as
above (since
γ
is known explicitly the powers are com
p
uted efficiently) one can compute
(
v
0
,v
1
) using a baby-step-giant-step algorithm in
O
(
√
d
log(
r
)) group operations. Finally,
we compute
a
and write
v
=
v
0
+
mv
1
where 0
≤
γ
u
+
v
(
r
−
1)
/d
(mod
r
).
=
Kozaki, K
utsuma an
d Ma
ts
uo [
318
] show how to reduce the complexity in the above
result to
O
(
√
(
r
+
√
d
) group operations by using precomputation to speed up the
exponentiations to constant time. Note that this trick requires exponential storage and is not
applicable when low-storage discrete logarithm algorithms are used (as in Exercise
21.5.5
).
The first observation is that if
r
−
1)
/d
1 has a suitable factorisation then Cheon's variant of
the DLP can be much easier than the DLP.
−
Corollary 21.5.2
Let g have prime order r and suppose r
−
1
has a factor d such that
g
a
d
then one can compute a in O
(
r
1
/
4
log(
r
))
group
r
1
/
2
. Given h
1
=
g
a
and h
d
=
d
≈
operations.
=
i
=
1
d
i
where the d
i
Corollary 21.5.3
Let g have prime order r and suppose r
−
1
g
a
d
i
g
a
and h
d
i
=
are coprim
e.
Given h
1
=
for
1
≤
i
≤
n then one can compute a in
O
((
i
=
1
√
d
i
) log(
r
))
group operations.
Exercise 21.5.4
Prove Corollaries
21.5.2
and
21.5.3
.
As noted in [
104
] and [
122
], one can replace the baby-step-giant-step algorithms by
Pollard methods. Brown and Gallant
10
suggest a variant of the Pollard rho method, but
with several non-standard features: one needs to find the precise location of the collision
(i.e., steps
x
i
=
x
j
in the walk such that
x
i
+
1
=
x
j
+
1
) and there is only a (heuristic) 0.5
10
See Appendix B.2 of the first version of [
104
]. This does not appear in the June 2005 version.
