ZK8: An introduction to Hasse's theorem/cool facts about elliptic curves – Ariel Gabizon - Aztec

Transcript

Well, after our fun at KVM, the next talk is by Ariel Gabizon, the chief scientist at Aztec Network. He's going to talk a little about Hasse's theorem and some of the important underlying primitives of elliptic curves that are used in almost all blockchain today. Thanks very much. Uh okay. Thanks a lot for coming. Uh So, let me first address the question of why why to talk about a basic math theorem at ZK Summit. Um And if I have to make an argument for it, it would be that my hope is that,

you know, by opening a little the elliptic curve black box beyond just being a group with hard discrete log and the bilinear pairing some sometimes, we can get interesting results for SNARKs. So, just two two recent examples are this first work of a way to prove that like a Pedersen hash is correct without actually computing it in the circuit, but instead using this classic theorem about something called principal divisors. And another example that got a lot of attention in our sort of field is this work of of the StarkWare people uh of how how to get FFT-like algorithms even when we don't have our beloved

subgroup of order that is a power of two. Uh yeah. Uh right. What what is Hasse's theorem? So, so say we have some elliptic curve over a field FP. And and we ask the question, how many points are there on the curve over FP? And I'll let's denote that number by capital N. Uh so, we know that n is at least one because we always have what's called the identity of the curve or the point at infinity.

And we know that n is at most 2p + 1. Why? Because right, every value we put in for x there's going to be only at most two options for y. Uh, so Hasse's theorem tells us that this number n is going to be very close to p actually. So, if we denote uh the difference bet- a as the difference between p + 1 and n, then this difference is actually going to be at most 2 * √p.

So, this is uh, very foundational for elliptic curve cryptography cuz it tells us, say we want a curve of a a certain size, say size roughly 2 to the m, so how do we get such a curve? Uh, well, we can just pick any prime p with m bits and just take any elliptic curve over fp and we're guaranteed it'll have size roughly 2 to the m. Of course, it's not sufficient for elliptic curve cryptography cuz we'll want a prime order uh, group of this size, uh, but it's it's foundational uh, for it.

So, let me walk you through some some of the parts of the proof of this theorem and hopefully show you some interesting elliptic curve uh, facts on the way. Uh So, the proof begins with some junior high algebra in a sense. So, again, we're denoting by A the difference between the field size plus one and the number of points on the curve over FP. And this polynomial is going to accompany us for the the the the whole talk. This polynomial L, which is x squared

minus ax plus p. So, the coefficient of x is like the difference between the field and the curve size um inverted and the constant coefficient is the field size. So, engrave this polynomial in your in your mind. Uh and I claim that it's enough to show that if the roots of this polynomial this is just polynomial over the integers, not a finite field. It's enough to show that the roots of it are not real numbers.

Um Why is that? Because uh So, again, going back to junior high uh math, right? We always we compute the discriminant when we want the solutions of a quadratic, which is here going to be a squared minus 4p. So, right? When there's no real solutions, we know that this discriminant is negative. And that's exactly going to show us that the absolute value of A is smaller than 2 square root p.

Cool. Uh Uh right. So, So, let's as a sort of warm up and something we'll use later, let's show that we want to show the roots aren't real. Let's show they're uh, they're at least not integers. So, so let's write right, we know L we can write it as a product of linear forms uh, over the just the complex numbers.

It has some roots. Uh, and and right and we know that then the the constant term is going to be the product of the of these roots. And A is going to be the sum of them just by right, multiplying out the this these products. So, since uh, P is prime, then uh, there's only going to be basically two options for omega one and omega two.

Uh, the first one is that they're going to be one right, that P is prime and then they have to they have to be a factors of P. So, the only options are that they'll be like for example one and P. But, if that's the case, then A which is their sum will be P plus one. And since A is the the difference between the field and the curve, it will mean that there's no points on the curve. But, we know that the there's always at least one point on the curve, the infinity point.

So, this can't happen. And similarly, you can rule out the second option which is minus one minus P. So, so this tells you that the roots of L are not at least not integers. And we'll use that a bit later. So So now the next thing we're going to take a little detour. Then the next thing is going to be to show where we want to we want to know what are the roots of L over the complex numbers. The next thing is going to be sh showing that a certain what's called

endomorphism is a root of L. So we're going to need to talk about endomorphisms for for a few minutes. Uh So So what are endomorphisms? So this is like a definition I read 10 times and each time I would forget what's the what's the definition of it. Like uh It's all the things with phisms in the end would just mix in my in my head. So the way I I remember it, it's like it's homomorphisms, which is easier to remember. It's just any map that respects the group law.

Uh but that sort of know the group they're working with is an elliptic curve. So So what does that mean? Uh it means Yeah, the map respects the the group law as we you know, we've probably seen many times. Uh but the the knowing that it's an elliptic curve, it means that also this map we can if we look at the coordinates of the elliptic curve point uh we can represent the home the this homomorphism by rational functions in the coordinates of the of the curve.

Right, and this bar here is we're looking at points solutions on the curve, not just over FP. Uh but over the closure, so over F coordinates in FP squared, FP cubed, and then so forth. Uh and an important point is that we can think of these endomorphisms as a ring.

So right, for that we need to define multiplication of two of these. And multiplication is naturally going to be composition. So like psi 1 * psi 2, what what is that? That's going to be just psi 1 composed inside with psi 2. Right? And just as a little exercise, if if if both of these are expressed as rational functions, then definitely when we compose them, they can still be uh expressed as rational functions. So let's use this little notation. We'll use it towards the end. End E is the endomorphisms of the curve.

And it's a ring, it has addition and multiplication. Cool. Uh So let's look at two There's basically two examples of endomorphisms. Uh the first one is just this scalar sort of scalar multiplication. So we take a point P and for some integer we output C * P. Uh and basically the reason this is an endomorphism is right, we have we have equation we have equations for doing doubling and addition on on a curve. So, using that we can express c * p as some rational functions of the

coordinates. Uh so, the second example uh uh is what's called the Frobenius endomorphism. So, this is like uh when you're taking the point xy and mapping it to the point x to the p y to the p. Right? So, first of all, we see clearly it satisfies the third condition, right? We're expressing it as rational functions by definition.

Uh So, one thing to that maybe is confusing in the first in the first you're like, wait, isn't this the identity map cuz x to the p is just x? So, here it's crucial that like we're we're looking at points over the algebraic closure. So, this isn't just the identity map, right? And And interesting thing is sort of looking at the curve over the closure, it'll allow us to finally get this bound on the number of points over fp, which is what we want. Uh so, so let's do a little exercise to to see that this is really an endomorphism. So, basically, the reason it it is is that

uh we we have this this little formula also for right that a + b to the p even when the points are not in fp, but in an extension is a to the p + b to the p. And so, let's see that let's see, you know, for example, like one thing an endomorphism has to satisfy is if it map it maps a point on the curve to another point on the curve. So, so let's see let's see that that holds. So, let's start with some point XY on the curve. So, it's on the curve so it satisfies this thing.

So, if this is zero then I take it to the P it's also zero. Uh And now because of this right this linearity of this raising to the power P, I can basically shove all the all the P's inside. Uh and right when I shove them inside I when it's something that's actually an FP like these coefficients A and B then the P just just disappears. Uh So, what what is what is this give us?

It gives us that if X the point XY is on the curve so also the point X to the P Y to the P is on the curve. Right. Uh so so here's the I'm going to basically right in this overview I'm going to use two you know heavy artillery two big sort of cannons that you know their their proof is a whole thing but uh the first sort of you know

heavy artillery I'm using is this uh theorem or lemma that this endomorphism this Frobenius endomorphism is actually sort of a root of this polynomial. What what does it mean for the endomorphism to be a root of the polynomial? It means that if now right we we showed how to do multiplication as composition. So, if we're going to look at now this endomorphism, like phi squared minus a times phi, right? A times phi is like do Frobenius and then do scalar multiplication by a.

Uh plus p, so this is going to be the all zero map on the curve. This is going to map all the curve to the point at infinity. Or to see this more explicitly, it means that for any xy on the curve, even one with coordinates in some, you know, big extension of fp, if you look at this point, like xy raised to the p squared minus a times xpy p plus p times xy, this is going to be the identity point on the curve for for any point, even uh over the closure.

Uh and just I felt I should, you know, mention SNARKs. So, uh maybe something interesting for SNARK optimization. I mean, we usually look at curves for, you know, over a prime just a prime field, but if we'll ever look ones over p squared or whatever, uh maybe a nice little uh bit is that right? You want to get, say, p times your point. Uh so, p so you can actually get it by a times your point, right? Where a, the number of bits in a is just half of of compared to p. Um minus uh minus this x to the p squared y y to the p squared.

So, so this gives you some shortcut of getting p times uh xy. Okay, so we're almost we're almost there. So we've we've shown or well, we've seen that this endomorphism this Frobenius endomorphism is is a root of L in in some sense.

But we want like actual we want like to show that an imaginary number is also a root of L. So so we need some way to map these endomorphisms to complex numbers. Um And this is where this theory of what's called complex multiplication comes in. So what it gives us is there's going to be some isomorphism from this ring of of endomorphisms

to some subring of the complex numbers. This ring I call here RE. And the the crucial point is that RE it's a subring of of complex numbers, but its intersection with the reals is only Z. So more specifically R is going to be all the points that you can write as Z plus Z times D for some imaginary number D.

And now I claim to you so this right this this T is going to map the Frobenius endomorphism to some complex number to some number in RE, I claim to you that this number is is also going to is going to be a root of L. Uh why? Because the fact that T is an isomorphism uh right? It so it sort of commutes with addition and multiplication. So so if you you write it out, you see you can replace the the T and L. You can compete commute them.

And now so you have T of of L of uh L of phi. L of phi, we know it's just the zero map. And now right? So T is a an isomorphism, so it's going to What is it going to map the zero map to? It's just going to map it to to zero. Uh So so this number that is mapped to from Frobenius uh let's call it omega, it's going to be an actual root of L.

So now right? We want to claim that it's a it's an imaginary number. Uh Well, we've shown before in our warm-up that a root of of L cannot be an integer. So it's in RE, it's not an integer integer so so the only right? So it's not it's it can't be real. There's no other real numbers in RE, so it must be an imaginary number. And uh we're done, right? This This means that discriminant is is negative and and we we've got we've got the the Hasse bound.

Uh Yeah, so that's uh that that's it. Uh how much How much time do I have left? 5 minutes? Oh okay. Uh So So yeah, so basically that's it. Uh I I do I do have So, one little slide of just a I'll do a a little rant of historical So, what where where did this theorem come from that the the endomorphisms are uh you know, equivalent to uh to this some imaginary ring in the complex numbers. So, So, it it came from sort of the 19th century uh where people

were studying elliptic curves over over complex numbers. Not over finite fields like we do in cryptography. And then there's this really cool equivalence. Maybe you've seen that all elliptic curves over complex numbers, they're they're equivalent to toruses or So, basically the the complex numbers modulo a lattice. And then the endomorphisms there correspond to complex numbers that that that preserve the lattice, that don't If you multiply anything in the lattice, it stays in the lattice.

Uh and sort of what happened was uh you know, Hasse was trying to prove this and and peo- people Hasse and others were were like, "Okay, maybe this whole theory of complex multiplication, maybe it also actually works over fields of characteristic P." And uh and yeah, and turn turns out it it does and they worked hard to to prove it. Um And So, where where does this polynomial L come from? Uh so, yeah, very you know, I'll say very roughly, it's it's related to what's called the the zeta function of the of the elliptic curve. So, right, there's this whole Riemann hypothesis

where you want to prove that the non-trivial roots of uh uh of the Riemann the Riemann zeta function all have like uh real part half. Uh right, and it's very hard question. So, people were looking for okay, maybe for other zeta functions we we can prove it that the the roots are there. And it turns out that yeah, for the a zeta function of a elliptic curve is much easier to work with. And then proving that, you know, the same thing about the roots of the uh a zeta function of elliptic curve, it it exactly me implies that the the roots of you know, these roots omega one, omega two

we were working with uh they're they they have um uh they they they have like uh absolute value square root P. Um right, which which also right, gives us gives us you know, this bound cuz this A was the sum of them. Uh yeah so uh I I I I used yeah uh for prepare this this book the first book you probably all heard of the the second book is yeah, I also recommend to to look into it. It has a lot of interesting anecdotes uh also just in doing math in Europe during the sort of beginning of World War II or

just before that. So, a lot of interesting personal anecdotes. And uh yeah, thank you very much. Hey, we got time for one or two questions and then we got right for lunch. But uh yeah, so I think a mic is coming around. Uh if you have a question, please speak into the mic for the recording's sake. Thank you. And if folks could try not to leave in too large a number before the question is done, I think it'll be helpful. But we'll wrap up in 5 minutes.

It's it It's not working. Okay. I'll speak out loud. Thank for wonderful talk, Ariel. It's of course very sad that we haven't started on this torus stuff of complex numbers from the very beginning. I love this how torus is storing storing guys the 30 condition. Um actually a serious question. All these endomorphisms uh you talk about and this Frobenius endomorphism actually from the security perspective I wonder can it happen that we discover so many endomorphisms easily computable that discrete log becomes easy in curves?

They've got like so many kind of relations that relate kind of seemingly unrelated points and how does it happen that like everything becomes breakable if you find too many relations like this? Uh yeah, I don't know. That's that's an interesting question. Uh yeah, I don't know. Uh yeah, yeah. Um

I don't Yeah. I I don't know I don't know how to imagine it. Uh Sorry. It's not a very satisfying answer. Um I don't I don't know. Yeah, uh so since I come from the crypto side uh my Yeah, I guess my knowledge of beyond what I the slides is uh not deep or for the question. Sorry. Yeah. Does the other root of alpha have any significance?

Uh we found Frobenius that was useful as one of the roots was Yeah, that is a lot of complex conjugation. Yeah. Right. Sure. Yeah, so so in in the complex numbers it's going to be the conjugate. Yeah, so I wonder what endomorphism the the other root corresponds to. Yeah, that's an interesting question. I don't know. Uh but but which

which automorphism exactly? Um right, so the question yeah, the conjugate which exactly automorphism is it going to um correspond to? The the what, sorry? The the involution. So you have this automorphism that squares to minus one. And every elliptic curve comes with it, and I guess it's the equivalent to complex conjugation when you do it over finite fields.

Uh okay. Uh Yeah, no, I guess the the question is not what the conjugation corresponds to what like this the conjugate of Frobenius, what what what does it look like as an endomorphism? Yeah, I was saying that it's simply Frobenius composed with this involution involution. Right, but what is what is the involution look like on the curve? I guess like what mapping is it exactly? Uh Oh, just X Y to X minus Y?

Oh, okay, so you're saying the the the conjugate to Frobenius is maps XY to X to the P minus Y to the P maybe. Yeah, yeah, that makes sense. That makes sense. Yeah, probably it's that. Awesome, time for we're going to take a break for lunch. Thanks. Thanks a lot.