Cryptography Reference
In-Depth Information
and Lenstra [
86
], large values for
n
S
can lead to slower algorithms (e.g., due to the fact
that the precomputed steps do not all fit in cache memory). Hence, as Exercise
14.4.9
shows, useless cycles will be regularly encountered in the algorithm. There are several
possible ways to deal with this issue. One approach is to use a “look-ahead” technique
to avoid falling in 2-cycles. Another approach is to detect small cycles (e.g., by storing a
fixed number of previous values of the walk or, at regular intervals, using a cycle-finding
algorithm for a small number of steps) and to design a well-defined exit strategy for short
cycles; Gallant, Lambert and Vanstone call this
collapsing the cycle
; see Section 6 of [
215
].
To collapse a cycle one must be able to determine a well-defined element in it; from there
one can take a step (different to the steps used in the cycle from that point) or use squaring
to exit the cycle. All these methods require small amounts of extra computation and storage,
though Bernstein, Lange and Schwabe [
57
] argues that the additional overhead can be made
negligible. We refer to [
45
,
86
] for further discussion of these issues.
Gallant, Lambert and Vanstone [
215
] presented a different walk that does not, in gen-
eral, lead to short cycles. Let
G
be an algebraic group with an efficiently computable
endomorphism
ψ
of order
m
(i.e.,
ψ
m
=
ψ
◦
ψ
◦···◦
ψ
=
1). Let
g
∈
G
of order
r
be
g
λ
so that
ψ
(
x
)
x
λ
for all
x
such that
ψ
(
g
)
=
=
∈
g
. Define the equivalence classes
ψ
j
(
x
):0
g
a
i
h
b
i
by using
x
to
x
={
≤
j<m
}
. We define a pseudorandom sequence
x
i
=
ψ
j
) and then acting on
x
i
with this map. More precisely,
j
is
some function of
x
(e.g., the function
S
in Section
14.2.1
) and
select an endomorphism (1
+
x
1
+
λ
j
i
(the above equation looks more plausible when the group operation is written addi-
tively:
x
i
+
1
=
ψ
j
)
x
i
=
x
i
ψ
j
(
x
i
)
x
i
+
1
=
(1
+
=
λ
j
)
x
i
). One can check that the map is well-defined
on equivalence classes and that
x
i
+
1
=
ψ
j
(
x
i
)
x
i
+
=
(1
+
g
a
i
+
1
h
b
i
+
1
λ
j
)
a
i
(mod
r
) and
where
a
i
+
1
=
(1
+
λ
j
)
b
i
(mod
r
).
We stress that this approach still requires finding a unique representative of each equiv-
alence class in order to define the steps of the walk in a well-defined way. Hence, one can
still use distinguished points by defining a class to be distinguished if its representative is
distinguished. One suggestion, originally due to Harley, is to use the Hamming weight of
the
x
-coordinate to derive the selection function.
One drawback of the Gallant, Lambert, Vanstone idea is that there is less flexibility in
the design of the pseudorandom walk.
b
i
+
1
=
(1
+
ψ
j
) for any
Exercise 14.4.10
Generalise the Gallant-Lambert-Vanstone walk to use (
c
+
c
∈ Z
. Why do we prefer to only use
c
=
1?
Exercise 14.4
.1
1
Show that taking
n
S
=
log(
r
) means the total overhead from handling
cycles is
o
(
√
r
), while the additional storage (group elements for the random walks) is
O
(log(
r
)) group elements.
Exercise
14.4.11
together with Exercise
14.2.15
shows that (as long as computing
equivalence class representatives is fast) one can solve the
discrete lo
garithm problem
using equivalence classes of generic size
N
C
in (1
o
(1))
√
πr/
(2
N
C
) group operations
+
and
O
(log(
r
)) group elements storage.
