How hard is Discrete Logarithm, really? (Joux's Algorithm)

[Ken_g6]

Possibly not as hard as we thought!

http://www.technologyreview.com/news...curity-crisis/

However, it is possible that algorithms able to solve the discrete logarithm problem quickly could exist.... Earlier this year, French academic Antoine Joux published two papers that suggest such an algorithm could be found before long. “This is a big deal, since there was marginal progress for 25 years,” said Samuel. “This will spur researchers into looking more closely at the problem and most likely result in more progress.”

One reason to believe that progress will be swift, says Samuel, is that Joux’s advances weren’t based on inventing completely new techniques. Rather, he applied known tricks that hadn’t previously been used on this specific problem.

So, does this mean we'll soon be proving primes by factoring them? (I'm guessing even ECPP will be faster in most cases.)

Does this mean we'll soon have faster sieves? (I'm guessing there's a good chance?)

This all seems to stem from Joux's algorithm and a related paper, which I only found reference to in a Soap Box thread.

[CRGreathouse]

Can any of our crypto experts weigh in here? I would have thought that the restrictions to small characteristics would have been too strong for this algorithm to be used for cryptanalysis. Don't most schemes (ElGamal, Diffie-Hellman, DSA) use where this is inapplicable? Does this affect Rijndael/AES or is the mixing sufficient protection?

[R.D. Silverman]

Originally Posted by CRGreathouse

Can any of our crypto experts weigh in here? I would have thought that the restrictions to small characteristics would have been too strong for this algorithm to be used for cryptanalysis.

It is. You are correct. All of the random speculation about the imminent
end of DL based crypto is just that: random speculation.

Further, even for fields such as (say) GF(2^607), we don't know if the
improvement makes attacks on such field(s) practical.

The improvement does not seem applicable to NFS at all.

Don't most schemes (ElGamal, Diffie-Hellman, DSA) use where this is inapplicable? Does this affect Rijndael/AES or is the mixing sufficient protection?

It does not affect AES at all.

[CRGreathouse]

This is why I love this forum.

[R.D. Silverman]

Originally Posted by CRGreathouse

This is why I love this forum.

Generally speaking the speculation comes from people who don't
know the subject material.

NFS was first developed for the IFP. It was then modified to be applicable
to DL over (large!) prime fields. It was not directly applicable to extension
fields.

Enter the function field sieve (and Coppersmith's algorithm [for p =2]). It handles GF(p^n) for large n and relatively small p. Various improvements
have allowed attacks on larger p and somewhat smaller n, but the FFS is
not applicable to large prime fields.

Historically, the algorithms have been driven by attacks on IFP then
adapted to DL. Further, the IFP attacks have applied only to prime fields.

The random speculation arises from people who think that somehow an
improvement for small characteristic fields will translate to large prime
fields (thus making RSA & DH more vulnerable). Historically, it's been the
other way around.

[Primeinator]

Originally Posted by R.D. Silverman

Generally speaking the speculation comes from people who don't
know the subject material.

NFS was first developed for the IFP. It was then modified to be applicable
to DL over (large!) prime fields. It was not directly applicable to extension
fields.

....

The random speculation arises from people who think that somehow an
improvement for small characteristic fields will translate to large prime
fields (thus making RSA & DH more vulnerable). Historically, it's been the
other way around.

Is there a pocket RD Silverman app?

[Ken_g6]

It's baaaack!

The security of a variant of the discrete logarithm, reputed to be very complex, has been called into question by four researchers from CNRS and the Laboratoire d'Informatique de Paris 6 (CNRS/UPMC), namely Pierrick Gaudry, Răzvan Bărbulescu, Emmanuel Thomé and Antoine Joux (3). The algorithm they devised stands out from the best algorithms known to date for this problem. Not only is it significantly easier to explain, but its complexity is also considerably improved. This means that it is able to solve increasingly large discrete logarithm problems, while its computing time increases at a far slower rate than with previous algorithms.

This result, published on the site of the International Association of Cryptologic Research and on the HAL open access archive, was presented at the international conference Eurocrypt 2014 held in Copenhagen on 11-15 May 2014 and published in Advances in cryptology.

So, anybody who knows about discrete logs want to look this paper up and help us understand if it means anything? Edit: And if it's any significant improvement over the previous result?

[R.D. Silverman]

Originally Posted by Ken_g6

It's baaaack!





So, anybody who knows about discrete logs want to look this paper up and help us understand if it means anything? Edit: And if it's any significant improvement over the previous result?

Are you too lazy to read it yourself?

I have already read it. It has almost zero impact on applied cryptography.

[philmoore]

Originally Posted by Ken_g6

It's baaaack!

So, anybody who knows about discrete logs want to look this paper up and help us understand if it means anything? Edit: And if it's any significant improvement over the previous result?

Just wanted to point out that this paper is the same one linked to in post 1, although a more recent version. I tend to agree with RDS that the Science Daily article appears to be just some more recent hype about research that has been in the public eye for some time and not referring to any more recent publications.

[R.D. Silverman]

Originally Posted by philmoore

Just wanted to point out that this paper is the same one linked to in post 1, although a more recent version. I tend to agree with RDS that the Science Daily article appears to be just some more recent hype about research that has been in the public eye for some time and not referring to any more recent publications.

ken_g6 asked the same question LAST AUGUST that he asked two
days ago. Why, I don't know.

The implications were already discussed last August. There is virtually
no impact on cryptography. DH does not use high-degree low characteristic fields. ECDSA & EL-GAMAL can, but it is not required.
The use of these two is rather rare. (especially the latter).

Crypto Suite B contains no algorithms that depends on DL over
finite fields.

I still have not seen a discussion anywhere as to whether the
improvement is practical. We all know how implementation overhead
can kill an algorithm, even one with reduced asymptotic complexity.

[CRGreathouse]

Originally Posted by R.D. Silverman

I still have not seen a discussion anywhere as to whether the
improvement is practical. We all know how implementation overhead
can kill an algorithm, even one with reduced asymptotic complexity.

It looks like it is practical, yes:
http://arxiv.org/abs/1402.3668