LACAL researchers set a new cryptanalysis record

The 'Discrete Logarithm Problem' (DLP) is a hard computational problem that has been studied for over a century and has been of immense importance to cryptography since the invention of public key cryptography in 1976. A significant proportion of our secure online transactions -- not to mention numerous other applications -- depend on variations of the DLP, so it is essential that this problem is very difficult to solve. One variation of the DLP which uses complex mathematical maps on objects known as `supersingular curves' was proposed back in 2001 and has been seriously considered for deployment in practical applications. Systems of this type that meet the industry-standard security level were believed to be so difficult to break, that it would require all of the world's computational resources more than 40,000 times the age of the universe to break them. Such astronomical time-spans imbue a very high level of trust in the use of such systems, which is an essential prerequisite before individuals, corporations, industries and governments have the confidence to use them.

One approach to solving the DLP which goes back to the 1920's consists of two key stages. If both of these stages can be made efficient, then the DLP becomes easy. Since the early 1980's there has been virtually no progress in this field, with both stages remaining very hard. However, just one year ago this particular type of DLP began to buckle under the pressure of a series of algorithmic breakthroughs that had the potential to prevent these systems from ever being deployed. Robert Granger and his colleagues at University College, Dublin, showed that the first stage can in fact be solved very easily. A French team led by Antoine Joux subsequently made the second stage `very nearly' easy. A rapid series of DLP computational records ensued in ever larger fields as these new methods were explored and tested for the first time. One drawback of these computations was that the DLPs studied were of a very special kind, and it was not at all clear whether the fledgling techniques could be applied effectively to the parameters featured in the literature.

The research team focused on two systems in particular, which were both designed to be industry-standard secure, and discovered several practical improvements to the new algorithms. The first system was believed to maintain its security even in light of the new methods. However, they showed that it would only take a year using EPFL's computational resources to solve the DLP. The second system had already been shown to be slightly weaker, but still far beyond the practical range of computation. However, the researchers were able to demonstrate the complete insecurity of this system, by solving an example DLP in the equivalent of two hours with EPFL's computational resources. These results imply that all such systems should never be used in practice, as suspected once the new methods were discovered.

Robert Granger has been a scientist at LACAL since October 2013. His research focuses on the number theoretic assumptions and applications underlying public key cryptography.
Thorsten Kleinjung joined the lab in 2008 as a postdoctoral researcher. His research interests include integer factorization, discrete logarithms and related areas.

Read here to find out more on the project.