Cryptography: Making elliptic communication cryptic

The Partnership for Advanced Computing in Europe (PRACE) released its new annual report last week. The article below is a 'success story' taken from this report...

The quantity of sensitive information now regularly exchanged over the Internet might astound previous generations. This places high demands on secure data handling. Encrypted data exchange generally requires a key sequence that can be used to encode and decode the transmitted data. The challenge is to develop encryption protocols where this key cannot be cracked by a third party attempting to intercept the data exchange. To this end mathematicians have been working to identify problems which are relatively simple to confirm given the solution, but hard or impossible to solve without it.

“All the keys we are using in cryptography fit into this scheme,” explains Antoine Joux, a  researcher at the University of Versailles in France.  His work investigates the use of ‘discrete logarithms’ in cryptography. “Take an integer x and a number  mod P and calculate J to the power x,” he explains. “This is easy to compute but finding x (given the  value of J and J to the power x) is difficult. Finding x is  called finding the discrete logarithm.” 

Yet, although finding x is “difficult”, progress in the development of more efficient algorithms over the past 20 to 30 years have raised questions over the security of cryptography protocols based on this kind of discrete logarithm known as ‘finite field’ logarithms. As a result large key sizes are required for implementing these cryptography protocols. The increasing tractability of these problems to solution has stimulated research in a different type of discrete logarithm based on elliptical curves.

“An elliptic curve is a very classical mathematical object, which has been used in mathematics since the 19th century”, explains Joux. The points on such a curve can be handled just like usual numbers, in the sense that you can add them, using a fixed recipe, which is not complicated at all to use (but took quite a lot of mathematical sophistication to figure out in the first place). Given a fixed point P on the curve, you can then easily find P, P+P, P+P+P and so on. What is difficult, though, given another point Q on the curve, is to determine how many times you have added P to itself to obtain Q (even if you are given the information that Q is the result of adding P to itself a finite number of times). “There is no easy way to do this”, says Joux.

Finding this value in elliptical curve problems is described as the elliptical curve discrete logarithm and has been used in cryptography since the mid 1980s. In fact with their added complexity these protocols provide cryptographic keys, which are now used in secure shell (SSH, a network protocol for secure communication) and smart cards and are significantly more efficient than those based on finite field discrete logarithms. “Nowadays I think most governments recommend using at least 2000 bits key size,” says Joux referring to cryptography protocols based on finite field discrete logarithms. “For elliptical curves the equivalent recommendation is around 256 bits.”

In fact, some of Professor Joux’s recent research has suggested that some elliptical curve discrete logarithms may in fact be less difficult to solve than had been previously believed. He and his colleague Vanessa Vitse, now assistant professor at the University of Grenoble, have worked on a type of elliptical curve found over a finite field of P to the power 6. They showed that by transforming the problem to a different curve over a smaller field two previously reported methods of attacking the problem could be combined to find a solution, clearly compromising its security. “And we showed this by just computing the discrete logarithm for a curve of this form at sizes which should not have been possible,” says Joux.

This sort of research is very important. “By doing this kind of cryptography you remove branches that are hopeless,” he explains. It prevents people working to optimise protocols—finding specific ways of computing in the cryptographic path more efficiently or making the smart card algorithm smaller—when the protocol is not secure in the first place. “What you want to do is to remove the dead ends.”

Joux’s collaboration with Vitse in this work also typifies the size of collaborations in this field. Researchers working on similar problems span most of the world including Germany, France the UK and Canada, and many other countries. Yet broadly international collaborations seem rare. “It’s much easier to collaborate on the theoretical ideas than it is when you are dealing with real-life implementations,” explains Joux. “Because you need quite a close-knit team if you want to programme it all and run it on a machine.”

He also emphasises how the field has benefited from the development of cluster computing, where several machines may run in parallel. “You can have 1,000 machines run for a day to see if something will work or not,” explains Joux. “With classical computers it would take months or a year to confirm an idea but with the big machine you can get confirmation very quickly which is very useful for research.” To date, the researchers have been awarded 750,000 hours on each of the CURIE FN, CURIE TN (both at GENCI @CEA) and JUGENE (GCS@ Jülich) supercomputers.

His current research is moving away from the elliptical curves and revealing further limitations of finite field discrete logarithm cryptography. “I really think it is no longer a good option unless you use a really huge key,” he concludes, providing examples of the key sizes that have been solved and hence found no longer secure. “Just to give you an idea of the dimensions, right now the record is close to 2000 bits.” In fact, just a few days after our interview, Joux was able to announce that he had succeeded in work on a much larger record of over 4000 bits. In this exciting and ever evolving field, it seems the bar for secure complexity is constantly rising.

The full PRACE annual report can be read online here.