An efficient hardware implementation of the tate pairing in characteristic three

Abstract

Discrete Logarithm systems with bilinear structure recently became an important base for succesful cryptographic protocols such as identity-based encryption, short signatures and multiparty key exchange. Since the main computational task is the evaluation of the bilinear pairings over elliptic curves, which is known to be prohibitively expensive, efficient hardware or software implementations are required to render them applicable in real life scenarios. In this thesis, an efficient accelerator for computing the Tate Pairing in characteristic 3, based on the Modified Duursma Lee algorithm is presented. Accelerator implemented shows that it is possible to improve the area-time product by roughly 12 times on Field Programmable Gate Array (FPGA), compared to estimated values from one of the best known hardware architecture implemented on a same type of FPGA. Also the computation time is improved up to 16 times compared to software applications reported. In addition, the result of an ASIC implementation of the algorithm is presented, which is the first hitherto. Both implementation results show that pairing based cryptosystems can be used even on constrainted devices such as smartcards.