Research On High Performance Bilinear Pairing Algorithm And VLSI Implementation

Pairing-based cryptography is an emerging research field in public-key cryptography. For the last decade, cryptographic pairings have been creatively and widely employed to build novel and powerful information security schemes. Provided by pairings, People can have access to security tools that are unimaginable in traditional cryptography. However, due to the intricate mathematical structure, pairing computation is much more challenging compared with RSA and ECC. Therefore, the efficiency of pairing computation usually turns out to be one of the key factors in realizing a pairing-based security scheme.This thesis devotes to design a high-performance algorithms and VLSI implementation of pairing computation. The trade-off between performance and flexibility is made by integrating application-specific processor with dedicated crypto accelerators. A survey of pairing-based cryptography-history and the-state-of-the-art-is given at the beginning to picture pairing research status.A brief description of pairing theory from mathematical view is provided for better understanding of pairing structure and optimization techniques in following chapters. And techniques providing great efficiency improvements are summarized. Starting from extension field arithmetic, details of each technique is explained in the context of Miller algorithm. These theories and techniques may fulfill the basic requirements of implementing pairing.Through analyzing Miller algorithm, we propose two novel modular multiplication methods tailored to pairing computation based on the analysis of algorithm herirachy. Both of them are derived from Montgomery multiplication with quotient pipeline. The first one combines two modular multiplications to compute them in parallel and save partial products compression. A new architecture dedicated to this algorithm is proposed and integrated in the crypto-processor. Algorithm one provides high efficiency but suffers from data width extension. Another algorithm is then proposed to solve this problem by introducing Montgomery reduction.At last, a crypto-processor for pairing is introduced with detailed specification on each module. Operation parallelity and fine algorithm scheduling is exploited to abtain high through-put. The processor is fabricated using TSMC65nm technology. The chip achieves800MHz with266.5mW power consumption and a core area of2.51mm2, and computes an optimal Ate pairing (254-bit curve) in0.64ms. Based on this result, we further improve the architecture and gain higher through-put. The improved processor is synthesized using TSMC65nm technology, and256-bit pairing implementation is added for a comprehensive comparision with related works.