Cryptography Reference
In-Depth Information
1
induced by the map from
1
to
G
q,
2
.
We now present the partial group operations on
A
A
1
is not a group with respect to these operations, since the identity element
of
G
q,
2
is not represented as an element of
We stress that
A
1
.
A
1
define ab
Lemma 6.3.12
Let the notation be as above. For a,b
∈ A
=
(
ab
−
B
)
/
(
a
+
A
)
and a
=
a. Then abis the product and a
is the inverse for the partial group
b
−
A
−
law.
1
Proof
The partial group law on
A
is defined by comp
2
(decomp
2
(
a
)decomp
2
(
b
)). Now
a
b
+
θ
+
θ
ab
−
B
+
(
a
+
b
−
A
)
θ
decomp
2
(
a
)decomp
2
(
b
)
=
=
A
)
θ
.
a
+
θ
b
+
θ
ab
−
B
+
(
a
+
b
−
The formula for
ab
follows.
Similarly,
a
+
θ
a
+
(
−
A
−
θ
)
decomp
2
(
a
)
−
1
=
θ
=
θ
)
,
a
+
a
+
(
−
A
−
which gives the formula for
a
.
It follows that one can compute directly with the compressed representation of elements
1
requires an inversion, so is not
very efficient. For cryptographic applications one is usually computing comp
2
(
g
n
)from
comp
2
(
g
); to do this one decompresses to obtain
g
T
2
(
F
q
). Note that computing the partial group law on
A
of
G
q,
2
, then computes
g
n
using any one
of a number of techniques and finally applies comp
2
to obtain a compact representation.
3
∈
6.3.2 Lucas sequences
Lucas sequences
4
can be used for efficient computation in quadratic fields. We give the
details for
G
q,
2
⊂ F
q
2
. The name LUC cryptosystem is applied to any cryptosystem using
Lucas sequences to represent elements in an algebraic group quotient of
G
2
,q
. Recall the
trace
Tr
F
q
2
/
F
q
(
g
)
g
q
for
g
=
g
+
∈ F
q
2
.
∈ F
q
2
satisfy
g
q
+
1
=
∈ Z
define
V
i
=
Tr
F
q
2
/
F
q
(
g
i
).
Definition 6.3.13
Let
g
1. For
i
Lemma 6.3.14
Let g
=
v
1
+
w
1
θ with v
1
,w
1
∈ F
q
and θ as in equation (
6.1
). Suppose
g
q
+
1
=
1
and let V
i
be as in Definition
6.3.13
. Then, for i,j
∈ Z
:
1. V
0
=
2
and V
1
=
Tr
F
q
2
/
F
q
(
g
)
=
2
v
1
−
Aw
1
.
2. V
−
i
=
V
i
.
3. V
i
+
1
=
V
1
V
i
−
V
i
−
1
.
V
i
−
4. V
2
i
=
2
.
5. V
2
i
−
1
=
V
i
V
i
−
1
−
V
1
.
3
This is analgous to using projective coordinates for efficient elliptic curve arithmetic; see Exercise
9.1.5
.
4
They are named after Edouard Lucas (1842-1891); who apparently died due to a freak accident involving broken crockery.
Lucas sequences were used for primality testing and factorisation before their cryptographic application was recognised.
