Cryptography Reference
In-Depth Information
Exercise 11.3.22
Show that
r
00
···
0
−
λ
10
···
0
λ
2
−
01
···
0
.
.
λ
l
−
00
···
1
is a basis for the GLV lattice
L
.
Exercise 11.3.23
Show how to compute the coefficients
a
0
,...,a
l
for the GLV method
using Babai rounding.
Exercise
11.3.24
gives a construction of homomorphisms for the GLV method that apply
to a large class of curves. We refer to Galbraith, Lin and Scott [
207
] for implementation
results that show the benefit of using this construction.
Exercise 11.3.24
(Iijima, Matsuo, Chao and Tsujii [
274
]) Let
p>
3beaprimeandlet
E
:
y
2
x
3
=
+
a
4
x
+
a
6
be an ordinary elliptic curve over
F
p
with
p
+
1
−
t
points (note
∈ F
p
2
be a non-square and define
E
:
Y
2
X
3
u
2
a
4
X
u
3
a
6
over
that
t
=
0). Let
u
=
+
+
F
p
2
. Show that
E
is the quadratic twist of
E
(
F
p
2
) and that #
E
(
F
p
2
)
=
(
p
−
1)
2
+
t
2
.Let
E
be the isomorphism
φ
(
x,y
)
φ
:
E
→
=
(
ux,u
3
/
2
y
) defined over
F
p
4
.
(
x
p
,y
p
) and define
Let
π
(
x,y
)
=
φ
−
1
.
ψ
=
φ
◦
π
◦
Show that
ψ
:
E
→
E
is an endomorphism of
E
that is defined over
F
p
2
. Show that
ψ
2
=
[
−
1].
#
E
(
F
p
2
) be a prime such that
r>
2
p
and
r
2
#
E
(
E
(
Let
r
|
F
p
2
). Let
P
∈
F
p
2
)have
order
r
. Show that
ψ
2
(
P
)
−
[
t
]
ψ
(
P
)
+
[
p
]
P
=
O
E
. Hence, deduce that
ψ
(
P
)
=
[
λ
]
P
t
−
1
(
p
1) (mod
r
). Note that it is possible for #
E
(
F
p
2
) to be prime, since
E
where
λ
=
−
is not defined over
F
p
.
As in Remark
11.3.17
, for some applications one might be able to choose a random
GLV expansion directly, rather than choosing a random integer and converting it to GLV
representation.
There is a large literature on the GLV method, including several different algorithms
to compute the integers
a
0
,...,a
l
. As noted earlier, reducing the bit-length of the
a
i
by
one or two bits has very little effect on the overall running time. Instead, the weight of the
entries
a
0
,...,a
l
is more critical. We refer to Sections 15.2.1 and 15.2.2 of [
16
] for further
details and examples of the GLV method. Section 15.2.3 of [
16
] discusses combining the
GLV method with Frobenius expansions.