A Karatsuba Algorithm Based Accelerator for Pairing Computation

Elliptic curve cryptosystem costs smaller calculation complexity compared with RSA. Identity Based Cryptography is a state-of-art scheme in all the elliptic curve cryptosystems. Bilinear pairing calculation over elliptic curves is the most time-consuming part which is also the pivotal to build IBC schemes. We dedicated this paper to the study of accelerating pairing computation. The proposed design uses Karatsuba algorithm-based multiplier and exploits parallelism at different layer of extension field. On the other hand, some algorithm-level techniques are used for square for F
_q
12. Finally, the design is implemented on Xilinx Virtex-6 platform with the verification the R-ate pairing computation used in Identity-Based Algorithms SM9 issued by China, takes only 5.83ms. The results also outperform the performance using OpenCL.