11–20 of 36 posts
Earlier quoted context omitted.
Elliptic Curves are one of the core mathematical constructs behind most of the commonly used non-RSA asymmetric cryptographic algorithms (curve25519, ed25519, ECDH, ECDSA).
But is there a particular reason like a news event that they're trending right now?
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0].
A group is a set of things, and a binary operation that satisfies certain rules.
At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-Hellman-Merkle-Williamson, or in factoring via Pollard P-1, use the fact that the numbers we are using are an example of a group.
The groups being used are usually:
* For DHMW, the integers modulo a large prime, or
* For RSA, the integers that are co-prime to the product of two large primes.
In each case the operation is multiplication modulo something.
So then we can ask if the same algorithms work if we use a different group instead, and whether the result will have better or worse characteristics. The answers to that are (1) yes, the algorithms work in other groups, and (2) it depends on the particular group or groups used.
So given an elliptic curve, it turns out that the points can form a group if we define a particular operation[1]. Then it turns out that the rational points form a group. Then we can convert that to work modulo a prime, and we end up with a finite group.
And that's exactly what we need to use some of our algorithms.
The question of whether this group is better depends, and is too long to fit in a single HN comment, but the main point is that there are many possible elliptic curves to choose from, and many possible primes to use, and so we have more choice. That alone makes it worth considering.
But the answer turns out to be yes, some of the algorithms have better characteristics on these new groups. For example, using elliptic curves we can use smaller keys for RSA or DHMW, and the elliptic curve version of Pollard P-1 is now the third fastest known factoring algorithm, and probably fastest over a certain range of sizes.
I would be happy to answer any questions, either here or by email.
[0] https://en.wikipedia.org/wiki/Group_(mathematics)
[1] And augment the points, and avoid certain pathological curves
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
Ignoring many important details ... Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0]. A group is a set of things, and a binary operation that satisfies certain rules. At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-He…
With recent(ish) leaks about what the NSA is doing in terms of breaking widely-available crypto, the question has arising about what weaknesses might exist in current classical techniques. RSA and DHMW have been around for a long time, and much is known about specific weaknesses. Some primes need to be avoided, for example in DHMW one should avoid primes P where (P-1)/2 has lots of small factors.
But all the elliptic curve cryptography is comparatively new, and weaknesses are still being found. It's plausible that there are simple things to avoid when choosing an elliptic curve, and so perhaps we should just use the elliptic curves recommended to us by security experts.
But after Snowdon, etc., people are becoming wary of trusting experts, so they want to know more about the implications of their choices, and what options they might have. This is an on-going issues, and now, as people are starting to understand the mechanics of implementing systems that use elliptic curves instead of just Z_p, so articles are being written aimed at the non-security-community people.
And so articles appear that are readable and relevant.
Just my $0.02
the profusion of posted slides on the internet is a detriment to researchers everywhere. so many times i've googled something technical (CS, math, engineering) and what percolates to the top are lecture slides, which are almost useless for actual in depth learning. edit: spoke too soon - only the first link is slides.
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
[edit: this paragraph, based on my old notes on the subject, seems to be incorrect, see sdevlin's comment below] More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength. Elliptic curve solutions also tend to be more computationally efficient, both in terms of key generation as well as encryption operations; this performance delta increases rapidly as "equivalent" key sizes grow.
Regarding "trending":
-- They're under active fundamental research, which is fun (RSA is well established, whereas new EC proposals are still under active debate)
-- They've been the subject of some drama, which is also "fun" (conspiracy theories related to several EC proposals/recommendations, debates regarding a primary EC researcher, etc)
Earlier quoted context omitted.
can you explain to me why an elliptic curve over C is a quotient manifold (like the torus on page 7 of the first set of slides)?
I would expect him to spell this out in lectures 15 and 16. It does take work. What is surprising is that despite their all looking the same -- certainly they are the same as real manifolds -- there are tons of elliptic curves. The difference is in the complex analytic structure.
Earlier quoted context omitted.
It believe mathematicians will continue to favor boards. Sitting in the audience I greatly prefer this; however, such lectures have less chance of being posted at all. For this topic we are lucky to have Silverman's book [1], which everyone seems to like. [1] https://www.math.brown.edu/~jhs/AECHome.html
can you explain to me why an elliptic curve over C is a quotient manifold (like the torus on page 7 of the first set of slides)?
[1] - https://www.amazon.com/Complex-Algebraic-Mathematical-Societ...
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?
That is the feature, it means they can define a binary operator that given two points returns a point, the third intersection with a line. This opens up a Pandora's gift.
Earlier quoted context omitted.
I would expect him to spell this out in lectures 15 and 16. It does take work. What is surprising is that despite their all looking the same -- certainly they are the same as real manifolds -- there are tons of elliptic curves. The difference is in the complex analytic structure.
They (the space of complex points on any elliptic curve over C) are the same (homeomorphic) as topological spaces. However, they are not the same as complex analytic manifolds, which is a stronger condition (requiring an analytic isomorphism, not just a topological one).
Of course, I've learned a lot about these things from your writings.