Cryptography Reference
In-Depth Information
We can generalise this example as follows.
Example 14.4.6
Let
G
be an algebraic group over
F
q
with an automorphism group Aut(
G
)
of size
N
C
(see examples in Sections
9.4
and
11.3.3
). Suppose that for
g
∈
G
of order
r
one has
ψ
(
g
)
∈
g
for each
ψ
∈
Aut(
G
). Furthermore, assume that for each
ψ
∈
Aut(
G
)
g
λ
ψ
. Then for
x
one can efficie
nt
ly compute the eigenvalue
λ
ψ
∈ Z
such that
ψ
(
g
)
=
∈
G
={
∈
}
one can define
x
.
Again, one defines
x
by listing the elements of
x
as bitstrings and choosing the first one
under lexicographical ordering.
ψ
(
x
):
ψ
Aut(
G
)
Another important class of examples comes from orbits under the Frobenius map.
Example 14.4.7
Let
G
be an algebraic group defined over
F
q
but with group considered
over
F
q
d
(for examples see Sections
11.3.2
and
11.3.3
). Let
π
q
be the
q
-power Frobenius
map on
G
(
g
λ
F
q
d
). Let
g
∈
G
(
F
q
d
) and suppose that
π
q
(
g
)
=
∈
g
for some known
λ
∈ Z
.
Define
th
e equivalence relation on
G
(
F
q
d
) so that the equivalence class of
x
∈
G
(
F
q
d
)
π
q
(
x
):0
is the set
x
={
≤
i<d
}
. We assume that, for elements
x
of interest,
x
⊆
g
.
Then
N
C
=
d
, though there can be elements defined over proper subfields for which the
equivalence class is smaller.
If one uses a normal basis for
F
q
then one can efficiently compute the elements
π
q
(
x
) and select a unique representative of each equivalence class using a lexicographical
ordering of binary strings.
F
q
d
over
Example 14.4.8
For some groups (e.g., Koblitz elliptic curves
E/
F
2
considered as a group
over
F
2
m
; see Exercise
9.10.10
) we can combine both equivalence classes above. Let
m
be prime, #
E
(
F
2
m
)
=
hr
for some small cofacto
r
h
, and
P
∈
E
(
F
2
m
)oforder
r
. Then
π
2
(
P
):0
π
2
(
P
)
of size 2
m
.
Since
m
is odd, this class can be considered as the orbit of
P
under the map
∈
P
and we define the equivalence class
P
={±
≤
i<m
}
π
2
.The
distributed rho a
lgorithm o
n equivalence classes for such curves is expected to require
approximately
√
π
2
m
/
(4
m
) group operations.
−
14.4.2 Dealing with cycles
One problem that can arise is walks that fall into a cycle before they reach a distinguished
point. We call these
useless cycles
.
≡
x
−
1
.Fix
x
i
=
Exercise 14.4.9
Suppose the equivalence relation is such that
x
x
i
and
x
−
1
let
x
i
+
1
=
x
i
g
. Suppose
x
i
+
1
=
i
+
1
and that
S
(
x
i
+
1
)
=
S
(
x
i
). Show that
x
i
+
2
≡
x
i
and so
there is a cycle of order 2. Suppose the equivalence classes generically have size
N
C
. Show,
under the assumptions that the function
S
is perfectly random and that
x
is a randomly
chosen element of the equivalence class, that the probability that a randomly chosen
x
i
leads to a cycle of order 2 is 1
/
(
N
C
n
S
).
A theoretical discussion of cycles was given in [
215
] and by Duursma, Gaudry and
Morain [
172
]. An obvious way to reduce the probability of cycles is to take
n
S
to be very
large compared with the average length 1
/θ
of walks. However, as argued by Bos, Kleinjung