Episode 324 - Discovering New Elliptic Curves with Antonio Sanso and Youssef El Housni

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week Nico and I chat with Antonio from the EF and Usef from Linea at consensus about their new work families of prime order endomorphism equipped embedded curves on the pairing friendly curves this conversation has us diving deep into elliptic curve

cryptography covering things like bander snatch and how this is used in veral tries or trees we couldn't quite figure it out we try to tease out what the terms in the title of this work means like embedded curves being endomorphism equipped as well as discussing how they were able to actually achieve this work this one is a cryptography heavy one so get ready now before we kick off I just want to highlight the ZK jobs board for you there you can find jobs from Top teams working in ZK so if you're looking for your next opportunity and want to jump in be sure to check it out and if you're a team looking to find great talent be sure to add your job to the jobs board today I've added the link to the ZK jobs board in the show notes now Tanya will share a little bit about this

week's sponsor nada's the shielded asset hub Hub rewarding you to protect the multi-chain built to give you full control over sharing your personal information namata brings data protection to existing assets applications and networks namata ends the era of transparency by default enabling shielded transfers and shielded cross-chain actions to protect your data even when interacting with transparent chains namata also introduces a novel shielding rewards system by holding your assets in a shielded set you help strengthen nada's data protection guarantees and collect n rewards in return namada will initially support IBC and ethereum based assets but will ultimately serve as a single shielded hub for all assets across the multichain

learn more and follow namada mainnet launch at n.net and now here's our [Music] episode so today I'm here with Antonio core researcher at the ethereum foundation and youf who works at consensus on the Linea project welcome both of you to the show thanks a lot Anna for the I'm really pleasured to be here thank you Anna for having me and thank you Nico as well yes and Nico is our co-host for this one hey Nico hey Anna hey Yousef hey Antonio yeah so this is an episode that's been a long time coming uh Antonio we started talking about doing this episode I think almost a year ago and then you were working on some exciting research you had sort of

asked me to hold off uh and now we are very excited that we get a chance to talk to you about some research I'm actually curious if that was the research or if this is new research actually you know like uh the things like that I standardly do is like I work on at least two three problems at the same time okay and when I'm stuck or like bored with something and I cannot solve it I just like switch topic and switch to search and that this like sometimes I'm lucky enough to solve something and uh if not I just like stop I go to the next problem and so uh I repeat the the cycle think like but when we were talking last summer about it was not this paper exactly was something else that us solve it so I see

I will for a future episode exactly well I'm glad we're getting a chance to get to know you anyway on the show uh youf we met I mean I remember you spoke at the notorious ZK Summit 5 online event the one that crashed through the whole day this was right when Co hit we did not have a like this was kind of our put together backup plan to throw a summit online with tools that were not very performant I guess but I remember you gave a talk at that I think your talk went okay yours did not crash as far as I remember yeah yeah I don't remember this was my first ZK Summit where I actually had a slot and that's why um I

talked at the ZK Study Club on ZXI I think it was one year ago it was also online yeah well we're going to dig up both of those videos as well so we met back then tell us maybe a little bit about what you've been up to since then if you've made sort of any changes in the type of research you've been doing or if yeah if you've had some new findings yeah so um now I'm working on linear the ZK evm but before I was working on gach yeah which was now which is now absolved by Linea so I'm still working on gnach and uh on Linea so there is a lot of implementation because we need to go on production we need to deliver things and stuff but before I was doing more research uh and and when I had this talk on the ZK Summit 5 it

was about elliptic cures and I'm still doing research about elliptic cures I mean the paper were talking about today is also about elliptic curves um and then I met Antonio and then he brought me back to research nice yeah so I'm still trying to do both I have a quick question about gark I've heard recently that there's not only one implementation of this is that true is gar like a whole body of work so gar is more of a EOS system but actually there are two libraries so both are WR in go so one is gar crypto which has all the cryptographic Primitives like ffts MSM finite fed elliptic curves and then there is gnag which implements the SNS based on G crypto so it has the plun

implementation the go 16 some other variation like gkr some checks and then so there are a lot of project that are using either one or both and these are doing their own thing with G so we just help them extend knock and yeah which one are you working on so I'm working on both actually oh you are okay you actually see what's happening in both of those yeah are you worried sometimes about things like this splitting too far apart like does it create issues down the line if like a library that becomes kind of used and then there's a team that needs something else so they kind of fork it off start building in a different direction like does that yeah is that something you worry about or is this a good thing I mean we we always welcome contributions to the C orar

Library so if it gets merged to it then it's nice for example so there is in goyama who did the GPU acceleration and then they did a contribution back to gnog to to integrate their GPU acceleration into gnog this was nice for example there was BNB so biners who were doing some stuff with gnog and then they contributed to back to G so I I mean everyone is is allowed to do they want to extend it to foret but it's really nice to to go back to G and try to match things but now that we are working on linear so the whole things we are doing on Gag aimed to linear but we still want to have time to support other teams that are doing something else with the ZK snacks and ZK in general so we're

partitioning time this way uh Antonio let's hear a little bit more backstory from you I'm curious when you got started at EF what you started on and what led you to work on this kind of stuff sure um I actually start the foundation uh in the cor research team about three years years ago and the first things I've been working on actually is the motivation of this probably of some of things we're going to discuss today but basically like the first things I worked on is like during one of the meeting that we were having with the cryptographic team danr uh one of my colleagues that's probably pretty well known in the in theum ecosystem was actually asking for a specific elic cves for a project that he was doing with the

with the vitalic basically what is now know known as a veral tree ah and basically like they were asking for a for a curve that has the best field equal the the scalar field of bls2 31 it's like this really famous like paing friendly curve the one that came out from the c um project and basically like this motivated research on on on something on the kind of new curve that that is now known as a band snatch and that's basically like one of the first things that I've been doing at the foundation but what brought me there is like um I one things that I've been working before and uh where I met Justin basically is like I've been working a

lot on on the topic of BDF and uh actually one of the paper I've been working with other co-authors before was discussed in one episode here this this famous isogenous vdf or in famous isogenous vdf so you had you had look at fa yes presenting it and I'm actually a CO out on that paper and uh this kind of um contact that with Justin on vdf might be let's say into the the EF isogenes had an issue though right I actually ran into Luca and he was like did you hear what happened and I hadn't actually but I but I want to ask you is the work that you did what happened from there on that topic so what you probably refer is like

the the on the postquantum word like one of the Primitive for that was presented the to be ized as a post Quantum key exchange sidh got badly broken not on quantum computer but on standard computer so like what was supposed to be Quantum resistant was actually uh broken on a normal laptop in less than five minutes or a few seconds now I guess with the with the performance of the attack now and it was like a a disaster for this scheme called sidh that L is actually one of the co-authors but basically that has no impact on uh on our vdf okay and as well has no impact on the original isogen assumption uh that is um the first way that isogenes

were introduced to the cryptography world so let's say short of a long story is like Sid is broken but isogenes are more alive than ever but I'm a bit bullish on isogenes so sounds like you're a bit biased yeah yeah but uh of course I am but um I mean I know that for sure isogenes are not there I mean that specific things got badly broken but the original isogenes assumption they're still alive so there's like the scheme now that is based on isogen for postquantum is called CDE and not just saying here probably will not be one of the favorite of many people but yeah it's it's actually really cool and like

to come back to your question the actually the isogenous vdf is not touched as well by this attack got it so I'm curious how did the two of you meet and start collaborating on elliptic curves so I think the first time I I knew Antonio was because of the vdf uh paper about I mean I I must have seen his name before but the time I remembered his name was about the paper he did with Luca de and Simo Mas but I think the first time we physically met what during the ZK Summit in Amsterdam I guess o zk7 yeah yeah zk7 so and uh also we tried to collaborate before with Antonio and Diego ARA who's a professor at uh

arus University in Denmark so we're here today to talk about this paper the name of the paper is families of prime order endomorphism equipped embedded curves on pairing friendly curves say that quick seven times we Happ how did you come up with the title no just kidding let's let's jump into it and then we'll probably figured that out yeah probably like connect to what I was saying before like me and and a couple of co-authors that is not youf like we we came out with this new curv called band nutch U about three years ago after this request from u d and balic but the reality is like that banders nut should not exist it's really should not n like just to

give a bit of background on elliptic curves usually like there are two ways to to build elliptic curves you can like having a best field is like the field of definition of thetic Curves and and you want the the number of points of the order to be like cryptographically strong namely like the the number of points of the curve should be a lot and the the the factorization of the order should be not smooth so you IDE you want the prime order name like the number of points to be prime or to be like a primes and multiply by a small number let's say four let's say you know 12 this called co-actor when you are search for searching for a new elliptic cves you have two ways to do it you you either like try randomly elliptic CES

you change you can change the base field and try elliptic CES in a random way and hopefully this will bring one day to have the right number of points so either primes or big with the with the small co-actors or you employ something uh complex multiplication that is like well it's it's really really nice math but uh will not fit the the length of this episodes it's some really cool thing and basically like if we talk about the BLS 12 31 scolar field to become the base field of a new elliptic curv was already done by a cve Again by the Z team and this curve is called jbjb so they they they were actually use the

scalar field of Bas 12 1231 to build a new elliptic cve but they did it in the first way Nam like they try different electric cves until they they came out to a this new new electric called jbjb what I've been trying to do instead after that D vital has this new curve is to employ CM Cs and so CM method so this other method because this will allow some something called GV endomorphism optimization that a way to to actually speed things up operation up and the the the Intriguing fact that I still cannot explain today is that uh we employed CM method and with a fixed based field that

is the scalar field of BS 381 and this actually gave us a cryptographically strong crew and a cryptographically strong Twisted group and the the the likelihood that this happens is nil literally nil so I'm going to have to ask you to define a bunch of things here because there's a lot of complex ideas and words that you know most of us don't know about um and the first one is why would I bother having a curve inside a curve you were saying we want to take the scaler field of BLS 12381 why do I want to use that scaler field as the base field for a new curve sure I will let actually youf reply that

because it's way more skilled than me on this specific area well yeah um so the question is I mean we're building snots right and snacks are like for generic purpose you want to prove any kind of statement but some of the statements we see in applications are statements about elliptic curves themselves imagine you need to verify a signature or you need to verify the pre image of a hash that is based on a analytical like the pon hash in that was used back zcash Sprout so the question then is you need this statement to be expressed in the minimum constraint possible but if if you're using an elliptic curve then uh you're

doing uh the arithmetic over the field of definition of this eliptic curve but then remember you have another elliptic curve that instantiates The Snug and this elliptic curves these two elliptic curves are distinct so if you're doing the arithmetic for your statement over the field of definition but then you're doing your snar proving over another field defined by the snot curve then you have a mismatch m and this mismatch is a big problem if you want efficiency so one way to solve this is to find two elliptic curves for which the statement elliptic curves is defined over the field where we do the SN computation so

I'm not I'm not sure if it is clear but it's it's the same problem that we had back in jeeto uh we had it in Z we had it in U MNT 4 mn6 uh curves so it's always the same problem and we just need to find these two elliptic curves so ideally we would like to find a cycle which means that we can use an elliptic curves as the statement elliptic curve and the other one as the snar elliptic curves and vice versa but for some efficiency we or some applications we want just the thing one way so you can do this for recursion for anything else sounds good so that's the embedded curves part of

the paper title exactly we we have two words down many more to go okay so I guess the follow-up question for me is Antonio you mentioned that uh zcash already had come up with jobjob why was it necessary to come up with bander snatch so uh the requirement that I got with the from from D was like Hey this curve should be as fast as possible so you know like when you think about um speeding up operation on elliptic curves you think about GV that's actually what if you think about the curve that is in both Bitcoin and ethereum is like um before like I think until 2019 2020 they had the glv optimization because not all the coues actually can

have glv optimization only the cve built in a specific way with the CM method allow this glb optimization and to come back what I was saying uh up to 2020 19 I guess the both Bitcoin and ethereum had uh the the curve with the GV ready to be used on the scalar multiplication but it was a patent so they they actually were ready to use but they could not use it until like the patter patent expired and uh yeah now GB is free to use by by anyone so when D and metallic they were asking about like hey I want this coup to be as fast as possible I say yeah there's job job but let's see if actually you can find a ACM

curve and again like I I thought that this will bring nowhere but actually I was extremely surprised again should not happen but well it happened and one thing that to to actually specify here is it is true that GB helps for scalar multiplication and so helps like for many cases but at the end uh for for verical trees where bandness is actually is going to be deployed it will not help too much eventually because for MSN for multiscalar multiplication uh glv degrades with the number of scalar multiplication so for big MSM glv will not help anymore and this is this actually in the in the original paper but for scalar

multiplication you have a gain of about 50% so actually bage is 50% faster than JJ you just mentioned this thing that was patented that came became unpatented or it expired is that something you run into a lot in the work that you do where you're like there's an amazing solution you know it would be amazing but you you can't use it or what what actually is the issue like some company owns it you could use it but you'd have to pay them like what what actually stops you yeah unfortunately in the field of cryptography happens more often than than you want to one famous case apart gvn signatures they were as well patented so if you think about DSA and acda signatures are by far to be perfect

they we don't have prove of security we do have forar but for like 25 years we could not use it because of this previously was the case of RSA and uh there are as well cases of litic cve certicom had a lot of patents on litic grve even even I think Point validation was was patented by CTIC other cases are even symmetric cryptography I think OCB is by far the best as method for encryption and it's patented so you know like unfortunately it happens only the good things they they expire after 25 years I guess I think actually we're now ready to explain the title of the paper no we saw what an embedded curve is you

mentioned you know jobjob versus bander snatched it's endomorphism and GV so what does the title mean what does the paper do so just to give some credits the first guys who introduced the notion of an embedded curve was in a paper called Coco by uh cband coros and it was for the exact same problem which is to have native arithmetic in the statement uh with respect to the snug field and then the zcash guys introduced jupj which is the exact same thing as the curve in uh cocoa paper but they just express it in a specific eliptic curve form which is called Twisted Edwards to

enhance the the number of constraints and then there is Bender snatch as Antonio explained where him and Coors try to have the same curve functionality as jujub or crossbar paper but with the glv with this additional structure this additional endomorphism to make things 50% faster then what we trying to do in this paper and then I'm going to explain now the title is families of endomorphism equips Prime order uh eded curves embedded curves yeah so the embedded curves is this part which is we we are doing the same thing as kba or JJ or bander snatch then the other thing is in the more ISM equipped so we're we're

doing the same thing as Bender snatch but not as J and c and the other thing is prime order so uh elliptic curves have an order which is basically just the number of points on this elliptic cures and this is the group defined on which we're going to do these cryptographic operations and this number of points can be prime or can be composite so if it is composite then we have some issues because we need to multiply by co-actors we need to check that the points are on this sub group we are working on and stuff like this but it comes with fast operations but now we know how to do fast operations over Prime Order Group both out of the circuit and also in a snar context and

you can also look at Halo 2 book or Gar implementations so this is a new part so we are doing the same as kba juj Bender snat but we adding the prime order thing but beyond all of this the question that question we were asking is is there a family of such curves so instead of just finding one curve one isolated curve the question was asked with Antonio was whether we are possible to find families of elliptic curves like for example instead of choosing for example the bls2 381 curve or the BN 254 curve on etherum and then looking if there is an embedded curve that has this criteria what we try

to do is we find both the snar curve and the embedded curve in a way that there isn't only a single isolated curve but you just change parameters and then you have an Infinity number I mean not an Infinity but a lot of a family of of CES so I hope this explained the title I I think will be as well useful to go to do a step back on how you actually find par fored CES so basically like there are less than 10 families of uh par friendly curves so pairing pairing friendly curves are pretty rare they if you take any random curves elliptic curves is not pairing friendly mhm so technically we'll say that the embedded degree is

big and you want this embedded degree instead to be small so if you take a random elri CES is not going to be parent friendly in the early 2000 uh a lot of researchers like Barto theic Barto again with Li and Scot so do we have BN BLS we the MNT we have like Freeman they came out with way to solve something called diof fantin equations there I'm introducing more terms and terms every time but but basically like d equation are like a normal equation where you find Solutions uh not on the real but either in the rational or in the integers so

you take an equation and you don't want the solution to be over the complex or the real numbers but you want the solution to be on the integer on the or or the rational so if you want actually to find paing friendly curves at the end of the day your problem is to solve this Dian equation and solving D equation is not easy it's actually pretty complicated and basically like baric Barto Lim Scot they came with this clever way to solve Dian equation and this allows to find family of par friendly CPS so you start from a seed from like a parameter and you actually you're able to spit per friendly cves so this paper we did with the USF is actually is extended the original method

of finding pairing friendly cves so you use the same seed and at the end of the day you don't only have the parent friendly cves but an Associated embedded cves of prime order so you have like in one goal you have both and uh we do this again solving this day found in the questions all right we've um kind of covered like what the paper tackles and what you guys are trying to solve here how do you tackle this kind of resource question like what is the the angle with which you go in what's the initial idea I'm still uh on the on the quest of try to understand why band does not exist because still didn't understand actually if you read the the conclusion of this

paper is uh we say that we explain something on this paper so we generalize the cves like um band not and so on like and we the the initial paper was like only um covering BLS and this paper we cover as well other course like uh BN and KSS but um we kind of explained more than we used to know before this paper but we still don't explain band not so really this can became kind of obsession for me and is not the only one I have unfortunately it's like I still would love to understand why band does not exist because this should not really

like if you do the math and the likelihood that this exists we did actually few years ago and it's like close to zero I mean if you take if you should not be there and U so that that's the motivation of this kind of works I guess maybe you were that one malicious prover that found the negligible probability of winning you see like in in these things I don't believe in coincidences when there's M involved so i' rather believe there is of some kind of hidden structures so far and Bally like there was an interesting talk by Nadia hinger few weeks ago at pkc she did like the she was an invited guest and uh she did a survey on security that

is one of my other passion on constructions and she was like sharing kind of an opinion from V castri one of the guys that U broke this Asen scheme s the one we mentioned before and actually vter was mentioning that he actually trust more RSA assumption so factorization than elliptic curve DLP wow and the reason behind that is because in elliptic cves you have way more structures than in pure factorization now this is actually can sound a bit controversial for sure but I understand where it comes from because when you add structures in things you have you probably gain speed but you open your let's say holes for potential

security Bridge I mean this is very similar to how pairings were first discovered right they were first a method of attacking certain curves exactly yeah the the first things like that happen with pairing was like this mov attack and even there like now the curve that to we use for pairing is like uh BLS but before the BN curves they were really more popular and there there's this famous quote of menzes that say like B curves are too good to exist and and indeed like now we are actually not using it anymore because like we know that they're like less safe than the than we thought they were are you worried this might be the case with bander snatch so here we open a big

debate U and uh we we go basically like if you remember what we were saying before there are two ways to to build elliptic CSE the random way and the CM way uh there's a website from DJ barnan this one of the most famous cryptographer it's called safe cves and basically like in his opinion for example he doesn't trust cm cves and if you go there's a list of security things that he checks and it doesn't trust cves like bandersnatch but at the same time the cve that where Bitcoin and eum are deployed that they do ecdsa signature it's actually a same curve that's why you can do GMB so we actually you know it's like these are things that we will

discover eventually maybe but you know like uh there is no agreement at the moment on on this topic you talk about these two like bander snatch has these two things that shouldn't be the same but are the same kind of like can you can you say that again you talked about like the I'm not going to be able to word this right but like you have a curve and then you have the Twisted curve or something sure can you just say that again because you're saying is that are you saying because they both exist here it shows that like there should be an underlying structure it would be very unlikely that these two things coexist so what I was trying to say is this like let let let me take a step back is um both JJ and bandersn are uh So-Cal

Montgomery CES so usually when I'm interested again more more terms like montomery CES are like they can never be prime order they're like they have always a co-actor and the co-actor is at least four so but the good things is that you can use like different way of doing scalar multiplication not the usual the usual like method that they use for for VR scures but you need to pay like a little price so usually you do like X only arithmetic so you do the arithmetic without using the y-coordinate but you have to be careful on one things that the the isomorphic curves that is called Twisted curve is as well cry cryptographically strong and you know

the amazing thing of bandn is that when we actually found it not only like the the curve band nut had a number of points that was like cryptographically strong but also the the as amorphic Twisted curve was strong yes and that's unusual and that's why you think there's a reason that it has both of these qualities or both of these curves being secure I will be a surprised to be to have all one part to be cryptographically strong okay but the amazing thing of BN is that they have like B to be cryptog strong for example for BLS 1277 only one is strong the the twist is not strong I see and instead like for

bls2 31 like both are cryptography strong and again I will be surpris already to see the first case seeing both I mean is I mean maybe in couple Fe I hope that we will be back talking about why then doesn't exist I wish our listeners could see how much uh side nodding there's going while you're saying this like the the disbelief the sheer disbelief yeah it's really amazing I mean again we we actually I can remember now because I don't have any more this these noes but we did actually the calculation and it's really unlikely I mean you've mentioned b s JJ this work where does this work actually get used is it part of some systems that we're aware of the motivation is like again

from from Band came from this request that I got by D vitalic and is burle tree burle tree is like um is is going to be shipped in ethereum not in the next upgrade but um in the so not in Petra but I think in Osaka hopefully okay and basically like eum is going to change the way how things are persisted so we will move from uh I think it's a Patricia Merkle tree to to to verle and verle tree will actually use band Nots and yeah that's that's the main motivation but in this case this is not new curves is it is it is are you saying like the veral trees will use these curves or yeah I'm kind of trying to

figure out exactly what the connection is there ver ver will use uh the the motivation of this paper will use like band Notch okay we'll use bander snatch B but if people will have other they want new paring friendly cves with this paper they can actually in one go they can find BLS or or BN or KSS paring friendly CES and the associated embedded groups in one go so they they they don't need like to to have lack like we got with bands they they can really like engineer that actually I have a point to add to this which is a problem we have in the blockchain community uh when we are doing elliptic curve cryptography which is basically so

we know elliptic curves cryptography from other parts of cryptography and then we know pairing friendly curves and now we are using pairing friendly Curves in SNS so what we did is we just took an elliptic curves that we know from the elliptic curve cryptography and then we added uh just um a criteria which was again another word which is the two adicity which means that we can do ffts over the snar field quite efficiently and then we worked with this curve so this curve is for example the bn24 which is on ethereum or the bls2 381 which is on zcash and now also on ethereum but then whenever we have a new problem it's

very difficult to move from this old elliptic curve to a new elliptic curve for example when we want to do things like embedded arithmetic then we were lucky to find B snatch but it's not always the case I mean I ran Antonio code on I think uh a dozens of elliptic cures and none of them was uh had unimited curve with this security and uh so it's really really unlikely and I think that it should exist I mean my take on is it should exist because I mean it's so improbable that there must be a reason for it so when we wanted for example to do recursions Al zix then we had to introduce a new elliptic which

was the BLS 377 and then the bw6 that's forms a two chain with it now now that we want to find uh families of embeded curve the problem we face is we need to introduce others paing friendly elliptic Cur so we cannot just pick an elliptic C that we use on ethereum and then find an eded so it's always the same problem which we keep the discovering new uh requirements and every time the requirements means that we need to start from the beginning we cannot just take any CES we had before and then add this new elliptic Cod to it I've always understood that like the things that have been implemented in ethereum or like choices that like early ethereum Engineers made sort of impacted how these newer systems can actually

interact with it and it sounds like the change that's happening here is it at the base layer like this sounds like it's part of the upgrade so this would be like the introduction of a new family of curves or curve specifically yes and you're saying you you can't add on it's not modular you can't just like upgrade what's exactly there you have to sort of start again exactly so for example if we want to use this families in ethereum for example we need not only to add this new embedded curve but also the underlying SN elliptic curve which would replace BLS 2 381 but it's very difficult to do so I mean I have a NE IP to add B W 6761 curve four years now I wanted to

ask you what year at least let me give you the news I mean it's not so new anymore but basically like finally after like three years or fighting BLS 12381 pre compiles will be shipped in the next upgrade of ethereum so this is yay ni is yeah it took only like three years but at the moment like and I'm bit let's say ashamed I can say that at the moment like the only promiles for paring friendly course we have is like BN 254 and yeah I mean it's not as weak as that everything is going to fail but it's not clear how many bits of security they it has but definitely definitely not 128 bits of security and it's the only

option we have now in the pre compile I do want to come back to um the paper of today's session because there's one thing that we didn't really cover is what is the method that you guys came up with to find these families of prank friendly curves with embedded curves yeah so as uh Antonio was mentioning earlier so you have these Doo fantin equation so the nice thing about these complex the CM curves complex multiplication curves they need to satisfy some equations so as Antonio said those pair infant cures are rare So and they follow an algorithm for example the BLS algorithm the BN the KSS the Freeman so there are different families but they are like just maybe less than 10 and these algorithms they verify some

equations and there is one equation that is called the complex multiplication equation and this complex multiplication equation has some uh parameters which are again discriminant of the complex multiplication the finite field characteristic of the finite field of definition uh the number of points or the order and when we talk about families those parameters actually are not integers but they are pols so if they are pols then I can just substitute evaluate these pols in some seed and then I have a curve if I change the seed I have another curve and this is what defines the family so what we did is we took those families we already known which are the BLS for example 12 24 and

its generalization the BN the KSS and we added a new criteria which is also another polinomial equation which is basically the field of definition of the embedded Curve will be the scalar field of uh the underlying curve and this underlying curve since it comes from a family it can be expressed as a polinomial so we just substitute this polinomial which is a scalar field in the field of definition of the eded curve and then we have an equation and we need to solve this equation and to solve this equation we do what we call a half gcd which is basically we have its boys down to having a polinomial which we need to express uh the rational function of polinomial and once we have

this we just evaluate and we have the equation of this new eded curve order and this polinomial uh we just check if it is irreducible or not if it is irreducible it means that it might give raise to uh Prime order uh family this first equation when I was talking about the complex multiplication discriminate we fix this this complex multiplication discriminate but looking at the subfields uh quadratic subfield and uh for example if we take the discriminant equal to three four or six we go over all the options and for example if the complex multiplication discrimin is for example D is equal to 3 we know that there are six twist so earlier anonio

was talking about that twist but actually it depends on the discriminant if the discriminant is random there is just one quadratic twist if it is equal to three then there is a quadratic twist two cubic twist twist and two60 twists so we go over all those twists and we check if the polinomial are ir reducible and each time we give families based on all these orders and at the end of the paper we have so constructions over BN BLS KSS and we give concrete examples following our algorithms of elliptic Cur like for example we have introduced a blsw 380 and with its embedded curve that is in the morphism equipped byb W okay so it's a lot of tral an error in

the final stages in the final stages exactly I mean the in in the construction uh it's not trial and because we have an algorithm but then to find the elliptic curves yeah absolutely I mean because you need also to find the nice to adity the nice how many way to have fast pairings and stuff like this and just to add like what you have said like the reason this works is because like the best field that is the order of the very trended CS is a cyclotomic polinomial and omic polom sounds like a cool band name I like it yeah but that's basically like it's a mouthful word but mean like reducible

polom with nothing fancy but just mle but this is I think the the most important thing that I forgot to say it's it's because the scalar f polinomial is a catomic polinomial all they act from one what tools when you're actually like doing that trial and error part of it what are you actually doing I don't know enough about the work you do are you doing it like each one you're just trying them out are you running something like where how what do you actually use to do this so we use Sage mats okay which is a python based uh uh framework to do math but I think we have uh we have algorithms that uh that we have from the community like Alpha from

in Ria in France to to Define find these curves to to find this curve with to change the seed and stuff like this so we already have the algorithms and normally they should be linked to the paper in this field like are there cryptography specific tools and also are there like this kind of cryptography specific tools or are you able to just use existing math general math tools always uh Sage math is actually defines already uh these cryptographic tools for example you can do your own code your own class in Python but you need to Define everything from scratch but for example when you use Sage math or for example there's also magma you can for example just type elliptic curve you

give the finite F GF and then you give your number and then you give the coefficient and then boom it gives you analytic curve nice so yeah I mean otherwise it would be very very difficult to write everything from scratch and then you use an algorithm to like create multiples of these until they have the properties that you're looking for yeah so once we have defined those pols and we know that for example if a polinomial is reducible then we know for sure that it's not going to give a prime order because it is factorized but if we know that it is irreducible then there are chances so we just have some seeds and for the seeds we have some other parameters for example if we looking for BLS 12 we need the all the parameters to be integers right but in some polinomial we have

divisions by some integers so we need the C to verify some conrant so that's those polinomial gives integers if we need to add CS for example we need some other congre criteria so we just have an algorithm that takes into considerations all those criteria and then we we we we iterate over this seed until uh one clicks these actually are just to complete the things like of course like cryptographers use these tools but it's is a tools for number theories that I mean they are used as well not only by cryptographer but if you're all interested about number theory that like you don't care about application like you can still use it this pretty cool cool I mean for added context this sort of work finding curves with properties

is sort of the the boundary between what is pure math and what is cryptography like you're you're sitting on that boundary here and actually you know like before you were actually joking on it rightly but actually like this kind of cryptography especially isogen like by far the most mathematical area of cryptography so it's like the majority of people who work in this area are like number theorist or like mathematician more than than pure cryptographers like are really the the part cryptography is pretty big area but um you know if you see like uh the this this era of cryptography is the the most number theoretical one especially like if you think about elliptic CSE there's intersection between many are of mathematics you go from F fields of

course algebraic geometry but you I know something called imagin quadratic field so it's really like really number Theory things like that it's it's really like by far the best are of cryptography in my in my bias the way your opinion nice I have a sort of a higher level question here which is bringing it back to the veral trees or ver is it veral trees or veral tries or is it just a choice pronunciation I think yeah I think it's like I can't remember which one D use all the time because I've heard I've heard both heard both yeah but my my actual question here is like I sort of understand it in the ethereum context but youf you're working at Linea as an L2 I guess you will be able to use these

veral tries it'll make something better for you but maybe you can give us like that higher level like use yes so for Linea as a ZK evm we're driven but what ethereum decides right so if you have an ethereum so for example uh so we were talking at the beginning about these embedded curves to verify some signatures for instance but for ZK evm the signature is already defined on ethereum and it is the ecdsa over a specific curve called sep 254 we cannot just use this uh paper with it but we need to go with the the decisions of ethereum for example so I'm not sure so I'm not sure about veral trees uh per se but we have a little of flexibility that

we did for example in linear to use new elliptic curs which is basically so we're using a notion of embedded curve which is what we call the two chains where we have first elliptic curve and the second elliptic curve with where there is a dism mat so the same thing as uh embedded curve but on the other way but the idea is basically since we do not have this m match we can aggregate a lot of blocks of transactions a lot of proofs and then at the end of the day we have a proof over an elliptic curve that is not native to ethereum so we instead we were doing things on ethereum elliptic cve we're doing it on our custom elliptic Cur so namely BLS 377 and BW 6761 but at the end of the day we

cannot push this final proof to eum so here we do some nonnative field arithmetic where we force this proof bw6 to be on BN which is basically having a final proof a b254 proof of bw6 so the flexibility we have for Layer Two is before pushing things on ethereum and so then are you saying that like in a way this work like there's such a great use case for these curves that having the curves implemented on the base chain helps later because if you had these curves on the base chain it would be better for Linea away absolutely absolutely the other way around is the hack I explained which is doing things the way we want and then incurring this

final mismatch yeah but like when this new thing goes through you won't have that problem absolutely right but it's not necessarily its use in veral tries that Linea will make it take advantage of uh I mean it can you be used on veral tries but it can use on anything I mean I just gave the example of aggregation because this is what I've been working on on Linea but it works also for V TR cool I have one last topic that I want to touch on because we've talked about curves a lot throughout this whole episode and I wanted to ask the both of you how do you feel about so the recent developments where things seem to be moving more towards the direction of uh Starks and hash based um proof systems I feel bad but I feel bad just because I like

elliptic roof too much and U but I mean of course like Stark is great progress is inevitable but I would really love to see elliptic CES as long as I can so hopefully I'll be retired before this because I'm too old I'm the 80s and but even like if you think about postquantum crypto it's all about ltis and that's why like isogen is the last attempt to keep elliptic Gres into the game if isogenous will not exist you will not see any more elliptic RS in cryptography with postquantum crypto and so as a elliptic lover I will hope that the snark will win Tower star youf what about yourself I think I have a similar take as Antonio which is it's too bad

that iips are disappearing a little bit but I mean they're still there for some for example in some new schemes like uh in Nova scheme or for example in in zcash for Halo to like those cycles of non-parent friendly elliptic C so there is a still place for elliptic C but I agree that there is a lot of development for hash based snars or stars and uh I still do believe for example as a builder of a ZK evm there is place for both actually and this is what we do because we have um our own proof system which is based on orine we call it Vortex and it use code based cryptography so it uses hashes and we use actually a latis b bed hash and at

the end of the day we need an elliptic curve to go on ethereum so uh there is still place for both cool well youf and Antonio thank you so much for coming on the show and telling us all about this work that you did sort of the background on the work how we can use it I mean this was definitely an episode that for me was somewhat deep in the weeds but I'm glad that I got to also tease out a few you know questions I always wanted to ask cryptographers and and got to ask you guys so yeah thanks thanks a lot Anna thanks a lot niik I really appreciate it thank you both thank you very much Anna and niik cool so I want to say thank you to the podcast team Rachel Henrik and Tanya and to our listeners thanks for listening