Cryptography Reference
In-Depth Information
(
q
n
1)
/
(
q
d
1) and, by Lemma
6.1.5
, gcd((
q
n
1)
/
(
q
d
Recall that
n
(
q
)
|
−
−
−
−
1) : 1
≤
n
(
q
). Hence, all the norms are 1 if and only if
g
n
(
q
)
d<n,d
|
n
)
=
=
1, which proves
the first claim. The second and third statements follow immediately.
Corollary 6.2.3
Let n
∈ N
and q a prime power. Suppose g
∈
G
q,n
has order r>n. Then
g does not lie in any proper subfield of
F
q
n
.
g
n/d
,
Proof
Suppose
g
∈ F
q
d
for some 1
≤
d<n
such that
d
|
n
. Then 1
=
N
F
q
n
/
F
q
d
(
g
)
=
but this contradicts the order of
g
being
>n
.
T
n
is irreducible and of dimension
ϕ
(
n
). Hence,
T
n
is a variety and one can speak of birational maps from
It follows from the general theory that
T
n
to another algebraic set. We
refer to Section 5 of [
453
] for details and references.
ϕ
(
n
)
.
Definition 6.2.4
The torus
T
n
is
rational
if there is a birational map from
T
n
to
A
ϕ
(
n
)
(
F
q
) is a compact representation for
G
q,n
. Performing dis-
crete logarithm cryptography by transmitting elements of
If
T
n
is rational then
A
ϕ
(
n
)
(
F
q
) is called
torus-based
cryptography
and was developed by Rubin and Silverberg [
452
].
If
A
ϕ
(
n
)
, given by
rational functions. This is not an algebraic group in general since there is not usually a one-
to-one correspondence between
T
n
is rational then there is an induced “partial” group operation on
A
ϕ
(
n
)
(
A
F
q
) and
G
q,n
. Nevertheless, “most” of the elements
F
q
) and, for many cryptographic purposes, the partial
group law is sufficient. In practice, however, working with the partial group operation
on
A
ϕ
(
n
)
(
of the group
G
q,n
appear in
ϕ
(
n
)
is not usually as efficient as using other representations for the group. The main
application of tori is therefore the compact representation for elements of certain subgroups
of
A
F
q
n
.
It is not known if
T
n
is rational for all
n
∈ N
(we refer to [
453
] for more details and
references about when
T
n
is known to be rational). The cryptographic applications of
T
2
and
T
6
rely on the well-known fact that these tori are both rational. The details are given in
the following sections.
As mentioned in Section
4.3
, sometimes it is convenient to consider quotients of algebraic
groups by an equivalence relation. In the following sections we describe algebraic group
quotients (more commonly known by the names LUC and XTR) for
G
q,
2
and
G
q,
6
,butwe
construct them directly without using the theory of tori.
6.3 The group
G
q,
2
Define
F
q
2
= F
q
(
θ
) where
θ
2
+
+
=
Aθ
B
0
(6.1)
∈ F
q
such that
x
2
for some
A,B
+
Ax
+
B
is irreducible over
F
q
(e.g., if
q
is odd then
A
2
−
4
B
is not a square in
F
q
). In practice, there are performance advantages from using
