Cryptography Reference
In-Depth Information
computable” (see below for a clarification of this term) group homomorphism
ψ
and replace
the computation
g
a
in a group of order
r
by
t
he multi-exponentiation
g
a
0
ψ
(
g
)
a
1
for suitable
a
1
|≈
√
r
. Typical choices for
ψ
are an automorphism
of an elliptic curve or the Frobenius map on an elliptic curve or torus over an extension
field.
More precisely, let
g
integers
a
0
and
a
1
such that
|
a
0
|
,
|
F
q
) be an element of prime order
r
in an algebraic
group and let
ψ
be a group homomorphism such that
ψ
(
g
)
∈
G
(
∈
g
(this is automatic if
g
λ
for some
λ
ψ
:
G
(
. The meaning
of “efficiently computable” is essentially that computing
ψ
(
g
) is much faster than com-
puting
g
λ
using exponentiation algorithms. Hence, we require that
λ
and
r
F
q
)
→
G
(
F
q
) and
r
#
G
(
F
q
)). Then
ψ
(
g
)
=
∈ Z
/r
Z
−
λ
are not
=−
small; in particular, the map
ψ
(
P
)
P
on an elliptic curve is not interesting for this
application.
Example 11.3.21
Consider
T
2
(
F
p
2
), with eleme
n
ts represented as in Definition
6.3.7
so that
u
∈ F
p
2
corresponds to
g
=
(
u
+
θ
)
/
(
u
+
θ
)
∈ F
p
4
. It follows by
L
emma
6.3.12
u
p
(
w
here
θ
2
to
g
p
(
u
p
θ
)
/
(
u
p
that
A
−
+
Aθ
+
B
=
0)
corresponds
=
+
+
θ
)
=
(
u
p
θ
)
−
1
. Since computing
u
p
for
u
u
p
is a useful efficiently computable group homomorphism with respect to the torus group
operation.
One can also perform exponentiation in
G
q
2
,
2
⊆ F
p
4
using Frobenius. Given an exponent
a
such that 1
θ
)(
u
p
+
+
∈ F
p
2
is easy, the map
ψ
(
u
)
=
A
−
a<p
2
one lets
a
0
and
a
1
be the coefficients in the base-
p
representation
of
a
and computes
g
a
as
g
a
0
(
g
p
)
a
1
. Note that
g
p
is efficient to compute as it is a linear map
on the four-dimensional vector space
≤
F
p
4
over
F
p
.
Other examples include the automorphism
ζ
3
on
y
2
x
3
B
in Example
9.4.2
and
the automorphisms in Exercises
9.4.5
and
10.2.8
. Computing the eigenvalue
λ
for
ψ
is
usually easy in practice: for elliptic curves
λ
is a root of the characteristic polynomial of
ψ
modulo
r
.
In some applications (e.g.,
=
+
F
p
3
) or some automorphisms on genus 2 curves such as
the one in Exercise
10.2.8
) one can replace
g
a
by
g
a
0
ψ
(
g
)
a
1
T
2
(
ψ
l
−
1
(
g
)
a
l
−
1
for some
l>
2.
We call this the
l
-dimensional GLV method. We stress that
l
cannot be chosen arbitrarily;
in Example
11.3.21
the map
ψ
2
is the identity map and so is not useful.
In the previous section we sketched, for elliptic curves, the GLV method to represent an
integer as a short Frobenius expansion with relatively small coefficients. One can do the
same for any endomorphism
ψ
as long as
ψ
(
P
)
···
=
=
g
λ
in multiplicative
[
λ
]
P
(or
ψ
(
g
)
notation). The
GLV lattice
is
l
+
1
x
l
λ
l
L
={
(
x
0
,...,x
l
)
∈ Z
:
x
0
+
x
1
λ
+···+
≡
0(mod
r
)
}
.
A basis for
L
is given in Exercise
11.3.22
. As explained earlier, to convert an integer
a
into GLV representation one finds a lattice vector (
a
0
,a
1
,...,a
l
)
∈
L
close to (
a,
0
,...,
0)
a
0
a
i
for 1
(using Babai rounding) then sets
a
0
=
a
−
and
a
i
=−
≤
i
≤
l
.
