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.
Search WWH ::




Custom Search