International Association
for Cryptologic Research

As hardware capabilities increase, low-power devices such

as smartphones represent a natural environment for the efficient

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 efficient computation

of the Optimal-Ate pairing over Barreto-Naehrig curves in software at

different security levels on ARM processors. We exploit

state-of-the-art techniques and propose new optimizations to speed up

the computation in the tower field and curve arithmetic. In

particular, we extend the concept of lazy reduction to inversion in

extension fields, analyze an efficient alternative for the sparse

multiplication used inside the Miller\'s algorithm and reduce further

the cost of point/line evaluation formulas in affine and projective

homogeneous coordinates. In addition, we study the efficiency of using

M-type sextic twists in the pairing computation and carry out a

detailed comparison between affine and projective coordinate

systems. Our implementations on various mass-market smartphones and

tablets significantly improve the state-of-the-art of pairing

computation on ARM-powered devices, outperforming by at least a factor

of 3.5 the best previous results in the literature.