3 ms·
I found your comment interesting, especially the Miller '85 reference. You certainly don't come across as condescending, so don't worry about that. You are of
by xyzzyz 9y ago
I found your comment interesting, especially the Miller '85 reference. You certainly don't come across as condescending, so don't worry about that.
You are of course right that extra structure helps with solving DLOG. I was hoping that you could point me to some specific reasons why DLOG is easier on real/complex curves. I'd be very interested in learning these.
I don't find a "nice smooth curve vs. scatterplot" argument very convincing by itself -- you only care about a cyclic subgroup anyway. Take a complex elliptic curve, viewing it as a torus consider its fundamental parallelogram, and plot a cyclic subgroup on this parallelogram. Won't you get a nice scatter plot just the same?
Even if you can use this extra structure to find some more efficient DLOG algorithms, you could try to apply the same solution as with the crypto based on multiplicative groups of finite fields: just use larger points. My understanding so far is that the reason we don't do it is purely computational efficiency -- I'd be very interested in learning any reasons to think the contrary.
And, back to the original point, I think that the drawings of real/complex curves are very helpful when learning the basics. The group law is really best understood if you actually draw some lines intersecting the real affine part of some curve, show what happens when you draw a tangent line etc. If you confine yourself to finite fields, while it formally works just the same, the geometry is much less obvious, and talking to beginners about Cartier divisors and line bundles won't help much.
While the finite fields are the whole point of elliptic curve cryptography, they are definitely not the whole point of elliptic curves, and in fact I believe that complex case with all the extra structure is best for educational purposes.
- red_admiral 9y agoI'm afraid I don't have a neat answer to why your first question. I did find the Koblitz paper I meant earlier but it's more about why one particular attack won't work: https://link.springer.com/article/10.1007/s001459900040 https://link.springer.com/article/10.1007/s001459900040 There are other reasons beyond efficiency why I would prefer people to switch their DLOG crypto to EC in practice: it's hard enough to implement - even with introductory blog posts with images - that your average developer leaves the details to an expert. libsodium for example is very well designed and written and few people think "I know, I'll write my own Curve25519 implementation" but lots of people seem to think that they understand finite fields well enough to build crypto, after all they have a bignum library and a modexp function, what could possibly go wrong?. I've seen finite-field discrete log software that is supposed to be production ready with the following problems: * Non-constant time implementation of "schoolbook" square-and-multiply. * Forgetting to check if points really are in the group, e.g. you're supposed to be working in a q-order subgroup of Z^*_p where q | (p-1)/2 but the software accepts any integer less than p as a group element. * Crash or infinite loop if you pass 0 as a "group element". * Parameters can be specified or overridden by the sender of a message and set to tiny values. * Not checking whether the modulus is prime.