3543 articles – 5273 Notices  [english version]

inria-00424016, version 1

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

Jean-Luc Beuchat () a1, Jérémie Detrey () b2, Nicolas Estibals () c2, Eiji Okamoto () a1, Francisco Rodríguez-Henríquez () d3

IEEE Transactions on Computers (2010)

Résumé : 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 $\F_{2^m}$ and $\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.

• a –  University of Tsukuba
• b –  INRIA
• c –  Université Henri Poincaré - Nancy I
• d –  Insituto Politécnico Nacional
• 1 :  Laboratory of Cryptography and Information Security (LCIS)
• University of Tsukuba
• 2 :  CACAO (INRIA Lorraine - LORIA)
• CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
• 3 :  Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional (CINVESTAV)
• Centro de Investigacion y de Estudios Avanzados del IPN
• Domaine : Informatique/Cryptographie et sécurité
Informatique/Arithmétique des ordinateurs
Informatique/Architecture
• Versions disponibles :  v1 (16-10-2009) v2 (29-11-2010)

• inria-00424016, version 1
• oai:hal.inria.fr:inria-00424016
• Contributeur :
• Soumis le : Mardi 13 Octobre 2009, 16:54:46
• Dernière modification le : Jeudi 25 Novembre 2010, 14:59:08