Paper 2009/398

Fast Architectures for the $\eta_T$ Pairing over Small-Characteristic Supersingular Elliptic Curves

Jean-Luc Beuchat, Jérémie Detrey, Nicolas Estibals, Eiji Okamoto, and Francisco Rodríguez-Henríquez

Abstract

This paper is devoted to the design of fast parallel accelerators for the cryptographic $\eta_T$ pairing on supersingular elliptic curves over finite fields of characteristics two and three. We propose here a novel hardware implementation of Miller's algorithm based on a parallel pipelined Karatsuba multiplier. After a short description of the strategies we considered to design our multiplier, we point out the intrinsic parallelism of Miller's loop and outline the architecture of coprocessors for the $\eta_T$ pairing over $\mathbb{F}_{2^m}$ and $\mathbb{F}_{3^m}$. Thanks to a careful choice of algorithms for the tower field arithmetic associated with the $\eta_T$ pairing, we manage to keep the pipelined multiplier at the heart of each coprocessor busy. A final exponentiation is still required to obtain a unique value, which is desirable in most cryptographic protocols. We supplement our pairing accelerators with a coprocessor responsible for this task. An improved exponentiation algorithm allows us to save hardware resources. According to our place-and-route results on Xilinx FPGAs, our designs improve both the computation time and the area-time trade-off compared to previously published coprocessors.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Tate pairing$\eta_T$ pairingelliptic curvefinite field arithmeticKaratsuba multiplierhardware acceleratorFPGA
Contact author(s)
jeanluc beuchat @ gmail com
History
2009-08-19: revised
2009-08-15: received
See all versions
Short URL
https://ia.cr/2009/398
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/398,
      author = {Jean-Luc Beuchat and Jérémie Detrey and Nicolas Estibals and Eiji Okamoto and Francisco Rodríguez-Henríquez},
      title = {Fast Architectures for the $\eta_T$ Pairing over Small-Characteristic Supersingular Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2009/398},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/398}},
      url = {https://eprint.iacr.org/2009/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.