Cryptography Reference
In-Depth Information
A naive implementation of t
he
method stores all the points
P
i
until a match
is found. This takes around
√
N
storage, which is similar to Baby Step, Giant
Step. However, as R. W. Floyd has pointed out, it is possible to do much better
at the cost of a little more computation. The key idea is that once there is a
match for two indices differing by
d
, all subsequent indices differing by
d
will
yield matches. This is just the periodicity mentioned above. Therefore, we
can compute pairs (
P
i
,P
2
i
)for
i
=1
,
2
,...
, but only keep the current pair;
we don't store the previous pairs. These can be calculated by the rules
P
i
+1
=
f
(
P
i
)
,
P
2(
i
+1)
=
f
(
f
(
P
2
i
))
.
Suppose
i ≥ i
0
and
i
is a multiple of
d
. Then the indices 2
i
and
i
differ by a
multiple of
d
and hence yield a match:
P
i
=
P
2
i
.Since
d ≤ j
0
and
i
0
<j
0
,it
follows easily that there is a match for
i ≤ j
0
. Therefore, the numb
er
of steps
to find a match is expected to be at most a constant multiple of
√
N
.
Another method of finding a match is to store only those points
P
i
that
satisfy a certain property (call them “distinguished points”). For example, we
could require the last
k
bits of the binary representation of the
x
-coordinate to
be 0. We then store, on the average, one out of every 2
k
points
P
i
. Suppose
there is a match
P
i
=
P
j
but
P
i
is not one of these distinguished points.
We expect
P
i
+
to be a distinguished point for some
with 1
2
k
,
approximately. Then
P
j
+
=
P
i
+
, so we find a match between distinguished
points with only a little more computation.
The problem remains of how to choose a suitable function
f
. Besides having
f
act randomly, we need to be able to extract useful information from a match.
Here is one way of doing this. Divide
G
into
s
disjoint subsets
S
1
,S
2
,...,S
s
of approximately the same size. A good choice for
s
seems to be around 20.
Choose 2
s
random integers
a
i
,b
i
mod
N
.Let
≤
≤
M
i
=
a
i
P
+
b
i
Q.
Finally, define
f
(
g
)=
g
+
M
i
if
g
∈
S
i
.
The best way to think of
f
is as giving a random walk in
G
, with the possible
steps being the elements
M
i
.
Finally, choose random integers
a
0
,b
0
and let
P
0
=
a
0
P
+
b
0
Q
be the starting
point for the random walk. While computing the points
P
j
, we also record
how these points are expressed in terms of
P
and
Q
.If
P
j
=
u
j
P
+
v
j
Q
and
P
j
+1
=
P
j
+
M
i
,then
P
j
+1
=(
u
j
+
a
i
)
P
+(
v
j
+
b
i
)
Q
,so(
u
j
+1
,v
j
+1
)=
(
u
j
,v
j
)+(
a
i
,b
i
). When we find a match
P
j
0
=
P
i
0
,thenwehave
u
j
0
P
+
v
j
0
Q
=
u
i
0
P
+
v
i
0
Q,
hence (
u
i
0
− u
j
0
)
P
=(
v
j
0
− v
i
0
)
Q.
If gcd(
v
j
0
− v
i
0
,N
)=
d
,wehave
k ≡
(
v
j
0
− v
i
0
)
−
1
(
u
i
0
− u
j
0
)(mod
N/d
)
.
Search WWH ::
Custom Search