Hacker Newsnew | past | comments | ask | show | jobs | submit | graybanana's commentslogin

We have the same issue (billions of URLs). The newer bots that rotate IPs across thousands of IP ranges are killing us and there is no good way to block them short of captcha's or forcing logins, which we would really rather not inflict on our users.


I think the author's point is that while you might a priori think there are lots of groups out there that might be good candidates for DH, it turns out that elliptic curves are a strictly better choice than every alternative, and the reasons for this were definitely no fully known at the time Miller and Koblitz proposed ECC.

There was a period during which there was lots of interest in using abelian varieties of higher dimension (arising as Jacobians of curves of higher genus), with dimensions g=3 and g=4 being particularly attractive because then you could work over a very computationally friendly base field like Fp with p = 2^61-1. But it turns out the discrete logarithm problem (and therefore DH) is strictly easier in these settings (one can exploit Weil restrictions to get an algorithm that is still exponential-time but strictly better than O(p^(g/2)). But this wasn't known until the 2000's.

That leaves g=1 and g=2 as the best choices, and the group law is faster and simpler for g=1, and as far as I know nobody is really working on the g=2 case anymore (but there was a lot of activity in this area 10-20 years ago).


While not completely explained in the article, the author correctly notes that the non-singular points on a singular cubic curve over a finite field form a group (under the same elliptic curve group law) that is isomorphic (in an easily computable way) to either the multiplicative or additive group of a finite field.

You can find more details in Silverman's book on elliptic curves, or if you don't have access to that, see Section 24.7 in Lecture 24 of https://ocw.mit.edu/courses/18-783-elliptic-curves-spring-20....

One could nitpick by pointing out that singular cubics are not elliptic curves (which are, by definition, smooth projective curves). One could also nitpick that the real reason you don't want to use DH in the multiplicative group of a finite field is that there is a known subexponential time algorithm that breaks DH in that setting (forcing > 3000-bit key sizes) whereas for elliptic curves the only known attacks take exponential time (and 256-bit keys are fine). But I don't think either of these nitpicks contradicts the author's thesis.


While not mentioned by the author, there is an alternate reason why finite field DH can be seen as a special case of ECDH, kind of: namely, there exists special elliptic curves (actual, smooth projective curves) that do have an efficiently computable endomorphism to a suitable form of the multiplicative group, via pairings. This is in essence the MOV attack against the XTR cryptosystem. That doesn't fit neatly in OP's framework, though, because the map isn't a morphism of algebraic groups (it is efficient for other reasons), and it is cheating a little bit, because the inverse map isn't efficiently computable.

Another point that the author glosses over a bit is that higher dimensional abelian varieties offer other instances of DH that are genuinely different from ECDH, and that are occasionally useful (mostly the case of Jacobians of hyperelliptic curves of genus 2). There isn't really a trick to make an arbitrary hyperelliptic curve DH/abelian variety DH instance a special case of ECDH: if anything, the relationship would be in the reverse direction.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: