3 ms·
To clarify some of these points further: - As mentioned elsewhere in the discussion, the algorithm does have an impact on some elliptic curve-based cryptosyste
by mti 12y ago
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).