“Reed Solomon codes over the circle group" - Ulrich

Transcript

hi everyone today for the L sh session we have sh who is a cryptographer at poon Labs uh he has worked in quite a few different companies including OB labs and or labs and was a lecturer for quite a few years at FH compan his recent work is on PR expand quotes uh Al nice paper on russion on MAR that I encourage you to read and me anous credentials on the close uh so feel free to ask questions as we speak uh I will and yeah the floor is yours thanks Rafael uh couldn't hardly understand you because of I think it's

your headset or or my connection but I I just got the core the most important statements and yeah thanks for the introduction So today we're going to call talk about uh a a a tiny paper that we that we published I think it was in May or so uh it's a joint work with Daniel and and Jack Jackie from polygon zero and it's about uh essentially of our search for the field we will support imp plony 3 so you find that you it's but uh going to the complex extension we will see not

and uh doing rolon and calling over the unit cirle there you find the ePrint as listed here I don't know if you see my mouse cursor do you see my curse or is it just the window we we can see your but you can't see my mouse you you can see my mouse or you can't we can we can that was a positive you can yes okay okay so let's start okay so first of all so this is here about stars so uh they

allow arbitrary sized Fields uh so and and the main uh because they don't use elliptic curves uh is for commitment in this so um you can use any any arbitr sized field the smaller the better and this allows uh and that's the main reasons why they're typically faster than standard elliptic curve systems I'm not talking about recent advantages in in in foldings uh that because the main reason for that for that uh the M advantage of small Fields is you can represent the trace uh much much tighter so there's much less Gap it's not like you have

something uh your Elements which are typically quite small embedded in a 256 large bit large field and the second is uh so you have tile representation of the anterior execution Trace you want to prove and second it's uh most of the pro doesn't even run in the extension field and most of it what what what what are like dominant costs of the proof uh it's uh to commit the trace itself that costs in our case an fft the ffts to to extrapolate to the fry sampling domain and then hash it so these are two the committing cost commit

cost and uh evaluating constraints so Trace is quite wide in our setting quite long so uh evaluating the constraints involves this Trace pols only so the tighter the representation is the there there the cheaper the ffts involved in polinomial arithmetics so roughly ah hi Paul oh no sorry this was this was a different so so uh so essentially I guess it was two 20

2021 but Daniel might correct me maybe it was even 2020 when they discovered uh when haish disc and was discovering the Goldilocks field which is the plony 2 uh base field 64-bit field uh about the same year at least to private communication uh should have been also around 21 uh risk zero came up 22 but uh they seem to already work with the baby bear before they went to public here so baby bear is a 31 bit field so uh now thinking about plony 3 currently in

development we were asking ourselves what is a good uh uh so first of all we want to do a step from 64bit down to 31 bit for uh for speeding up and the and our question is which which is the best 31 bit field to choose either baby bear or some similar field to baby bear that's the question here and uh what do I mean by better so not talking about Hardware circuits so really just about standard CPU architectures like arm x86 so we want to we want to have a f that performs faster than baby

bear and which is still star friendly so that's the aim that was our aim okay so Daniel was P pushing very much looking uh uh for possibilities involving the ment Prime M31 so that's 2 31 minus one it's it's really a prime and uh it's extremely elegant uh for highspeed arithmetics over standard uh CPU architectures so uh here's here's a table that I just put to took out of uh of the

paper so what you see here is uh so on on two architectures it's arm and x84 uh the arm is is an apple M1 and and the x86 is an INT I Lake and you see here not in the uh M31 arithmetics in the parallelized setting of course so uh so it's the neon if I understand correctly it's the neon uh uh instruction set on arm and it's the AVX 512 on on on EX on on the int ice lake so you see here clearly uh that the moles the cost of a multiplication of an M31 both

architectures is is between 30 up and even more than 50% faster so uh it's important to point out here that that the baby bear uh is is using is using montgomer arithmetics that's considered here so that uh so so the advantage is not using plane reduction over the Manan Prime versus uh plane reduction over baby bear it's really baby bear with its most uh most uh let's say reasonable uh choice of arithmetic representation and uh M3 1 with the standard uh reduction which is very cheap so we expect speed out multiplication well we observed and I

think that uh Jackie did even further improve here these are the this is the table from from from May uh so between 35 50% faster in multiplication addition the same so that's the pro much uh uh much faster arithmetics on on standard CPU architectures the con is it's not fft friendly and in fact it's the worst case of fft uh uh friendliness you can face in Prime Fields because of that specific form you know P minus one uh is 2 31 minus 2 I mean we can just take out one two out of

of the sum and see this is the the term in the remaining term in the brackets that's an odd number so it's of the form P minus one is of the form two times odd and that means you only have two roots of two two aric roots of unity which are order two roots and these are exactly plus and minus one these are the only two other Roots you face in uh you find in M31 okay so we were thinking about strategies what to do with that field if it's that worst case fft

friendly so the first ideas was uh let's look at different different radiuses here so P minus one is not toic it's worst case toic but it has a lot of other quite uh quite nice small prime factors here's the factorization you see 2 3 with multiplicity 2 7 11 31 I mean these these small factors together uh multiply up to a domain of size approximately 15 bit large which is not much uh taking the one 151 which is uh unpleasantly large into account we we approach maybe some practical domain sizes Beyond 1

million uh but still it's not as fast even if you would have throughout three a pure power of three it wouldn't be as fast as a two atic fft so that so we dropped that even uh yeah we dropped that idea the other thing we were uh we were looking at is expand the codes like uh uh Starks like breakdown uh in the end at least I mean everything a bit suent here in the slides so not saying breakdown is slower uh in general but for for the situations

we Face uh not too long traces so so the the advantage of breakdown the linear encoding cost of breakdown is only at very high high number of uh of message uh message size very very large mess message sizes and for the for the application we are looking for uh we are at the break even Point ordinary R Solomon versus uh uh versus expander codes where the where they almost evenly perform so so we expect we don't expect it much faster and uh maybe not even

faster in our applications uh besides that you f that that that EXP B codes come with the problem of quite large proof sizes need to be wrapped all the time it's not a show stopper but again something that needs to be taken into account in the whole recursive process and the next thing is algebraic geometry codes over over over elliptic curves like the EC fft papers uh we didn't uh dive much into it at least I didn't Back Then basically the main reason is because it's advanced

math yeah I needed to learn algebraic geometry that's a way to go that's possible that brings us also down being able to do the same as as baby bear does in the or any other two Artic field does but it uses a lot of uh uh advanced math here so moving over to rational functions over analytic curve instead of having a polinomial IOP and so on so uh the funny thing is that over M31 we can do much simpler and that's is what this talk is about it's a

simple idea it's it's something that we just ran over it uh in a single day essentially after thinking a bit and and we call it the M fft okay so what is it what is the nice thing about the M31 though it's so poorly to AIC it's the it's the complex extension so there is only the the polinomial x^2 + 1 is irreducible there is no root of minus one in the massen field no square root of minus one so does you can make the complex extension as in the traditional

analytic case you know from calculus going from the real numbers to the complex the arithmetics the same and uh now if you look at in the final word what is the main advantage of the field it's highly toic because P the the order of its multiplicative group is p^2 minus one which factorize p+ one p p minus one p minus one is troublesome is four but p+ one is so we have at least we find at least roots of unity of order 2 to the 31 actually also 2 to the 32 but we keep with the 2 to the 31 for

reasons that become clear in a second so there are the complex extension is fftt friendly and if you look at these two to the 31 roots of unity they belong to the unit circle what is the unit circle just by definition it's this uh it's this uh this uh uh quadratic uh curve defined by this equation so uh and you can simply verify that different ways to do it you can

move over more the classical algebraic geometry uh how you call this projection the parameterization of the unit circle uh or you just look at the simple computation here so so just it's like uh so c z is like X I use the standard notation like from calculus whenever I write z z it's it's X Plus i y and uh with real plus I imaginary part so Z times the conjugate of c and the conjugate of Z is as as in calculus it's an automorphism of of the field which leaves the real subfield invariant the real line invariant therefore you can uh

uh you can quite easily prove that it's actually the franos ism of this that's quite simple I mean cenus isomorphism leaves the real line invariant that's given and if you plug in I the only the root of unity you know that I is mapped to minus I under the P's power because p is if you if you write has exactly the property that it's not yeah just it's a simple calculation there's not much much to do so so you see immediately that at that demanding that X2 + y^2 is equal to to one is

demanding to X2 + y s is equal or or Z is a p+ 1 power uh root of unity not power root of unity so so just one second back so it's it's fft friendly and this is this is the the order of the unit circle which consists of all two to the 31th roots of unity and three that's well-known literature you over the standard

analytic uh uh complex ffd a lot of things are known if you're if if you consider just real data as the input you can optimize a lot and improve improve the fft significantly and that's straightforwardly can taken over to the fin to the situation we Face here M31 and its complex finite extension so uh so concretely in the cost of an fft over a domain of size two to the N is almost the same as a native let's first look at the native a native fft koui toic fft

per each per each element of the domain we have log domain half multiplications and log domain one additions the double number of additions as multiplications these are the standard operation counts for coola 2K and for optimizing the complex fft for real value data gives us essentially gives us the same number of multiplications just a little overhead like uh log one over two per element to be processed in

addition so very comparable for for those who are more familiar with all this algorithms this this is the split radics in the three in so-called 33 regime where multiplication by twidle factor is realized by three uh base field multiplication plus three base field ODS so so how's that why is not why is that so much cheaper and and and just just the Mind map here is because we have four very beautiful roots of unity these are plus one minus one okay these are the standard beautiful Roots but also plus I minus I which cause AO ready for radics four or something similar uh

but split radics even better so uh uh and conjugation we have symmetry so whenever I start with real Val function in every single step of the fft network we can leverage symmetry the Spectrum or let's say the output of the fft of a real valued function is symmetric with respect to the conjugation me that means if I consider if I place place uh if you consider the value of the fft at that point here say I didn't I didn't draw any point here then it's the same uh over there but just

conjugated so we have a herian symmetry here conjugate Symmetry and that's the main reason why it's so much faster than the complex fft itself so almost just a second back almost as fast as uh a native fft number of operations and given the fact that the mole over M31 is cheaper than the mole over baby bear like 30 to 50% cheaper while the ads perform the same we expect signific we we expect uh a noticeable uh Improvement

here I say expect because the implementation is still about uh to converge here so it's not still not ready so so that that solves one thing so fft is not a problem we can use the split radics optimized for real it's not a problem though we go to the complex extension what about the other thing we need to we need to extrapolate from our witness domain to obtain read solomone code words or obtain just values over extended domains for polinomial arithmetics if you consider here a CO a

subgroup the black one yeah the black R is subgroup of S1 yeah so we have we have given a real valued function uh over over H over the black subgroup and we want to extrapolate it to uh to a call set of it that's the red one so that's extrapolation and in general you know you start off with real valued functions you get something which has this hermitian symmetry in the Spectrum but once you you multiply with powers of of the shift if people know how how extrapolation is used uh fft based extrapolation is done you

Disturb This symmetry Semion symmetry where the powers of T and going back uh evaluating this fft evaluation uh might be even not so easy to improve in the first at first glance and produces complex output so it seems like a showstopper if you just think of it only a millisecond if you think a few longer on it you can improve here and that's actually the observation uh in in in that uh in our paper I call it the rectification theorem so the funny thing is yes they're complex the output the

extrapolated value over a call set of the units of the subgroup that's comp that's complex but it's almost real in sense that the values essentially for let's for forget for a second it actually only holds if we have ah there's still a c0 here this would be the mean for forget it for a second so if if if we start off with a function that has average zero forget the c0o here then uh there are they all the values over the the extrapolated values over the coet LIE on a line which

goes through the origin a real line as a Subspace of the complex so that's here the real line M31 is like the field of the reels and row of T is the the shift that defines the C set so uh it's a complex number times this so it's really a line in the complex plane and moreover these these these rectification factors the form the form an isomorphism so I will I wish so so that means like you have the factor space uh uh S1 over subgroup say if the sub group

has has index F four or then then uh it this this is a Four Element cyclic group and its image is gain a four elementy cyclic group in essentially it's in S1 it's just a projective variant of it so the image is like this so so given here uh given think of it in this picture it's it's five I just did it not to have not to have a too regular image uh so that means those five we wouldn't face in our situation because it's not too addic

yeah so but doesn't matter for for the principle here I want to illustrate so so if if H has index five in s one so there are only five cor sets then what are the what are the rectification Factor you just take 10th root of unity this is 2 * bet the root and take its powers so this are sorry that was accidentally so again so if we would have five cets only within S1 then we take the 10th roots of

unity because the first time it's real again is after five powers and that that that would that that would be the rectification Factor you would see or in other words the first call set or let's say the initial one corresponds to the real line that means that we start off with real values therefore we end up with real values if we don't extrapolate at all the next C set would have values over this line determined by the generator of order doubled it index but you and then this would be the

line the values would lie in in the next coret and in the next coret in the next the fourth C the fifth coret is here the first one was trial one and then we would return the next one would be is again we we end up again real I hope this was not too confusing so so just to recap here so let's ignore the fact that we don't know sorry Let's ignore the fact that we don't know about the mean of the function that's technically in our context not a problem we can make these functions having zero mean at almost no

extra cost and so we can simply just re if y these values by by multiplying uh with the inverse of the of of that of that factor row so that means it see yes they are complex but we can by simple multiplication complex multiplication and it turns out in practice you can even read it off in in in the most situations we Face having index two or index four uh yeah so so these are easy easy to read

off so and that's that that that that brought us to I didn't know a better word of it almost native Solomon code uh it's something it's based over over the unit c in the complex you but you input real and you get output real if you if you if you Reck ify so so that means commitment cost is not a problem either so it's as in baby bear if you use uh non-circuit friendly hases because it's a 31 bit field the same piece the same amount of data you need

to Hash uh if you circuit friendly hashes arithmetic hashes then it's even faster that's what I mean depends on the hash here you know and then coding cost as we saw that the m ffd is comparable to Native encoding so uh we expect it to be even faster but that has to be seen uh implementation will be ready soon and yeah little spoiler there will be followup work on this hopefully ready by end of the month not

this month end of November or so so with again with Shaka and d and this time also David from stare I don't see questions yet uh on the chat uh I had a couple myself so I I thought if you can came me well um you say that the F was much cheaper than more complex

is do do you know can you tell us what is the cost of complex ffs to have uh to have because of the complex fft itself yeah uh sorry I need to return here I go back to the slide because of the complex you just take the same uh the the complex ffd would be a two AIC one you just replace here you have the same number but instead like like here you see my mouse cursor uh but you have complex multiplications and additions that means a complex multiplication in the 33 regime cost it's like three times three multiplications for three

base field multiplications three real multiplications for a single complex plus additions even and addition itself is already because it's extension field of degree to twice as expensive so overall it's it's more than three times expensive to the or let's say the speed up is more than factor three from the generic complex fft down to the split radics yeah well it's it's I would say roughly about three times I didn't take into account it a simple observation that also over the complex for the generic complex multiplication by plus minus I

is easy so it's between two and three times faster maybe that's that's more more appropriate yeah um the second question I had was here you are focusing on M 31 but I guess this work can actually be used for any uh for any fields for any messing fields or I mean you can improve here uh or you can generalize here first of all is for fields which just uh have the specific uh in which x s x s + one is irreducible uh and I mean should be also

that p+1 is smooth so there's a recent publication that the room who's also here pointed me at yesterday so uh about fft that exactly use p+1 smoothness so it's a general let's say it's it's it's influenced by the EC fft either so uh so that means people just want smoothness that's that's that's the thing here that's the key thing you can do similarly not with the exactly so you might have a root of

unity uh well it's even excluded if if if p+ one is smooth that means has a high power of two P plus p minus one isn't and probably its worst case totic in most situations so you face again the M Property yeah so it can be extended to Fields but it's a highly specific I wouldn't know I mean there there are other missen there are probably other primes which satisfied but we didn't look much into it so we basically consider the whole thing main application the main field we have here at the M31 though can use it for the m17 also if that is of some interest I don't know and other maybe large primes that are

not maybe standardized primes that didn't look here into that are in which p+ one is smooth uh we we don't have a couple of questions uh the first one from ector uh what about order power of two other subgroups over the complex extension is the needle the most performance we can hope for I hardly could understand you is is it written in the chat can I read it yeah it is WR in the chat please read it just I just need to find how to open the chat ah now I can scroll here so what about other power of two order subgroups over the complex

extension I mean there's only that the the unit circle is for the fft you can go probably farther but there's a problem uh uh for going beyond the unit circle let me let me go back to uh to to to the powers we Face here there's actually only one additional factor of two so two the Red 2 31 corresponds to the unit circle x^2 + y^2 is + one the 2 31 * 2 if we just take out the two here the the other missing uh that

the one and only other power of two that is present here uh then 2 to the 32 is taking the unit circle x^2 + y^2 equal to 1 and uh adding the an what I call the anti-unit circle x^2 + y^2 minus 1 so the thing is yes this is uh so you have there's one a factor two larger than 2 to 31 uh subgroup but it breaks going over there breaks uh breaks uh the relation that conjugation

is inversion so even though you can extend the mft to that factor two larger subgroup I wouldn't know how to extend the rectifiability because it's it's it's it's a key property used in this rectification theorem which is actually quite simple you will just write down the forier series you just write down the powers of the shift and then you you Center the powers of the shift in order that you re

obtain a spectrum which is herit symmetric that's roughly in my words what's happening here so uh and that simply doesn't work out if if you can't say that the conjugate is the inverse this holds over the unit circle yes but over this Factor two larger group over the anti-unit circle doesn't hold I hope this answers the question but just maybe to add something uh unit circle is quite large to the 31 you know

so it in our context if you face such long traces like two to the 30 and you do extrapolation from one W with winess domain of size 2 to the 30 to one to the one and only coret this is within S1 then uh this is already quite I mean these are quite long traces here and we would you wouldn't probably well at least for our for for for for our uh considerations so to the 31 um I wouldn't I wouldn't recommend here to go

with work with higher blowup factors so Factor two is fine so okay is there any kind of prot operation protocol that you can that can drive you out requires you to get out of this real optimal real applications I I hardly understand the question uh could you clarify this is from from Perez no okay there's a new

m not sure if I understand with the cool CET uh I mean as long as we stay in ah okay I mean the thing is that uh that once once we would leave the realm of uh the realm of S1 of the unit circle then uh everything seems to break down here so the the whole so I would expect there is no rectification possible so that mean the main cost even over the cost that an F that all the ffd operations

consume uh the main cost is the hashing the representation of the code words and if we have fully complex uh uh complex uh code words the then uh it's the double cost and I would even expect to be more more more costlier than than the baby bear because arithmetics in the complex extension would be slower than native 64bit field arithmetics like baby bear but I'm not sure if I really answered the question with uh with that

yes that's okay another question we've seen wait wa a second we have highly toic M field this brings and it's a pain in the neck zo it's Scrolls automatically I don't know why do you foresee any way on which this can be applied to non highly duadic fields on the curves like I'm not I I I don't I don't uh I never look that I wouldn't even know what's

the 4 q in the grumping curve the Grump King curve so uh so I just meant that uh for so we have curves that have uh barely almost non uh roots of unity like they might have one as much uh so any kind of protocols that relay on having access to the having access to like highly or at least decently to addic Fields simply don't work so I was wondering whether this uh this solution that you brought to the table for meren Fields can be applied to other fields uh like the ones that are used in these

curves to get to get ffts and and highly toic fields from from the ones that are initially not I mean there is something generic in this idea uh like always you go to extension fields which are ffd friendly but the point is how which degree of extension you need and even if there's something like the generalization of all this improving real fft in the complex there you can you can improve here by using the franus fft so uh there's work on it but I don't recommend to to go that way if it's beyond degree to extension like we face with M31 I would rather recommend to use the EC

fft I'm not sure what do you understand by uh Liam's trick uh I mean uh EC fft I'm not sure if this is man Liam is here let him let him answer this question uh but I'm not sure uh uh if you mean the same trick that what I would understand stand under Liam's trick but uh uh that's just guessing so uh without clarifying the question I cannot answer okay seems to be

resolved according to your answer yeah well let's than again wish for and everyone have a good night I guess or day depend on where you are did hardly understand but I think it [Laughter] was uh sorry I was saying thanks again for the uh no I okay yeah thanks for having me