International Association
for Cryptologic Research

In this paper, we describe and improve efficient methods for computing

the hard part of the final exponentiation of pairings on Barreto-Naehrig

curves.

Thanks to the variants of pairings which decrease the length of the Miller

loop, the final exponentiation has become a significant component of the

overall calculation. Here we exploit the structure of BN curves to improve

this computation.

We will first present the most famous methods in the literature that en-

sure the computing of the hard part of the final exponentiation. We are

particularly interested in the memory resources necessary for the implementation of these methods. Indeed, this is an important constraint in

restricted environments.

More precisely, we are studying Devegili et al. method, Scott et al. addition chain method and Fuentes et al. method. After recalling these methods and their complexities, we determine the number of required registers

to compute the final result, because this is not always given in the literature. Then, we will present new versions of these methods which require

less memory resources (up to 37%). Moreover, some of these variants are

providing algorithms which are also more efficient than the original ones.