Cryptography Reference
In-Depth Information
≈
√
p
and so the
ate pairing is computed in about half the time of the reduced Tate-Lichtenbaum pairing, as
usual. We now demonstrate an optimal pairing with these parameters.
Substituting the polynomials
r
(
x
) and
p
(
x
) for the values
r
and
q
in the matrix
of equation (
26.8
) gives a lattice. Lattice reduction over
Example 26.6.3
The family of curve parameters in Example
26.6.2
has
t
Z
[
x
] yields the short vector
p
(
x
)
2
(
M
0
,M
1
,M
2
,M
3
)
=
(6
x
+
2
,
1
,
−
1
,
1). It is easy to verify that 6
x
+
2
+
p
(
x
)
−
+
p
(
x
)
3
0(mod
r
(
x
)).
Now
f
1
,Q
=
≡
v
Q
(and so both can be omitted in pairing computation, by
Exercise
26.3.12
). The ate pairing can be computed as
f
6
x
+
2
,Q
(
P
) multiplied with three
straight line functions, and followed by the final exponentiation; see Section IV of [
554
].
The point is that Miller's algorithm now runs for approximately one quarter of the iterations
as when computing the Tate-Lichtenbaum pairing.
1 and
f
−
1
,Q
=
26.6.1 Distortion maps
As noted, when
ˆ
t
r
(
P,P
)
=
1 one can try to find an endomorphism
ψ
:
E
→
E
such that
ˆ
t
r
(
P,ψ
(
P
))
=
1.
Definition 26.6.4
Let
E
be an elliptic curve over
F
q
,let
r
|
#
E
(
F
q
)beprime,let
e
:
E
[
r
]
×
E
[
r
]
F
q
)[
r
]. A
distortion
map
with respect to
E,r,e
and
P
is an endomorphism
ψ
such that
e
(
P,ψ
(
P
))
→
µ
r
be a non-degenerate and bilinear pairing and let
P
∈
E
(
=
1.
Verheul (Theorem 5 of [
556
]) shows that if
E
is a supersingular elliptic curve then, for
any point
P
∈
E
(
F
q
k
)
−{
O
E
}
, a distortion map exists. In particular, when
P
∈
E
(
F
q
)[
r
]
−
{
O
E
}
and
k>
1 then there is an endomorphism
ψ
(necessarily not defined over
F
q
) such that
ˆ
t
(
P,ψ
(
P
))
1. Since
P
is defined over the small field we have a compact representation
for all elliptic curve points in the cryptosystem, as well as efficiency gains in Miller's
algorithm. For this reason, pairings on supersingular curves are often the fastest choice for
certain applications.
=
Example 26.6.5
Consider again the elliptic curves from Example
26.6.1
. An automorphism
on
E
a
is
ψ
(
x,y
)
s
2
,y
∈ F
2
4
satisfy
s
2
=
(
x
+
+
sx
+
t
) where
s
∈ F
2
2
and
t
=
s
+
1 and
t
2
=
t
+
s
. One can represent
F
2
4
m
using the basis
{
1
,s,t,st
}
. It is clear that if
P
∈
E
a
(
F
2
l
)
where
l
is odd then
ψ
(
P
)
∈
E
a
(
F
2
4
l
) and
ψ
(
P
)
∈
E
a
(
F
2
2
l
), and so
ψ
is a distortion map
for
P
.
Exercise 26.6.6
Let
E
be an elliptic curve over
F
q
and let
r
|
#
E
(
F
q
)beprime.Let
=
∈
F
q
k
) define the trace map
k
k
(
q,r
)
>
1 be the embedding degree. For any point
P
E
(
Tr(
P
)
=
σ
(
P
)
.
σ
∈
Gal(
F
q
k
/
F
q
)
