Cryptography Reference
In-Depth Information
The basic principle of Vercauteren's construction is to find a multiple
ur
,forsome
u
∈ N
, of the group order that can be written in the form
l
M
i
q
i
ur
=
(26.6)
i
=
0
where the
M
i
∈ Z
are “small”. One can then show just like with the ate pairing that a certain
power of the Tate-Lichtenbaum pairing is
l
g
i
(
P
)
(
q
k
−
1)
/r
l
f
M
i
,Q
(
P
)
q
i
(26.7)
i
=
0
i
=
1
where the functions
g
i
take into account additions of certain elliptic curve points. Ver-
cauteren proves that if
l
iM
i
q
i
−
1
(mod
r
)
(
q
k
−
1)
ukq
k
−
1
≡
r
i
=
0
then the pairing is non-degenerate. The value of equation (
26.7
) can be computed efficiently
only if all
f
M
i
,Q
(
P
) can, in some sense, be computed simultaneously. This is easiest when
all but one of the
M
i
are small (i.e., in
) or when the
M
i
have a large common
prefix of most significant bits (possibly in signed binary expansion).
Vercauteren [
554
] suggests finding solutions to equation (
26.6
) using lattices. More
precisely, given
r
and
q
one considers the lattice spanned by the rows of the following
matrix
{−
1
,
0
,
1
}
···
r
00
0
−
q
10
···
0
−
q
2
01
···
0
B
=
.
(26.8)
.
.
.
.
.
.
.
q
l
−
00
···
1
One sees that (
u,M
1
,M
2
,...,M
l
)
B
(
M
0
,M
1
,...,M
l
) and so candidate values for
u,M
0
,...,M
l
can be found by finding short vectors in the lattice. A demonstration of
this method is given in Example
26.6.3
.
Note that loop shortening methods should not be confused with the methods, starting
with Scott [
481
], that use an endomorphism on the curve to “recycle” some computations
in Miller's algorithm. Such methods do not reduce the number of squarings in Miller's
algorithm and, while valuable, do not give the same potential performance improvements
as methods that use loop shortening.
=
26.3.5 Pairing lattices
Hess [
257
] developed a framework for analysing pairings that is closely related to the
framework in the previous section. We briefly sketch the ideas.
