Cryptography Reference
In-Depth Information
points of cryptographic interest). Show that all vertical line functions can be omitted when
computing the reduced Tate-Lichtenbam pairing.
26.3.3 Ate pairing
Computing pairings on elliptic curves usually requires significantly more effort than expo-
nentiation on an elliptic curve. There has been a concerted research effort to make pairing
computation more efficient, and a large number of techniques are known. Due to lack of
space we focus on one particular method known as “loop shortening”. This idea originates
in the work of Duursma and Lee [
173
] (for hyperelliptic curves) and was further developed
by Barreto, Galbraith,
´
OhEigeartaigh and Scott [
26
]. We present the idea in the ate pair-
ing formulation of Hess, Smart and Vercauteren [
258
]. Note that the ate pairing is not a
“new” pairing. Rather, it is a way to efficiently compute a power, of a restriction to certain
subgroups, of the Tate-Lichtenbaum pairing.
Let
E
be an elliptic curve over
F
q
and let
r
be a large prime such that
r
|
#
E
(
F
q
)
=
(
q
k
q
+
1
−
t
and
r
|
−
1) for some relatively small integer
k
,but
r
(
q
−
1). It follows
that #(
E
[
r
]
∩
E
(
F
q
))
=
r
. Since the Frobenius map is linear on the
F
r
-vector space
E
[
r
],
and its characteristic polynomial satisfies
x
2
−
tx
+
q
≡
(
x
−
1)(
x
−
q
)(mod
r
)
it follows that
π
q
has distinct eigenvalues 1 and
q
(mod
r
) and corresponding eigenspaces
(i.e., subgroups)
G
1
=
∩
ker(
π
q
−
[1])
,G
2
=
∩
ker(
π
q
−
E
[
r
]
E
[
r
]
[
q
])
.
(26.3)
(
q
k
1)
k
Since
r
|
−
1) and
q
≡
(
t
−
1) (mod
r
) it follows that
r
|
((
t
−
−
1). Let
T
=
gcd(
T
k
1
,q
k
t
−
1 and
N
=
−
−
1). Note that
r
|
N
. Define the
ate pairing
a
T
:
G
2
×
G
1
→
µ
r
by
f
T,Q
(
P
)
(
q
k
−
1)
/N
.
a
T
(
Q,P
)
=
2
√
q
and, typically,
r
q
. Hence, computing the Miller function
f
T,Q
typically requires at most half the number of steps as required to compute
f
r,P
.On
the downside, the coefficients of the function
f
T,Q
lie in
The point is that
|
t
|≤
≈
F
q
as before. Nev-
ertheless, the ate pairing often leads to faster pairings if carefully implemented (especially
when twists are exploited).
F
q
k
, rather than
Theorem 26.3.13
Let the notation be as above (in particular, T
=
t
−
1
and N
=
=
k
−
1
gcd(
T
k
1
,q
k
(
T
k
i
=
0
q
i
T
k
−
1
−
i
(mod
r
)
. Then
−
−
1)
). Let L
=
−
1)
/N and c
t
r
(
Q,P
)
L
(
q
k
a
T
(
Q,P
)
c
−
1)
/r
.
=
Hence, a
T
is bilinear, and a
T
is non-degenerate if and only if r
L.
