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
 
Search WWH ::




Custom Search