Notes

The first technique we investigate is computing inverse in extension fields by
using towers of extension fields and successively reducing inverse computation to
subfield computations via the norm map.We show that this technique drastically
reduces the ratio of the costs of inversions to multiplications in extension fields.
Thus when computing the ate pairing, where most computations take place in
a potentially large extension field, the advantage of projective coordinates is
eventually erased as the degree of the extension gets large. This happens for
example when implementing pairings on curves for higher security levels such as
256 bits, or when special high-degree twists can not be used to reduce the size
of the extension field.
The second technique we investigate is the use of inversion-sharing for pairing
computations. Inversion-sharing is a standard trick whenever several inversions
are computed at once. As the number of elements to be inverted grows, the
average ratio of inversion-to-multiplication costs approaches 3. Inversion-sharing
can be used in a single pairing computation if the binary expansion is read from
right-to-left instead of left-to-right. This approach also has the advantage that it
can be easily parallelized to take advantage of multi-core processors. Inversionsharing
for pairing computation can also be advantageous for computing multiple
pairings or for computing products of pairings, as was suggested by Scott [41]
and analyzed by Granger and Smart [25].
Ironically, although the two techniques we investigate can be used simultaneously,
it is often not necessary to do so, since either technique alone can
reduce the inversion to multiplication ratio. Either technique alone makes affine
coordinates faster than projective coordinates in some settings.
To illustrate these techniques, we give detailed performance numbers for a
pairing implementation based on these ideas. This includes timings for base field
and extension field arithmetic with relative ratios for inversion-to-multiplication
costs and timings for pairings in both affine and projective coordinates, as well
as average timings for multiple pairings and products of pairings. In our implementation,
affine coordinates are faster than projective coordinates even for
Barreto-Naehrig curves [8] with a high-degree twist at the lowest security levels.
However, we expect that for other implementations, the benefits of affine coordinates
would only be realized for higher security levels or for curves without
high-degree twists.
The paper is organized as follows: Section 2 provides the necessary background
on the ate pairing and discusses the costs of doubling and addition steps
in Miller’s algorithm. In Section 3, we show how variants of the ate pairing
can benefit from using affine coordinates due to the fact that the inversion-tomultiplication
ratio in an extension field is much smaller than in the base field.