zkStudyClub: Halo optimisations and constructing graphs of elliptic curves by Daira Hopwood

Transcript

So, welcome to this week's ZK study club. Today we have sort of the part two of the Halo study clubs that were started last week with Sean. Today we have Dara Hopwood who's going to be speaking about Halo optimization and constructing graphs of elliptic curves. Take it away. Hello and welcome. [laughter] Welcome everyone. Um okay. Uh I'm I'm Darra. Um I'm a cryptographic engineer at um Electric Coin Company. Um there are my usernames and this is the um the GitHub repo with the slides and um some animations and some uh some code. Um there's also a bit of code um in the

derweedle um repo as well. Um so um the outline of the talk um we're going to sort of discuss what a graph of elliptic curves is and why they're useful um and how to construct them. Um so so what are the obstacles to doing that? Um and it turns out that uh we'll need a a category of curves called um curves with complex multiplication. um those make it relatively easy to find cycles. Um then we um we talk about um other properties you might want um at

the curves like tuidicity which is useful for um certain proving systems um of more complex graphs. Um and hopefully if the demo gods are with me then um some live coding in Sage Math um to to show you how to to solve part of the problem for some new arbitrary new um uh curve that you want to construct a cycle for. Um and then we go on to um halo optimizations. So describing what um um halo and sonic circuit model is um how to do scala multiplication in circuits um how to optimize it even further um

and then doing fiat shamir in a circuit okay so let's um carry on um so what do I mean by a graph of elliptic curves um we've got it's a directed graph Um so we've got a set of vertices that are going to be the uh the primes um defining um our fields um so the field of definition of each curve and then the edges between those primes um represent the curves themselves. So we we draw an edge from one prime to another. Um so from P to Q when the

field of definition is P is FP and um we have an an order Q prime order subgroup. Um so that's FQ is where we're going to be doing the cryptography in the proving system. Um so yeah uh okay and we assume that um our proof system using this curve can efficiently support circuits over FQ.

Um okay so why would we need anything other than um a simple two cycle? Um well sometimes uh we want pairing friendly curves for our proof systems um and so um that's um a a functionality that we wouldn't get um just from a simple cycle. So I've drawn the the pairing friendly curves here in green. Um this on the top left is just um cycle of normal curves that aren't pairing friendly. Um as used for Halo. Um then below it we have uh can you see my um

pointer by the way? We can. You can. Oh, excellent. Yes. Um so this one is half pairing cycle. So one of the codes is pairing friendly. Um, and this is something like the cycle um in the original um BCTV 14 paper where this could be an MNT4 cycle uh MNT4 MNT6 um so something like that. And then you got things like um you have one pairing friendly curve, you um construct another one on top of it with Cox Pinch or whatever construction you want. Or this one here is um like we use in um sapling. We have pairing friendly curve

like BLS 12381 and then another um normal curve called uh which is jo in the case of sapling. Um and here this is um something a little bit more interesting that I've been working on recently. um I don't know whether we're going to need it but um the idea is that you have um a halo cycle and then on top of one of those curves you have um a pairing friendly curve. So that means that you can say you wanted to use gr 16 uh to prove something about um halo proof then you could use this kind of construction and I call this an inverted lollipop.

um just because of the shape and because uh we were originally trying to find um so the the opposite construction where you you start with a small um curve and then you go up to a cycle. Um but it turns out that that's very difficult to construct and we don't know how to do it. So this is one thing that you can do instead. Okay. So, why do we need cycles? Darra, could you could you go back?

Uh, for this uh cycle in the middle with the black and the green arrow, is there an application? That's not a cycle. Um, oh, no, no, uh, sorry, in the left side. The middle of the left side. Yep. Is there an application for that? So, you have one pairing friendly and one non-pairing. Um, so the So, this is actually used by the pickles proving system. Um I I don't know if we've got Isaac Mler or um I I can't see who's on the call. Um but um ask him about this kind of um construction and why it's useful. Um the the idea is that you can um do succinct proofs within the cycle.

So um the pairing friendly curve you could use um say plunk or got 16 or something like that. Um you obviously that that comes up with the trade-off that you need a trusted setup for the pairing friendly proof system normally. Um but it can be useful for efficiency. Thank you. And Darra uh so when you talked about the inverted lollipops you mentioned that that was uh an alternative to something else which didn't work out.

What was the other thing? The other thing would have been um you start with a a chain of pairing friendly curves. So like we have here um and then with a cycle on top. Okay. So it looks like a lollipop. Okay. And I don't know how to make those. Um so um why do we need cycles? Um so we assumed that our proof system could directly support arithmetic over FQ where where Q is the prime order. Um but if we want to do arithmetic with the the wrong fields and not FQ um that has an overhead of um over a thousand times. So

um I worked it out for um say another 256 bit field and it's something like um 1200 times um or sorry 1,200 constraints in R1CS um to do a reduction in the wrong field um and that's explained in this ticket. Um so we we can um use something like pluckup which is a way of doing tables in um the plunk like proof systems. Um and that does help a lot because we can um how this this works the sum of residues reduction is you um

you take each bit in the partial product and you reduce it independently and um then add them up. Um, so what Pluckup allows you to do here is to define tables so you can process more than one bit at once. But the the cost of those tables is um it's proportional to the table size. So exponential in the table width or the number of bits you're processing at once. So um you end up still having a um a very significant overhead because you can't use very large tables.

Um um for Halo anyway, we want to minimize the cost of the recursion um subcircuit. That's that's part of the aim, but you could use um lookup um in the same proof system if you if it was compatible if you made those changes. Um, so it's going to be um a little bit more complicated than um just using um a uh if if you only needed to do one level of recursion.

um then it would be sufficient to um just do your um arithmetic uh for the for one curve using the scalar field of the other curve. Um but what we'll actually need for the recursive proofs is to use two instances proof system. We got some diagrams of that later. Um so this is the cycle that's in the Halo paper. Um it it actually t takes a few hours to generate. Um but that's just because um uh we search for curves with um other nice properties besides forming a cycle. Um

so you'll see here that both of these primes um the zeros here mean that it has high toodicity. Um and that's useful for some proving systems. Um they both have 126 bit security. Um and uh yeah um so they have cubic endomorphism. So um we'll explain that what that means later but it basically means that you can do scala multiplication more efficiently. Um and these conditions here mean that the um the power of five map so the the map from X to X to the 5 in the in the field um is a permutation

and that's useful for um algebraic hashes like rescue. Um so I'm going to explain how we constructed these and um how you can generalize it um to other graphs of curves. Oh um notice that these are short vas um curves. Um so what's the problem with um constructing cycles? Um so we have something called the hassa bound um which determines what range the order of an elliptic curve can fall into. Um so if you have a

curve over FP then um its order is going to be approximately the same size as P um but it can vary by something that depends on the square root. So um so if you have um a 255 bit um curve cycle like like tweedle then the order of each curve lies in a range that's um 2 to the 129.5. Um so that's obviously a huge range. Um and there's a conjecture called the setoic conjecture um about how that distribution varies. It's not uniform.

Um it takes this shape here. Um, but we don't need to go into detail about that. So, so question. Uh, this is a bit confusing because it seems like you're suggesting the order is 2 to the 128 roughly speaking, but it's 2 to the 256, right? No, no. Um, the this is the the range in which the order can lie. Um, I'll show you on the next slide. So um each of these values is roughly um 2 to the 256 but the range of possible orders um is a a 2 to the 129.5 range.

Um is that clear? When you say range, it's like pus 2<unk> p to up to p + 2<unk> p. Correct. Exactly. Sorry, I I probably should have said that explicitly on the slide. Um okay. So, so the point here is um that if we start with um a curve over FP um we find its order Q and then we construct another curve over FQ and find its order R then there's negligible chance that P will be equal to R. Um unless we do we do something

else. We use some special construction. Okay. Um is that clear to everyone? Okay. Assume it's clear. Um this is assuming the field that it's over. Correct. Uh sorry. What what was that? I didn't quite hear. Oh, I was saying this is assuming the field like you're not going over extension fields or anything like that. Um we're only using prime prime fields here. Um I should have Yeah. clarified that um it turns out that it's it's um difficult to use extension fields. Um but prime fields are much easier. Um anyway um so what if we had some um way of

constructing curves so that um one of the possible orders was guaranteed to coincide. So here we have um curves over FP and they only have six possible orders. Um and then when we go to the curve over FQ, it also has six possible orders. And it turns out that one of those orders is P. Um so when we um try to find coefficients um for these curves so remember that the the curve equation is uh y^2 = x cub + b. So b is the coefficient here. Um as we vary b we

will get um of one of these six values. And similarly for the one of these six values there there are only six orders if we are restricting ourselves to this equation type which is a is equal to zero. Uh yes correct. Um there there are six orders for any given P um for any given Q. Okay. Um so the it turns out that um cm curves so curves with complex multiplication um have exactly this property um and the the case of where there's six possible

orders um is just the case that the equation that I just gave x y^2= xq + b. Um so I'm going to try to explain what complex multiplication is. um without using much heavy duty number theory, but just to make it less mysterious. Um and we'll see how well I do. Um sorry, sorry, I'm just confused. Uh on the previous slide, you said that um if you vary the B uh you get six possible orders for the curve. Y um and it seems now that you're saying that this property is actually um uh satisfied as soon as you are complex

multiplication. Is it always the case or do you need something else for these six orders to be there? Um so for complex multiplication curves um you have at most six orders and you you actually may have two, four or six orders depending on the equation. Um and for the equation I said you always have six orders. Yes. I mean in general when J invite is equal to zero you have six. Yes. Exactly. I I talk about J invariance a little bit later. Okay. I'm sorry.

Yeah. Um okay. So um so any curve has um an endomorphism ring. Um so I think we've talked about endomorphisms in previous CK study clubs but um basically it's a a group homorphism. It preserves the group structure um that's from the the group uh the curve group onto itself. Um and you can compose um endomorphisms. So you can effectively multiply them by composing them. Um and you can add them and that's an identity. So therefore it's a ring. Um and so an example of this is um

scale and multiplication by a constant um is an endomorphism. You can easily check that. Um but what you can do is to consider any possible endomorphism of an elliptic curve group um as being like a generalized scalar. Um so normally we're used to um scalers being integers um but think of any endomorphism as being a scalar. This is just one possible way of explaining it that that I find. Um so is a endomorphism a set of homorphisms?

Um an endomorph an endomorphism is a homorphism that is from the group onto itself. That's the definition. Um, is that clear? Kind of. Thank you. I think the question was about the endomorphism ring being a set of endomorphisms. Yes. Yes. Oh, sorry. Yeah, it it's an algebraic structure. It's it's a ring of endomorphisms. So, each element in the ring is an endomorphism.

I see. That's that's a bit harder to imagine. That's why. Okay. Okay. Well, um if you consider the simple case where you just have um integers, then it's clear that it's a ring, right? And the then the elements are just um elements of the ring. So the ring is just Z N where um n is the group order. Is that clear? Yeah. Okay. Right. Um so if we're just if we were just considering elliptic curves over finite fields um then it turns out that all endomorphisms are equivalent to scala

multiplication by an integer. Um but um for for any curve over a finite field um we can consider the curve with the same equation over the complex numbers. So each coordinate is a complex number. Um so it's a little bit hard to visualize because you effectively have four dimensions um two for each coordinate. Um and then complex multiplication just means that you can scale and multiply by a complex number. So um here's an example. Um we have this elliptic curve.

Um and we define multiply multiplication by i. So i is the square root of one as this. Um you check that it works. Um so if you apply this map twice then you get x here then minus y uh which is the same as i^ 2 * xy. So it works. Um so the what you end up with here is the scalers are um elements of a complex lattice. Um and in this example the lattice is um z i. So that's um

I'll show you some um pictures on the next slide. Um but that's just the Gaussian integers um of this. Um and if I've lost anyone then it's it's going to get simpler when we just consider the case of finite fields. So don't worry about it. I'm just trying to um make the idea of complex modification. Um that's mysterious because it it's referenced um very often in papers and they don't explain it at all. they they refer you to um Silverman's book or or whatever.

Um and it is actually reasonably easy to explain um just using basic principles. Okay. Um so we said that these generalized scalers so these endomorphisms um are in a complex latice. So here's the example we saw on the previous slide where um the elements of the lice are are in this arrangement. So this is called the Gaussian integers. Um and the other case um which is the J equals0 case that we're interested in um these are called the Eisenstein integers. Um so here um so if you you have four units

here um which are in the latice and here the the green dots here are the units. So you have six on the unit circle. Um so that's what defines these latises. Um so this case is nice for cryptography and it um seps into this case. So, um, we're we're not doing anything especially controversial or new here because, um, the billions of dollars riding on 6P256K1 being secure.

Okay. Um, so I just, um, told you about the units. Um, they're the elements that have a multiplicative inverse. So if you take some other element here um say this one um that doesn't have an uh inverse in the lattice. It's only these that have inverses. Um so the the inverse of one is one for example. Um and it turns out that the orders correspond to the um the number of units. So if you have a latis like this then you'll have four possible orders of the um curve. If you have a latis like

this you have six orders. Um so that's why that happens. Um and then when you map from the elliptic curve over um sorry I didn't quite hear you there. Your sound was difficult to understand. You say that again. I think that person just joined actually. I think it was just uh some background noise. Oh, okay. No problem.

Yeah. Um okay. So when we move from the elliptic curve over the um complex numbers um to the one over finite fields um these complex roots can correspond to um roots of unity in the finite field. Um so uh we might have um sort of six roots of um unity in the finite field. Um and then it will turn out that uh multiplying by one of these scalers is equivalent to um multiplying by an integer. Um but it it will be a shortcut to uh multiplying by that integer. Um

because um so moving um of in the um the imaginary direction here in the latis uh was that a question? I don't think so. I think it was background. Um so so moving to one of those units corresponds to applying um anomorphism which can be quite easy to compute. So that's useful. Okay. Um so so so Dar uh what do you mean? So just to see I understand the notation EQ means the the

whatever they're called isos isogyny whatever they're called. No no no. Um this is just saying that we have a curve defined over FP. Um and its prime order is Q. Oh, so that's just the endomorphisms of this uh curve. Uh sorry that um yeah, so in the finite field case um the endomorphisms are just the the endomorphism ring is just the integers. Uh yeah, I'm saying this this notation is E P arrow Q is for the the endomorphisms of of this curve of like size P over FQ.

Um you can think of it that way. Yeah. Um you you you can just think of this as being the field of definition P and the the scalar field Q if you want. um because it after we've explained complex quantification and we're just going to go back to um considering the simpler case. And what is you say the units correspond to the possible order? What what is what does it mean in order of EPQ? Oh, sorry. um the the possible orders of EP um as you vary uh the coefficient B

and the the number of things the possible ah the units of L correspond I see and and you haven't said how this correspondence happens I I will get to that [laughter] okay cool yeah know I thought it was like order in the sense that Sometimes they talk in complex multiplication. The Yeah. The the problem with number theory in general is that is having too few words in English to describe the number of concepts. Yeah. Uh okay. Thanks.

Um yeah, that's the only problem with number. No other problem. Yeah. Everything else is simple. Notice how I I carefully avoided saying unit circle here because that would have been really confusing. Um okay so um we should consider whether um CMS CM curves are secure. Um I mean I I've just said that um SEC V256K1 is a CM curve. Um and all um pairing friendly curve constructions that I know of or that that are in um any papers I know of um produce CM curves. Um so this is a a very wellstudied thing. Um and I don't

think that um there's any reason to believe that um the discrete log problem on these curves would be um any less um any less hard. Okay. Um even though they they're only a small fraction of curves. Um okay. So when we map the CM curve back to the finite field uh has a small number of possible orders um determined by the number of units um and that's determined by the J invariant. So turns out the so this case here um where we have a Gaussian latice is J= 1728 um and this

case here is J equals Z and you can compute the J invariant just based on the curve equation. I'm not going to um how you do that. You just look it up here. Um and the reason why um J and variant zero curves are interesting is um they have six possible orders and it'll turn out that um it's useful to have sort of several possibilities for the order because sometimes um uh some of them are excluded because um they will never be prime. Um so you you basically have six bites of the cherry

um to get something that's prime. Um are these six possible orders explicit or do you have to Yeah. So um I'm going to go into that in a few slides. Um but basically there's something called the norm equation um which allows you to compute them uh explicitly. Um we're going in we're going to go into some detail on that. Um okay so um this is the normal equation um uh dv^ 2 = 4p minus t ^2 um so all of these are integers um this d here is called um uh the fundamental discriminant um and

by convention it's it's normally negative um so what I've done here is just take the absolute value Um and V obviously P and T are integers. Um and then you have um a trace T. Um so I'm not I'm not sure how many um people are familiar with um the enough elliptic curve cryptography to um to have seen this before. Um but um the trace is basically um

it determines the difference of the order um from P+1. So remember we um talked about the Hassa bound. Um so the range of possible Q's is P + one plus or minus um 2 root P. Uh so that range and then t here um is something that can vary um up to uh 2 root p in magnitude.

And then it turns out that there's a relation between this t this capital t and the trace. Um so plus or minus t are two of the possible traces. Um and that's the case regardless of the j invariant. Um but in some cases there might be um more possible traces than this. Um so for the tweedle curves um all we do is set d equals 3 um it it turns out that um for cm curves um where the order is prime d will always be three. Um and then we pick we can almost freely choose integers V and T.

Um and then from that we can compute the prime. Um so we can both the prime and the order actually. Um and the reason we want to do it that way um is we want both of the curves in the cycle to have high toadicity. And we'll see in uh in a minute how we can choose V and T. So that's always the case. Um but first of all, let this is an explanation of why um this property holds. So um there a proof by uh Stanganger and Silverman. Um but the

their proof is quite complicated. Um and so I wrote up um a simpler proof um and that's in the accompanying notes which are in the um GitHub repo. So the proof actually of the case that we use for tweedle fits on one slide um and so we have this num equation um and we want to show that one of the possible orders for EQ is P. Um and it's just a um a straightforward application of algebra. Um we end up with so we have to distinguish between

the V and T for the um for the curve over EP and the V and T for the curve over EQ. Um it turns out that the V is the same for both. Um but T is different. So um TQ will be um will differ from TB TP by two. Um and if it does then um it works out that um the order of EQ is P. Um so this is one of the um possible orders of EQ. And remember, we we're going to have to search for the [clears throat] coefficient that um gives this order.

Um so is that reasonably clear? This is just a to explain that there's nothing mysterious about why this should happen. Um, it's it's something right in the Can we can we recap real quickly what happened up until this point in the presentation because I'm a bit lost after this whole CM. Oh, okay. Um, so what what we're trying to do um is uh understand um the construction for um uh for creating two cycles of curves. Um so curves where the order of one is um is the prime uh over which

the other is defined non but non-pairing friendly um the so this is in general um so both for for pairing friendly and non-pairing friendly curves I see okay so so any CM curve um pairing friendly curves um are basically CM curves because that's the only way we know how to construct them. Um but you can also construct non-pairing friendly curves that is CM um se256 K1 being an example.

Hey Darl, this might be a good moment to have a quick peek at the chat. I don't know if you can see it on your screen easily. Um, there's been there's a few points that were made, so might just be worth it to check it out quick. And if anyone else has anything they want to kind of raise, this might be a good moment to do that, too. I don't seem to be able to see the chat without um stuffing screen sharing for some reason. I don't understand why that is. Um, can you just read out the questions in the chat and I'll answer? So, I Yeah. Yeah. Just go ahead. you do you want to say what you wrote because it's a bit longer than just a [laughter] question.

No, I just didn't want to interrupt because maybe it's not that important. But in in one slide you said that um um so the in the ring of indomorphism is equivalent to the scala multiplication by integers when we are talking about elliptic curves over finite field. Yeah. uh why I wanted to say just it is the case for ordinary curves because for super singular curves the ring of indomorphism is an order in in quatonian algebra so it's not uh multiplication by scholars but I just didn't want to interrupt this um thank you for the correction I I'll correct the slides there um yes uh we don't want to use super singular curves because they're insecure um

but but yes that that point is well taken thank you Um, uh, anything else from the chat? I think everything else was like, uh, additional ideas or kind of backing up some of the stuff that was being spoken about. And someone did ask if I would export this. So, what I usually do is I take kind of relevant links and I add that into the show notes of YouTube. Um but if maybe I can add some of this text as well if if you guys think that would be um so there is a um there are some notes which are on HackMD.

Um let me actually uh I think you already sh did you already share that in the group before? I think I did. Yeah. Um okay. Yeah, I I'm pretty sure I shared them. We can put this we can share in the group after and we can also put this on the YouTube chat as well. Cool. Um, so yes, uh, uh, I I do actually have a a question. Go on. Um, so safe curves makes a big deal about, uh, low CM discriminant enabling, uh, some sort of row speed up. Is that a concern here? Is that why we're looking for 130 bit curves?

Um, does it matter at all? So, uh, you can compute, um, exactly the speed up. There's a footnote in the um Halo paper about exactly this point. Um so yes, you can use the endomorphism um uh in polard row. Um and that gives you a speed up of um I think it's square root three or something like that. Um so it's it's barely significant. Um and you can just compute what security your curve has. Um taking into taking that into account. Yes, I I think that it is well known but the when people are talking about the discriminant the multi the complex multiplication discriminant

being small it's not about the security but it's about uh the complex multiplication theory gives you the existence of the curve but then you need to find the coefficient a and bottom for instance so uh if the discriminant if the discrimin is too big then you cannot find this coefficient there is a method by atkin and moran to find this but in the kind curves. Dra is talking about when the J varant is zero in a when you have just x q plus b you do not need this middle because you have only six orders you can just try a few coefficient until you and until you the one clicks exactly yes okay thank you yeah that was a good point thank you um

[clears throat] so um we want the both curves to have um high toity um typically we want. Um so if we're using say um Gro 16 or um uh BCTV 14 pring systems um then we would need um a tidicity that depends on the circuit size. So um a tidity of C would uh allow for a circuit with um two to the C gates. uh and the the details may depend on the proving system but that's that's the basic idea. So we want um both P and Q to be 1 mod 2 C um and here's how we do that. Um I'm not going

to sort of go through this in detail but the idea is that we we can freely choose V and T. So we can choose them in order to guarantee that both um P minus one and Q minus one multiples of 2 to the C. Um and the this actually only works for two of the possible um orders. So two of the six orders, but that's okay. Um so um that's basically everything for um Halo cycles. Um but we might also want cycles that involve um pairing friendly curves. Um

uh just so that we can use um greater variety of proof systems. Um so brief recap of what a pairing is. It's a bilinear map. I'm not going to go through this in much take too long on this. Um so we pick um our pairing friendly curve. we're going to assume that it's in a parameterized family. So, um we have an integer parameter x um and then uh p and q. So, p is the field fp is the field of definition. Fq is the scalar field. Um they're defined by these polomials in x.

Um so, bn curves are an example here. Brutineric curves. um and so are BLS and KSS and MT curve, MMT curves, any um curve construction that you might want to use in cryptography is of this form really. Um so let's um consider how to um make half pairing cycles. Um so uh I I already um answered this in response to a question before. Um but the reason why you would want these is um so that you can um produce you can use a proving system um that

produces fully succinct proofs um as part of the cycle. Um so you won't be able to use that um for both sides of the cycle. Um but only being able to do it for one is sometimes sufficient depending on the so exactly how you do the recursion. Um, so I think Isaac Mler has a um a video about the um pickles proof system um that explains how that uses them. Um so um in order for curves to form a um a cycle, they have to be prime order. Um so so that the orders are within each

curve each curve has interval. Um and so that restricts us to some families of um pairing friendly curves like um BN Freeman or Mnt. Um and in practice we want the um curve to be as small as possible for a given level of security. Um so we want BN curves. Um and it turns out to be trivial because um all BN curves will form a cycle a two cycle. Um so we just search for the coefficients. Um as that's just a consequence of um this um okay

um and to get the twoicity we just choose the parameter to be a multiple of whatever tidity we want. But if if all BM curves form a cycle, they're pairing friendly. So you get a full pairing cycle, not a half pairing cycle. No, the the other curve um will have very high um embedding degree. So it won't be pairing friendly. Yeah. And I think you can't get cycles of parenting friendly because with BM by definition. Um yeah that that was proven in I can't remember the author's but paper. Yeah

yeah yeah um and it it also proves it for Freeman um curves as well. Yes. I mean the basic the basic pro is just a sum of the traces. The sum of the traces is equal to the number of cycles. So in uh in BN curves for example the the trace is 6 * x² + 1. So if you sum these equal to two then you will have that the only solution is x is equal to one and x is equal to one then you cannot find a a prime order for p neither for q.

Yep exactly. Um thank you. Um so yep choosing x here um notice that um if x is multiple of 2 to the c then so are all of these terms that involve x. So you get one modulo 2 to the c. Um so we might want to have other constructions um with one pairing friendly curve in the graph. Um I I don't know how to do constructions with two pairing friendly curves unless you use something like um cox pinch. Um so anyway if you have one pairing

friendly curves curve then um just figure out what your polomials are for the for P and Q here. Um so so you need to solve the norm equation that I gave before for each of the other curves in the graph. Um and so if it's not obvious how to solve them um you can um sort of just construct um some and say um find its order and then work out from that um what the solution to the norm equation must be. Um so J equals z curves. Um so very

convenient here because we have six chances to find a prime order. Um and then um just to to optimize the search um we can work out um sort of a congruence relation on x um so that um all of these polomials are more likely to be prime um and to have the right um it's you can't always um produce curves with high twoity. uh you might have to settle for high 3ity or some of the small volume set.

Um so let's see whether um we can um give an example of that of solving the um norm equation. So I'm going to have to um stop screen sharing the slides and I'm going to a sage window um and we'll see how to do that. So the motivation here is we want to construct um a KSS 18 curve because that's the this is the smallest construction I know of the the construction that gives the smallest P that I know of. Um so this cycle has to be around um sort of Q and

R have to be around 256 bits for security. Um and then KSS18 um will give you a secure pairing because um the size of GT will be 345* 18 which is um 6,100 and something um and um so that's secure. Um but this is uh this is minimal. Um so let's okay stop screen sharing and I'll screen

share my Sage window. Find it. I guess I should have um closed most of

my windows in order to make this easier. Let's reboot the whole machine. Ivan, you had that question in the group. Did you feel like it got answered? Uh yeah, I think so. Okay cool. Okay, cool. Um so, do you see my screen? Yep. Yes. Okay. Cool. Let me just Okay. So um the first thing we need to

do is um to work out the um the polomial for the order of the curve um our pairing friendly curve. Um, so, um, don't bother looking up that up because I've got it in my notes. Um, we have, uh, so, um, this is a slightly different parameterization than the one we usually see. Um, and the reason is that, um, uh, the usual one produces doesn't always produce integers. Um, but this is equivalent. Uh so it's 343 u to 6 + 37

u to the 3 + one. Okay. Um so that's the this for kss 18 curves. Um yeah, so this is the um the prime order of a KSS um 18 curve. Um so reparameterizing so that this is always an integer. Um and then okay so we want um to choose a U so that this is prime. Um, and we also want um you to be um quite simple because we want to be able to recognize um of the order in terms of you. Um so what

I'll do is um is find so so what I'm doing here is checking for each k um up to 100 um whether p of um 2 to the k is prime. I suppose I could just write two to the k here, but it's a micro optimization.

Uh why didn't that work? You mean in and not equals. It should be in range. Yeah, thank you. That shows you that I'm not just copying and pasting. Uh okay. So this tells us for example that um u equals um 2 33 um gives us a prime. Um so in if we were actually trying to construct a ks 18 curve, we would also have to check that um so the um the prime for the field of definition is also a prime. But

um and it turns out it isn't for this. But um it doesn't matter if we're just trying to solve the normal equation. Um because we're actually trying to find a the curve underneath the uh ks8 curve. Okay. So uh let's calculate our prime p. Um uh this is what it is in binary. So you can see it's very sparse.

Um and let's construct our elliptic curve over that prime. Um and so here are the vast trust coefficients. Um a is zero and b is five. say um and we'll count the number of points. That was fast. Um point counting used to be slow, but not anymore.

Um sometimes you have to um convert things to Python integers and save. Um so let's see what that order is. Okay. This um well that's interesting because it's very similar to P. So So is P prime by the way? Uh yes. Can we just check? I mean I I checked it above. Okay. Because the Yeah, I'm sorry.

Because the pol this is the polomial of KSS 18. Yeah. Oh, sorry. Uh it's the um the order of a KSS 18 curve. Okay. Yeah. So so all we need for this exercise is that the order is prime. Um we if we were actually constructing the curve, we would need the the field of definition to be prime as well. Darra, uh is there a reason that we're restricting attention to prime order curves? Um can't isn't it okay if it's uh just you know has a large prime factor um so actually the the the prime you're

talking about I think is the subgroup the prime subgroup order of the right yeah so um exactly um KSS18 curves um are not prime order so you also have another polomial for the co-actor which I um I haven't bothered with here okay great thank you yeah so So this is just the prime subgroup which is what we want for our to construct our graph. That makes sense. Okay. Um and then so let's um compute what the trace might be.

Um think what's that in binary? Oh, that's interesting. Um so remember that our parameter was this. Okay. So, okay. Okay. So, it looks like um this trace might be something like um so what's this might be 17 u cubed something like that.

Yep. Oh, hang on. You need a plus one there. Um okay. So let's guess that t is that. So um we then have so remember our norm equation is this. Okay. Um well we have p and we have t. So we can just um compute EV squared um that's let's take it square free part I take that correctly

okay three okay so v equ= 3 that's good uh so v ^2 = 2 over d um well a lot of better v square. Yes, it is. Um, so we can take its square root. Um, uh let's Okay. Um, and so we also need to work out what this is um, as a function of u.

Um, so I think it's fairly clear that this only differs in the first five bits here. So it's going to be of the form something times u cub + 1. So it's going to be 19. Okay. Excellent. So um that's our solution. Um so let's okay well we haven't checked that this is

true for all possible u um but let's see we can I prefer to use um parry for um operations on polomials. So you can do okay. So this is the polinomial for P and then V and then T.

Um and okay, so this is the right hand side of our norm equation and then the left hand side is going to be 3 * b u^ 2 and it's the same. So we know that this is true for all you. Uh any questions?

So this this is basic so um this is not unrealistic because this is actually how I did it when um I was trying to write the code to to find cycles under KSS18. I think people are mostly just really excited to see you live coding. So that seems to be the chatter right now. [laughter] Cool. Uh I didn't know whether that would all work, but it that worked out very well. Um does anyone have any questions about the maths?

Does anyone think that they could do this for another curve type now? Because that that's my goal really. Um, I don't want to be the only person doing this. Olivia, do you have a question? So, what is your goal there again? Uh, the so to teach other people to be able to um find arbitrary graphs of elliptic curves. But the the the only use case for the time being is something like so for cycles with pair infinity at least one of them is pickles, right?

Uh so so um that slide that I showed um only considers that case but um other people may have more ideas than I've had. So um you can sort of build on these techniques to do more interesting things or at least more complicated things. So the reason that this is possible to do with these parameterized families is because we have um is we know how to go from a a subgroup order to um the full curve construction. But could could you also do this with something like an Edwards curve?

Um so an Edwards curve um is never prime order. Um but as right as as long as your graph doesn't require it to be prime order then yes. Well but so in this case with the KSS um 18 curves they're also not prime order you said. Uh that's correct. Yeah but we we we simply know how to how to search for them on the basis of their prime order subgroup which is not necessarily true for other curve families.

Um yeah, I I don't know how you would do it for um cases where the the order is not parameterized. Um because it if um if any of the curves is not cm then you're not going to be able to solve its norm equation. And so it can still be a leaf in the graph. Um but it you're not going to be able to make it participate in a cycle. Got it.

Hey Darra, you know how uh you have a second half of this talk that talks about the circuits and stuff. Yeah. Since um we've done an hour so far, did you want to split that into a different uh study club? Maybe. Um it's so it's a a shorter part of the presentation. Let's see. I'm on slide 23 and goes up to slide um 36. So, um it's it's about half the length um of what I've done so far. I remember I did the live coding bit, so that's also um that also took longer. Um, so Anna, um, do you think we should split it or

Well, we have, so I think we could probably do another 20 minutes, but I don't know that we can do much more. So, it depends. Do you think that there'd be a lot of No, it can fit in 20 minutes. Yeah. Yeah. I've done this in 20 minutes. Okay. So, uh, let me, um, just before you move on, go on. Um, yeah, I was just wondering, so you um I basically have two questions. Uh, so you quoted this, um, result that said that you could move back and forth between two primes.

Um, if you had complex multiplication, I guess. Yeah. Um I so the first question I have is basically um is it is this all this paper says or does it describe other paths uh you could take between curves and um so the the original um Stanganger and Silverman um paper I I hope I'm pronouncing Stanganger properly. I'm not sure whether it's that oranga. Anyway, um uh it's so what that's trying to do is to count the number of um curves that form cycles. Um it it's um the paper's a few years old now. Um

and it wasn't specifically oriented towards cryptography. It was more of a pure number theory paper. Um so um there there may be other tidbits from that paper that we could mine but um I'm not sure there's anything that's directly useful. And does that answer the question? Uh well it um I'll just take a look myself I guess.

Um um and the other question I had was um um so you um you said you were going to you did everything you did as far as uh as I understood it always with with always uh with J and varian zero and you had reasons for it which um I don't remember but you had on your slide you said it's better to do it with J equals zero. Um can you do you have any idea if other J variants would be useful?

Uh so we know that J invariant um 1728 um never produces um prime order curves. Um uh that that's proven in one of the papers that I referenced. Um but other JM variants might be useful. Yes. Okay. Thanks. Cool. Um, so I'm going to screen share again now. Stop from current slide and let's see if I can get the Zoom window.

Sarah, I do wonder, are you sure you don't want to maybe do like an a bonus session where we finish it? I'm just The reason I say that is we only have 15 minutes left and I feel like no one will really be able to ask questions on what you're doing and I feel like there will be. Also, there's a few people that have dropped off that I think might want to have it. Um, would that be okay? We'll split it there. Okay. Because I think this is a cool stopping point and actually maybe it's good. We get actually a little bit more conversation out of this. Okay. So, let me just conclude or do you want to do you want to say sort of a conclusion?

Well, were there were there any more questions on the curve construction part? Uh, I had a question in the chat. Uh, it's somewhat abstract though like you said that it's infeasible. basically to find any cycles in non same curves but is there any reason why we would want to do that. Um so if you are worried about the security of CM curves then you might um other than that you might want complete curve equations that are really efficient to another curve type for legacy reasons uh like um you know constructing bulletproof cycles around ECDSA

standards or something right because most of the exist ing standards with with the exception of um SEC P256 K1 and some of the other SEC P curves yeah would not be CM all right thank you but you can use non CM curves at the leaves of leaves of the graph any other questions or shall Please stop recording.

Oh, I just had a quick question, Darra. Um, about requiring the J invariant J invariant to be zero. Um, is there a write up of that somewhere or is that in one of the papers you looked at or I know you said that's not that's like that's used for uh the curve used in Bitcoin. So, I was just curious like where that write up is of where it's useful. Um so um the reason the main reason it's useful is that you have these um um endomorphisms. So so that's how the um the second part of the um the talk followed on from the first I

I actually use the um endomorphisms um to explain how we optimize halo. Um so uh you'll have to wait for the next part of the talk for me to explain that I think. Got it. Okay. And I think you can also make the pairing faster because you can compress G2 up to a six. Oh yeah, that's another good reason. So that doesn't apply to the Halo curves, but it does apply to pairing friendly curves. Yes.

Go on G. But the the the reasoning about uh J andvariant zero curves um uh um mapping into uh finite fields in the way that they do is written down somewhere, right? What what uh what is that from? Um so that is um so slide slide 15 there's a reference to on orders of elliptic curves over finite fields. Um I think it's in that one.

Cool. Yeah, this was fun. Um it worked out really well. Um for your um curve search, is it is your curve search repo the best place to to find this? And the second question is the the the stuff that you did with with the parry calculator. Is that part of the like your normal workflow? Is that what you kind of normally do? And my Yeah. Uh so my normal workflow is to to have a Sage window open and a Perry window open. um and to just use whichever one um is most convenient um because Pari tends to handle polomials that with a very sort of

simple and concise syntax whereas for Sage you need to declare the variables slightly annoying and and for the brute forcing part is it can your normal computer handle it or do you send it away to the cloud and crunch it there or um uh so my computer can handle it it's just an ordinary desktop top with um six cores. Um awesome. And it doesn't these searches don't require very much memory. Um so um yeah, any desktop should be able to handle it. Um so the how long a search will take depends on basically how much time you have to optimize it. um and um

and whether you're searching for any um special properties of the curves beyond the fact that they form a cycle. Um also it it depends on how many curves you need to check a prime. Um so by the by the prime number theorem um so the the probability roughly speaking the probability of any um n bit number being prime is um uh one over so proportional to one over n. Um and so um the larger the numbers are the less likely they are to be prime. And then if you have to check several numbers for

being prime um you have to check more more of the parameter space in order to find one whereas it's usually so if if you're finding that that is a problem um then there's a trick that you can use um which I didn't um put on the slides but um So uh there's a technique called a factor wheel uh which you can generalize um to to use in these searches. So you can have effectively a very large virtual factor wheel um that satisfies all of the um the congruences that you

need. Um and so that makes it more likely that the um that each polomial um will produce a prime. Um, so if you if you're having trouble with how long the searches are taking, you can use that. No, thank you. I just uh I was going to play with it. I just want to make sure that I could. So, perfect. Thanks for your talk. Yeah. Um, so uh the the programs in the curve search repo um none of they all produce um curves um sort of relatively frequently. Um, so it's only if you're searching for something very specific that it would take a long time. Um, it

it takes um I think it's a couple of hours to search for the Tweedle curves. Um, but that's just because um we insisted on them being twist secure for some reason even though we're not actually using twist security in Halo. Um, but anyway, cool. Um, so let's stop recording if I can find the Yeah. Well, first let's say thank you. Thank you so much for doing this. Thank you. You're welcome. [laughter] It was It was a lot of fun.

Yeah. And we'll do a bonus. I guess we'll after this we'll organize this uh bonus edition of the Halo. Yeah. And maybe I can expand on um that part of it. Cool. Nice. See you next week probably. Yeah, I think some something like similar time, but we'll we'll coordinate in the in the chat. Okay. Thanks everybody. Bye bye. Thank you. All right.