4 ms·

There's some confusion going on here. This algorithm: - Has nothing to do with elliptic curves. - Has virtually zero repercussions in any real-world cryptosys

by pbsd 12y ago

There's some confusion going on here. This algorithm: - Has nothing to do with elliptic curves. - Has virtually zero repercussions in any real-world cryptosystem. - Is a mostly theoretical refinement of the 'cryptopocalypse' Joux algorithm, which only affects some special kinds of fields (namely small characteristic). - Is only being reported again now because the paper has just been presented at Eurocrypt. Here are some previous threads on the subject: https://news.ycombinator.com/item?id=6240434 https://news.ycombinator.com/item?id=6240434

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).
dang 12y ago
Thanks for clarifying this. We'll bury the post as a dupe.
DCKing 12y ago
None of the terminology or mathematics used seems to be specific to integer groups to my limited understanding. Could you explain why this has nothing to do with elliptic curve groups?
- tptacek 12y ago
  One start: http://crypto.stackexchange.com/questions/8301/trying-to-better-understand-the-failure-of-the-index-calculus-for-ecdlp http://crypto.stackexchange.com/questions/8301/trying-to-bet...
djmdjm 12y ago
AFAIK the relation to EC is that pairing-based cryptography is a popular (among academics at least) user of GF2m elliptic curves.
- tptacek 12y ago
  We're getting way past my comfort level, but the impact of the recent DLP attacks on pairing curves is because they involve mapping the curve problem into a multiplicative finite field, right? The DLP attacks themselves don't directly impact the ECDLP.

by pbsd 12y ago

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).

dang 12y ago

Thanks for clarifying this. We'll bury the post as a dupe.

DCKing 12y ago

None of the terminology or mathematics used seems to be specific to integer groups to my limited understanding. Could you explain why this has nothing to do with elliptic curve groups?

tptacek 12y ago
One start: http://crypto.stackexchange.com/questions/8301/trying-to-better-understand-the-failure-of-the-index-calculus-for-ecdlp http://crypto.stackexchange.com/questions/8301/trying-to-bet...

djmdjm 12y ago

AFAIK the relation to EC is that pairing-based cryptography is a popular (among academics at least) user of GF2m elliptic curves.

tptacek 12y ago
We're getting way past my comfort level, but the impact of the recent DLP attacks on pairing curves is because they involve mapping the curve problem into a multiplicative finite field, right? The DLP attacks themselves don't directly impact the ECDLP.