zkStudyClub: Elliptic Curve Fast Fourier Transform (ECFFT) [David Levit @ StarkWare]

Transcript

all right good morning or good afternoon everyone um today we have david levitt presenting uh elliptic curves fast forward transform some new uh some new techniques um for for elliptic curve cryptography that are relevant to snarks i'm very excited for him to present that joint work uh with uh that he did with ellie vince hassan dan carmen and swastika party um and thank you very much for being here david and thank you everyone else for joining today so david with that over to you take it away thank you alex so uh my name is david i'm going to talk with you today about the easy fft algorithm as alex said it's a it's a joint walk that i did with ellie ben sasson dan carmon

and the swastika party and we published here with the link to the published paper of the first part the second part is still in lighting so let's begin so fft fft is a classical algorithm it is widely used in many applications such as polynomial multiplication integer multiplication loading extension error credit cards snug stocks and many

more applications so this is a very elementary and basic algorithm and the and it has a one problem the very one problem it has is that uh it requires a a field that is fft friendly this means that that the size of the field should be of a special form for example if the multiplicative group is divisible by a large power of two

then we have a an fft friendly field there are some more examples but but the but until now uh there were many fields actually most of the fields uh were they not known to have in an fft like algorithm so what what do we do um let me let me say again that i would very much like you to jump in if you have any questions i

really like to communicate with my audience and so let me now show the the sketch of the solution the solution is very simple we just replace the multiplicative group with some other group the group we replace it by the uh by some elliptic curve group over the same field and the the advantage is that uh there are so many elliptical there are so many elliptic curves over the

any uh finite field that there is enough uh freedom to choose an elliptic curve of of some order that is divisible by a large power of two let's be more specific so by the has a well bound an elliptic curve e is always in this bound a cube plus minus 2 square root square plus 1.

so this is a bound bound of it's it's an interval of lengths 4 squared q so this means that if if we want an fft of size 2 to the n and if 2 to the n is smaller than square root q a where q is a side of the size of the field then we will probably uh it is a highly uh possible that that we can find such a curve and then uh and then use it for the

for an fft like algorithm a a result by waterhouse actually tells us exactly which sizes in this bound are achievable and actually actually if if if 2 to the n is is smaller than exactly a square root of q then then we are promised that that there is such a curve that that fits um

[Music] any questions by now so this is the really uh main idea of the of the algorithm and from now on i i will just describe it in more details yeah and i put this in the chat as well but if anyone has questions that they just prefer to type feel free and leave them there and i can ask them okay thank you alex so let's continue this is a the most general uh uh abstraction that i could

find for and for what what are the building blocks that we need for an fft-like algorithm so first of all we need the field okay and we need an algebraic group g so in the classical case g is going to be the multiplicative group and the and the in ecf 50 g is going to be an elliptic curve over k and then we need a set of points this set of points is the evaluation set which is predefined it is

[Music] it is considered a constant in the algorithm and the algorithm is a the algorithm gets a an input [Music] as an input a function f from from the algebraic group g to to the field it is given as a is coefficients in a coefficients in some linear space of functions so in the classical case these coefficients are the coefficients of

a polynomial and the purpose is to evaluate f at all the points of s as fast as possible so so as fast as possible until now m log n i'm sorry uh yeah sorry is there a question or maybe someone's unmuted possible uh if yeah there's a question though yeah feel free chime in also alex as the host you can mute people if you if there's accidental background noise i just i think good call thanks a reminder

okay thank you so so far we described the very well-known classical fft but we did it in a bit more general way so so we can plug in a some other building blocks that will serve our goals so so let's say let's first of all plug in the classical building blocks so k is a prime field it would be also a prime power g is

the multiplicative group of k and s is a coset of the group of 2 to the n roots of unity why do i say a coset in the the most classical case it's the trivial process it's just the group of two today and goods of unity but for example if we do load the extension then we we are given evaluations at one core set and we apply we apply inverse fft and and then a regular fft on another coset

and then we get the evolutions at the different coset okay so i still call it a classical case so this is s the set of evolution points and then we have l which is the space of all possible inputs the space of all possible functions that are that can be given as input to the fft so in the classical case it's the polynomials of degree at most 2 to the n minus 1.

here i have a notation for the riemann workspace of some divisor don't worry if you don't if you are not familiar with the riemann workspace i will not i will not talk further about about it i i will only note that it's the analog for for polynomials of low degree for the case of algebraic curves this is a not a

this is not a property that i'm going to use in this talk i just note it because uh there are applications in which this property could be used for example uh uh zero knowledge proofs but this is out of the scope of this of this talk so so these are the building blocks for the uh classic 150 and now we need to dive in for some more details

so the structure of the fft is is a squaring in each step right so so we need some a two to one map that is a the squaring map the text where they are the evaluation sets s and shrinks it to a half-sized set and after after the log m steps it it is shrink to a single point so if we have a in the trivial coset it

it will be shrink to the uh to the point one and if we are in the coset then it will shrink to a some other point right so this evaluation set is a is a string and then we actually recursively call to to a smaller size problem of the same of the same form a so this two to map two to one map that shrinks s actually can be extended to all the

all the multiplicative group g right so so actually these are the maps that uh that are the algebraic maps of degree two uh so in the classical case uh this all these maps are the same maps of squaring and all these groups are the same group the multiplicative group but here i formulate it in a more general way so that it can fit also to the elliptic curve case

okay and and the reason that i intentionally separate the group itself from the set of uh of evolution points is exactly like i said before the load the gear extension case so if we have this set the set this set of of [Music] the set s it has to be it has to be all the images of a single point over this

two to the two to one maps right so we to construct such set we need to take a single point p and we we look uh we say okay what are the two square roots of these points and then what are the square roots of this of these two points that that we have and then we and this way we construct this set over which it is it is [Music] it is easy to to evaluate

the function so in the classical case it we get a a coset of uh 2 to the n roots of unity and in the elliptic curve case we are going to get something else okay so this is just uh to to understand what is the methodology uh that is behind the uh finding this uh this set of uh of uh uh evaluation points because that's that's a nice way of looking at it even

for the standard fft i think right because uh because this causes cossets don't just come out of nowhere it's it's actually uh it's actually this is the way that that that they are constructed [Music] okay so let's continue uh here i have the same slide from two slides ago but with some changes so the gray lines are the things that stay the same and the blue lines are the new new stuff so

so we have this again this phi i which is this wearing map it it is a two to one map all the gi's are going to be the same multiplicative group and the and the sets of revelation sis are going to be cossets of of sizes that are uh that shrink each time by by two okay so later on we are going to make a comparison between this slide and the case of the elliptic curves a

okay one last important property of the fft is that we have this decomposition so if we get this input f f is the is the function that we want to evaluate at at the evaluation set so the most basic step is to to decompose it as as the sum of two functions uh in the classical way in the classical case it is going to be the the

odd monomials and the even monomials right so so in the more general case we replace the squaring map by our other two to one map and here we have still this a composition of of some smaller functions g and h with this squaring map and and here we have this x that separates the

two types of uh monomers here we have only even monomers after this composition and here by multiplying by x we get only even only odd monomers right so this function x uh separates the monomers between two different uh two different linear spaces uh but actually it doesn't have to be the function x it could be

it could be replaced by other functions with some properties that i will not get into detail now maybe maybe later i i if we have time i will talk about it tomorrow so so let's uh let's formulate formalize this the composition in some higher mathematical mutations so uh so every every algebraic morphem like like the squaring map

has has a pullback morphism which which we denote by by the star okay so if we had the vi which is a squaring then vi star takes as input a a function of the of the image space and the and moves it and the and returns the a composition function of g and phi okay so this is just a notation but it's a very useful inflation it actually says that if we have

a g coming from some linear space l i plus 1 then after composing with v we get a function in the linear space phi star of l i plus one okay and the same happens for h when it is composed with vi we get a function in the in the space vi star of li plus one and then we multiply it by x to get some other linear space of functions and since this two sets of functions are

linearly independent they're they don't intersect at a in in any uh anywhere but zero so this is actually a a direct sum of linear spaces and the and the space of all possible f functions is actually the direct sum of these two linear spaces okay so so let's uh let's get back to the algorithm itself so the algorithm gets

an input as input this f in the space of uh in the space l which is classically the low degree polynomials of degree up to 2 to the n minus 1 and and then it decomposes it to two functions g and h in this l1 space and then each of them is decomposed to uh to functions in in smaller and smaller spaces linear spaces until we get to the final space that is

the space of constant functions ln is a space of constant functions so it's just the the field itself k okay any questions until now very quiet okay so let's continue so again the same slide only this blue line is is a new line the before we have we had only the first l

which was the polynomials of the g at most two to the n minus 1 and here we actually realize that in each fft step we get a different set of functions uh actually polynomials of degree at most 2 to the n minus minus i minus 1 when i is the number of the step okay so when i gets to n then we get a polynomial of the g at most 2 to the 0 minus 1 which means a constant polynomials constant

functions and then it is easy to evaluate them at every point actually because they are they are very constant functions okay so this was the classical fft and here is a detailed explanation of of a a description of the algorithm itself so so the first step is to apply phi i on all elements of the input s i to get s i plus one

as i remind you it's the the evaluation set which is classically the sum coset of uh of a group of size 2 to the n minus 1 minus i okay so and s i plus 1 is all its is all the squares of s i okay so we apply squaring to get this other coset this step is uh actually can be pre-computed because the s i is known in advance it's not uh it's not considered an input of the algorithm but

even if it if we even if we we don't want to do the computation then still s i is of size m and so so this step is linear and in the next step it is going to be of size half m so so it is going so we are going to get a the sum of a of a geometric sequence which which converges to a linear linear complexity

okay um then we are going to decompose our input f which is the which is given as as a coefficient of monomials uh with the composite e we decompose it using this uh decomposition into two spaces we can see it also here that using this fundamental equation to get a g and h so in the classical

case it is very clear that g is only the even monomers h is only the uh the odd monomers uh so so this this the composition is trivial in the classical case but it is also a trivial in the general case why because because how do we represent l i l li is is actually a the the span of some of some basis of uh of a

spatial functions but i didn't i didn't uh explain how do i choose this function so the correct the the the right choice of of bases would be just take the basis of l i plus one pull it back using fee i right and use those use those functions and those functions times x to be the basis for li so so this the composition is the is trivial also in the general case okay

so this step is just taking our array of uh of monomers and looking at and splitting it into two parts okay and the and looking at the each part separately so the next step is to solve by occasion the smaller problems for g and h right and the final step which is the only step where we actually do something is to use this evaluation that we gave that we get from pre-karjan uh and

and they evaluate this equation to get the evaluations of f on all the points of si okay so far so good this is uh this is uh the um this is the description of uh the classical algorithm that you all know but only with a more from a more general point of view okay so the running time is as you know a t of m is you we have two uh calls to a recursive

two recursive calls uh to two problems of half the size plus this of m evaluations in this last step right so this is actually an off m log n okay so this is a a good point to ask four questions because after this slide uh is the same slide that we already saw uh it's just a reminder uh after this slide we are going to uh to talk about the

elliptical version so if there are any questions so far please ask now okay i see i'm sorry i i have a question so so there are variants of the classical fft um that are mixed radix or use different red x's than at radices than um than two um can those you put in exactly the same framework or

yes you're talking about the additive version right yeah yes so let's uh this is a great question so let's go back a few slides and just see what what is going to be there so in the additive case we have instead of the multiplicative group which is of size that is divisible by 2 to the n we have a the field is is itself the divisible by 2 to the n it's the field of size 2 to the n so so k is going to be a power of

a field a binary field g is going to be the additive group of the field itself s is going to be some linear subspace of this additive group which is also of size 2 to the n and l is also going to be polynomials of degree at most 2 to the n minus 1. so i was talking about the case where let's say you have an fft with red x3 uh wouldn't it be okay this is all okay so so here we have this to the end we can

also do a 3 to the n case also in the multiplicative case also in the additive case uh the difference is going to be here the function the morphisms fi are going to be three to one maps instead of two to one maps right but still you will have this one point in the end where all the evaluations are going to be in that point and the and to understand what is the a set of evolutions that you start with the s you just you just need to look at the pre-image the pre-images of this point

okay because cubing has three roots yeah okay yeah right okay and this is also in the additive a cubic case and also in the multi multiplicative cubic case okay got it um so okay and here we are going to to have some other equation which will have uh three parts okay the decomposition is going to be into three spaces uh with two different uh multipliers right here it's going to be one and then x and then x squared

yep makes sense right so it's it generally is perfect so just a reminder for those of you who didn't see the first the first slide the problem in the classical ffts is that they don't work for the fields that are not fft friendly uh and the divisive divisibility by 2 to the n is just one example of fft friendliness but it's it is still not known or it was still

not known that [Music] other that most that actually all fields can can have a an fft like variant and our solution is to replace the multiplicative group of the additive group in other cases with an elliptic curve group which has a much more freedom in its size okay so let's start with the obvious building blocks so k can be any prime or any binary field of also a prime power

field just any finite field g is going to be some elliptic curve of a nice order by nice order i mean divisible by power of 2 but it can also be divisible by power of 3 or some other radix as you wish so the main the main question here is going to be what is the two to one map what is the squaring map actually uh so the answer is that it's going to be an isogen

of a or actually something that is related to an hydrogen so let's say uh let's first of all discard uh define what is a nitrogen um elliptic curves are they are not just curves like they are actually groups so uh and the and the homomorphisms between those groups are called isogenys these are these are the functions that are defined using a rational functions okay

and they preserve there are actually homomorphisms so and there are there are actually a enough enough such isogenesis for for our purposes and this theorem describes exactly uh what what we need so the theorem says any finite subgroup of an elliptic curve is the kernel of some isogen what does it mean it means that if i have some

elliptic curve with a subgroup of size 2 to the n and i want to find a two to one map from this elliptic curve i just look at the subgroup of this curve of size two this cybo subgroup is by the theorem is the kernel of some esogenie let's say called this esogenic psi zero so this psi zero it takes takes this a a sub group of size 2 to the n to some other subgroup of some other elliptic curve

which is going to be of size 2 to the n minus 1. not the elliptic curve itself is going to be of size n 2 to the a 2 to the n minus 1 the only the image of of the of this morphem is going to be of size 2 to 10 minus 1. then we get this other subgroup in this other elliptic curve and it has in it also a a subgroup of size two this subgroup is the kernel of some other isogenic form e1 to e2

which also is a two to one map because its kernel is of size two so this way we construct we can construct a chain of uh elliptic curves they are all different curves but but [Music] it it's a they are all different curves but our general formulation of fft can can handle it so let's let's first of all show an example of such exogeny

uh here we have a specific example if we have e0 being the elliptic curve of this form uh notice that here we have this squared and not just b so this is not a general elliptic curve and e1 is going to be this other elliptic curve then we have this uh this exogenous site that is a of the grid tool it takes x y to this point and

first of all notice that i want you to notice that that the x-coordinate of the result depends only on the x coordinate of of the [Music] of the given point right um someone is typing and can you mute it please okay thank you so so so i'm going to use this fact that that only the

that the x coordinate depends only on the x of the input okay before i go on i want you to notice another thing that this elliptic curve e1 is is almost like is almost of the same form like e0 but what i'm missing here is that i need a 4 a b plus 8 b squared to be a square if this value is square itself then e 1 is also of the same form and then i can i can find another isogeny to some e2 in the continuous chain

do these have to be montgomery curves or um is that just for this example uh no it's it's just so for this example uh well actually every curve can be of we can they turn into a virus and and actually there is a is there is an algorithm to find this uh isogeny of of a given kernel which is which is an an o of one uh complexity okay so given

that if we if we are given this e0 then finding e1 is very easy the only obstacle is how do you find this e0 and this is a very well studied question which has which uh the the most uh the most naive solution is to just uh exhaustively search for this e0 and and just check what's its size and heuristically and also probably it is a

there are enough such elliptic curves to to find one in a in a poll in a in a quasi-linear time so so that would be size of the subgroup um times however long it takes to to count points on a curve it's not right i'm sorry the the time is is size of the subgroup times number times however it longs to count however long it takes to count points yeah yeah okay exactly exactly actually we don't we don't really need

to count all the points we we only need to to verify that it has uh that it is divisible by oh that's a good point yeah okay so so it's actually easier than counting okay so so as i stated uh in the previous example if a psi of the x part of psi depends only on dx and this is actually a theorem that if a e0 and d1 are given in extended voice transform then then this

isogeny is going to be of this form with the um with the psyx having a being depend depending only on the expert and this is equivalent to putting these [Music] curves in a commutative diagram so here we have e0 goes to e1 using this side here we have the projective lines the projective line is is just the field itself union the point at infinity so

so so that we can actually uh uh do this map from from an elliptic curve uh to the x part of uh of a point so if uh if we give it the point and infinity of the elliptic curve it goes to the point and infinity of this projective line okay questions about the sensation of a projective line no questions okay very good so so [Music] this map of taking the x-coordinate uh

it actually uh so we can make this uh as i said psi psi x is the x part of this of this isogeny and and i i can i can go from each direction and and get the same result so if i if i take this psi of a point and then

take the x coordinate of the result it's just the same as taking the x coordinate of the input and applying psi x okay this is what uh the this is the meaning of a commutative diagram it doesn't matter if i go from here or from here we get the same result so now that we have this theorem we can just apply it on the on the chain of elliptic curves that i that i told you earlier that i can find easily so we have here the e0 goes to e1 goes to e2 goes to e3 and so on

and each of them has a in a projection to the x coordinate a morphem and all these projective lines in the second row have have morphisms between them that make all this diagram commute well i have a small question okay do you really need a chain of the curve i mean can you not just have one elephant curve with the point of order two to the k

and then doubling that okay so uh the doubling map is actually a four to one map not a two to one map uh it is possible to use this uh this function it is not only that it is possible it's a special case of this more general formulation because the doubling map is actually a composition of of two isogenes so in the case of the doubling map you will have e2 equal e0 okay so this chain is going to be a

repetitive with a period and the only problem here is that that in order this to work you need the the two to the end subgroup to be of a of a special form you need it to be a the composition of two subgroups of size two to the half end okay because you actually need all the uh images of a single point to to be in your

group uh if if these woods don't exist in the base field then then you will not have your evaluation points so so um you said it's a four to one map that that's basically like the um classical fft with red x4 is that right right right okay so it will work if you choose a a proper electric curve this formulation doesn't doesn't uh care for the uh which elliptic curve you you find as long as its size is uh is good

yeah i i don't have any intuition for how efficient that variant is relative to using different curves because you you don't have to compute the isogeny but then you have red x4 so yeah okay so uh computing isogen is is actually far from being the bottleneck of the complexity so it's it's fine okay okay so now we have this uh chain of uh of commutative diagrams and and the what we are what we are going to do is actually

say that that the the two to one maps that we actually care about is the total one maps in the red path okay so each each map in this red path which start from this projection to the x coordinate and then uh taking only the x part of the isogenys these are going to be the two to one maps that replace the squaring map in the classical fft is it okay so

this way we actually can talk about polynomials in the in this construction because if we if we were talking about the the endogenous themselves then the spaces where the functions would live where human rock spaces of of elliptic curves and not polynomials of some degree using this a red path instead we can we can talk about a polynomials

in one variable okay um so sorry i'm not i'm still not quite sure about the the connection between the polynomials and the um projective line okay so so uh what we are going to let's let's say continue and uh i i i hope i will answer the uh your question in a few slides okay if if not then come back in a few slides okay so so let's uh let's say

detail about this building blocks so we have we had this k which was any field any finite field g0 was some specific elliptic curve and all the other gi's were the projective line okay and now i ask you what is going to be the evaluation set anyone has an idea i i mean it's it's on the slide yes it's

like okay so [Laughter] so the evolution sets are going to be exactly what we said before it's the uh the images of a of some point in the final in the final space so if the final space is here the the projective line we have here some some point then its images using one its images

uh in this red path is going to be exactly the pre-images in the other path okay because this is a commutative diagram so let's let's say look at the pre-images in this other path so first of all we take this point and we this point on the x line and we ask uh what are the points on the on the elliptic curve whose x coordinate is is this point p that we started with okay so these are going to be two points that are a plus minus of each other right

now that we have these two points uh we are going to to look at the pre-images of them in the isogeny so these are going to be a four points uh actually two pairs of points each pair uh is going to be two two points that that go to the same point so these are going to be actually um cos sets of the of the subgroup of size 2 right and it's going to be two cosets of the sub of size 2 the a coset and it's minus because here we get the

point and it's minus so it's here it's going to be a coset and it's minus and each time that i that i go back one step i i get a larger and larger larger and larger coset a a larger and larger pair of corsets until i get to g0 which which will contain a s0 which is a two corsets a coset and its minus of sum uh of some subgroup of size uh two to the n minus one

so so the the esogenic commutes with negation which is why it only multiplies by two at each step instead of for uh right right yeah right so so now that we understand this this evolution sets well let's say let's see what is going to be the the phi function so the first phi is as we said the x coordinate projection to the x coordinate and the next ones are going

to be uh the the x coordinate of the the x part of the isogeny which is just this simple function okay and well well um i i thought that i will not have time to to dip into more details um but it depends on you i have i have these

slides i have some more slides to talk about but uh i think this is going this is a good point for the questions and uh maybe i i don't remember who asked the previous question which i am pretty sure i didn't answer in the end so can you repeat the question please uh okay can you go back a few slides so i can remember what i asked i think it was here yeah it was it was to do with the relationship between the polynomials and the um projective line right the the the polynomials okay so

uh i thought it would be in this slide but it's actually in a in a slide later the um what what is the l spaces that are the species of of [Music] functions right so so if we go back a few slides uh to the a formulation of the of the general case uh ln is going to be the the um the constant functions right and then in each step

l i is going to be the uh somewhere the composition of a pulling back l i plus 1 and multiplying it by by this function x which actually does not have to be x it can be a any function of uh of uh um of degree one um any rational function of the year one actually so this when we start with l i plus one being polynomials then uh pulling it back with a squaring map gives also a

polynomials uh but in our case if i is not a squaring it's a it's some rational function so so the result is not is not polynomials it's going to be polynomials over some a constant denominator okay so l i is going to be actually all the low degree polynomials over some a constant denominator so so does does the degree of the numerator increase by the degree of the isogeny uh yes the degree of the you know of the

numerator increases uh uh by by two if it's a two to one uh map and uh all right okay and then we get uh and then we get that uh li is a space of a dimension two times the original dimension right yeah i see okay so if if you want to only talk about polynomials then you need to multiply uh this result by some by this denominator and then you will have here

two functions here you will have a one function and here you will have some other function okay in this case these two functions are one and x but it could be some other functions and then and then you will talk only about polynomials all the time but in the more general case you don't have to you can stay with these polynomials of log degree over some constant denominator and the only in the end normalized by by this final denominator if you like it depends on the on the application of course yeah

uh okay so uh this was one question um i will gladly answer any other questions i'm sorry so p phi i in this new case is basically a map between functions and fields right the fi define a in the case that we yeah the five stars are the functions between the uh linear spaces of uh of uh functions yes the function feels right the file themselves are the maps between the uh

they are directions like curves okay so basically the normal fft is basically on p1 basically it's a specific case that our curve is p is the rational line and now you're attending yeah yeah yeah okay thank you okay other questions thank you i think you answered my questions in the chats about how difficult is it to find the curves um the finding that i said your needs is trivial um yeah okay you answered all of this thanks

okay so actually now i'm suddenly confused by your last answer i thought the spies were i mean they were sort of inherited from curves but they were restrictions to x-coordinate uh of of uh of these maps from curves so they're all aren't they all like maps of the rational fluctuated sorry in one variable okay let's have a reminder let's go to the right slide so

here we have this uh specification of uh device the in the ec fft case the first five uh oh if you don't start away from the from there you can always start from the second step so the first phi may be the projection to the x-coordinate for the elliptic curve and then all the other phi's are going to be the x part of the isogeny as you said and this is in the ec fft case in the multiplicative case they are all going to be the squaring back okay

uh yeah thanks [Music] other questions so so i'm interested in the relative efficiency of this for um okay compared to classical fft because obviously let's consider a zero knowledge proof application you have the choice of either going to the next power of two or switching to easy fft if if you have some circuit size that is between two parts of two so so the question is which is more efficient in practice

okay so uh i'm not sure about the snarks but if you go if you look at the low degree extension problem then actually the code is i actually use the same code exactly for the two cases i only changed the the twiddle factors okay so it's it's a uh extremely the same just the same but my intuition was that it would be more expensive but if it's the same then that's a big deal because that immediately applies that that

immediately means you can have any circuit size um yeah that's great okay and do we have any other questions so this is probably uh i'm just probably not uh like a silly question but i'm i'm still trying to get the radix 2 from from just the doubling map so say i hate you know i fix one point of order two to the k in the curve and now i take as my evaluations that the x coordinate

of all its uh multiples so that's uh two to the k minus one point like uh x uh uh two to the x k minus one field element and now uh i think i'm wondering if on these two to the k minus one point the uh doubling map now is just the two the one like the restriction of the w map to the x coordinate is just uh to the one and uh if you could use that for like getting a radix [Music] okay what what you are going to get is is

actually in this uh decomposition where it is in this decomposition if you use only two uh when you only two functions instead of four as you should in the case of a four to one map then the set of possible functions that you get is smaller than the uh than the more general set so uh so if in the uh in in the ecf of t case f is going to be a all the it can be a any a low degree

polynomial over some constant denominator then if you drop to [Music] two summons then f will will be just some in some linear subspace of of this of this space okay also i i think doubling is more expensive than computing this um these phi axes so um there's no point in doing it that way anyway yeah it's it's just equivalent to having two steps of uh of this easy fft yeah i think in uh yeah uh allen he

answered my question i think it's paraphrasing but for me it's easier to to think about it uh but yeah basically the the phi will be degree four you know the case of the doubling match so so if i try to represent poland i can't represent polynomials of a certain degree as [Music] yeah maybe i or maybe i can if instead of times x i use uh like i'm wondering if i can represent all all four numbers of the certain well look at the dimensions here you have a l i plus one is of some dimension

and then uh pulling it back it stays with the same dimension but the uh the result that you wish for is of four times today this dimension yeah well yeah yeah yeah at the very least it's messy i mean i don't get all polynomials of a certain degree i get some weird subset of them if i if i just use two components or so yeah [Music] okay any other

questions yeah i think i'm going to go away and implement this go ahead also you mentioned uh david that there's a follow-up to this work coming right yes this there is a follow-up that uh explains exactly how we can use this method to do a stacks over [Music] over the any field and in particular we are interested in a sec-p field

so this is a non-fft friendly field but we want to prove ecdsa uh claims uh about uh fields uh and in fact so secp forms the cycle and the the only reason we aren't for example using sec p for um secondary insect q which is the other curve of the cycle for halo 2 is this issue of fft friendliness but if that issue is resolved then there is no reason not to use that cycle for halo 2

and be able to prove things about say bitcoin signatures and things like that exactly there's a couple more comments uh that are kind of being typed in here i think kobe mentioned um that you need the radix 2 structure not only for fft and some proof systems i don't know if there's anything you want to you know comment or if you want to comment on that i mean i i can comment about that so plonk was originally described as relying on um

uh password power of two subgroups but i don't think it really depends on that in any essential way it's easy to remove that assumption okay i'm actually not familiar with flux yeah i guess you just need a subgroup of some order that's close to your circuit size and you don't decide the fxp you don't care if that group is a power tool yeah you need the subgroup you don't need it to be a particular size

as long as it's larger than the seconds or the number of rows to be more precise awesome any uh any other questions in the group here um so basically it sounds like the performance is um is the same as like radix 2 fft and are there any are there any other downsides to this like is there anything else why someone wouldn't use this or are we literally just saying like now anything's possible with mfds well the only problem is finding the curve it's not a big problem but it is a small issue it's

it's a pre-computation but it's possible for the i think any any desirable fft size and so do we know the complexity of that it's a quasi-linear i'm not sure exactly so so if we go into that in more detail so for for each candidate curve you have to check that it has a subgroup of the right size right so that is just a scalar multiplication um of that size right with that number of bits

um okay so that's that's going to be pretty efficient because you only have to do two to the end of those and each one takes so it's o and something like that um of and what is n oh sorry um and um so if we call the um yeah if we call the subgroup size um i don't know um we call it m okay m and then um it would be o log m log m i think

uh okay um it's m because of the exhaustive search and then you say it's log m to to verify yeah to check each candidate well it's uh i'm not sure if it's exactly log n but it's it's a polylogin i think oh yeah thus uh no because the um it's it's log m times something that depends on the curve size um so it's um uh o lambda m log m yeah well lambda is your security parameter that's if you

you if you are using schoof right uh no that that's just to do the um the subcrite size check okay um i'm not sure how it's done but i'm pretty sure that it's uh and there are ways to get away from the size of the field problem um i mean it's a small constant anyway yeah yeah small constants yeah well complex multiplication gives you exactly the size you like you know you

can you can use cm method too yeah i think you're right you don't have to search for it by brute force okay can you use a um a super singular curve does that work yes yes it will work yeah okay i think that makes it easy of a binary field that's exactly what you get

okay no no that's not what you get i'm sorry that's what you never get but but it's it it doesn't matter you you can use supersonics yes awesome well uh david thank you very much for your presentation today and uh we're looking forward to your follow-up work and maybe we can have you back in here when that's out and and you know do it do another study club session about that thank you very much