“Is Bandersnatch for Real?” by Antonio Sanso

Transcript

hi everyone uh thanks a lot for coming for today's Lear and share we are very happy to have Anon s from EF talking about BND snatch Antonio has been working on quite a few different things uh one paper that I read and really enjoyed but also dread reading was uh about vdf a few years ago uh but he has worked on quite a few different things today he's going to talk about cryptography more particularly BND snatch and will be able potentially to have an answer whether BND snatch is real or not so thanks a lot Antonio for joining us today and the Flo is yours right thanks Rafel um yeah so just

quickly introduce myself as Rafel said I'm Antonio sansu colleague working at the as a researcher in the core Foundation team um and yeah today do a little correction to from what RAF said um yeah this talk in the paper is about a followup of batch and I hope you understand through the talk why is specifically this joint work I've done with youf El husne uh they print this uh online there's a there's a link there you can you can follow and see and uh yeah as usual um hold sec I

Mark like the slid that you requires a bit more attention with the with the red star feel free to interrupt me at any time during the call during the talk um in case you have questions I don't mind having question during um so as everything everything starts with the anelliptic Curve so or like everything that's related to this starts with antic cve and U yeah what is the cou to start with well is starting else the locus of a cubic equation where the coefficient A and B are over some field of definition so it's an algebraic curve

and uh as we know is is equipped with the some kind of group LW um so this what I'm going to show now is was already known by the phantos this famous Greek mathematician so it really discovered this beautiful group low so here in the in the picture we have the elliptic grve defined over plotted over real but he actually discovered that if you have two points that are rational p and Q you can actually always find a third Point P plus q and how do you do that yeah well you basically trace a line that intersect the the curve in

they intersect these two points p and Q being a third degree equation this line intersects the the the curv in the point R and you just mirror it and you have P plus Q so of course this uh this is not the normal addition but this a special kind of uh addition Lo um yeah in cryptography though we are not using litic over the real or the rational but we are more interested about litic Rover F pills so and they're a bit more ugly than the previous one so this is a really to examp examples where the litic is defined over Front Field of size 191 well now we have all the ingredients to do our below def change over this e

defin over fq how well how do we do that so the pretty simple the group elements are the points on the litic curve e uh the operation is the the point addition that I've just shown before and uh well we have a joint point at Infinity that is the acts like identity element the order of the the grp the group is the number of points defined by um that you can find using the sea algorith that is pretty uh fast and well in order to do def def kick change you need to believe that the elliptic discret log problem is hard on this group and that's um the way to to do the

fman um in order to to see what um what we're going to describe in this paper we need some uh some definitions so uh this is the way how you compute the I mean you know the formula to know the number of points over efq that you compute using thisa algorith Thea algorith um it computes the T in this formula so the number of points is Q + 1 minus t where T is the TR Probus soall and this TR of Probus is bounded by this has v bound and cannot be bigger than two sare root of Q um at the same time the the the number of points of the quadratic Twist of the curve is Q + one

plus T um one thing that we're going to use heavily in this talk and we use heavily in the paper is this this So-Cal CM equation um equation is um is an equation of this form where we have an additional parameter uh d uh that is called the discriminant of the curve so what we want to do what we're interested at is uh actually solving this equation over the integer so finding solution of where QT uh D and VR integer this this equation called Dian in equation um so um if you want really to to do litical cryptography then what we

we need is a curve now how do we find this curve and we basically have two ways to find an elliptic curve suitable for cryptography the first way is like what I call the nist way and I call like this because it's how the Mist found the curve Us in TLS so the famous p256 and so on we're found using this way and what you do is nothing else than look for random curve defined over efq uh Computing the cardinality using this sea algorithm that we just discussed and see if the the the order is suitable so if it's a prime number or is a or a prime number multiply M Factor this is a kind of rather slow way to find elliptic C

but it works pretty well uh the second way is what I call here the CM way and it's using something called CM method that we're going to see a gist in the next slide it's really there's a there is some deep mathematics behind the CM method uh but describing it is at high level not so complicated the point here is that um well this curs comes with some additional properties uh for example they have um some computable um anamorphism and uh well some people think that they're kind of dangerous to use but at the end of the day the scoups are pretty the one used in ethereum and and Bitcoin for example sep 156k one is

the really the C used in Bitcoin and ethereum well is is built using cm method so how does it work this method so I said we want to solve this dant in equation and the way to do it is just like we try different discriminants d uh and uh until uh and we apply kakas algorith until we find the solution so kakas gives some really it's really efficient to find solution for this kind of dunting equation and uh once we found the solution this implies that we have HD pairs of of such groupes that that satisfies the question um I say something that is not important for this

talk but for people that are into number Theory this HD is nothing else that the class number of the imagin partic fields of this discriminance but if you don't know what it is forget about it but important thing is that once we know the existence of HD pairs of elliptic curves we can actually find uh this sces using uh Computing the zero of something called Hilbert class polinomial all this is kind of seems pretty pretty complex and from the point of view of mathematics pretty deep but doing this with with some problem like Sage is pretty pretty super simple now some motivation of our our talk comes from from from this um um

dichotomy and dichotomy and this um the this history about jbj versus BN so um if we're interested about litic cryptography one branch of it that is really important is is called paing based cryptography this will allow us to do super interesting things like BL signatures or tri-party dman or ibe that is identity based encryption and um in order to do that we need some more definition uh and some special curve but the first definition we are interested at is the embedding degree and the bending degrees is nothing else the smallest positive integer K such that you have NR that

divides qk minus one and if if you find this K is then better degree at this point you can take the the full torsion of e that are nothing else than two points that have order eror and you can Define pairings where the the domain of definition are the two points p and Q def defined over G1 and G2 that are the groups of elliptic curves and the Cod is uh is over uh FK to the with the extension of FK where K is the the is the embedding degree for example the C Us in etherum is the most common C using in imparing best cryptography at the moment is BLS 12381 and the 12 in this

curve stands for the the Met degree of this curve is 12 so decay of the of this BLS SC is 12 so if we want to do pairing best cryptography we need pairing friendly curves so the the the most famous embedding curves uh are uh BLS at the moment previously they were baric until few years ago even the precompile of etherum uh at the moment has only BN curves they were the most efficient one until a few years ago the reason why they're not used anymore is because people believe there is an attack actually not they believe there is an attack that uh doesn't makes uh BN not having any more 12 128 bits of

security but the bits of security of bar curves is about 100 uh so that's why we migrate as a community to BLS curves and then there are other curves like ass in the table or or MNT BW what is common about this family curves that are defined using polinomial so the the way do you actually um you actually find suitable curves is starting from sdu and you have the the the base field the scalar field the Dr of robinus are defined based on this seeds so you actually are iterating over seeds until you find some suitable parameters and as well some properties

that will be interesting for zero knowledge for example uh one you want as well that the subgroup order R has high du adicity that is marful way to say that Rus one uh must be divisible by a high power of two and another things that's really interesed for ZK uh for parent friendly cves is that you want to have a UD with a low having weight that again is is a way to say that if you take youu at the SE and you put in a binary form um you want to have a lot of zero and this will have the Miller Loops being really efficient and you have other properties uh that you want to to have in order to have suitable uh parent

friendly course for TK now um this opens um the door to um to um the next chapter of this presentation is that is the the main actor of this presentation is like embedded course the first time that appear embedded course was in this work Coco I think it's like 2015 like this and the reason why appeared is because if you do pairings uh if you do ZK uh our per friendly curves um you have the the Ari the the arithmetic happens over the scalar field of BLS uh so will be actually nice to have a new curve defined over the scalar field of BLS

where the arithmetic happens and you can actually prove things uh about this new curve on your DK circuit and um this is um brings to to to the to the main protagonist of this this talk that is um band and jobjob and um basically um this started um two years ago when um vitalic and danrad were working on veral Tre or veral Tri projects never understood how to pronounce and uh they asked for an efficient um curve defined over the scolar field of BLS 1231 well we already

knew that jabjab existed but jabjab was built using using the N way and so was used randomly funing cves that they were Twisted Edwards over the scalar field of B2 TR one uh since they doneal risk for efficiency I we thought to um with the Simon and Z we have to apply CM method to see if we had some suitable curves and the reason why we we we actually were interested about same cures because they come with the soal glb and morphism that brings some speeds ined um if you see buers Notch for not based fixed based scar multiplication you see that

it's actually 42% faster than than than Chop Chop so we were looking for for for this curve using CM method as we said in order to to find CM suitable curves you actually iterate through the the discriminants so we try discriminant minus 3 minus 4 and well when we arri to the discriminate minus 8 we could not believe our our eyes and we found um suitable curves this band snatch that has is a perfect Mong curves being with aactor of four and uh as we I will mention in the next slides you want as well to have a twisted curve this save so it's remarkable fact that as well the twist of band snch has really high level

of security uh now if you want to really understand uh why glb is is actually fast uh here is a g a gist of what this is actually fast so for example suppose you want to compute uh scalar multiplication X time G where X is a scalar 26 bits and G is the the Bas the generator um and this curve that built using CM method they come with a with a fast to compute endomorphism so suppose that you have this endomorph endomorph endomorph Fe that allows to compute some some other point a the some

other points H that is a * G so at this point you can use some lais technique to split the the the 256 scalar uh fi is the scalar uh to two scalars of 128 bits uh this is a really simple 2 by two Lattis problem so it takes really few milliseconds at this point your scalar multiplication actually can be split in two simpler when I'm 20 bits uh scalar multiplication and you can apply uh some multibase multiplication that is actually faster in this case is simply a 2 MSM and um yeah uh so we found band snatch that and this is show again the

previous um um slide uh that see that you have on the right BLS tr1 and on the left the embedded group is either jbj or B um one little parenthesis the reason why both band nut and and and jabjab are Mongomery curves is in the past when uh elliptic cryptography was kind of a invented the couldve were defined over a biess model that are prime order the point is that if you see the the formulas for Point addition B they're pretty cers on and they comes with a lot of corner cases so uh people um um notably DJ barnon came with the c

25519 and show that the formulas are you have closed formula and it's only rtic and especially the fact that you have close formula is pretty friendly to have in a circuits so that's why both J ja and B were Lo to be on the Montgomery for so this is the close the the um historical background part if you have any question it will be a pretty good moment to ask otherwise we go to the subsequent part um I just have a quick question you just talked about and Mong reform what about the twisted uh because it's also quite interesting it's a fewer operation than Mong Marine and you have a complete

addition so there is anamorph between between Mong and Edward Twisted Edward forums so uh every cou can be can be represented in a vious model there is most generic one but Montgomery C they're pretty specific and uh they have aactor of at least four so they cannot be Prim order and Sam has Twisted Edward so you have anoris but you can always reach between Montgomery model and twisted Edwards but that's not the same for biust model only one cult four can be represented by a Montgomery model because you need the ecofactor of four thank you answer your question yeah yeah

yeah yeah uh thank you if you have any other question otherwise I will just go to the next part of the the doc all right so oh sorry yeah uh I have one other question which I could have asked iter so you you just talked about two different ways to find eliptic C with paing friendly tic C you were talking about the this way and the C ways uh this is about generic elliptic gr not paring friendly oh sorry yeah uh is that an advantage to use one over the other if you have Advantage so so the left the need way is is lower but the

problem is like the right way some people think that there are some special property properties about CM curves indeed they are uh the fact that you have this neomorphism so is good because having this neomorphism brings speeds yeah but from the other hand people like DJ barnan they are afraid that this this more structure that you you bring to the curve can be dangerous but again like the tech p256 K1 that we use in B in in ethereum and and Bitcoin is actually a CM Cur so it's really bigy one from one side you have like no structor and slow from other side you have like a lot of structors that brings speed through this GB andom morphism but yeah you don't you

we don't know yet we will never know if this structor brings some some security issue exent right so cool so uh here we start with the motivation for the for the new paper so um as we said before the the curves um the paing friend cves they um they're built using a CDU uh so here I put the CDU of dls12 3 at one so if you take the CDU your factoring is equal to- 1 * * 16 and this two biggish number and um what

happened is like I was observing the the table of band and what I noticed is that um well the order of two of the scores was uh had a huge overlap with the SE of the bls2 31 so this one was kind of remarkable and uh of course could not be a coincidence and uh require more uh investigation and we actually in this paper done with youf we found uh complete explanation why this happens and indeed brings a lot of framework for generalized cves like bandn that have a prime order and have up with this glb

and morphis and we see how this actually is possible before to do that we need a bit of notation so uh we just have the same notation before so where Q was already the characteristics but now at the moment we're working with the polinomial so we have a q that is defined by polinomial qu and the t is the trans Tu is the transus and R is the subgroup order for the embedded curve we have a Pedic of e and but um since the embedded curve are built using the scalar field of the pr curve you you have that area U is equals QE of U this is like by

definition now how this is um help us so what we want to do we want to solve this uh this again this CM equ question but for uh for embeded Curves so we start from the same equation before and uh as you can see we can uh substitute QE of U with with r u because again the scalar field of BLS 1231 or scalar field of the curv is the the best field of the embedded curve and uh now how can we solve this um for BLS for example um I'm showing you the solution for BLS but this will happen the same for BN and

KSS um if you see the ru for BLS is this polinomial this polinomial is a bit special um is indeed this called cyclotomic polinomial but again is a marful way to see that this a irreducible polinomial where the root of unity are known and uh for example for bls2 the the ru is nothing else than the 12 cyclotomic polinomial for BLS 24 the r is nothing else than 24 cyclotomic polinomial how does it help let's see so again we start from our below CM question and uh we know now that uh uh

Ru is a cyclotomic polinomial Now by construction uh we have this uh we have a number field K uh that is a number field over for BLS is uh over the K root of unity questioned by the cytomic polinomial and we have some standard result of theory of cyclotomic fields that we can actually use and leverage pretty well so we know for example that if you have a cyclotomic Fields so if you have a that K contains square root ofus one if four divides K and the square root ofus two if 8 divides K and so on so how

does this help again so step by step um this again our complex multiplication equation and let's see the information we we discovered in the previous slides how can help well we know that k for a number fields and we know that the some Fields have some square root that are contained in the fields so we can actually rewrite our uh complex multiplication equation in this way so we know as well that R is zero in the number field so we actually are taking our previous equation modu and we can rewrite in this way uh then we can apply some other

rewriting and basically we know that minus D is a is a square and we are actually bringing D from the other side and T from the other side and we we have another polinomial W now the fact that minus D is a square by definition guarantees a solution how do we find the solution to we apply some uh really efficient algorithm that is H gcd and uh from the fact that the the solution is guaranteed in this sub field uh we can we we we are sure that this how gcd is going to spit as a solution if we apply this for BLS uh here is the solution that we find and uh so what you can do now is uh do

whatever you were doing before when you're looking for BLS curve but you can extend uh the solution to embedded group so you in one go you can can find Bas curve and embedded curve only parameterized by the CDU and in this case what you're interested are the solution that are involved and the reason why we're interested about that is because there are um a reducible polinomial and we Leverage The bakosi conjecture that says that um if you have a reducible polinomial produce infinitely many primes for infinitely many integers so at this point you can find BLS curves and embedded curves parameterized by the CDU where the the

order of the embedded curves is uh is prime um now you might ask why Prime at this point you were saying before the bias equations uh have the some clumsy um some CL some clumsy formulas true but in the meantime after after theb introduced group 2559 we got a new paper from uh renes costell and batina where and we now have as well complete formulas for primor litic Curves so we can actually uh come back to what we started from from to Tobi model with prime order and having complete addition formulas to be building the circuit without any any

issues and on top we avoid annoyance that we have with co-actor I don't know if you remember years ago for example the ring signature Monero had a vulnerability because of this go Factor now uh another um uh think that we in the paper uh we uh apply our formulas to find new curves so we have now a bls2 380 curve with a prime order embedded cve with the ficient morphis a BLS 24315 and of course our Theory explains now completely the Pluto Aries cycle fund by Dar I think and I would like to conclude this

presentation with a a question for you um if someone in the audience will be able to answer this this this question I have so basically what we found now is this so we've introduce a new bls2 38 Z curve uh with an embedded curve of prime order this embedded cve of prime order is a j80 invariant so it's a j invariant zero curb so this means that you have a cycle so you have starting from a curve that is bls2 38 Z you have thein F Q order R you have your embedded curve that is base field R and that's order P but at this point you have another curve

def over P that has order R so you have the cycle and uh you have a chain of BW curve that is the standard chain uh with a BLS so what you can actually do now is do some Hollow super Nova Shenanigans over these two curves uh and then at the end do some ZK magic over bls2 Z cor and my question is is this any useful can you imagine any scenario where this is useful and this basically concludes my talk and I'm curious to know if someone has some idea for this if not I'm I'm concluding uh it's a good

question uh finding uh pairing of uh pairing of Cs uh to be able to implement uh hello has never been easy so having more options is always good uh I work I worked in the zkm team and we've been thinking of um using of using recursion uh so so we have had some team members looking at shova Hova and all the new protocols that have uh been released for the past year so and I think that there could be an interest uh but I can't guarantee it it depends on the on this curves parameters fa itties and so on uh but oh

this is this are bls2 zero is again is a ZK ZK friendly curve same as the Met curve so again like imagine you have all the power of hollow Supernova hypernova on the right so what you will have for example with pasta curves but at the end you can actually your arithmetic is ready to go on the bls2 3 Zer curve yeah because yeah I think it be useful uh it's uh for for EFM we've been waiting for bls2 uh 38 for quite a while uh and I think we're going to keep it for quite a while too so I think this could be quite interested quite interesting sorry yeah just like keep in mind it's not bls2 381 it's a new C we defin in the

paper oh sorry I forgot toit uh yeah right so this will be for some entirely new application where again it's a new curve defined but the the characteristic here that is new is the fact that you don't have all BLS curve and embedded curve but since the embedded group is a prime order and has J Bar and zero you can do some uh yeah uh I think it would be interesting uh I could see people trying to use it uh I haven't really heard of it so far but I'm not talking with the relevant people this is new again like this is

new on our so uh bring the message along maybe someone will will actually is looking for this and uh here's the solution and we we will have some new results coming soon as well I guess on this on this like um curves [Music] um connections between others so it's like we will have a we will have more to come that sounds great and basically that's it if you have any question about previous slides otherwise it's that's the end yeah uh unfortunately I don't see any questions in the chat uh I don't have more questions on my end

but I will be sure to relay your presentation and your questions to the relevant teams in EF uh I'm sure that the hello to Team would be quite interested in looking more in your paper uh and make come back to you all right so if there's no more questions thanks a lot s for joining us today and thanks a lot everyone for joining and see you next time for the next learning session have a good day thank you bye-bye