Advances in Solving the Discrete Log Problem

At Eurocrypt this year, researchers presented a paper that completely breaks the discrete log problem in any field with a small characteristic. It's nice work, and builds on a bunch of advances in this direction over the last several years. Despite headlines to the contrary, this does not have any cryptanalytic application -- unless they can generalize the result, which seems unlikely to me.

Posted on May 20, 2014 at 6:13 AM • 13 Comments


GweihirMay 20, 2014 8:08 AM

Thanks for that comment. About what I expected, i.e. not a problem at this time and possibly not ever. I got the same impression from the paper, but this is far enough from my area of expertise that I could have been mistaken.

On a related note, what the press writes these days seems to be restricted to recognizing keywords, but actual interpretation, meaning or context seems to be far, far to complicated for them, making them worthless as a source. Basically the press is only useful to find out "something" has happened and the gross area it has happened in.

Jarrod FratesMay 20, 2014 3:19 PM

I've seen a few places mention that they broke two algorithms, but I can't seem to find out which ones. That would be useful information.

Nick PMay 20, 2014 3:37 PM

My decision to build on mostly symmetric algorithms and supplement with unusual public key methods (eg NTRU) is looking better all the time. I'm curious if there's a way to modify existing public key systems to add unbearable computational complexity to the person on the middle without much on other ends. Do for public key methods what Scrypt does for password hashing. Might be worth research as the attacks keep getting better.

Meanwhile, I'll keep recommending things I know will give hackers and cryptographers headaches with minimal user effort. :)

ThothMay 20, 2014 10:38 PM

@Nick P

If you were to agree on a set of code signals after you have done your Diffie-Hellman, you could send a bunch of random strings to each other that have been encrypted to spam the attacker until either of you reach an agreed timeout limit or either side sends a signal for the real deal to continue. No one's gonna guess it right ? :D :D

On a more serious note, properly arranged key exchange are best done in person without a doubt which is why important secrets are still handled by trusted couriers or in person.

These researches are interesting but they don't represent an actual break and the news media are always trying to find new stories ... nothing new as it's their business model.

JeroenMay 21, 2014 2:20 AM

I just finished watching the Black Hat 2013 presentation: The Factoring Dead: Preparing for Cyptopocalypse

They make the point that there have been some advances in solving DLP that are worrying, and that we really should start planning to move off of RSA now before it is being broken somewhere in the next 2-5 years.

TomMay 21, 2014 6:45 AM

So I read the paper and as expected didn't understand more than a few sentences. Then Bruce comes along, stating news outlets are exagerating or just wrong (as usual) and cryptography isn't broken, just as I expected.

I'm appreciating "Liars and Outliers" more from day to day. This is a matter of trust. Again.

How should people not interested/familiar with blogs like this handle these headlines? I'll tell you how they will handle them: Not even start with encryption at all, as it "isn't safe anyhow". The media's coverage of news like this is doing an immense amount of harm to the whole world.

GweihirMay 21, 2014 10:34 AM

@Tom: These things are difficult even for experts. Ordinary people basically have no chance of understanding anything. I mean, even here people claim nonsense like "RSA will be broken in the next 2-5 years", when there is absolutely no reliable indication of that happening. (The people claiming that at Black Hat 2013 just extrapolated things that you cannot extrapolate. If that worked, the last theorem of Fermat would not have been any problem at all. This utterly stupid approach has been used for Public Relation and "getting business by creating fear" before. It basically never pans out.)

This is of course a severe problem. When totalitarianism raises its ugly head again, as it has rather obviously been preparing to do the last decade or two do, the handful of experts are easily rounded up and interned, compromised or killed, and ordinary people will not have any chance of fighting that monster because not being able to communicate cripples any and all chances at resistance. It is just like the 3rd Reich, the DDR, the USSR and others like Northern Korea never happened. People really are stupid and do not learn from history.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Resilient Systems, Inc.