Paper 2012/408

Efficient Implementation of Bilinear Pairings on ARM Processors

Gurleen Grewal, Reza Azarderakhsh, Patrick Longa, Shi Hu, and David Jao

Abstract

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.7 the best previous results in the literature.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pairing based cryptographyBN curvesARM processors
Contact author(s)
razarder @ math uwaterloo ca
History
2012-07-25: revised
2012-07-24: received
See all versions
Short URL
https://ia.cr/2012/408
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/408,
      author = {Gurleen Grewal and Reza Azarderakhsh and Patrick Longa and Shi Hu and David Jao},
      title = {Efficient Implementation of Bilinear Pairings on ARM Processors},
      howpublished = {Cryptology ePrint Archive, Paper 2012/408},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/408}},
      url = {https://eprint.iacr.org/2012/408}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.