Cryptography Reference
In-Depth Information
the group operation is given by the polynomial mult(
x,y
)
=
xy
and the rational function
inverse(
x
)
) as an algebraic set).
The additive group is useless for cryptography since the discrete logarithm problem
is easy. The discrete logarithm problem is also easy for the multiplicative group over
certain fields (e.g., if
g
=
1
/x
(Example
5.1.4
shows how to express
G
m
(
k
⊆R
∗
is easy
due to algorithms that compute approximations to the natural logarithm function). How-
ever,
G
m
(
∈ R
∗
then the discrete logarithm problem in
g
F
q
) is useful for cryptography and will be one of the main examples used in
this topic.
The other main examples of algebraic groups in public key cryptography are algebraic
tori (see Chapter
6
), elliptic curves and divisor class groups of hyperelliptic curves.
4.3 Algebraic group quotients
Quotients of algebraic groups are used to reduce the storage and communication require-
ments of public key cryptosystems. Let
G
be a group with an automorphism
ψ
such
that
ψ
n
=
→
G
is the identity map and
ψ
n
is the
n
-fold composition
1(where1:
G
ψ
◦···◦
ψ
). We define
ψ
0
=
1. Define the
orbit
or
equivalence class
of
g
∈
G
under
ψ
to be [
g
]
={
ψ
i
(
g
):0
≤
i<n
}
. Define the
quotient
as the set of orbits under
ψ
. In other
words
G/ψ
={
[
g
]:
g
∈
G
}
.
We call
G
the
covering group
of a quotient
G/ψ
. In general, the group structure of
G
does
not induce a group structure on the quotient
G/ψ
. Nevertheless, we can define exponen-
tiation on the quotient by [
g
]
n
=
[
g
n
]for
n
∈ Z
. Since exponentiation is the fundamental
operation for many cryptographic applications it follows that quotients of algebraic groups
are sufficient for many cryptographic applications.
G/ψ, then
[
g
]
n
is well-defined.
Lemma 4.3.1
Let n
∈ Z
and
[
g
]
∈
Proof
Since
ψ
is a group homomorphism we have
ψ
i
(
g
)
n
ψ
i
(
g
n
) and so for each
=
[
g
]wehave
g
1
∈
[
g
n
].
g
1
∈
The advantage of algebraic group quotients
G/ψ
is that they can require less storage
than the original algebraic group
G
. We now give an example of this.
⊂ F
p
2
of order
p
Example 4.3.2
Let
p
be an odd prime. Consider the subgroup
G
+
1.
∩ F
p
={
G
then we have
g
p
+
1
Note that gcd(
p
−
1
,p
+
1)
=
2so
G
1
,
−
1
}
.If
g
∈
=
1,
which is equivalent to
g
p
g
−
1
.Let
ψ
be the automorphism
ψ
(
g
)
g
p
. Then
ψ
2
=
=
=
1in
F
p
2
and the orbits [
g
]in
G/ψ
all have size 2 except for [1] and [
−
1].
The natural representation for elements of
G
⊆ F
p
2
is a pair of elements of
F
p
. However,
since #(
G/ψ
)
=
2
+
(
p
−
1)
/
2 one might expect to be able to represent elements of
G/ψ
using just one element of
F
p
.
