3532 articles – 5253 references  [version française]

inria-00424016, version 2

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 60, 2 (2011) 266-281

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 $\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:  CARAMEL (INRIA Nancy - Grand Est / LORIA)
  • INRIA – CNRS : UMR7503 – Université de Lorraine
  • 3:  Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional (CINVESTAV)
  • Centro de Investigacion y de Estudios Avanzados del IPN
  • Domain : Computer Science/Cryptography and Security
    Computer Science/Computer Arithmetic
    Computer Science/Architecture
  • Available versions :  v1 (2009-10-16) v2 (2010-11-29)
 
  • inria-00424016, version 2
  • oai:hal.inria.fr:inria-00424016
  • From: 
  • Submitted on: Thursday, 25 November 2010 15:05:28
  • Updated on: Wednesday, 9 February 2011 17:03:06