Cryptography Reference
In-Depth Information
types leads to a solution to the discrete logarithm problem. The sets are smaller than the
whole group, but they must overlap (otherwise, there is no chance of a collision). Typically,
one of the sets is called a “tame set” and the other a “wild set”. The pseudorandom walks
are deterministic so that when two walks collide they continue along the same path until
they hit a distinguished point and stop. Data from distinguished points is held in an easily
searched database held by the server. After reaching a distinguished point, the walks re-start
at a freshly chosen point.
14.7.1 Two-dimensional discrete logarithm problem
Suppose we are given
g
1
,g
2
,h
∈
G
and
N
∈ N
(where we assume
N
is even) and asked to
g
a
1
g
a
2
. Note that the size of the solution space
is
N
2
, so we seek a low-storage algorithm with number of group operations proportional
to
N
. The basic Gaudry-Schost algorithm for this problem is as follows.
Define the tame set
find integers 0
≤
a
1
,a
2
<N
such that
h
=
2
={
∈ Z
≤
}
T
(
x,y
)
:0
x,y <N
and the wild set
W
=
(
a
1
−
N/
2
,a
2
−
N/
2)
+
T
2
={
(
a
1
−
N/
2
+
x,a
2
−
N/
2
+
y
)
∈ Z
:0
≤
x,y <N
}
.
In other words,
T
and
W
are
N
×
N
boxes centered on (
N/
2
−
1
,N/
2
−
1) and (
a
1
,a
2
)
N
2
respectively. It follows that #
W
=
#
T
=
and if (
a
1
,a
2
)
=
(
N/
2
−
1
,N/
2
−
1) then
T
W
is a proper non-empty subset of
T
.
Define a pseudorandom walk as follows: first choose
n
S
>
log(
N
) random pairs of
integers
=
W
, otherwise
T
∩
−
M<m
i
,n
i
<M
where
M
is an integer to be chosen later (typically,
M
≈
g
m
1
g
n
i
N/
(1000 log(
N
))) and precompute elements of the form
w
i
=
for 0
≤
i<n
S
. Then
2
choose a selection function
S
:
G
→{
0
,
1
,...,n
S
−
1
}
. The walk is given by the function
n
S
(
g
)
)
.
Tame walks are started at (
g
1
g
2
,x,y
) for random elements (
x,y
)
walk
(
g,x,y
)
=
(
gw
S
(
g
)
,x
+
m
S
(
g
)
,y
+
∈
T
and wild walks are
started at (
hg
x
−
N/
2
+
1
1
g
y
−
N/
2
+
1
2
∈
T
. Walks proceed by iterating the function
walk
until a distinguished element of
G
is
visited, at which time the data (
g,x,y
), together with the type of walk, is stored in a central
database. When a distinguished point is visited, the walk is re-started at a uniformly chosen
group element (this is like the rho method, but different from the behaviour of kangaroos).
Once two walks of different types visit the same distinguished group element we have a
collision of the form
,x
−
N/
2
+
1
,y
−
N/
2
+
1) for random elements (
x,y
)
g
1
g
2
=
hg
x
1
g
y
2
and the two-dimensional DLP is solved.
