A new algorithm for more secure cryptographic exchanges
© Inria / Photo Kaksonen
Last December in Seoul the article "Counting points on genus 2 curves with real multiplication" by Pierrick Gaudry (LORIA/Caramel project-team), David Kohel (Institut de Mathématiques de Luminy) and Benjamin Smith (Grace team, formerly Tanc) won (jointly) the prize for best article at AsiaCrypt 2011, one of the three most important international conferences on cryptology.
"Counting points on genus 2 curves with real multiplication" demonstrates a real step forward in the field of cryptography. The need to encipher information to transmit it securely is increasingly felt in the digital world, to establish secure communications, to prove identities on line or even to sign digital documents. To do this, the most common method used is a public-key cryptosystem, which is the opposite of a private-key system where the two parties who wish to exchange information must also exchange their private keys. In the case of public-key systems, each instance, for example each digital signature, is based on one example of a very difficult mathematical problem and the system's security depends entirely on the difficulty involved in solving it. To ensure the difficulty of these problems "point counting" algorithms are used to verify the security of the future cryptosystem.
The state of the art in public-key cryptography was based, until now, on problems with elliptical curves. Google, for example, uses them for its secure web pages. Recently, researchers have focused on genus 2 curves as an improved version and a successor to elliptical curves. Yet while genus 2 curves have wonderful theoretical properties, there was a significant obstacle preventing their practical use: in many cases (particularly the case of the prime field) their point counting algorithms are simply far too slow. By way of comparison, it is possible to count the number of points on an elliptical curve in just a few seconds. Up until now the same calculation with a genus 2 curve required several hours, which made them impossible to use as well as to experiment with.
In this paper, the researchers presented a new algorithm for a practical class of genus 2 curves that represents a radical improvement in point counting performance. Indeed, the new algorithm works so well that it shattered the world record in counting points on genus 2 curves (in the case of the prime field). Thanks to this innovation in computing security, it is now easier to construct appropriate genus 2 curves for modern cryptosystems.