The ethSTARK Toy Problem

Transcript

We're gonna have Albert present on the toy problem. Um, thanks. It's a pleasure. Thanks for the invitation. So, this is a joint work with Matthew who's now doing a PhD at EPS. This work was done when he was working with us at Nether. So the the agenda is to present the Estar toy problem and the the conjectures around it and then then present some results and observations about it and then discuss whether we should have a toy problem and which one.

Okay. So what are these conjectures or what's the setting? So we have a degree bound D a subgroup D of a finite field of size D + one with D + one being a power of two and there's this problem which is supposed to be a simple setting to try to deise attacks for the for the star or the fry or some frying problem. So the prover is tasked with choosing a map from D2 to F. of a word and then the verifier replies with a random element and then the goal is to use the prover has to convince the verifier using that this map in here is close to our solo with dimension d + one

and the map is f of x minus the random challenge divided by x. So the first conjecture says that the sound is error and best you can do here is 1 / f plus the rate of the code so dimension divided by the the size of the evaluation domain d uh raised to n q which and gives the number of fry queries. I'm assuming everybody is familiar with the fry protocol. So the second instar conjecture is that this this um this problem is um a good proxy for the start IOP. So any the conjecture poses that

any attacker to the to problem can be turned to attack to an attacker to the stark IOP and vice versa uh with the same and both attackers have the same sound deserved. >> Yes. >> Should there be some multiple sorry multiple group size like two * >> like right now you don't really have >> Oh yes yes yes yes >> it should be like instead of b here in the original it should be over yes >> should um should your denominator >> yeah it should be f of x - fa x >> what

>> it should be f of x - f beta on xactly approximately test >> you take B to be zero >> but >> you're testing is the function f evaluating at beta if f is f of zero equal beta that's what's missing >> uh would that even be true for arbitrary f right >> just the f >> there's no completeness of this protool >> correct >> it's just soundness >> yeah yeah >> so there's No honest prover that can pass this. It's just >> any proofer just cannot pass it because high probability f of zero is not >> it's a throwaway statement that is

designed to be false. >> Yeah, it's designed just to see what's the sound of this. >> Okay. >> But I mean just who picks who picks F? Because can't the prover just pick F where this is true? >> The prover picks F. >> But then I just pick an F where it's true. >> Pick an F. You don't wait. >> Let me tell you, let me tell you what I'm doing. >> Okay. >> I see how if you beat that for sure, you destroy any start. Great. >> Okay. Okay. >> Weird. >> All right. We we can discuss whether this is weird or not afterwards.

So, and first result and present is an attack problem with this accessibility which is larger than the the conjecture one. Of course, it's not of any practical consequence because this extra term in here is still negligible. If if the rate is one half, then it's just one little security less. I think that the interesting thing about this result is the actual attack and the proof that the attack succeed with this probability. uh result two is I think the second if that conjecture maybe I I don't know it's quite easy to it it is intuitively it sounds very incorrect intuitively because in the stark IOP you can exploit the deep query

point to build attacks in quite simple ways if if you are familiar with this type of IOPS you'll come up with an attack that succeeds with this probability in two or three minutes and these attacks you you just exploit uh being lucky with the deep query point and there's nothing similar to to taking a deep query point in this in the toy problem. There's nothing like we are checking that two polomials are uh equal by evaluating them at a random point. So it's it's intuitively very unclear that the toy problem is really a proxy of this kind.

And result number three which I think is conceptually more interesting is that for any strategy to a variation of the toy problem there exist an attacker to the start IOP that succeeds with this probability. So the probability of of the attacker to the variation of the toy problem plus this term on the dimension of the code. So what is NQ? >> NQ is the number of right queries. >> Okay. So 2 row to the NQ will be some small fraction.

>> Yes. >> But that numerator like 2 row to the nq f will be less than 1 / f or what? >> If the if the rate is less than uh 12. Yes. It's an impliminal term. the attack doesn't have any practical consequences. So and and it should be like that because f some right we'll never get anything that's not negligible here. >> Oh so if row is one half then you get a one over f >> term and otherwise it's something really small.

>> Yeah. >> Okay. So and then uh after presenting these results I'd like to discuss what to setting we should use if any and let's get to it. So >> so we just have result three. So it's not a like it's nice but it's like the wrong direction right we want to if and only if on that >> well result three says that the star the toy problem or at least evaluation of it that looks like it is not a proxy of the star.

Yeah, we want to show that anybody that attacks the star can also attack the toy. >> Yeah. >> Well, this is an attack, right? So, this is >> but this is like saying this the this is for to say that the the toy problem is probably not a good as is formulated now is not a good proxy for the start. If you want to attack the star IOP, you shouldn't just be attacking the toy problem. >> Just quickly with with the result one in some Okay, in a weird one we had row than a half. Doesn't this suggest that taking more query queries makes us less sound?

>> No. >> It's more sound. >> But uh hang on. Doesn't success go the wrong direction? Like like if row is bigger than a half then two row is bigger than one. So as nq nq is big then that >> row will always be a half or less. >> Row is one over a power of two. Not so you could use like you know the 1.5 blow up that they use in darker at some point like it's like >> yeah you like I mean I can just take the poly or something which is like you know 1.5 times bigger than my rate is like >> 2/3 which is bigger you can't do that it's

like this gets very strange if you have rowing and a half right >> I I'm not sure if it would working if the attack would work with row bigger than 100. Yes, we would need to check. >> So >> in here row is at most 100. >> I mean I I hate to be annoying but like let's say row is a quarter. Okay. Then and NQ is like 100. >> Yeah. Then you're stating that what you have 12 to the 100th power over F. >> That number is so small that like that might be fewer than in other words to even that just gets rounded to zero I'm sure right unless you have a huge amount of slightly more

term >> but the amount of random coins you sample is like finite right so the the possible success probabilities that you can even have can't have arbitrary denominators like they they can't have denominators with like >> but the number of random coins is depend on NQ so if I bring NQI I have more random coins in my probability space gets like >> but now you have a denominator that's like 2 to the nq * f right so >> yeah but that's the amount of randomness also that you use >> well you need log f* nq bits of randomness sample >> might be more than you sample right size like

size of n times size of what is it nq * log nq * n F * NQ >> bits in the denominator. >> Yeah, >> which I think is enough for you to for this to make sense. >> Is it cuz >> then you can have exponential in the number of bits that you >> sampling the >> Oh. Oh. Oh, interesting. Can I also add the point is the to problem conjecture says that the best attack on the to problem is 1 / f plus row to the n. So the point here is not like how good this attack is. It's just that

>> this attack in itself shows you that the conjecture is a bit too optimistic already. >> Well no well >> even if this term is the tiniest thing in the world positive I'm asking if it can even be positive right because if how if if it's too small it just must be zero. But no, >> if they show that it's bigger than this, then what you're saying just the actual result just is even better, not worse. You don't round it down. >> I think the point is not really that what was this success probability. The point is that there's a a way to attack the toy problem which is not described in the paper which is a valid attack.

>> You want that term to be positive for this to be an a result and not a no. That term needs to be positive. But the term is positive right now this term negative or or zero if row is not zero or negative >> and I prove that some I don't understand >> yeah let's let's move on >> yeah yeah right so it's okay >> all right so what's the attack described in the if paper the rubber chooses a a polomial arbitrarily and sends it to the verifier or sends evaluation of the map to to the verifier verifier replies with a random challenge and then there's two cases. One is that the random challenge

is equal to the constant of the the constant term of the polomial and in this case the this quotient the quotient becomes a polomial and then the prover can behave honestly in f and it will convince the verifier with probability one. Otherwise the paper proposes computing a interpolating the the map that you have to apply fry on. So you just compute a polinomial qfs that agrees with your map on a set s of size t + one. You have to choose this set so that it is closed under location and then you you engage with the verifier on Friday and hope to get queries from the set.

If you get qu only queries from the set S, the verifier will never detect that you swapped the map you are using and you will convince the verifier otherwise the verifier might catch you and otherwise you just behave honestly. >> So is J and Q. So you have Q here and then you have J agent for the same. >> Yeah. Yeah. G is Q. I changed it at some point and I forgot to change this one. Okay. So error of this is one / s plus row to the iq.

Uh so as I um as I said if case one happen if if the first situation happens and verify your access for for sure if case two happens the only consistency is that again q and g are the same. Uh the only inconsistency is that the brewer is using a a different map than it's supposed to use and it's only detectable if the verifier samples a query point in some set where Q and the true map agree and in that case the success probability is the ratio between the this subset and the the size of the evaluation domain raised to the number of queries. Now if your denominator is just uh is just x or a polomial of

degree one then this s prime is just uh s if the denominator is larger this prime to be larger. So if you for example here you put x to the 10 then there's an extra error term here because it's possible unlikely that uh the interpolation agrees with a true map on a larger set but anyway so Okay.

>> Um, no. I was going to skip this, but then we can prove it now. So if if fus beta x agrees with a pol on a set >> then f ofx which is a polomial of degree dal x >> then in case two we are assuming that beta is not the constant term of f. So if s prime is too large then f and f has constant term beta because they must be the same polomial if s prime is too large.

Okay. So this has degree d and this has degree d + one and s prime has if s prime has size larger than d + one then they must be the same polomial. So they have the same constant term >> but is it ne kind of Q or G can have degrees smaller right? Uh yeah >> but you did it already on a set which is larger than the four.

>> Yeah. So if here I put 10 um it's possible like like s prime can be larger. You need a larger set to make them make them equal and as long as you are not forced to have them equal uh you you don't violate the condition that All right. So new attack sample a polomial at random and send it to the verifier or send it to evaluation on the evaluation domain. Verifier replies with a challenge and now case one is as

before. If the challenge is the constant term of the polomial, you just behave honestly because your the the honest map is in the code. Case two, the idea is that we behave honestly until the last round. So we engage in fry verifier sends a fry folding challenge alpha one and then the prover computes the honest fold of the honest map with the challenge alpha 1 and the result is a map from this square to f. So this square means the power of the square powers of the elements on D and F is the usual fold. Here I'm using the simplest version of frying possible where faults are too high

and what happened. Okay, then pro compon sends default to the verifier if the valuations on B. This keeps going for new rounds. Verifier sends in the second last round verifier sends a challenge. The prover computes the honest spot of the previous map. With this new challenge, it sends it to the verifier. Verifier replies with a new challenge.

>> Sorry, H are pol. >> They are um they are maps. They are functions because in this phase two you start with a map. It's not a pol. >> And what does it mean when you send this? >> You send the evaluations of this function on the 19. >> Yeah. An oracle or a commitment. >> All right. So now the verifier sends the last challenge and now the honest prover in fry will send the fault of the last map of this last challenge. So it would send this map if the prover was honest if the provers honestly in front. But

instead what the prover does is it looks for the constant such that the honest such that this constant agrees with the honest fault of the previous map on the maximum amount of elements of the last domain of fry. Last domain of fry is d the evaluation domain raised to um the dimension of the code. So it looks for this constant and it sends this constant. Remember that at the end of the prover has to send a constant or a polomial in the clear. So it just sends this constant.

So let's recap. Prover samples a random polomial. If it verifier replies with a challenge, if the challenge is the constant turn of DC is zero, the prover engages honestly with the verifier. Otherwise, the prover behaves honestly until the last round. So it sends the honest faults of the map which is not a polomial and at the end instead of sending the honest last fault which it cannot because the program has to send a constant it sends the constant that the constant that agrees with the honest fault on the maximum number of points.

Is it possible to show it on like small like one >> to show um >> what exactly >> if this works this works for for mu= one right? >> Yeah. So so if um if mu is one verifier would send a challenge and then the next thing that the prover has to do is to send a constant. So the prover would send a constant such that the only fault of f minus beta /x agrees with this constant on this square.

>> I mean maybe we can just take the small small f like c 0 linear f >> just set f equals z. >> Yeah, you can just set f equals z and that just set f equals z and then basically what the pro is working with is uh beta on x and then we could just work through this like >> and then what if you send zero then what? So, so the provers f equals z initially and then the verifier replies with beta and if beta equals z the prover succeeds and if beta doesn't equal z the proven now has to do fry on the polinomial beta / x and so now you could just write down like so the proof is alpha 1 and I think we showed in the previous slide the formula for h1 of x >> and if you just set f ofx if you set the

thing you plug in to be beta on x we can just work out exactly what like what the fold like what's the fold of beta on X. It's like you can just work that out based off that formula. >> I don't think that you have just a rational function of degree one. >> Yeah, you do. Just said I'm just setting f(x) equals z. >> It works for rational functions either which is not that obvious. So >> I mean what is not obvious that there exist some some some constant with >> con maximum right? There's one at least there's a constant that agrees with the be on one point.

>> If the aration is in degree one it's not obvious that maybe >> yeah it could it could be just one point. Yeah. But it could be more max. >> We are going to analyze the attack. Now >> in the analysis will you use the fact that f is random or would the same analysis work with all the functions? >> No it's crucial that f is random. So let's see the analysis. >> Doesn't the pro get to choose F? >> The prover chooses F, but here it chooses it randomly. It's very important.

>> Okay. >> Yeah. Yeah. In the toy problem, you can choose any F you want, but in this attack, you choose a random F. >> Okay. So >> success probability. If case one happens, V accents for sure. Interesting case is case two. So if case two happens and beta is not the constant term of the polomial then the verifier accepts if and only if all the query points in f all five query points satisfy that the honest fault of the last map at the corresponding point in the last domain

is equal to the constant the provers because this is the only inconsistency the verifier make right? It just behaved honestly throughout the entire problem and at the end it sent an um an incorrect fault. It didn't send the map it was supposed to send. So the verifier will detect this if and only if it queries some point in uh in the query fry query phase such that this doesn't happen. All right. So we have to analyze what's the size of the largest subset of the valuation domain containing y such that this equation holds

>> if it only occurs there could be inconsistencies that oh sorry >> everywhere else >> so because here we have y to the d + one and this smooth and raising to the d plus one is aorphism uh d max is a multiple of d + one. So the the size of the max is a multiple is a * d + one. And now the question is what's k? So uh if we fix beta and the challenges then we have a fixed k and the success probability in case two for these fixed challenges is exactly this is uh k times the rate of the code raised to the

number of query points. >> Wait wait wait wait. Isn't shouldn't this depend on the number of uh elements that agree with C max? >> Yes. Which is this? This this is the set. >> Yes. So shouldn't the size of Dmax Oh, you defined K to be the size of DAX. Uh >> K is the number of points here. such that this such that this is true.

>> Yeah. Yeah. Yeah. Okay. >> Can it be one? >> It can. It definitely can. >> It can be one. Yeah. In general, it will be one. >> The point is to exploit when it's more than one. >> Yeah. >> So, um yeah. So, for if we fix beta now and for and leave the alphas as random, then the success probability if k is two happens is the probability that k is 1 rate to the number of queries plus the probability that K is larger than two times 2 * the rate to the number of queries.

And now the question is what is the probability that K is larger than two because remember that the original attack had this term and we are trying to add an extra term. So the lema is the result is that k is larger than two with probability 1 / f and that's why we get the success probability I mentioned at the beginning >> where does two row sorry where does two row come from >> where does the last expression is you see the expression it's k >> so um Yeah. So it's like it's the for fixed beta the success probability is

probability that k is one time row to the n plus row plus probability that k is 2 * 2 row and so on. But uh here I just put k. >> Okay. So some remarks I'll explain why um we the probability that k is larger than two is 1 / f. I think it's more it's more interesting than what I was expecting when I was um analyzing at the beginning the probability of this of this approach. So this is extremely larger than the start probably is it's not it's not too much but it's larger.

So there's a general line of thought or conjectures which expect that fry query phase only adds a row to the end error term. I guess this shows that it's not possible strictly speaking. you have some extra terms that come from the query phase. You'll never be able to do exactly row to the NQ and as I said the proof of success probabilities I I personally find it slightly interesting. >> Sorry. >> Yes. So do you think this is sort of like conceptually the reason why in sort of the the up to capacity conjecture we have an open interval whereas if you don't have this

extra term that you now figured out it's sort of going all the way up to the closed end of this interval. Is this morally the same reason? >> I'm not sure it's the same reason actually. I'm not sure >> it's a good question. >> Yeah, >> I still failed to understand. Okay, if >> sorry if new is equal to one, we have degree one f is linear and you say that uh c k can be equal to two. If k equals to two with probability like and this probability like one / f it sort of says there is one special alpha one for which

you succeed but how can it be if you have just for one and you respond with sim x and that's it how can it be that there is some special one for which you succeed >> well maybe we can see the this this analysis of this success probability and check what happens when mu is one. All right. So let's see why the probability that k is larger than two is at least 1 / f. So first attempt first thing um I thought was going to work for sure is that since the initial map and

the ch the folding challenges are random and beta is random one would expect that the honest fault of f minus beta x is a uniformly random a uniformly random map among the set of maps that go from the last uh f doain to that sounds reasonable and that's what I was expecting but it's not the case >> it's not the case because you excluded because fal >> because you are not in case one so >> the folding is identical even if you are

in case one so the distribution on hu is actually independent of which case you're in, right? It depends only on the C. >> Yeah. Yeah. It actually doesn't depend on on the case. We'll see now why. Uh so if this was true and the honest map was uniformly random among the set of all the honest maps that go from the last sprite domain to F, then the probability that K is larger than at least two is the probability of sampling a non-jective map among the set of all such maps. And this probability is about row to the minus 2 / f.

We can we can check why but not not too relevant. Now we can just take it for granted. However, it turns out that this map the last map is very far from being random. There's actually just two degrees of freedom in this map. And the the presence of this denominator this pole in this function is crucial to have one one of the degrees of freedom. If this pole was not there, there would only be one degree of freedom and it would not be possible to prove that this this probability is more is larger than zero.

>> Yes. >> Uh so coming back to this this last question about have been random or like not not uniform. So uh you analyze the success probability of this attack you cannot do a union because that would be the wrong direction. Right? So what what you have to do is you have to say okay probability that I win and I'm in case one that's one f plus probability that I win and I'm in case two. So in that second term I have to condition that I'm in case two. So at that point I can no longer assume that um Yeah, because because you you can do that if you do a upper bound of the success probability but here you want

the lower bound. So you cannot just do the trivial unit bound. >> Yeah. Yeah. You need to like do the total probability and then in the second term you have to condition on >> being in the second case. Yeah, in the actual analysis we we do this we do we do this printing and we don't do counts. Yeah. >> Uh so let's uh continue with the proof of of the lema. So let's look at the at fault as a linear operation between linear operator between the set of maps uh from the valuation domain to f uh and the challenges to the set of maps from the square of the valuation domain to f.

So the fault of the honest map fault of f_sub_x minus beta /x in the first step is the fault of this expression in here writing f in in its polinomial form and fold is a linear oper operator. So we can rewrite this expression in this form. So we got this linear combination of the fault of the monomials. So mono powers of x starting at the power minus one and these coefficients are uniformly random and I guess that if we are in case two we

also we have to condition that c 0 is not equal to beta and iteratively f is um f is we can use linearity of fold iteratively so this expression means folding mu times with the challenges alpha one up to alpha mu. So if we fought mu times with the original honest map we end up with uh so we would end up with this expression in here but now we here we have qu of mu times. So quicing mu times of the honest map is this linear combination with this random coefficient and in here we have the new fault of the powers of x starting at minus one. So

overall if we write h mu as a vector so the vector of of evaluations of the map on the last f domain we obtain that it the vector is exactly this in here. So we have this matrix whose rows are the new m new y's fault with all the challenges of the powers of x on a fixed element of the final f evaluation domain.

So the rows are indexed by elements from the last evaluation domain and the columns are indexed by powers of x. And then the final map is this. It's this matrix times this vector here which and this vector here is almost uniformly random. And so this is a a matrix times an almost uniformly random vector which means that the result of the multiplication of the matrix and the vector is a vector with the rank of the matrix degrees of freedom intuitively.

So the question is what's the rank of the matrix and it turns out that the the matrix has rank at most two and it has rank two with overwhelming probability. So if you look at alpha as indeterminates then you get a matrix whose degree whose rank in the ring of polomials and the indeterminates is two and then you can use multiple lema to prove that the rank is exactly two except with negligible probability and if the rank is exactly two and it's not one then you can prove that that this map uh is not injected at least with this probability.

= >> Can we just Can we just do the mu= 1? I think you can just do one% [Music] easily. >> Can we finish? Wait, >> you can just you can just work through this like on paper with mu= 1 d= 4 and setting the zero polomial and you get you get exactly what >> I feel I vote that we finish the f the main presentation and do this. What do other people think? >> Yes. >> All right. Okay. So now I want to talk about the start IOP.

So cars on the st IOP. We have the sub a subgroup B of size B + one and an over subgroup of size P + 1* inverse of R. There's that question about the master attack. So it was computationally efficient right? >> Yeah. Yeah. Not efficient. Just a successful but it is tiny but other than that it is a real >> yes. Uh so then we have a constraint. So I'm describing a simplified version of the start IP. Uh so we have the oversight group the valuation domain B a constraint polomial which I assume is of degree two and then an error is these

two domains H and B and the constraint polomial and that's the instance and the a witness a valid witness for this instance is a der of polomials where all polomials are are of degree at most D + one and Q vanishes on the valuation domain when you replace the y's by the polomials. So start is a let's say it's an iOP for proving this relation everything is simplified here though in in reality the iOP and the air are much much more complicated. So the iOP works as follows. The provers the evaluations of the Q's on the on H and

the evaluations of this uh this polomial in here where you replace the Y's with the Q's by the vanishing polomial of B. So the evaluations of this map to the verifier. This map is a polomial if the prover is honest. Then the verifier sends a soal deep query point in the field. The prover replies with the evaluations of the maps Q. The verifier checks that Q when you replace the Y with the polomials little Q evaluated at at the query point is equal to R

evaluated at the query point times the >> Z D Z I forgot to add to multiply R by Z D at Zeta and then the verifier errors and some random challenges to batch to use bugs in Fry and then program a modifier engage in Fry to test proximity to the reasonable code of this function in here which is the function that's supposed to certify that the prover correct evaluations of Q and R here it should also send R of that

and is it clear? It's I hope you've seen the start otherwise this probably doesn't make much sense. Um so the second conjecture is that the start IP is as hard as the toy problem. I think it is very dubious and it's not um it is kind of clear why it's utopious and the reason is you can exploit this setting here. So you can have the prover arbitrary polomials at the beginning of the protocol and then you interpolate the this quotient function in here on a set of size v + one and you hope to receive uh the query point in the interpolation

set and if you receive the interpolation point in the query set the verifier will never detect that you sent an invalid an invalid map here that you send just some interpolation of the true map and this will succeed with probability at least plus one over f could be more actually but at least plus one over f and this is the first attack you would think of and I think this type of attack is qualitatively not present in the toy problem it doesn't look I I don't see why this would be uh comp included in the toy problem.

Um, so yeah, we have seen so far an attack to the toy problem with this soundness error. We have also seen an attack to the star with soundlessness error D plus one / F. This means that the two conjectures are not true like they cannot be true at the same time. um first conjecture is this proof by a small margin. So I think the what's interesting about the the this attack is the proof of why the success probability is what it is and that it is an orthogonal attack to the one proposed in the paper.

And the second conjecture is formally not disproved. So I think it is very obvious for the reasons I already explained. And now I will actually show that you can uh build an attack to the start IOP from an attack to the to a variation of the toy problem that succeeds with probability much much larger than the the attack to the toy problem. Okay. Okay, so the attack applies to errors with an isolated variable which is which are errors where the constraint polomial has a linear term.

You can say polinomial has for example is of the form c * y plus a polomial that doesn't depend on on y1 and this is uh this is I think this is a natural scenario where for example you are expressing constraint of the form first cell of a row is a polinomial expression of some cells in the previous rows. So the idea here is that if your constraint polomial uh has this isolate isolated term then you can falsely prove the evaluation of this expression

of the polomial replacing the y's by the q's. You can if you are able to falsely prove uh evaluations of Q1 then you can prove evaluations of Q of the bigger Q. Ar you can prove arbitrary evaluations. If if you need this thing to be certain value, you will just solve for Q1 and then prove that Q1 evaluates at whatever um solution you found. And this this will allow us to prove that big Q evaluated at za is consistent with the quotient with the vanishing polomial of the valuation the value um of the of

the evaluation domain and the and the r sent by the prover. So the attack the attack looks like this. Prover chooses arbitrary polomials of degree plus one and sends the sends its evaluation on h to the verifier. And then the prover interpolates the quotient of x replacing the y by q and the vanishing polomial on a set of size d + one and it sends this the evaluations of the interpolation to the verifier.

Verifier replies replies with a deep query point in case one. If the if the deep query point belongs to the interpolation set then the malicious prover continues honestly. So this is the situation of the first attack to the stark iOP we saw. And in case two, the maiser computes a value for an evaluation of Q1 that solves this equation. And this can always be done because because the polomial is linear on Y1. So you can always solve you can always solve for Q1 star here.

And now you send honest evaluations of Q2 up to QL honest evaluation of R hat at zeta and then you send this ponest evaluation of Q1. Now the verifier asserts uh this equation and of course the equation holds because the prover evaluation of Q1 so that it holds. The verifier replies with the batch fry randomness and now you use fry to test proximity of the of this quotient poly which quotient maps to the original.

So this is just the earest uh max function that you you would apply fry on using this dishonest evaluation of Q1. So this is a polomial because the Q's are polomials and the Q2's Q2 up to QM za are honest evaluations. So this is just a polomial and this is not a polomial. This is a function because q1 star at za is not an honest um it's not it's not an honest evaluation of q1.

So observation is that the f the pin part here resembles a toy problem setting where the prover choses prover chose Q1 arbitrarily. Then it received a a challenge zeta and some maybe some more randomness and from this it computed q1 star of zeta. But this Q1 star of Zeta kind kind of looks random, right? Because you can choose Q2 and etc to be random. And this Q1 star of Zeta is whatever you have here minus this over over C. And if there's more constraints, more polinomial constraints in your air,

then you are actually batching them with randomness. and then q1 star of za is actually uniformly random because of this extra randomness. So uh so so here prover chose a polomial it had freedom to choose q1. It received a random point q1 star of zeta and now it has to prove that this function in here is close to the rich solom code basically because tx is already a polomial. So proving that this function here is close to the code is equivalent to proving that this pink function is close to the code.

So this is just the this is basically the toy problem except that we have a random challenge here. If if this zeta z was all here, this would just be the toy problem. But this this attack succeeds with probability strictly larger than the toy problem because there's h1. Case one happens with probability this d plus one over f and case two is the toy problem. So the success probability of this attack is d + 1 / f plus whatever you can do in this variation of the toy problem.

>> Sorry. >> Yeah. You have to remove the the you have to make sure that you don't get uh zeros in the denominator but the the stack I hope I described is simplification. Okay so I think this is just what I explained of why not to problem is contained here and I'll just move to the end of the talk. So some final thoughts is that there's a general conjecture that the fry query phase adds ro to the number of queries to the error term and many companies use this bound.

this um work shows that's not possible strictly speaking even though uh if the rate is not one half it's lower than 1/2 the term is extremely small and if the rate is 1/2 the the extra term is still very small and that variation of the problem I mentioned is contained in the star IOP strictly contained I'm not sure if the two if the two problems are the same have no idea if they are equally the variation of the toy problem or the toy problem. Uh I think it's still interesting to study these toy problems but we must be aware that they are not full proxies of the star

and as a question I would like to pose. Should we have toy settings? If we should have toy settings which one should we have? I also wonder if the toy problem and this variation of the toy problem where you have a random element in the denominator are equivalent. And yeah, I wonder if if the attack to problem the the philosophy of of of the attack to the problem of trying to to get that the only spot becomes slightly close to the goal can be expanded or combined with other attacks and that's it.

[Applause] So awesome, awesome, awesome work. So yeah, I mean stepping back a little bit, this is actually an attack on Fry that is better than the previous best known attack on Fry. Is that true? Like >> I'm not familiar about attack attacks on Fry. >> But this is an attack >> this is >> this is an attack on Fry. >> It's really necessary that you have the the X in the quotient here for the to attack problem to to work. Of course, you cannot prove that.

>> No, no, no. Okay, but forget toy problem. Let's say I'm attacking Fry for some reason and I can still do this, right? >> But so if you see this, the conjecture tells you um the best way to beat the third problem >> is either to get lucky with beta or you have this row to the n / q chance which if we look at fry we know that's that's a quick phase. So the conjecture sort of ignores anything going wrong in the folding phase. So if you have any attacker, if you describe any attacker that tries to take advantage of a bad folding challenge, you will get something better than just road to the end of a cube.

>> So it's not an attack over fried per se that's better than the ones we knew. It's just like >> waiting. Yeah. >> Which ones did we know? Are you describing a different attack on Fry that's better than this or what? I >> I don't know. What we do know is like the soundest proof tells us if anything goes wrong in one of the folding phase, there's an error term for that. And if anything goes wrong in the preface, there's an error turn. Now whether or not we have attacks that exploit something going wrong, we don't know. And here they're describing one that exploits something going wrong in the final uh folding challenge.

>> Yeah, but it was assuming that the point was could be inside the domain, but if you just force that the point is outside of the domain when you sub, then this attack wouldn't work. >> What point are we talking about? >> Set up. When when he chooses set up for the attack, Yeah, I I'm ignoring that. I'm talking about the folding phase of the Fry protocol. >> Okay. So the the the proof of security of Fry tells you that um if if if the initial word is say not close to the code, let's say be bigger than unique decoding radius, then your per query error is bounded by like 1/2 plus row over two. So this is not contradicting

that, right? In other words, the the upper bound on on soundness error is 12 plus row over two. So for row equals one that's like 3/4s and then 5/8 and then 716. So that's what that's the upper bound. This gives you a a lower bound that's better than row over uh that's better than row, right? >> Yeah. Yes. So that doesn't contradict the upper bound obviously because it's proven. Um but I think nobody had this is a better lower bound than was previously known. Is that a fair statement or what?

>> I don't know. >> Has anybody written down an attack on this is an attack on fry generally? >> No. I mean I I think it it if if you look at the term just for for a toy problem, it was too super aggressive. not not taking into account any any uh soundness errors knowing soundness errors of the folding uh of the folding rounds before you quer that's my understanding. So uh it's simply you know if if you would if you would try now the same against uh in a more sensible way having an error for fry which is also divided into falling face and and query face you probably

wouldn't get something better I guess >> just let me just let me just rephrase my my question basically this seems to me the general attack on fry. I, a fry attacker, can use this trick, right? I don't care if it's from the toy problem or if it's in base fold or in anything. I this is a new way to attack fry. Um that um >> but it's not not with better probability than >> so what better attack is there on >> you can get n plus so I mean currently the the toy problem is one on f plus uh queries. You can get n plus one on f when n is the number of rounds.

Yeah, >> you can get that from the toy problem too. I think I think the estimate for the toy problem you can be n plus one on f not one on f. So you're saying you have an even better attack on the toy problem than this attacker? >> Yeah, >> because you just have to set it up so that all you need is like one bad like every time you get a fold, it should be like basically the error estimate should be bad or or one of the alphas is bad and that gets you plus one episode three >> but that that's looking at soundness right of all the applications we care about the non-interactive scheme where we have roundaround soundness and if you analyze the non-interactive scheme by roundness you usually depend on the rounds because you can take a max. And the reason is that

>> an attacker that wants to attack all rounds, of course, it has a probability of n times that, but it also has to spend n times as much time. And so if you look at the definition of bit security that says success probability divided by running time, then this can this term n cancels out. And so if you analyze it that way, >> I I don't think so. I I can I can write down an attack on the joint problem that gets a sample. >> Oh, sure. He's right. What he's what he's saying is uh this this this attack would be better in an interactive attack.

>> Exactly. Yeah. >> Not interactive. It's not the sum of the soundless errors of each round, which is why you get locked in. >> All you need is something to go wrong in one of the >> Yeah, but you have to spend n times as much time. I I just run the protocol and my probability of getting success is not one on, it's n on one. >> Yeah, but we don't care about the success probability. We care about the ratio between success probability and running time. >> But this is that like the other attack just only does the first round repeatedly and so doing all >> Okay. So what I was saying is you're right that in the interactive scheme you have an end times round error.

>> Yeah. >> But that's not what really matters for us in practice. We care about the non-interactive scheme where we should use round samples to analyze it. And then if you analyze it via that way, your success probability will still have uh will sort of have a max instead of a sum and then really the number of runs doesn't matter. I can show you >> is a point that like that if your attack is relying on something going on in one of the alphas, you might as well just try like repeatedly try the first alpha.

Like there's no point doing the whole the fry protocol. You should just attack the first round. Okay. Like I said, when attack's the worst round, right? >> Sure. Sure. >> Are you are you saying you you can get bad folding challenges? >> Yeah. >> But but can you really like the probability bound isn't but but can you do like do an example? Do we have is that a black or not? >> No, it's not a blackboard, but we have this. >> Okay. >> So just to clarify, what is your n the number of rounds? >> No, no. Yeah. I mean, I'll just do the >> Are we attacking the interactive protocol? I mean, >> we're attacking the toy problem. So, >> okay. For that for that, I I agree that because it's an interactive thing. I agree that the number of rounds is

>> Yeah, I think you're right. >> I think you can actually also like for the analysis, you can also avoid the dependent on the number of round because then you kind of like, you know, you can think of the same round do state analysis. So you get like okay I transition from doom to non doom probability then if I instead of taking a union bound I take combination then the com combination is still the maximum so the the the sar will concise you don't need to get that nation >> okay so what's what's the simple version of the toy problem so the provers the function f the verifier sends beta the prover then uses this to comput f ofx X

minus uh beta on X. >> I don't sorry to interrupt. We are like formally we are at that time. So if people want to go to a break just to let you know. >> Yeah. Sorry feel free to leave at I mean we can talk about this later if people want to get coffee first or something. >> No no we you won't be dabbing. We're going to stay with you. >> Okay. So and and then the prover and then the prover basically the prover commits to this polinomial the verifier sends an alpha and then the prover uses to like form for alpha. Okay, so let's let's just do the simplest the simplest case here where we're going to work where our domain has exactly four elements, right?

We got one plus or - 1 and plus or minus i and then we're going to set like little d is equal to two so that our polial okay so the conjecture now is that the the probability is like one on f um plus row to the this is the toy problem. I know you've improved it slightly. My claim is that like we can easily we can we can just get two and f without sort of doing nothing here. Um all we have to do is just the prover sends the zero polinomial to the verifier. Okay. So it commits to the the vector of zeros.

The verifier sends back beta. And so now what's the provers's polinomial? It's exactly beta on x, right? Or negative beta on x. Okay. So what does what does the prover now now commit to when they commit to this? taking it to negative beta beta uh i beta negative i beta right where this is like 1 i so now we do the first folding step the verifier sends alpha so how do we fold well the fold the folding function looks exactly like we take sort of h of x plus h ofx on 2 plus uh alpha * h of x - h ofx

on 2x. Right? So what happens in this case? Well, we have a negative beta on x. That's an odd function. So this is just zero. So what we all have to worry about is this thing. But it's pretty easy to see that if we apply that to negative beta on x, what we get is negative alpha beta on x^2. Right? So what do we get down here? So now they said alpha and the prover now has the polinomial alpha beta negative alpha beta and so what's happened well if alpha was zero the proof is one so we already have if beta zero the prover wins if alpha zero the prover wins so we already have a f and then the prover just sends alpha beta alpha beta and now the verifier does a bunch of samples and

basically if the verifier ever hits this term the verifier wins and otherwise the prover wins. So you're sort of tribuling at this. >> No, no, no. >> That was too fast. I didn't get your two here. >> So, okay. So, the what? So, one of the x is coming from if beta is equal to zero, we we win, right? >> Yes. >> Okay. And now if alpha is equal to zero, then the the alpha fold of this thing is is is just zero. So, >> so and in that case, these are both zero.

>> So, so if alpha is equal to zero, we always win. >> Yes. So that's 2 f >> in the interactive >> because b is one over f and alpha is one over f >> in the interactive world. Yes. >> Yes. Yeah. So the probability that is zero. >> Does it show a dependence on the number of rounds? I mean that just shows that term >> my claim is you can modify this pretty easily to get to get one on each round. Like it's a more complicated >> or the interactive protocol. >> Yes. >> But we don't care about the interactive protocol in practice. Right. >> Problem is an interactive. I'm I'm just doing the toy problem. All I'm saying is the toy problem should be n plus one f.

>> Okay. Sure. Then the question is do we really care about the toy problem? >> Sure. >> In the end we care about you know >> if you're that like in each my claim is to be in every round you have a one error. >> If you you have first there's probability take over beta >> doesn't matter what >> it doesn't matter because one f >> bet is a random choice random field element. Yes, we >> we f you succeed. Yes. Now we consider the other case. Okay. >> So you so the assume test for beta is not zero.

>> Now if alpha is zero the probability you succeed is one like now you randomly pick alpha. >> So you you randomly pick two things. If either is zero then then you succeed. >> Yeah. But in the other case is taking the probability 1 - 1 f. >> Sure. Sure. So like technically this is like 1 - 1 1 - 1 - 1 f but I'm just killing the one square term >> then right what you what you get the one >> okay so so if you want we can write this as like I guess you can do this if you want my claim is that like adding this term doesn't really >> okay so I guess this is what I'm truly claiming something like this >> I'm happy if you want this to be the

claim it doesn't matter to me too So like my claim is that we can sort of ignore higher power. So remind me what the initial the initial attack the initial >> the initial claim was that is was this um >> initial one is this and I found that we can get like >> you're claiming that there's easier there's an easier words you can get lower and is then you have one 1/2 plus 14 right so originally you have three quarters and what do you So what do you mean 3/4? I mean f F should be like 2 to the 3, right?

>> Right. Or what? >> What? >> How big is your F? >> F is the size of the field. >> Yeah. F is large. >> So F is like 2 to the 30 or 26. >> Okay. Then >> yeah. >> So >> what you mean L? What is L? And the number of >> oh n oh sorry so n I mean so if n is low then like then then then the row term is on the dominates right >> yes and that's tiny so it's just >> okay

so I I think there there's a bit of a subtlety which is that your attacking challenges other words your attack depends on whereas the other attack is actually totally independent >> wasn't implicitly attacking bad challenges >> no he wasn't he was attacking a final double >> yeah which would come from bad challenges >> couldn't that evening challenges are not >> no that's the definition of Bad folding challenge. You get like closer to the code. Does that make sense?

>> No, but he didn't need to get closer to the code. >> No, he did get closer to the hecting challenge. >> This attack folded fully honestly. Couldn't it happen? >> I fold it fully honestly. >> Yeah. Yeah. It's when Dmax or when K is bigger than one. That's the case where you you got lucky with your full challenge. >> Yeah. Like that's the only >> where else having double values means you got closer to the concept because the repetition code >> all I'm saying is like CXA is I don't I don't have the same

notation If alpha is zero, then cm max equals z because there are two zeros. >> If alpha is not zero, then we don't we don't zero. >> Yeah. If alpha is zero, c max is zero. >> No, no, not >> Oh, sorry, sure, sure. Yeah. So, if al cm max is two, otherwise it's one. No, I said just like so yeah, you're right that like this isn't technically the the sort of bound we showed is technically like one minus one uh like to the this is where like the

the n + one plus row to the n where I should use n here I guess like n r and n where this is the number of queries and this is the number of rounds. I think this is this is what the right the right bound for the toy. Yeah. >> This this is the bit about like having to do each round separately, right? Yeah, I think

>> you want to level And I think that