Cryptography Reference
In-Depth Information
Tr
F
q
6
/
F
q
2
(
g
n
).
Definition 6.4.8
Fix
g
∈
G
q,
6
.For
n
∈ Z
write
t
n
=
Lemma 6.4.9
Let the notation be as above. Then, for n,m
∈ Z
:
t
n
.
1. t
−
n
=
t
nq
=
t
m
t
n
−
m
+
2. t
n
+
m
=
t
n
t
m
−
t
n
−
2
m
.
g
n
(
q
−
1)
g
n
(
−
q
)
Proof
We have
t
n
=
g
n
+
+
The first statement follows from the proof of
Lemma
6.4.6
, where it is proved that
t
q
Tr
F
q
6
/
F
q
2
(
g
−
1
).
For the second statement an elementary calculation verifies that
g
q
g
1
−
q
g
−
1
=
+
+
=
(
g
n
g
n
(
q
−
1)
g
−
nq
)(
g
m
g
m
(
q
−
1)
g
−
mq
)
t
n
t
m
−
t
n
+
m
=
+
+
+
+
(
g
n
+
m
g
(
n
+
m
)(
q
−
1)
g
−
(
n
+
m
)
q
)
−
+
+
g
n
+
m
(
q
−
1)
g
n
−
mq
g
n
(
q
−
1)
+
m
g
n
(
q
−
1)
−
mq
g
−
nq
+
m
g
−
nq
+
m
(
q
−
1)
.
=
+
+
+
+
+
This is equal to
t
m
t
n
−
t
n
−
2
m
.
It remains to give a ladder algorithm to compute
t
n
. In this case, one can work with
triples (
t
n
+
1
,t
n
,t
n
−
1
) of 'adjacent' values centered at
t
n
. This is the
XTR representation
of Lenstra and Verheul [324]. Note that, given
t
1
=
Tr
F
q
6
/
F
q
2
(
g
) one can compute the triple
(
t
1
,
3
,t
1
). Given a triple (
t
n
+
1
,t
n
,t
n
−
1
) and
t
1
one can compute the triple
centered at
t
2
n
or
t
2
n
+
1
using the following exercise.
(
t
1
,t
0
,t
−
1
)
=
Exercise 6.4.10
Prove that
t
1
t
n
+
t
n
+
1
;
1.
t
2
n
−
1
=
t
n
−
1
t
n
−
2
t
n
;
t
n
−
2.
t
2
n
=
t
1
t
n
+
t
n
−
1
.
3.
t
2
n
+
1
=
t
n
+
1
t
n
−
Exercise 6.4.11
If one uses triples (
t
n
+
1
,t
n
,t
n
−
1
) as above then what is the cost of a square
or square-and-multiply in
G
q,
6
?
Exercise 6.4.12
Give a more efficient ladder for XTR, for which the cost of squaring and
square-and-multiply are the same.
In other words, one can compute Tr
F
q
6
/
F
q
2
(
g
n
)from
t
=
Tr
F
q
6
/
F
q
2
(
g
) using polynomial
arithmetic and so
G
q,
6
/
Gal(
F
q
2
) is an algebraic group quotient. Performing discrete
logarithm based cryptography in this setting is called the
XTR cryptosystem
.Tosolve
the discrete logarithm problem in
G
q,
6
/
Gal(
F
q
6
/
F
q
2
) one usually lifts the problem to the
covering group
G
q,
6
⊂ F
q
6
by taking any root of the polynomial
x
3
F
q
6
/
tx
2
t
q
x
−
+
−
1. For
further details about efficient arithmetic using XTR we refer to [
520
].
F
67
(
i
) where
i
2
Exercise 6.4.13
Represent
F
67
2
as
=−
1. Given that
t
1
=
Tr
F
67
6
/
F
67
2
(
g
)
=
Tr
F
67
6
/
F
67
2
(
g
7
).
48
+
63
i
for some
g
∈
G
67
,
6
compute
t
7
=
