Faster discrete log algorithm and your internet security

STORY BY Artem Kaznatcheev

Published: June 21, 2013

Significant progress has been made toward an efficient algorithm for computing discrete logarithm – a problem whose assumed difficulty to solve underlies much of modern cryptography. On June 18th, Razvan Barbulescu, Pierrick Gaundry, Antoine Joux, and Emmanuel Thomé published a quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic.

When you send any message on the internet, like the one requesting to see this article, the packet bounces from one router to the next until it finds its destination. At each point along the way, anybody can open your packet (say your local malicious hacker or the NSA), inspect its content, and learn what you sent. Yet you still feel comfortable entering your credit card number on Amazon or other big vendors; are you simply trusting that everybody in the internet is honest and nice, and nobody will look at the information you sent?

Not quite, you actually use a techology called public-key cryptography to encode your message. Since Amazon and you can't meet in a dark alley to share a private secret to encode messages, you instead rely on computational complexity: the hope that some functions are easy to compute in one direction, but very hard to invert. The two most common – and closelty related -- problems in use for this are factoring and discrete logarithm. For example, it is easy to take two prime numbers and multiply them together, however it is much more difficult to take a large composite number and find two numbers to multiply to form it. The RSA cryptosystem is based on this.

Similarily in a finite field – a finite set of elements with two special elements called 0 and 1 and operations + and * that behave as we expect, in particular for every element a there are element b and c so that a + b = 0 and a*c = 1 – it is easy to do repeated multiplication (exponentiation) but hard to figure out given an element b, how many times you have to multiply b by itself to get some number a. Cryptosystems like the ElGamal in GNU Privacy Guard, Diffie-Hellman key exhange, the US government's digital signature algorithm, and modern elliptic curve cryptography are based on this task.

If somebody found an algorithm to quickly compute discrete logarithm then they could break all these cryptosystems and make your internet transactions insecure. Obviously, this is an important problem for computer scientists and on Tuesday, June 18th significant progress was published. Razvan Barbulescu, Pierrick Gaundry, Antoine Joux, and Emmanuel Thomé released an algorithm that could compute the discrete logarithm in finite fields of small characteristic in quasi-poynomial time. Although this is not the holy-grail of computer science efficiency (polynomial time), it is a huge and innovative improvement. Algorithmic economics pioneer Noam Nisan commented: "this result should cause a small drop in the share price of Internet companies that rely on RSA encryption and such (e.g. Amazon)" because ideas on factoring and discrete-log often go hand-in-hand and this could set off a cascade of improved algorithms.

Fields medalist Timothy Gowers wrote about the new algorithm: "One of the nice things about being a mathematician is that from time to time there are clusters of exciting breakthroughs" and 2013 has been an exciting cluster so far, first the resolution of the odd Goldbach conjecture, major progress on the twin primes, the Kadison-Singer conjecture and now this. For an overview aimed at experts, take a look at Galbraith's blog post.

Other Stories by Artem Kaznatcheev
[^] comments powered by Disqus

Have a topic you want covered? Let us know.