Cryptography Reference
In-Depth Information
There is a very serious problem with cycles that we do not discuss yet; see Section
14.4.2
for the details.
Exercise 14.4.1
Write down the formulae for updating the values
a
i
and
b
i
in the function
walk
.
Exercise 14.4.2
Write pseudocode for the distributed rho method on equivalence classes.
Theorem 14.4.3
Let G be a group and g
∈
G of order r. Suppose there is an equivalence
relation on
as above. Let N
C
be the generic size of an equivalence class. Let C
1
be the
number of bit operations to perform a group operation in
g
and C
2
the number of bit
operations to compute a unique equivalence class representative x
i
(and to compute a
i
, b
i
).
Consider the rho algorithm as above (ignoring the possibility of useless cycles, see
Section
14.4.2
below). Under a heuristic assumption for equivalence classes analogous to
Heuristic
14.2.13
the expected time to solve the discrete logarithm problem is
π
2
N
C
+
g
o
(1)
√
r
(
C
1
+
C
2
)
bit operations. As usual, this becomes
(
√
π/
2
N
C
+
o
(1))
√
r/N
P
(
C
1
+
C
2
)
bit operations
per client when using N
P
processors of equal computational power.
Exercise 14.4.4
Prove this theorem.
Theorem
14.4.3
assumes a perfect random walk. For walks defined on
n
S
partitions of
the set of equivalence classes it is shown in Appendix B of [
24
] (also see Section 2.2 of
[
86
]) that one predicts a slightly improved constant than the usual factor
c
n
S
=
n
S
/
(
n
S
−
1)
mentioned at the end of Section
14.2.5
.
We mention a potential “paradox” with this idea. In general, computing a unique equiv-
alence class representative involves listing all elements of the equivale
nce class
, and hence
needs
O
(
N
C
) bit operations. Hence, naively, the running time is
O
(
√
N
C
πr/
2) bit opera-
tions, which is worse than doing the rho algorithm without equivalence classes. However,
in practice one only uses this method when
C
2
<C
1
, in which case the speedup can be
significant.
14.4.1 Examples of equivalence classes
We now give some examples of useful equivalence relations on some algebraic groups.
Example 14.4.5
For a group
G
with efficiently computable inverse (e.g., elliptic curves
E
(
F
q
) or algebraic tori
T
z
with
n>
1 (e.g., see Section
6.3
)) one can define the equivalence
x
−
1
.Wehave
N
C
=
relation
x
2 (though note that some elements, namely the identity
and elements of order 2, are equal to their inverse so these classes have size 1). If
x
i
=
≡
g
a
i
h
b
i
then clearly
x
−
1
g
−
a
i
h
−
b
i
. One defines a unique representative
x
for the equivalence class
by, for example, imposing a lexicographical ordering on the binary representation of the
elements in the class.
=
