2015-12-22



Not directly. It looks like the papers in question are

Antoine Joux, “A new index calculus algorithm with complexity [math]L\bigl(\tfrac14 + o(1)\bigr)[/math] in very small characteristic”, Cryptology ePrint Archive, Report 2013/095;

Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé, “A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic”, Cryptology ePrint Archive, Report 2013/400.

These are very impressive results indeed, but they are not immediately applicable to practical Diffie-Hellman cryptography, which is performed in a field with very large characteristic ([math]\mathbb F_p[/math] for a large prime [math]p[/math]).

The relevance to RSA is even more tangential. There is an easy reduction from factorization of an RSA modulus to the discrete logarithm problem over that modulus. However, finding discrete logarithms over a composite modulus remains just as hard as factoring the modulus and finding discrete logarithms over the prime factors, so this doesn’t seem likely to be a fruitful path toward breaking RSA. See also Michael Hamburg’s comment.

Joux’s results are likely to spark further research in this area, and it’s always possible that related research will eventually yield improved attacks on Diffie-Hellman over larger characteristic. But I wouldn’t worry that modern cryptography is in serious danger of being broken any time soon.

Read other answers by

Anders Kaseorg on Quora:

How would you show that there is a number in the set [math] \left\{2^1 - 1, 2^2 - 1, 2^3 -1,....,2^{98} -1\right\} [/math] which is divisible by 99?

Are there any odd perfect numbers?

Can we have a number system with the base pi?

Show more