Cryptography Reference
In-Depth Information
W
. To sample
√
π
#
A
elements in
A
it is necessary to sample #
T/
#
A
elements in
T
and
W
. Hence, the number of group elements to be selected overall is
#
T
Let
A
=
T
∩
#
A
√
π
#
A
O
(1)
=
o
(1))
√
π
(#
A
)
−
1
/
2
.
+
(#
T
+
The average-case number of group operations is
o
(1))
√
π
N
2
N/
2
0
N/
2
(
N
2
x
)
−
1
/
2
(
N
y
)
−
1
/
2
dxdy.
+
(
N
−
−
0
Note that
N/
2
√
N
(2
√
2)
.
x
)
−
1
/
2
dx
(
N
−
=
−
0
The average-case expected number of group operations is therefore
√
π
(2(2
√
2))
2
o
(1)
N
−
+
as stated.
The Gaudry-Schost algorithm has a number of parameters that can be adjusted (such
as the type of walks, the sizes of the tame and wild regions etc.). This gives it a lot of
flexibility and makes it suitable for a wide range of variants of the DLP. Indeed, Galbraith
and Ruprai [
210
] have improved the running time to (2
.
36
o
(1))
N
group operations by
using smaller tame and wild sets (also, the wild set is a different shape). One drawback is
that it is hard to fine-tune all these parameters to get an implementation which achieves the
theoretically optimal running time.
+
Exercise 14.7.6
Determine the complexity of the Gaudry-Schost algorithm for the standard
DLP in
G
, when one takes
T
=
W
=
G
.
Exercise 14.7.7
Generalise the Gaudry-Schost algorithm to the
n
-dimensional DLP (see
Definition
13.5.1
). What is the heuristic average-case expected number of group operations?
14.7.2 Discrete logarithm problem in an interval using equivalence classes
Galbraith and Ruprai [
211
] used the Gaudry-Schost algorithm to solve the DLP in an
interval of length
N<r
faster than is possible using the kangaroo method when the group
has an efficiently computable inverse (e.g., elliptic curves or tori). First, shift the discrete
logarithm problem so that it is of the form
h
g
a
with
=
−
N/
2
<a
≤
N/
2. Define the
u
−
1
equivalence relation
u
G
as in Section
14.4
and determine a rule that leads
to a unique representative of each equivalence class. Design a pseudorandom walk on the set
of equivalence classes. The tame set is the set of equivalence classes coming from elements
of the form
g
x
with
≡
for
u
∈
−
N/
2
<x
≤
N/
2. Note that the tame set has 1
+
N/
2 elements and
g
x
,g
−
x
every equivalence class
{
}
arises in two ways, except the singleton class
{
1
}
and the
class
{−
N/
2
,N/
2
}
.
