ZK12: Cyclic Groups from Geometry - Alp Bassa

Transcript

[Music] thank you all for coming it's a pleasure to be talking here thanks for coming after the lunch I'll make sure you don't fall asleep with lots of M it's even the title is a bit cryptic so it will be a surprise what it's about uh but uh so let me start by introducing myself my name is Al basa I'm a head of cryptography at veradis so veradis is a a um security company we do audits in the blockchain space uh focusing a lot on ZK but also other stuff too and uh most of the team members come from academic background um more on formal

verification so we also have some in-house tools that we develop that we use in our Audits and so on and um we also have some research that we do inhouse and um it's a lot about formal verification but we also do research in cryptography and number Theory and so on so today I'm going to talk a bit about um cyclic groups from geometry so what's it about so you know lately there have been all these variations of the fast forer transform you you might have heard EC fft Circle fft galwa fft and so on and uh I'll not talk about anything new but what I'll try to do is I'll try to give you uh a way of um think of these in a unified manner so um there are very

many nice ideas in all of these contributions I'll maybe one aim of the talk is to push them more into the spotlight and uh I'll try to kind of show how you can kind of interpret many of the results there from results about curves covers of Curves automorphisms of Curves and some basic group Theory and um I don't claim to be complete there are many details I will leave out but that's just to give you a rough overview how you can kind of see them together as instantiations of one uh idea and that will hopefully help to generalize it and kind of uh hopefully boost some research in this direction and uh cause some um visibility to those nice results okay so um first about fft I guess most of you

are familiar with so the main idea is that um when you have a polinomial let's say over a field in our case it will be a finite field there are various ways of representing it one way would be to just list all the coefficients but you also know that if you have a polinomial of degree n it has n coefficient n+1 coefficients and it is uniquely determined by its value at n+1 points yeah so these n plus1 points x0 up to xn I will call the evaluation domain and rather than thinking of the polinomial as represented by its coefficients you can think of it as represented by uh its values at those points in the evaluation domain yeah so you can pass back and forth between those two I mean because

of some analogy with uh um like the forer transform you can usually call the coefficient form the time domain the values you will call the frequency domain and you want to kind of pass back and forth and this is basically just linear algebra yeah so you have the vector space of polinomial you can either represent it in a monomial basis or a lran basis and that would just correspond to passing from the coefficient form to the evaluation form yeah and why is that useful uh I mean for instance if you want to do fast polinomial multi application if you have two polinomial of degree n if you want to multiply them in a trivial way you would need order of n squ operations if you do it a bit better use katuba or

something else you can lower that but if you represent your polinomial in uh evaluation form then you know that uh the value of the product of two polinomial is the product of the values of the polinomial so you just need to do a component wise multiplication yeah so you can pass from one domain multiply there fast and then pass back of course there's the issue with the degrees of the polinomial so I'm not going into any of those details but this would be just one reason why you would be interested in having polinomial represented in uh evaluation form and uh to pass from one representation to the other basically what you would need to do is you need to

evaluate the polinomial at many points so you need to do fast multi-point evaluation given a polinomial you want to have a fast way to evaluate it at many points and the fast forer transform allows you to do it in uh nlog n order of nlog n operations yeah so what how does it work so let me talk about the more General setup the discrete forer transform over a finite field so you have a finite field with Q elements you take a primitive end root of unity so this requires that already there is an element of order n in the multiplicative group of the finite field so n has to divide Q minus one this restriction will be important later on in the talk and you just take as your evaluation domain

the end roots of unity right and then um when you want to evaluate a polinomial you just have to uh compute that sum over there which is in fact in terms of linear algebra it is just a multiplication by a vont determinant which already shows that also going back will be something similar right because the inverse of a vont determinant up to scale is again a vont determinant okay so how can this help speeding up so assume now that the N that you have that was the order of the root of unity that I had that so n was the size of the evaluation domain suppose N is a power of two yeah so you need that a big Power of Two

divides Q minus one you again take a end root of unity you look at all the end roots and you look at that as a evaluation domain but then uh some very nice idea is basically if you want your polinomial if you have your polinomial F ofx you can separate it into those monomials that have a even exponent and those that have odd exponent so given F ofx you can write it in this very particular form using polinomial F0 and F1 of half the degree how is that useful it's useful because of the following fact if you have a root of unity of order 2 to the L it's Square will be a root of unity of order 2 to the L minus

one so uh so evaluating F0 of x^2 or FS1 at x^ squ as at any of the roots of unities just corresponds to evaluating F0 or FS1 at the corresponding uh 2 to the L minus first root of unity Yeah so basically the squaring operation that you have uh shrinks your evaluation domain yeah so the evaluation domain shrinks the degrees of the polinomial R but the number of the pooms double yeah so rather than evaluating one polinomial at two to the uh K points you will evaluate uh two polinomial of half the degree of 2 to the K minus one at half the many points and you can kind of you

don't stop here you can go on recursively rather than evaluating F0 and F1 at the uh smaller evaluation domain that I'll denote by S1 you can again uh separate them both of them into odd and even parts and go on like this yeah so you might be wondering what's going on here if you want to generalize it understand it like there are some very nice things that fit in very nicely together right you have the sets the evaluation domain um you have the map X squ right that was kind of the map that you have substituted into the polinomial there's this one function X in front and they fit very nicely together in the sense that if you take your evaluation

domain if if you square all elements the size U gets half right and you you know that uh for given a polinomial of given degree you reduce the problem to pooms of lower degree so there's lots of magic happening here so once you understand this magic you can try to to kind of generalize it and mimic it in other setups right but um in this particular case we needed that Q minus one is divisible by a very high power of two or it is at least a smooth number it has many small fact uh factors and uh this puts restriction on the que that you can use on the size of the finite field so it puts restrictions on the finite field

itself yeah so you might want to look use some other primes that are good for fast arithmetic like goldilux primes or baby bear and others but they do not have this property that Q minus one is divisible by a high power of two oh sorry they do have you can find those primes that have this nice property that Q minus one is uh divisible by a high power of two but you have to restrict to those basically you have to look explicitly for primes that that so that P minus one is highly divisible by two which kind of uh is a restriction that you want to get rid of yeah and a solution to this is to look at variations of the fast forer transform

one way would be rather than looking at at 2 to the L root of unities you can generalize it at 3 to the L root of unities so you want that P minus one is divisible by a high power of three or there is another method called the discrete Gala transform by kle from 1996 uh so it says that if p+ one is divisible by a high power of two so if you take a prime P such that p + 1 not P minus 1 but p + 1 is divisible by a high power of three to uh you could for instance take any of the m n primes then uh I mean if uh p+ one uh this would imply that P is congruent to three

module of four right I mean if uh your power of two is at least four you know that um p + 1 is divisible by four so P has to be congruent to three module of 4 you know that minus1 it does not have a square root inside FP so there's no element whose square is one you can adjoin that element that I just denoted by I so it's an element whose square is equal to minus one you can adjoin it to FP you get an extension field FP squar and then the nice thing about fp^ squar is it's just like the gaussian integer so it's elements of the form a plus b i where A and B are in FP so you have a total of p^ squ many points if you look

at the invertible ones you get p^ 2 minus one points right so uh in the normal finite field the multiplicative group had order P minus one now we have a multiplicative group of order P ^2 minus 1 but for that we pay that we have to work in a larger finite field right but the nice thing is um p^2 minus one has not only the factor P minus one but also the factor p + one yeah so it would help you if already p + 1 is divisible by a high power of two and in the particular case of a meren prime if you take a prime of the 2 to the Q minus 1 you see you'll get a total of Q + 1 factors of two yeah and uh but for that

you what you pay is you work inside an extension field um you have to weigh out if it's worth or not and this idea uh I'll come back to it later when I talk a bit more about Circle Starks uh but there are some nice results also already for those fields so if you take a m m Prime other than the case for Q is equal to two then uh result by cbor and Tesha already tells you how you can explicitly find a primitive root of unity right and it also helps that although you're working inside FP squar your initial problem was something in FP so you wanted to evaluate at points in FP so it's kind of a way to say that you do like a um forer

transform with real signals so to say you can create some um uh speed up from there too but then the question is what are other options and can we really understand what's going here behind the scenes and uh for that I'll talk a bit about geometry yeah so we had seen that in the fast forer transform this map X squ had the played The prominent role so let's look at this squaring map I mean on the left you see the graph of the squaring map in the case of the of complex numbers basically you should think of the complex plane and then uh uh for each complex number you have two square roots right so over each point in the plane you will have

two points lying yeah two points on this of the cir of the surface that lie over uh each point except the point zero will only have one point lying over it or you can visualize it in terms of the real picture so if this is the y- AIS and that the x-axis x^2 is equal to Y so for each y value you have two x values that map to the given y value Yeah so basically what you have is I'll just tilt the picture over so you have a two to one map from the graph the parabola you'll have a map to the y- axis right and for each point on the y- AIS you will have two points on the curve

mapping to that one point yeah or if you want let's move the y axis out so you have the parabola over here you have the line down here and you have a map from the parabola down to the line that's the square and map right such that for each point on the line you exactly have two inverse images except the 1.0 which has a point of Multiplicity two over it if you want yeah okay and you can think of this more generally you can have a complicated curve and it could cover a simpler curve if you have a map from a higher curve to a lower curve this is called the covering and given a point P it will have three points q1 Q2 Q3 over it uh but if you take another point R it

might be that one of the points might come with a multiplicity yeah so if you take the point P move it slowly towards R you see that the Q2 and Q3 those two points will collapse to a single point s two so you should think of S2 as a point with multiplicity lying over it but counting with multiplicity if you have a certain covering map of a certain degree you will have as many inverse images as that degree okay and uh now in the fos forer transform you're basically repeating the squaring map many many times Yeah so basically what you're doing is you have a line you have the squaring map down to another line that's a two to one map any point

on this second line will have two inverse images you apply the squaring map again again and again yeah and you see already if you take a certain uh certain set it looks like if if the set is chosen nicely uh it will shrink yeah but then the problem is of course uh I mean as you know in re in the world of real numbers if you want to take a square root of a number the outcome might not be real again right if I take the square root of minus one I get a complex number yeah so you might have to grow the field and that you don't want to do so basically you want to have uh points up there that are defined already over the field over which you're working such that uh under the squaring map you

get two smaller and smaller sets yeah and the way to kind of Ensure this is using uh automorphism so basically what you do is um on the line you have an automorphism of the line to itself which is corresponds to taking a point multiplying it with the root of unity right and then uh if you take a point and if you look at all of its orbits right when you pass to the quotient curve that orbit will collapse to a single point yeah except the point zero that will be a fixed Point under that group action that uh will have so it will be a single point lying over a point down here right so basically you see you obtain in a very natural way

from an automorphism of the curve up there you get a quotient map to a uh curve down there which just has a point down there for each orbit up there yeah so whenever you have a curve with a group acting on it you can kind of potion up potion out that group action you get a curve down there okay uh and then uh we had this nice property that if you have a function f you I could write it in terms of two functions F0 and fub1 this is basically related to a way of uh connecting functions on the curve up there and functions on the curent curve down here once you have a covering map

if I have a function f on the lower curve then I can pull it back to a function up there basically if I know how to evaluate a given function at points on C if I have a map five from C Prime to C I can obtain a new function five star of f which is taking a point if you want to evaluate five star of F at that point you just first map it down and then you map by F yeah so it's basically just composition with five and in our previous case five was X squ and if you remember we had F0 of x^2 and fub1 of x^2 that's just composing with the uh covering map between those two lines yeah exactly that's the squaring map and here uh uh the pull basically

the pullback of a given function was just composing it with the map F which which gave you this function X squ over here okay so we have seen that automorphisms and coverings they're intimately related and they might be useful uh and we have seen that the function spaces are also related to each other right given functions down you can pull them up to functions above and in fact all functions above uh so I'll denote by fq of C Prime all functions on the curve above fq of C will be the set of functions on the curve below and you can show you see easily that the functions on the curve above are forming

a finite Vector space over the field of all functions below right uh which means if you choose a certain basis you can write any function above in terms of functions below by multiplying by those basis elements and in the case of the squaring map that basis is just the basis 1 x so that's why that X Factor in front of f1x s was coming from but of course you don't want arbitrary functions you want to restrict on to nice functions like polinomial and so on and um there is ways to do that but there's some further reasoning that you need to do at this point okay so maybe this was fast and a lot but basically the upshot is if you have a

curve if you have automorphisms on the curve you can get functions down to a simpler curve functions above you can write in terms of functions below and the evaluation points if they're chosen nicely if they're chosen as orbits under that automorphism they will always shrink in size and having automorphism will all also guarantee that you have many points yeah so that's kind of the rough idea okay so then let's see what we can do with the line let's start with the line and what can we map to from the line right so basically you're interested in automorphisms of the line and it's very classical they're just the elements of the projective General

linear group yeah so given a point on the line uh you can just apply this mous transformation right given coordinates X you take a matrix a b c d with nonzero determinant you can Map X onto the M by the muus transformation ax plus b divided by CX plus d to another Point again on the line and that gives you an automorphism of the line yeah in fact it's a projective line but I'm not going to go into those details yeah so uh you have this very large automorphism group of the line uh I mean the line is very simple but it has lots of structure it has a huge automorphism group and then um the idea is okay let's look at

subgroups of it the subgroups will Define you the quots they will Define you the maps F and so they will give you the covering they will give you which functions to compose with and they will also tell you what the nice sets are that you want to have and also if you want your functions to be invariant under those automorphisms that will also be possible by looking at them and then subgroups of pgl2 are classically known um I mean it's a result by Dixon more than 100 years ago uh which basically tells you uh over a finite field the projective General linear group has only those subgroups yeah and I just want to stress like the last ones are not too interesting A4 S4 A5 they're just finite

so you can't do much there is no parameter n that you can grow in it uh we have the elementary ailan P groups we have the cyclic groups of order dividing Q -1 and Q + 1 that's already two factors we had seen before and we have the dihedral groups yeah so uh let's go one by one from the Elementary ailion uh P groups You' basically get what is known as the additive ffts uh if you look at the cyclic subgroups of order dividing Q minus one this would just correspond to multiplication by end root of unity that would be the automorphism that you have and that's the very classical Construction yeah where you take end roots of unity and do the discrete forer

transform and if a high power of two divides n divides Q minus one you can choose that as n and that will speed up things yeah if you look at cyclic subgroups of order Q + one so these are known as singer subgroups I mean there is a construction what their generators are and so on I won't go into those details but you can easily construct elements in the automorphism group so can construct matrices of order Q + 1 yeah and that's basically what's used in the g f oft by uh Lee and Shing basically they uh take uh just an element of order dividing Q +

one and use that to kind of shrink the evaluation domain and the Pol the function space that they're looking at and then there are the dihedral groups so dihedral groups just correspond to uh symmetries of a regular Eng gon yeah so there's a parameter n if you have a regular Eng gon like a six gone eight gon the stop sign right you can just rotate it and what you can do is you can also flip it right and the set of all those symmetries they form the dihedral group of order 2 N and they just correspond to if you look at the root of unities they just correspond to rotating uh in the circle yeah which brings us to the circle Stark or the circle FF f t by

harber livid in papini um which basically uses a model of the line given by uh a fine curve which is the circle right on the circle you have a action of the uh algebraic group so SO2 which is just the rotations basically it's a fancy way of saying rotations and a basically a point would correspond to a certain rotation if you have a point with coordinate CS it would correspond to this Matrix over here C and S are basically like they should remind you of cosine and S which are the usual functions that you get when you do things in R2 and reflection along the x-axis would correspond to uh inversion and what you can do is so uh inside this

dihedral group you have first of all a cyclic group of order n if you use that cyclic group you would be getting back the G fft alternatively uh you can use the full dihedral group but then you have some issues with ramification and so on so I won't go into the details but you can't use the whole um dihedral group but you just have to use half of it and once you do that you recover the circle fft yeah um so basically uh these are so to say the maps of curves that you have either you can uh first take an inversion and then go down n minus one step or you can just do look at the

cyclick subr group and go down all the way here yeah that's how they are kind of related and um the reduction step I mean basically you would be choosing a base on top you have this field having X and Y below you have the field having X only you can choose one y as a basis for the one above and then afterwards it's basically a squaring it's not really a squaring but it's so that the whole composition map corresponds to taking out quotients by dihedral groups yeah okay and then there's the ecft I have no time to talk about it but uh it's very it's a very nice construction basically what you do is you you ask yourself uh

what are groups where what are curves where I have a very natural group action on and elliptic curves are a group by themselves so you have a group action given by translation so given an elliptic curve you can take the subgroup and then you can have have a map from the elliptic curve to the quotient by the translation map uh by the group generated by translations corresponding to points in the subgroup yeah uh the problem is you have to work with by variate functions in this case because you have a x and a y coordinate uh and you have to point work with points with two coordinates but in fact you don't so that's again very classical mathematics beginning of the 20th century lates map basically say

that on the elliptic curve you have this involution mapping a point to its negative if you quotient out by that you get a map to the to the line and this quotienting out by minus one behaves very nice it commutes with all the isogenes so if you have a nice map F above you can get a similarly nice map F head down there yeah and this gives you the EC fft construction by bason Caron karti and leave it and um so I'll just finish with some questions there are many questions that you could ask at this point um depending on what your taste is what you're looking for but basically uh so there one first question

would be um there are several models for all those covers that you have right there are various models for the groups there are various models for the coverings of Curves and can you choose another one what is a way to optimize it can you do this optimization for additive ffts uh the reman r space which is kind of the space of functions that you restri red to has a lot of algebraic structure besides being just a vector space right it's basically functions and you cannot only add them but you can also multiply them can you exploit this additional structure can you rather than evaluating at points can you evaluate at extension points in extension Fields um what's the optimal way for EC fft what

are good choices for elliptic curves and isogenies can use other projections to the projective line besides quotienting out this um involution multiplying by minus one and then there are a whole bunch of other curves of higher genus not the line analeptic curves which are Gina zero and one but arbitrary High Genera so those curves have many more points can you use those uh so you don't have to kind of restrict yourself to what's bounding you namely the H Veil bound you have very nice curves with many automorphism many points the Herm Mission curve Suzuki curve recurve might they give you anything yeah this and many other questions but I'll stop here and uh thank you