Cryptography Reference
In-Depth Information
We stress that being an algebraic group is not a group-theoretic property, it is a property
of a particular description of the group. Perhaps it helps to give an example of a group
whose usual representation is not an algebraic group.
∈ N
Example 4.1.1
Let
n
and let
S
n
be the group of permutations on
n
symbols. Permu-
tations can be represented as an
n
-tuple of distinct integers from the set
{
1
,
2
,...,n
}
.The
composition (
x
1
,...,x
n
)
(
y
1
,...,y
n
) of two permutations is (
x
y
1
,x
y
2
,...,x
y
n
). Since
x
y
1
is not a polynomial, the usual representation of
S
n
is not an algebraic group. However,
S
n
can be represented as a subgroup of the matrix group
GL
n
(
◦
k
) (for any field
k
), which is an
algebraic group.
F
q
. For each example of an
algebraic group (or quotient)
G
we will explain how to achieve the following basic func-
tionalities:
Our main interest is algebraic groups over finite fields
efficient group operations in
G
(typically requiring
O
(log(
q
)
2
) bit operations);
compact representation of elements of
G
(typically
O
(log(
q
)) bits);
generating cryptographically suitable
G
in polynomial-time (i.e.,
O
(log(
q
)
c
)forsome
(small)
c
∈ N
);
generating random elements in
G
in polynomial-time;
l
to
G
or from
G
to
l
in polynomial-time.
hashing from
{
0
,
1
}
{
0
,
1
}
In order to be able to use an algebraic group (or quotient)
G
for cryptographic applications,
we need some or all of these functionalities, as well as requiring the discrete logarithm
problem (and possibly other computational problems) to be hard.
We sometimes use the notation AG to mean “algebraic group in the context of this
topic”; similarly, AGQ means “algebraic group quotient in the context of this topic”. The
aim of this part of the topic is to describe the algebraic groups of relevance for public
key cryptography (namely, multiplicative groups, algebraic tori, elliptic curves and divisor
class groups). As is traditional, we will use multiplicative notation for the group operation
in multiplicative groups and tori, and additive notation for the group operation on elliptic
curves and divisor class groups of hyperelliptic curves. In Parts III and V, when we discuss
cryptographic applications, we will always use multiplicative notation for algebraic groups.
The purpose of this chapter is to give the simplest examples of algebraic groups and
quotients. The later chapters introduce enough algebraic geometry to be able to define the
algebraic groups of interest in this topic and prove some important facts about them.
4.2 Examples of algebraic groups
The simplest examples of algebraic groups are the
additive group
G
a
and
multiplicative
group
G
m
of a field
k
.For
G
a
(
k
) the set of points is
k
and the group operation is
given by the polynomial mult(
x,y
)
=
x
+
y
(for computing the group operation) and
k
∗
= k −{
inverse(
x
)
=−
x
(for computing inverses). For
G
m
(
k
) the set of points is
0
}
and
