Departamento de Computación

Pairing-based cryptography is a novel and extremely active area of research which is at the core of elegant solutions to a number of long-standing open problems in cryptography. In the mid-nineties, Menezes, Okamoto & Vanstone and Frey & Rck introduced the Weil and Tate pairings in cryptography as a tool to attack the discrete logarithm problem on some classes of elliptic curves defined over finite fields. A few years later, Mitsunari, Sakai & Kasahara, Sakai, Oghishi & Kasahara, and Joux discovered constructive properties of pairings. Their seminal works sparked an extensive study of pairing-based cryptography, and a rapidly-growing number of protocols based on the Weil or Tate pairings have appeared in the literature: identity-based encryption, short signature, broadcast encryption, and key exchange in wireless sensor networks to mention but a few. Such protocols rely critically on efficient algorithms and implementations of pairing primitives.

At first, it was thought that the rich fine-grained parallelization potential shown by hardware platforms could be exploited in order to produce faster and more compact pairing implementations. Through the years, this assumption has been confirmed in many research works. However, in the last few years a second wave of authors have investigated the challenges associated with the efficient implementation of pairings in software platforms. From the results reported by those research works, it appears that software pairing libraries can sometimes compete with their hardware counterparts. Furthermore, yet another way to exploit parallelism can be instrumented when the multi-core architectures introduced just recently by Intel are targeted. Multi-core architectures can be seen as a massive way to obtain parallelism via the concurrent usage of powerful individual processors that are tightly interconnected.

After a short introduction to pairing-based cryptography, we describe the design of a fast multi-core library for the cryptographic Tate pairing over supersingular elliptic curves. Our approach is based on a careful and simultaneous study of the different relevant fields, ranging from theoretical foundations (number theory, computer arithmetic, etc.) to practical considerations (computer architecture, SSE instruction set, etc.). The performance of our library appears to be the fastest pairing timings yet reported.