Cryptography Reference
In-Depth Information
Lemma 6.3.19
Given
(
V
i
,V
i
−
1
)
and V one can compute
(
V
2
i
,V
2
i
−
1
)
(i.e., “squaring”) or
(
V
2
i
+
1
,V
2
i
)
(i.e., “square-and-multiply”) in one multiplication, one squaring and two or
three additions in
F
q
.
Proof
One must compute
V
i
and
V
i
V
i
−
1
and then apply part 4 and either part 5 or 7 of
Lemma
6.3.14
.
Exercise 6.3.20
Write the ladder algorithm for computing [
n
]
V
using Lucas sequences in
detail.
The storage requirement of the ladder algorithm is the same as when working in
F
q
2
,
although the output value is compressed to a single element of
F
q
. Note however that
computing a squaring alone in
F
q
2
already requires more computation (at least when
q
is
not a power of 2) than Lemma
6.3.19
.
We have shown that for
V
G
q,
2
one can compute [
n
]
V
using polynomial operations
starting with the pair (
V,
2). Since
G
q,
2
is in one-to-one correspondence with
G
q,
2
/
∈
σ
,it
is natural to consider
G
q,
2
as being an algebraic group quotient.
Performing discrete logarithm based cryptography in
G
q,
2
is sometimes called the
LUC cryptosystem.
6
To solve the discrete logarithm problem in
G
q,
2
, one usually lifts
the problem to the
covering group
G
q,
2
⊂ F
q
2
by taking one of the roots in
F
q
2
of the
polynomial
x
2
−
Vx
+
1.
= F
37
(
θ
) where
θ
2
Example 6.3.21
Define
F
37
2
−
3
θ
+
1
=
0. The element
g
=−
1
+
3
θ
has order 19 and lies in
G
37
,
2
. Write
V
=
Tr
F
37
2
/
F
37
(
g
)
=
7. To compute [6]
V
, one uses
the addition chain (
V
1
,V
0
)
=
(7
,
2)
→
(
V
3
,V
2
)
=
(26
,
10)
→
(
V
6
,V
5
)
=
(8
,
31); this is
because 6
=
(110)
2
in binary so the intermediate values for
i
are (1)
2
=
1 and (11)
2
=
3.
Exercise 6.3.22
Using the same values as Example
6.3.21
compute [10]
V
.
Exercise 6.3.23
F
q
multiplications and squarings to compute a
squaring or a squaring-and-multiplication in the quotient
G
q,
2
using Lucas sequences with
the cost for general arithmetic in
G
q,
2
⊂ F
q
2
.
Compare the number of
6.4 The group
G
q,
6
F
q
6
of order
6
(
q
)
q
2
The group
G
q,
6
is the subgroup of
=
−
q
+
1. The natural represen-
tation of elements of
G
q,
6
requires 6 elements of
F
q
.
∈ F
q
2
and
θ
2
Assume (without loss of generality) that
F
q
6
= F
q
3
(
θ
) where
θ
+
Aθ
+
B
=
0forsome
A,B
∈ F
q
.
6
The original LUC cryptosystem due to Smith and Lennon [
515
] was using Lucas sequences modulo a composite integer
N
;
we refer to Section
6.6
for further discussion. The finite field version is only very briefly mentioned in [
515
], but is further
developed in [
516
].
