Gurleen Grewal, Reza Azarderakhsh, Patrick Longa, Shi Hu, and David Jao
As hardware capabilities increase, low-power devices such as smartphones represent a natural environment for the eﬃcient implementation of cryptographic pairings. Few works in the literature have considered such platforms despite their growing importance in a post- PC world. In this paper, we investigate the eﬃcient computation of the Optimal-Ate pairing over Barreto-Naehrig curves in software at diﬀerent security levels on ARM processors. We exploit state-of-the-art techniques and propose new optimizations to speed up the computation in the tower ﬁeld and curve arithmetic. In particular, we extend the concept of lazy reduction to inversion in extension ﬁelds, analyze an eﬃcient alternative for the sparse multiplication used inside the Miller’s algorithm and reduce further the cost of point/line evaluation formulas in aﬃne and projective homogeneous coordinates. In addition, we study the eﬃciency of using M-type sextic twists in the pairing computation and carry out a detailed comparison between aﬃne and projective coordinate systems. Our implementations on various mass-market smartphones and tablets signiﬁcantly improve the state-of-the-art of pairing computation on ARM-powered devices, outperforming by at least a factor of 3.7 the best previous results in the literature.
In Conference on Selected Areas in Cryptography (SAC 2012)
Publisher Springer Verlag