Cryptography Reference
In-Depth Information
Exercise 14.7.1
Write pseudocode, for both the client and server, for the distributed
Gaudry-Schost algorithm.
Exercise 14.7.2
Explain why the algorithm can be modified to omit storing the type of
walk in the database. Show that the methods of Exercise
14.2.16
to reduce storage can also
be used in the Gaudry-Schost algorithm.
g
a
1
g
a
2
Exercise 14.7.3
What modifications are required to solve the problem
h
=
such
2
that 0
≤
a
1
<N
1
and 0
≤
a
2
<N
2
for 0
<N
1
<N
2
?
An important practical consideration is that walks will sometimes go outside the tame
or wild regions. One might think that this issue can be solved by simply taking the values
x
and
y
into account and altering the walk when close to the boundary, but then the crucial
property of the walk function (that once two walks collide, they follow the same path) would
be lost. By taking distinguished points to be quite common (i.e., increasing the storage) and
making
M
relatively small one can minimise the impact of this problem. Hence, we ignore
it in our analysis.
We now briefly explain the heuristic complexity of the algorithm. The key observation is
that a collision can only occur in the region where the two sets overlap. Let
A
W
.If
one samples uniformly at random in
A
, alternately writing elements down on a “tame” and
“wil
d” lis
t, the expected number of samples until the two lists have an element in common
=
T
∩
is
√
π
#
A
O
(1) (see, for example, Selivanov [
483
]or[
206
]).
The following heuristic assumption seems to be reasonable when
N
is sufficiently large,
n
S
>
log(
N
), distinguished points are sufficiently common and specified using a good hash
function (and hence are well-distributed),
θ>
log(
N
)
/N
, walks are sufficiently “local” that
they do not go outside
T
(respectively,
W
) but also not too local, and when the function
walk
is chosen at random.
+
Heuristic 14.7.4
1. Walks reach a distinguished point in significantly fewer than
N
steps (in other words,
there are no cycles in the walks and walks are not excessively longer than 1
/θ
).
2. Walks are uniformly distributed in
T
(respectively,
W
).
Theorem 14.7.5
Let the notation be as above, and assume Heuristic
14.7.4
. Then the
average-ca
se
expected
n
umber of group operations performed by the Gaudry-Schost algo-
rithm is
(
√
π
(2(2
−
√
2))
2
+
o
(1))
N
≈
(2
.
43
+
o
(1))
N.
Proof
We first compute #(
T
∩
W
). When (
a
1
,a
2
)
=
(
N/
2
,N/
2) then
W
=
T
and so
N
2
. In all other cases, the intersection is less. The extreme case is when
#(
T
∩
W
)
=
(
a
1
,a
2
)
=
(0
,
0) (similar cases are (
a
1
,a
2
)
=
(
N
−
1
,N
−
1) etc). Then
W
={
(
x,y
)
∈
2
N
2
/
4. By symmetry it suffices to consider
Z
:
−
N/
2
≤
x,y <N/
2
}
and #(
T
∩
W
)
=
the case 0
≤
a
1
,a
2
<N/
2inwhichcasewehave#(
T
∩
W
)
≈
(
N/
2
+
a
1
)(
N/
2
+
a
2
)
(here we are approximating the number of integer points in a set by its area).
