Paper 2015/192

Memory-saving computation of the pairing final exponentiation on BN curves

Sylvain DUQUESNE and Loubna GHAMMAM

Abstract

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.