New algorithm shakes up cryptography

Alternative interpretation: Gotta love how European research funded by tax-payer euros enters the public domain — as it should.

Fwiw, on this side of the pond some are somewhat bemused by how e.g. US big pharma firms are allowed to patent research results that were funded by tax-payer dollars.

He's referring to the previous work of Joux, such as this: https://eprint.iacr.org/2013/095.pdf.

"Today's" result is an improvement over that and previous works. So what we know is that attacks on curves over GF_{2^m} are getting better.

Why wouldn't a researcher publish? It's one of the only ways to advance your career as an academic.

I haven't read the new paper†, but the original Joux paper that this refines didn't apply to the ECDLP. ECDSA and ECDH don't rely on the hardness of the DLP; they rely on the hardness of the ECDLP. Part of the point of the ECDLP is that it is less amenable to classical lines of attack on the DLP, like index calculus, from which this algorithm is derived.

See also https://news.ycombinator.com/item?id=7759441 --- who, as always, knows what he's talking about.

† Edit: 'pbsd suggests there may not be one.

To clarify some of these points further:

- As mentioned elsewhere in the discussion, the algorithm does have an impact on some elliptic curve-based cryptosystems, but it is an indirect one. The attack is against the discrete logarithm problem in small characteristic finite fields; that isn't a security concern for the elliptic curve DLP (even over fields of small characteristic), except in the special case when ECDLP reduces to finite field DLP. That reduction is called the Menezes-Okamoto-Vanstone attack, and only applies to a restricted class of elliptic curves: so-called "pairing-friendly" curves, which are used in pairing-based crypto.

- In particular, the attack has no impact on even small characteristic NIST curves, or basically on any curve used for "traditional" (as opposed to "pairing-based") elliptic curve cryptosystems, including ECDH, ECDSA, ECIES, etc.

- On the other hand, the paper is a huge deal for people interested in the implementation of pairing-based crypto / cryptographic bilinear groups, because small characteristic fields (mainly supersingular curves over GF(3^m)) were the preferred approach for implementation in hardware, and even in software if you wanted symmetric pairings. Joux's original L(1/4) paper meant that people had to take a closer look at the trade-off between characteristic 3 and large characteristic in hardware (and it was also very important as the most significant algorithmic advance on the DLP since GNFS), but it wasn't quite "apocalyptic". This paper, on the other hand, has a quasi-polynomial attack, which means pairing-based crypto in small characteristic is dead (and more generally, symmetric pairings have become very unattractive).

- Whether this affects "real-world crypto" depends on were you set the limits of the real world.　SSL connections and credit cards are unaffected, sure, but there are limited deployments of things like group signatures that have to take a close look at the math used in their implementation.

- The first preprint did appear publicly last summer, so it's true that this is not fresh news to the community, although I think it's great that this result gets some publicity beyond academic circles (and IMHO it fully deserves its best paper award).