Compact flexible and fast coprocessor design for elliptic curve pairing operation on reconfigurable hardware

Official URL: http://192.168.1.20/record=b1378277 (Table of Contents)

Proposal of Identity-Based cryptography by Shamir in 1984 opened a new area for researchers. Failing to provide a feasible implementation of identity based encryption (IBE), Shamir developed a signature scheme, whereby signatures can be verified by publicly available information such as signer's identity. Since the first efficient implementation of IBE realized using pairing operation on elliptic curves due to Boneh and Franklin a plethora of papers has been published and many studies have been conducted covering different aspects of pairing-based cryptography. Today, pairing is used in many cryptographic applications including, identity based cryptography, key exchange protocols, short signatures, anonymous signatures and in many other newly emerging protocols and schemes. Also, pairing is still a developing research field yielding important challenges for the research community. Pairing computation involves fairly complicated operations compared to classical symmetric and asymmetric cryptosystems. Multitudes of pairing types have been proposed after its first appearance in the literature. Also, each of them involves selection of many parameters such as the choice of the underlying field and its characteristics, order of the embedding degree, type of the elliptic curve etc. Therefore, different types of optimisations are possible rendering selection process extremely difficult. Because of the abundance of choices, for an efficient pairing implementation many criteria have to be examined. For instance, selection of pairing type, construction of finite fields and elliptic curves, coordinate systems to represent points on the curve and algorithms and architecture for arithmetic operations play a crucial role on the performance of the specific implementation of the pairing-based cryptography. A multitude of implementations regarding to pairing-based cryptography have been proposed in the literature. However, most of them are software realizations; the reason being is the complexity of the overall system. Some hardware implementations have already been proposed, but most of them are very specific, therefore lacks flexibility and scalability. Due to the complexity of the system, some researches advice to use dedicated implementations for specific set of parameters even in software, limiting the flexibility of the implementation further. In this thesis, we propose a very generic, flexible and compact hardware coprocessor for all kinds of pairing implementations intended for implementation on reconfigurable devices (e.g. FPGA). Our co-processor supports all types of pairing operations with different parameter classes via making use of highly-optimized hardware implementations of basic arithmetic operations common not only to pairing operations, but also to elliptic curve cryptography and other public key cryptography algorithms. Our design utilizes the idea of hardware-software co-design concept. To accelerate pairing computation we implement some units responsible for performing the most time-consuming operations as a generic, but highly optimized hardware circuits, whereas we prefer to implement some complex parts (unworthy of hardware resources) in low-level software of micro-instructions. Although we use two arithmetic cores running concurrently, our design still manages to be compact thanks to its careful and generic design.