Software Implementation of the Cryptographic Tate Pairing

Software Implementation of the Cryptographic Tate Pairing

Dr. Jean-Luc Beuchat 

Texto completo de la Conferencia   

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.


Esbozo Curricular

Jean-Luc Beuchat received the MSc and PhD degrees in computer science from the Swiss Federal Institute of Technology, Lausanne, in 1997 and 2001, respectively. He is an associate professor in the Graduate School of Systems and Information Engineering, Laboratory of Cryptography and Information Security, University of Tsukuba, Tsukuba, Japan. His current research interests include computer arithmetic and cryptography. He has published several journal and international conference papers. He has won two times, in 2007 and 2009, the best paper award in the premiere cryptographic conference Workshop on Cryptographic Hardware and Embedded Systems.