Cryptography Reference
In-Depth Information
(The Gong-Harn cryptosystem [235]) Consider the quotient
G
q,
3
=
Exercise 6.4.14
g
n
G
q,
3
/
σ
where
σ
is the
q
-power Frobenius in
F
q
3
.Fix
g
∈
G
q,
3
and define
t
n
=
+
g
nq
2
g
nq
∈ F
q
. Show that the characteristic polynomial for
g
is
x
3
t
1
x
2
+
−
+
t
−
1
x
−
1.
Hence, show that an element of
G
q,
3
can be represented using two elements of
F
q
. Show
that
t
n
+
m
=
t
n
t
m
−
t
n
−
m
t
−
m
+
t
n
−
2
m
.
Hence, develop a ladder algorithm for exponentiation in
G
q,
3
.
3
m
with
m
Exercise 6.4.15
(Shiras
e,
Han, Hibin
o,
Kim and Takagi [476]) Let
q
=
−
√
3
q
+
√
3
q
q
2
∈ F
3
6
m
have order
odd. Show tha
t (
q
+
1)(
q
+
1)
=
−
q
+
1. Let
g
−
√
3
q
g
√
3
q
and
g
q
3
1. Show that
g
q
+
1
+
1
dividing
q
+
=
=
1. Let
t
=
Tr
F
q
6
/
F
q
2
(
g
) and
s
√
3
q
are
t
and
t
q
.
Hence, one can use
s
as a compressed representative for
g
; requiring only half the
storage of XTR. To compute Tr
F
q
6
/
F
q
(
g
n
) one solves the quadratic to obtain
t
, computes
Tr
F
q
6
/
F
q
2
(
g
n
) using the XTR formulae, and then performs the further compression.
=
Tr
F
q
6
/
F
q
(
g
). Show that the roots of
x
2
−
+
s
sx
6.5 Further remarks
Granger and Vercauteren [
242
] have proposed an index calculus algorithm for
F
p
m
)
where
m>
1. Kohel [
316
] has shown that one might map the discrete logarithm problem
in an algebraic torus
T
n
(
F
q
) to the discrete logarithm problem in the generalised Jacobian
(which is a certain type of divisor class group) of a singular hyperelliptic curve over
T
n
(
F
q
.
This latter problem might be attacked using an index calculus method such as Gaudry's
algorithm (see Section
15.6.3
). It seems this approach will not be faster than performing
index calculus methods in
F
p
n
, but further investigation would be of interest.
6.6 Algebraic tori over rings
Z
Z
Applications in factoring and primality testing motivate the study of tori over
.As
mentioned in Section
4.4
, the simplest approach is to restrict to
N
being square-free and to
use the Chinese remainder theorem to define the groups. First, we explain how to construct
rings isomorphic to the direct product of finite fields.
/N
=
i
=
1
p
i
be square-free. Let
F
(
x
)
x
2
Example 6.6.1
Let
N
=
+
Ax
+
B
∈ Z
[
x
]bea
quadratic polynomial such that
F
(
x
) is irreducible modulo
p
i
for all 1
≤
i
≤
k
. Define
)[
x
]
/
(
F
(
x
)). By the Ch
in
ese remainder theorem,
R
=
⊕F
p
i
. We will usually
write
θ
for the image of
x
in
R
and
θ
R
=
(
Z
/N
Z
Bx
−
1
.
Define
G
N,
2
to be the subgroup of
R
∗
of order
i
=
1
(
p
i
+
=−
A
−
x
=
1) isomorphic to the direct
sum of the groups
G
p
i
,
2
. Note that
G
N,
2
is not usually cyclic.
We would like to represent a “general” element of
G
N,
2
using a single element of
Z
/N
Z
.
In other words, we would like to have a map from
Z
/N
Z
to
G
N.
2
. One can immediately
