Elliptic Curves

https://math.mit.edu/classes/18.783/2015/lectures.html

by CarolineW • 9 years ago

122 34 9 years ago

math.mit.edu

ice1092• 9 years ago

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.

stablemap3• 9 years ago

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

ice1092• 9 years ago

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

zitterbewegung• 9 years ago

When I was doing research projects for my undergraduate degree we primarily used the web differently. 0. First thing we would search is the Arxiv front end http://front.math.ucdavis.edu/ . Usually we would have a researcher in mind. If we didn't then we would look at Wikipedia. 1. We would use wikipedia to get general knowledge and information about the topic. Sometimes lecture notes and presentations would be looked at too but we would eventually get to papers. 2. If the topic was relevant after getting the gist we would look at the citations on wikipedia and track down authors. 3. Books we would obtain electronically. Papers would be tracked down on Arxiv. 4. Rinse and repeat if you didn't understand a topic that was cited in any of the other steps.

lukejduncan• 9 years ago

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?

baobrien• 9 years ago

Elliptic Curves are one of the core mathematical constructs behind most of the commonly used non-RSA asymmetric cryptographic algorithms (curve25519, ed25519, ECDH, ECDSA).

v64• 9 years ago

But is there a particular reason like a news event that they're trending right now?

ColinWright4• 9 years ago

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

ColinWright4• 9 years ago

As to why they are trending ...

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

ColinWright4• 9 years ago

A smidgen too late to edit the comment to add this ...

One advantage of ECC (Elliptic Curve Crypto) is that the keys are smaller, and hence it's easier to implement on resources constrained devices such as smart-cards and IoT devices.

gogoengie2• 9 years ago

Regarding importance, it provides an efficient alternative to RSA.

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

sdevlin2• 9 years ago

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.

This isn't correct.

The reason RSA (and classic DH) keys are gigantic is because index calculus techniques yield efficient attacks on systems based on finite fields. We need big keys to make them impractical.

EC systems are not susceptible to these attacks because the points on a curve comprise only a group and not a field. Counterintuitively (to me, at least!), they're safer because they have less structure.

williamstein2• 9 years ago

As a side note, the author of the linked notes on elliptic curves (at MIT) co-founded a successful tech startup company in the 1990s involving high speed networking, then only much later went back to grad school and became a computational number theorist.

fibo• 9 years ago

From a math point of view are interesting cause since are equations of third grade, any line in a projective space will intersect them in three points.

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.

number-sequence• 9 years ago

Yes, elliptic curves are huge in cryptography, but they are also mathematically significant. They are the degree three nonsingular algebraic plane curves with at least one rational point. This makes them essentially "one step up" from the conic sections. The conic sections, of course, are well understood including the parametrization of their rational points. However, elliptic curves are much more subtle! We do not even have proven algorithms for determining the size of any elliptic curve's set of rational points, and in specific the algebraic rank of that set. The Birch and Swinnerton-Dyer conjecture is one of the millennium prize problems, and it relates elliptic curves' algebraic ranks to their analytic ranks. Elliptic curves are also very related to modular forms, and this connection is part of the theory that allowed Andrew Wiles to prove Fermat's Last Theorem. In the study of the rational solutions to integer polynomial equations, i.e. Diophantine Analysis, elliptic curves are one of the next stepping stones that must be more thoroughly understood before we can have a more complete understanding of polynomials in general. Their applications in cryptography and integer factorization are huge in applied mathematics, but they are also incredibly important subjects to fields like algebraic geometry, diophantine analysis, and of course, number theory.

aswanson• 9 years ago

Comments like this make me really, really wish I had majored in mathematics.

801699• 9 years ago

"... they're trending..."

they date back to the 80's.

to predict the future, some look to the past for ideas.

others monitor the present e.g. github commits for popular projects - reject anything that has no recent activity.

the context is per packet encryption, the space and time needed to do it.

this is not the approach taken by tls where one compromised packet can compromise the entire "encrypted stream". nor is the approach taken by dnssec where instead of encrypting some third party gives their blessing to (signs) the data being communicated.

elliptic curve crypto is not new. but encrypting each and every packet on the internet separately is "new" (or at least "different" from current practice).

this is my understanding. i could be wrong.

Elliptic Curves

Related Stories