zkStudyClub - IOPs with Inverse Polynomial Soundness Error (Gal Arnon - Weizmann Institute)

Transcript

Hey guys. Hey guys. How's it going? Hey. Uh hey Elon, how's it going? All right. Uh sorry, can you guys can you guys hear me? Uh I can hear you. Okay great. you. Hi. Sorry, I uh my Zoom subscription expired, so it was only going to be an hour, so I had to like re-update it and it took a second. So, sorry for the slow for it's usually I Yeah, usually we start 15 minutes before for an AV check, but no worries.

Um good to go. I'll update the Luma and I'll put this in the chat. Um Uh Gal, do you want to uh uh present your slides? Just make sure all the AV works and everything as far as Yeah, if you're planning to present slides. Um you don't have to, but if you're Yeah, uh I am I you need to uh allow me to present slides. I always forget this part. I have permission. Sorry. Yeah. Yeah, one second. All right. Okay, try now. Okay.

And you can hear me fine, right? Cuz I had problems with my microphone before. Yeah, I can I can hear you. Elon, can you hear Gal? Yeah, I can hear you guys. You should update the Luma. Yes, I will update the Luma right now. I just wanted to make sure we had you guys all set and I'll post the link in the group as well. Okay. Great. Can you see the slides? Everything? Uh I can see, yep. Looks great. Yeah. Okay. Great. Yeah. Thank thanks, Alex. Thanks. Yeah, that's right. Sorry for the sorry for the delay here. Uh looks like we have nine uh we have nine uh people who registered and uh we'll probably have a couple more people end up uh kind of filtering in, too. So, this will be good. Uh one second here.

Let me just update this with the link. Okay. And yeah, so Elon, you should have gotten an email now uh with the updated link and I will put it in the CK Study Club channel. Do this right now.

All right. Great. So, we'll give it a couple minutes here. My experience in the past with this is that the first 10 or so minutes, people will filter in. Um and then uh we get started maybe 5 to 10 past depending on when we have kind of a quorum. And we'll let you present this work. Gal, it's it's up to you if you want to um if you want to take questions throughout, if you prefer to wait till the end, it's it's totally up to you. By the way, is Gal or Gal? Like what's the right way to say it?

It's Gal. Gal okay cool. Which is sort of in the middle, yeah. Just wanted to make sure I'm you know, I'm going to I'm going to American English speaker, which means I mispronounce almost everybody's names. So uh but I I for the purposes of the video or for the recording, I wanted to make sure I I do it right. And by the way, we are currently just so you guys know, we're already recording. Um I'll just edit out all this beginning and then we'll we'll start at the we'll start right basically like when I introduce you. And Elon, and is it Elon is the right way? Yeah, that's close enough. That's fine.

Like even people in Israel have a problem with my name, so like uh All right. I'm sure you're just making me feel better with that comment, but if you have a problem with Elon, then I just let me know now, but otherwise I'll just Gal and Elon, you know, cuz you guys are the co-authors. Um Yeah. and Alessandro. So I'll introduce you the way it will work is I'll introduce you guys in the at the beginning. I'll then I'll let you read the title and you can jump into it. And then you can just let the audience know if questions if you want to take questions at the beginning or sorry, throughout or at the end. And then I will I don't know if you have two screens or not, Gal, but I if not, then I can read um I can read from the chat as

as questions come in. Uh yeah, I I I only have one screen here. Okay, great. So I if I get if you want well, maybe just tell me now. If a question comes in the chat, do you want me to interrupt you at like I won't interrupt you in the middle of your sentence, but like at the next pause, or do you want to just wait and hold all those at the end? No, I prefer to to have questions in the middle, so if people aren't understanding then I can react to that. And Elon, also feel free to butt in as well, if you want. Yeah, I think questions are welcome and even if people just unmute themselves, that's the best.

Great. Um Yeah, I don't I don't mind if people are unmuted. Okay great. Let me just uh say one thing before uh people join and we start. Uh there is uh a non-negligible probability that there will be sirens here, where in Israel located. Uh in that case, I guess me and Guy will go. And we will come back like in 4 minutes. So, just uh maybe be patient if that happens. I hope it won't happen in the next hour.

Yeah, definitely. Well, I was actually just about to ask how you both are doing. I was assuming you both were in Israel currently, and um you know, thoughts and prayers with for you and your families during this time. Uh yeah, we're fine, we're safe, but it's a you know, complicated situation and uh Yes. Hope uh we'll see peace uh soon. Yes, I think I think I think we all we all feel that way. Um having spent personally some time in the Middle East with rockets over my head, I also wish that that you don't have to experience that for too much longer.

So. Yeah. Uh cool. So, we'll let people filter in here. We've got actually a pretty good group already. I'm just going to get a glass of water personally, and then I think probably in the next 1 to 2 minutes we can just get started. Uh so, Elon, as you pointed out, if there's any kind of interruption, um we'll just plan on what we'll give it uh what do you think what is a reasonable interval to for you that for you guys? Um would it say 10 to 15 Let's say 15 minutes. I'll just put everyone on break for 15 minutes, and we'll plan on doing think 15 is too much. I think between 5 and 10 is uh Okay.

Yeah. It It is fine. Yeah, so uh So, we'll make the plan a 10-minute We'll call We'll just say 10 minutes we'll resume and then if whatever reason exceeds 10 minutes, we'll reschedule and finish the talk at like next week or at a better at a different time. And uh so that way you guys can complete the talk and we'll continue the discussion, but that way you guys have the opportunity obviously to get to shelter if you need to. Yeah, that sounds good. Sound good? Okay, great. Um okay. Uh let me just get a get a drink of water and then I think we can just kick off.

Yeah, I'll get some water as well. All right. Um okay, so like I said,

we're already recording here. Um and so I'm just going to We'll just take a quick pause and I'm going to just introduce you guys. Uh I'll introduce both of you. Uh Gal, I know you're presenting, but I'll introduce both of you since you're both co-authors. And then it will be off to it. So, Welcome everyone back to another edition of ZK Study Club. This week we're very excited to have Gal and Ilan, uh co-authors on this paper the title which you see here. Uh and they're going to be presenting this work today. Uh also a co-author who's not here is Alessandro Chiesa who's been a guest here before. Uh but with that, welcome Guy and uh and Elan.

We look forward to hearing uh more about this topic. Um please take it away. Okay. Thanks for having us here. Uh so, I'll be talking about IOPs with uh oops, sorry. IOPs with inverse polynomial soundness error. And uh as Alex mentioned, this is joint work with uh Ale and with Elan. So, hopefully uh everyone here knows what PCPs are, but I will just reiterate. Uh we have a verifier that wants to know the validity of some statement uh here modeled as uh X belonging to some language, and a prover that uh you know, knows the answer and wants to prove it to the verifier. Sends some uh very long message, a possibly long message, and the verifier uh reads a few symbols from

this message and should be convinced whether the statement is true or false. A uh generalization of this uh PCP system are are IOPs, uh which are just the interactive generalizations. So, the verifier and the prover have some longer conversation, which the verifier sends a message, then the prover answers with a PCP-like message, and so on. And at the end, the verifier reads a few symbols from each one of the prover's messages and decides whether to accept or reject based on that. Uh oh, I should have mentioned at the beginning of my talk, uh anyone feel free to stop me at any moment with questions. Uh just unmute and talk or write in the chat. Uh

both are fine for me. Okay. So, that's uh IOPs. Uh so, why are we interested in IOPs? Well, I guess I don't need to talk about this too much in this forum, uh but they're interesting uh both in theory and in practice. Uh in in theory, uh they're uh uh an interesting uh abstraction layer um for a lot of like uh theoretical cryptography and also practical cryptography. They've been used in theory for delegation of computation for hardness of approximation. And in practice, they're used to uh handle the validity of transactions of worth, you know,

billions of dollars. They're they're very important both in theory and in practice. Uh so, that's just because I'm going to talk about a lot about these objects, I'll just go over all of the parameters that we care about for interactive Oracle proofs, IOPs. So, the main parameters are the number of rounds, which is the main difference between PCPs, cuz PCPs have only one round or no rounds, depending on how you want to define it. Uh the length, which is the number of symbols in the proof, the alphabet size, which is the uh the the size of the proof alphabet, so every symbol has some uh

has some size. The number of queries read by the verifier and the soundness error, uh the probability of accepting a false statement. Okay. So, I'm going to go quickly about some of the known landscape for results on PCPs and IOPs. This is very partial, but it's what's more relevant to this paper. So, the first thing I want to talk about is the amazing PCP theorem, which is the first uh I don't know if it's the first, but it's like a very big and important theorem saying that NP has a PCP with polynomial length,

constant alphabet size, the constant the verifier makes a constant number of queries, and the soundness error is some constant, say 1 1/2. So, this is an amazing theory, but there are still things that that could improve. The first thing that we could improve from this these parameters is the proof length. We we want a linear length PCP if possible. So that means that this uh uh poly enters into O of n.

And the rest of the parameters are the same. And while we don't know how to do this for PCPs, we do know how to do it for IOPs. One of the main benefits of IOPs are are improving the length of PCPs. The best PCP that we know is quasi-linear. So we're actually quite close in some sense for PCPs in in this problem. Another problem that I Another thing that we could want to improve uh on the PCP theorem is this soundness error. So in in real-world scenarios, we don't want constant soundness error. We don't want the the verifier to accept a false statement with 1/2 probability.

That that doesn't uh That wouldn't satisfy any customers. It wouldn't satisfy anyone. So uh we want to improve that. One way of doing it is taking the PCP theorem and amplifying. Uh here uh I'm talking about soundness error that's inverse polynomial, which is a very interesting uh parameter regime which So uh this is going to be the parameter regime that we're going to care about. Uh once if you want some other uh security parameter, you can take this and keep amplifying to some you know 2 to the minus lambda. But so if you take the PCP theorem and you amplify, that is you repeat the the PCP logarithmic number of times,

you'll get uh the soundness error that we want, so inverse polynomial, but you'll get uh logarithmic number of queries. And that's very costly for us, especially when thinking of how we take these PCPs or IOPs and uh uh transform them into real-world systems into SNORGs and SNARKs. Uh these this is uh very inefficient. And uh it's conjectured uh that we can actually get this by instead of having a logarithmic number of queries having a polynomial size alphabet but still constant number of queries.

So, we're reading more symbols. We're reading basically log n symbols uh like bits, sorry, uh for every every query that we make, but these are grouped together rather than in the amplified PCP theorem where they can be scattered apart. And this is uh way more efficient when we try to compile this into into a SNARK. And also Okay. Can I ask a question about the soundness uh um so it says one over n uh um usually I'd expect um SNARK uh 2 to the minus lambda for a separate security prop um parameter lambda.

Um what's the relation between those two? Uh sorry, what do you mean? So so um what why does it say one over n instead of um 2 to the minus lambda for some separate security parameter? Oh, so so here I'm I'm talking about getting one over n and then if you want something better than that, you could uh keep you could improve it. Uh so specifically uh for the sliding scale you wouldn't uh expect for this this uh sliding scale conjecture, you wouldn't expect to get better I guess in both cases uh for uh lambda, you'd have you might have some

dependency on lambda. This this would be the best dependency on n that we can have. I see. Um Yeah, so so this is this would be the best that we could sort of best we could hope for and then beyond that, yes, of course, you would you need some uh further amplification if you want negligible soundness error. But this would still be more efficient than taking uh the PCP theorem and then doing that. So, the sliding scale conjecture, as you can see by this uh question mark, is unknown both for PCPs and IOPs. It's uh very it's very important, like I said, in in for practice, but also for theory.

Uh if we get the sliding scale conjecture for PCPs, this has a lot of uh theoretical uh um this will give us a lot of theoretical results about hardness of approximation mostly. And also for uh if we get the sliding scale conjecture for IOPs, then uh by a previous paper of uh mine Elan and uh uh Sandro and the May, uh we know that uh this would imply uh uh with certain parameters, an IOP with these parameters with certain number of rounds, sorry. An IOP with these parameters would also imply the PCP theorem, so the the PCP style sliding scale conjecture, sorry.

Um and so this would also be a very important theoretical result. So, both for PCPs and IOPs, it's very interesting. And the best PCP that we know, or the best that we know uh before this work, is uh by uh Dinur, Harsha, and Kindler, who get the 1 over n soundness error, but they have a poly log log n uh query complexity. So, they don't, you know, it's it seems quite close, but the the gap is actually quite big between this poly log log n and O of 1.

Uh before I go to our result, are there any questions about this uh, this table? Okay. So, our result is uh, an IOP that uh, uh, is basically the best uh, uh, beats uh, sorry. Beats uh uh DHK and is uh, yeah, so I'll just go over it. Uh, so we show that IOPs are beneficial for high soundness and small query complexity. Specifically, we show that every language in NP has an IOP with the soundness that we wanted 1/n and has both round complexity and query complexity log log n or O(log log n).

So, before we had a poly log log n or if we just took the PCP theorem, just uh, uh, log n uh, and we get log log n. Uh, more specifically, if we look at R1CS, uh, then we can have a slightly better trade-off between the soundness, the alphabet size, and the proof length. So, before we I just wrote, you know, general poly n here, but we actually get something that's uh, relatively short as well. Uh, we not super short. Uh, we we we want we wish we could have We hope to improve that, but uh, it's also quite short.

Uh, are there any questions about the these main results? Okay. So, the main uh, tool to the underlying our result is a new test for Reed-Solomon codes. So, first of all, what is uh, Reed-Solomon code? Uh, so Reed-Solomon code with some field F, some evaluation domain L, and degree D are all of the functions from L to D such that there exists some polynomial of degree at most sorry L to F.

That there exists a polynomial of degree at most D that agrees with the function on every point. So, it's basically the evaluation of polynomials over this evaluation domain L of degree D polynomials degree at most D polynomials over L. The rate of this code is which we'll denote by row is D plus one over the size of the evaluation domain. And uh we were uh in a uh test for a proximity test for a Reed-Solomon code we have some function in the sky F that maps from L to

to the side to the field. And we want to know whether it's actually a codeword or something that's relatively far from a codeword. So, delta far from a codeword. Uh and the way that the approver is going to prove to the verifier this is using basically an IOP. So, they have some interaction between each other. The verifier is going to read some symbols from the approver's messages and read some symbols from the the function in the sky and decide whether it's an actual it's convinced that it's a codeword or you know, if it rejects and we require that uh

if it's very far from a codeword then it should reject with some high probability. Yeah, this is what I said. If F is delta far from the Reed-Solomon code then the verifier should accept with probability roughly proportional to delta to one minus delta. Uh because if we only change one symbol from F from being a a real codeword then the verifier is very unlikely to see this, so we we can't expect to get very good uh um to the verifier to reject with high probability.

So, what is known for uh these kinds of proximity tests, uh well, first of all, there's a very long line of work uh on trying to do this with PCPs. Uh I'm not going to cite all of them because there's really a lot of things. Uh altogether, they achieve uh uh quasi-linear length, a constant query complexity, but they have uh constant soundness error. Uh so, it only works if uh delta if delta is uh if the codeword is very far from uh low degree, which by by far from low degree, I mean far from the uh Reed-Solomon code, then uh this it still accepts with some

constant probability. It's not going to be sufficient for us. For IOPs, we know uh something a lot better. So, the uh most famous protocol uh by now is uh FRI. Uh FRI has linear length, has uh log D queries and log D rounds, and the soundness error scales roughly with uh 1 - delta plus some uh parameters that depend on the rate and on uh some small error.

Uh and uh our new uh uh proximity test for Reed-Solomon codes has uh slightly longer length than uh than FRI, but has log log D query complexity and round complexity. The soundness error is also uh very similar. Uh this uh 1 over 4 parameter in the rate rather than 1 over 2 here, uh we can get rid of that. Uh we know by now how to get rid of that. So, you can just think of them as basically having the same soundness error.

I'll just say a small comment in Fry, usually we think of the conjectured regime of parameters. And if you assume this conjecture, then the square root row in Fry is just square root is just row. And this is the same case in our result. Yeah, I I I'll reiterate what Elan said. For Fry, usually we think of a conjecture which says that this error is actually 1 minus delta plus row plus some epsilon zero.

Uh this what I wrote here is with square root row is what we can probably show. And the same goes for us. We have a very similar conjecture to theirs, basically the same thing, uh allows us to get to uh 1 minus delta plus row. Are there any questions? Okay. Uh so, our protocol at a very high level has two different parts. Uh polynomial IOP for low degree testing and a compiler that takes polynomial IOPs and low degree tests and outputs uh proper IOP.

So, first of all, what are polynomial IOPs? Uh I'm guessing that everyone here knows, but I will uh tell you again. So, a poly- a polynomial IOP is a restricted form of IOP, restricted for the prover because all that it can do is send actual polynomials of degree at most some parameter D. So, every one of the prover's messages is promised to be a proper polynomial uh uh over the entire field. Uh then the verifier can query this polynomial at these polynomials at whatever points it wants.

Uh So, that's a polynomial IOP. And uh what we do is we build our low degree test in a recursive manner. First of all, we we build a polynomial IOP uh that checks proximity uh for degree D polynomials. So, it's a proximity test in the polynomial IOP model. In this polynomial IOP model, the prover is only allowed to send polynomials of degree at most square root D. So uh it sent the prover sends polynomials of degree square root D, but somehow you're verifying a polynomial of degree D.

We take this with a low degree test that works for square root D for polynomials of degree square root D. The compiler takes these two things together and outputs a low degree test for degree D. So, just to reiterate, we take a polynomial IOP where the prover uses uh degree square root D uh polynomials that allows for checking polynomials of degree D. We take it with a uh low degree test for square root D, and we compile them together to get uh to D.

Uh and so, we start with some arbitrary small uh small value. Let's take two in this uh example. So, we have a trivial uh uh test for constant for some for constant degrees. And we uh this will be this. Uh and then we compile this over and over again, growing the degree every time until we get to D. And because we square it every time, this takes log log D steps. So, each each one of these compilation steps is actually going to be some constant number of rounds and some constant queries. And overall, we're going to get uh log log D.

Uh so I will say just a few words about the compiler. We build a compiler for high soundness compiler for polynomial IOPs. Uh it takes a polynomial IOP where the prover uses degree D. Uh before this was square root D. Uh here this is more general so just uh D. Uh low degree a low degree test for degree D and the some rate parameter row for the the rate that the compiler is going to use. And outputs a standard IOP for the same relation that the polynomial IOP was for.

And importantly we wanted to preserve high soundness. Uh so if the so our compiler has uh the property that if uh the polynomial IOP has some soundness error beta, usually polynomial IOPs have very good soundness error since you can the the prover has uh way less uh things that it could do. So we can think of this beta as something very small. And the low degree test has some soundness error epsilon of delta where delta is the the distance that uh that is promised.

Uh that the um that we have to decide whether either the the um function is a codeword or it's delta far from a codeword. And the compiler outputs an IOP with uh soundness error that's the maximum between this beta which like I said was we think of as very small. And the error of the low degree test when applied to some just think of this as very large distance. It's very close to one depending on the on the rate. Plus some small soundness error but some small error.

Uh and this is this is important because of our uh the recursive way that we work. We have to keep the soundness error very high all the time. Uh so the previous uh uh polynomial IOP plus uh low degree test compiler is achieved constant soundness error. Uh and uh So you would have something like epsilon of some constant here. Uh And also importantly because of this uh recursive construction that we have, the compiler invokes the low degree test only once. So remember we built the low degree test using the compiler and low degree test in previous round. So we

can't have many calls to the low degree test because that would blow up very quickly. So we have to have only one call as well. And uh one comment under the conjecture of FRI, then this would be epsilon of distance 1 minus rho and not square root of Yes. Yes. Or very close to minus 1 minus rho. Yeah. Yeah. 1 minus rho plus some very small value. Yeah. Is it exactly the same conjecture that's used in FRI or is it just a similar conjecture?

Um I think it's very similar. I I'm I'm not sure if it's exactly the same one. I have to think about that. Uh Ilan, are you are you Uh We we can come back to this. Uh I I I think it's uh very it's very at least very similar. Okay. Basically it's basically going to be the same but I Uh Yeah, I I guess that uh I Uh yeah. So Gal will soon get to this proximity gaps and and stuff like that.

And we use like a we prove like a stronger version of of what's known about the proximity gaps. And so then if you have the conjecture, oh you need a stronger version also to this conjecture. I I will also Sorry. Yeah so currently I I I don't think it's like exactly the same conjecture. Okay? But I think soon we'll be able to prove that like these two things are if and only if. Okay, thank you. I will also mention that Sorry. I will also mention that in this paper the we don't have this conjecture. This is what this

improvement with the conjecture is is something in uh things we're working on now. So uh if you look at the paper, it's it's not going to appear anywhere. Understood. Uh someone raised their hand before, I think. Uh Okay, maybe it was a mistake. So I'll keep going. Uh okay, so I have this picture of how how we can construct our low degree test. And in this talk I'm going to only mention only talk about how we uh build this uh polynomial IOP uh for testing degree D polynomials.

Uh All right. Sorry. Yes. Uh okay, so remember we have this function uh mapping from the evaluation domain L to the field. And we want uh that if F is uh not too far from the um the Reed-Solomon code, then the verifier should accept with probability roughly uh 1 minus delta. Uh so uh if we have if the delta is small, then should still accept with relatively high probability. But what's more interesting is if delta is large, then we should the verifier should accept with very small probability. If delta is something like 1 minus uh 1 over n, the verifier should accept with probability roughly 1 over n.

So, uh let's have we're going to have some assumptions on this evaluation domain. Uh I will mention that these are very this is similar to the assumption that Frey uses. So, we're going to assume that the evaluation domain is a multiplicative subgroup of F star uh whose order is divisible by some M which you can think of M is roughly uh square root of T. So, in general I will be omitting a lot of like floors, ceilings, plus minus ones. Uh I they're just they just overcomplicate everything. So, M is roughly square root of T. So, things don't work out exactly, that's why because I'm just omitting

things. Uh and the full protocol actually works when the evaluation domain is anything as long as F star contains a subgroup of the similar order, but here we're for simplicity we're just assuming that uh L has this L has this multiplicative subgroup. Uh So, we're going to partition the evaluation domain L uh using some a polynomial G. Uh in general I will use hat to denote polynomials. So, G hat is a polynomial uh So, G hat of X is equal to X to the power of M.

And why do I say this partitions? So, we can think of uh all of the outputs of this uh polynomial when given values from L. And uh then think of all of the values that map to each one of these. And because of this multiplicative structure that we have and because uh they uh the the subgroup uh its order is divisible by M uh this partitions L into uh Sorry. Uh partitions L uh into uh L over square root D or L over M

uh different parts which are all all have the same size. I wrote I wrote here square root D again. It's it's actually a sort of M, I think. Uh So, we're partitioning it. I I haven't explained why yet. Uh So, now for the why. Uh we're going to use this fact uh that was uh at least in this context shown by uh Vencislav Sudan. And is this false? Let's let's take some uh univariate polynomial F hat. Then there exists a unique bivariate polynomial Q hat.

Uh Sorry. There exists a unique bivariate polynomial Q hat whose degree in its first value uh variable is uh the degree of F over the degree of G. And the degree in the second variable is at most the degree of G such that basically uh Q hat encodes uh F in some of its locations. Specifically, Q hat of G hat of Z, {comma} Z is equal to F F of Z for every Z.

Uh sorry, for every Z in this uh evaluation domain. So, uh in the evaluation domain in this specific uh structure uh Q hat encodes F hat. And importantly again, Q hat has degrees that are relatively small. Specifically, in our case, because G hat has uh degree M, which is roughly square root D. Uh These uh the the um degree both on the uh X variable and on the Y variable of Q is going to be roughly square root D.

So, we're we have uh we turned a took a univariate polynomial of degree D and returned it into a bivariate polynomial with degree square root D in both sides. In both side dimensions. Uh the converse is also true. So uh for every Q hat with uh the right uh individual degrees if uh Q hat is uh uh Q hat has this uh um encodes in this way Q hat of So Q hat of G of Z {comma} Z is delta far from F of Z on on the evaluation domain,

then this means that F is delta far from a degree D. Uh yeah. So now I I wrote I wrote all of things and it's very possibly very unclear. So I have a pictorial uh a picture of this. So we take F and we map it to Q hat. Every one of these uh these partitions that we had turns into a row of Q hat because these are exactly the rows are exactly uh Q of I {comma} X.

Right, it it was uh G of X {comma} X. So now it's uh whatever value I is the row. So we think about these uh partition partition parts as being in different rows. And uh the row degree of Q is square root D and the column degree is also roughly square is also square root D. So now that we have this uh mapping uh what can we do? Well, let's assume for a moment that somehow we can send bivariate polynomials of degree square root D in in uh individual degrees square root D.

Uh well, th- this is then it's actually quite easy to uh to test whether F is close or far from low degree. The prover will just will send this polynomial this bivariate polynomial which is supposed to have this property this this mapping. And uh the verifier will choose a random location and check whether uh it agrees with this polynomial agrees with F. The function that we're trying to test. Uh and for convenience for later, whoops sorry.

Convenience for later, uh notice that choosing a random value in L, which is this whole thing, and then uh it is is equivalent to sampling a row and then sampling a column that is relevant to that part of the row. So, which is this? Uh sample a row from S. S is the list of the rows. And then sample from LI, which is whatever maps to this row I. So, for convenience I'm going to switch this.

But it's exactly the same thing. Uh again, I don't know yet how we sample we send sorry Q hat, but let's let's run with it for now. So, why does this work? Well, suppose that F is delta far from a Reed-Solomon codeword. Then by the previous claim that we had we had in the previous slide, uh for every uh bivariate polynomial Q hat, F is delta far from Q hat uh of uh uh Q hat of X, X evaluated on L.

And so, because it's delta far, and the verifier is going to sample one of the locations in which it's different with uh probability delta. And so, the verifier accepts with probability at most 1 minus delta. So, if we could send this bivariate Q hat, we would be done, basically. This protocol would work. And the problem is how how do we do this? We can't just send this. Remember, we are in the polynomial IOP model. So, this means that the prover is allowed to send uh or actually has to send uh polynomials of degree square root D.

But it these are univariate polynomials. And here we wanted to send a bivariate polynomial. So, it's not clear how to do that. And this is what we're going to do now. So um we're what we want to do now is to show how we can send Q hat or approximately send Q hat. It's not going to be precisely uh committing to Q hat. So, uh we have this uh uh and we have the power to send uh univariate polynomials of degree square root D.

Uh and uh we have this uh bivariate thing which is supposed to have both its rows are supposed to be of degree square root D and its columns are supposed to be of degree square root D. So, we might as well utilize this fact and uh send the rows at least. At least send something that we can do. So, we'll have the prover send each one of the rows as a polynomial. So, remember the row is supposed to be uh Q of I, X. So, it's a This is supposed to be a polynomial of degree square root D. So, the the prover can actually the honest prover can send this.

So, we'll have the prover just send all of these. Okay. Uh uh uh we have to we wanted a bivariate polynomial. So, we have to test that these rows are actually consistent with some bivariate polynomial of individual degree square root D. We know that the rows of whatever I sent are degree square root D because we're in a polynomial IOP model. But, what about the columns? What about, you know, looking at the rows uh one after the other at the same location, why should this be the evaluation of degree square root D polynomial? And it should be that if uh if Q hat was actually uh bivariate

bivariate low degree. So, our goal is to test that these columns are actually uh low degree. So, the the first thing uh I would I would do, I think the natural thing to do, is to choose a random column and try to test that it is actually of degree at most square root D, right? Because I I wanted to test that these columns are these columns have some property, might as well choose one and test this property. Okay. So, how do we test this property? Well, first of all, let's sample a column at random. So, CJ.

And we want to test that it's uh low degree, that is has degree at most uh square root D. And actually uh in you know, this sort of seems um like you know, we want to test something that something is low degree, and so now I sort of reduced it to testing that something is low degree, it doesn't seem to make sense. But, the point is that CJ uh is supposed to have degree at most square root D. And because we're in the polynomial IOP model, we actually quite easy to test uh um distance from square root D.

We have the prover send a polynomial that is supposed to just be the polynomial extension of uh uh CJ. It's just supposed to be the polynomial that agrees with CJ on all all locations. And then uh if CJ is actually close to a low degree polynomial, it should there should be some V hat. So, the verifier can can sample a random location and just check whether V hat agrees with the column, which just means checking the the row at the right place.

So, we just have the prover send a polynomial. And then we compare the column with the polynomial on a random location. So, if this column is close to low degree, if the degree is with most of the points, then this should test should pass with high probability or if conversely if this was very far from low degree, then this test passes with very low probability because there is no degree square root degree polynomial on which it agrees with a lot of points.

Okay great. So, we've we've we've figured out how to do this test. But the question is does this actually suffice? Is this enough? So, Polishchuk and Spielman showed in the 90s that if the verifier accepts basically this test, they showed slightly different test, but it is implied from theirs that this would work. If the verifier accepts with some constant probability, some actually quite large constant to like 9/10 or something like that, then there there actually is a low degree bivariate polynomial Q hat such that these rows are constant close to

like they they describe a bivariate polynomial that is constant close to this low degree Q hat. So, that would mean that, you know, we actually the prover actually sent something that is, a constant close. But we wanted uh uh uh we wanted high soundness. We wanted the verifier we don't want uh the verifier to accept with constant probability. We want the verifier to scale with the distance, basically. So, it's actually still open whether this in this test if the verifier accepts with probability 1 minus delta for some uh some other delta, say

uh 1 over n, is it true that the rows are you know 1 over n close to uh to Q hat? And we don't know. Um we we worked quite hard on trying to figure this out and we couldn't. Uh so, we have to find some other way to to get around this. Uh and it would be very interesting to solve this open problem and that would uh possibly simplify the protocol. Uh so, the idea to solve this is to somehow test all of the columns at once.

Cuz the the the way that the reason that the uh Polish experiment uh doesn't work is that you're sort of limited to only one, you try to reconstruct things and it it just fails. So, if you try to test all the columns at once, this should, you know, be much stronger. Uh but the question is yeah, how how are we going to test that a lot of columns are low degree at the same time? Uh this seems very inefficient. And this brings me to an interlude about uh proximity gaps.

So, we have a bunch of uh think of these as as the columns, but if a bunch of uh claimed codewords of uh Reed-Solomon code, and uh we're going to take a random linear combination of them. So, we're going to choose some alpha j's and uh generate some C star, which is the random linear combination of the the C J's. with alpha J C J. Okay. Uh Why does this help us? Well, there's a nice theorem that says that uh if the probability that C star, this random linear combination, is close to Reed-Solomon codeword

to a Reed-Solomon codeword is uh with high prob- with you know, with some relatively small probability sorry. Uh then actually all of the C J's are close to Reed-Solomon codewords. So, what this says is that, you know, if C star is close to Reed-Solomon codeword on, you know, say these three green locations, then there are three green locations for every codeword. They're all actually close to low degree. And this tells us that in order to batch test uh C1 to CL, these columns, we can actually just test C star. We don't have to test all of them.

Uh and actually the theorem that the the authors here showed is much stronger than what I just presented. They show that C1 to CL have uh correlated agreement. Which means that the picture is actually not like this. The picture is like this, where all of the codewords have this the agreement points are on the same location. So, uh C1 to CL, they all agree and the the in this example on the last three locations, uh but notice that I uh drew it the way the way I drew it, C star has its three locations somewhere here at the top, and these

have their location at the bottom. Uh and this is actually uh uh a gap in in their the this theorem. This theorem actually this is what they show. Uh and you can conjecture uh that we conjecture that uh their picture shouldn't actually be like this. It should be like this. So, the correlated agreement should also include C*. And if C* has uh is close on these three locations, then they should all be close on the these same locations. So, they should all agree with each other.

And this is uh uh So we this seems very natural. It doesn't come out precisely from the the at least not from the theorem. Uh it probably does from the proof, but uh this uh it would be nice to to actually prove this conjecture. Uh and in this talk I'm going to use this conjecture. But uh in the actual uh paper we bypass this conjecture by proving a weaker lemma that suffices for us.

So, uh again, what is the conjecture? I'm saying take a random linear combination and then test that it's close to low degree. And in the same points where it's actually close to low degree, then uh the uh the columns are the codewords that we summed together are close on these exact locations. Uh Galen, stop you for a second. There's a question in the chat. Uh do you run uh Matias asks, do you run batch fry on multiple columns? Uh so, I think you're about to answer this. Uh I'll just say that we don't run fry cuz fry is too expensive. So, we cannot run fry any like we're doing something more

efficiently, right? We do batch these columns together, but God is going to present what is the problem with uh batching them uh in a second. And just a second comment, that this conjecture is just for ease of this talk, like in the paper we don't use this conjecture, and it has and it's related but has nothing to do with the conjecture on the parameters that you can get up to row and not square root row. Yeah. Okay. So, that's like a conjecture of, you know, of list decoding, how how how close can you get to the to the rate. Uh but because we need this exactly slightly stronger version that they didn't explicitly prove in the in the paper, so like now we have a two conjectures uh for the parameters.

Uh we did open up the proof. It looks like you can prove this. It just, you know, uh you know, it it takes a lot of time, and eventually we just changed the protocol to get around this. Okay, but for this talk it's it's much easier to just assume that this is true. Yeah, for for this talk just assume it's true. And like Elan said, the it seems by going over the proof uh of this paper that it should be true, but uh proving it is uh this this is a very complicated messy paper, so proving it was uh it seemed like a lot of work, so we managed to get around that.

Okay so oops. Yes. Okay. So, now that we know that we can if we we batch test we can batch test all of the columns by testing the random linear combination, uh let's try to do that. So, the verifier will choose coefficients. Uh and this uh now that we have the coefficients, then this uh C star is just well defined by the sum the random linear sum of these uh uh of the columns. And now we want to test that C star is uh low degree, and this goes to the the question.

So, like how do we how do we test that C star is low-degree? Uh more precisely, how do we access C star, right? Cuz uh reading one location in C star, we have to read all of this sum. So, that just means uh querying the entire row uh or or every column and checking the sum. It It doesn't uh doesn't make sense. And this would have query complexity that's uh huge. Uh but you should uh but uh observe the this uh following fact. So, C star, by definition, C star at some location I is the sum over all of the columns of uh of A J C J at location I.

But what does it mean to sum all the columns? It means to sum over this this row, right? Because each of the columns at one loc- a specific location is just the row the the uh the row R at uh all of the uh each one of the column locations. Right? And this looks like the this uh row R is actually a polynomial. We know this because the the prover sent it to us and we're in the polynomial IOP model. Uh and this looks like a weighted uh polynomial sum. This looks a lot like the sum-check uh problem. So, we have we want to uh check the the sum of some polynomial over a bunch of locations.

In this case, they're weighted as well, but uh whatever. So, uh this is actually what we're going to do. So, uh we're going to use a univariate sum-check protocol. So, in in the univariate sum-check problem, we have a uh or the problem that univariate sum-check solves, we have a univariate uh polynomial uh P hat and a multiplicative subgroup uh uh L, which was exactly the case that we have here. Uh in this case P hat was our I. Uh and we have a high soundness small query polynomial IOP to prove that the sum of P hat over the evaluation domain is equal to sum uh gamma.

Uh that's what the univariate sum check uh does. Uh and uh I will very quickly uh give some hints as to how this works. It's not a protocol we invented, but uh just uh uh if people probably here most people have seen it, but uh it's surprising to people who haven't. Uh So, it uses these uh the following fact that the degree if the degree of uh a polynomial P hat is smaller than the size of the summation domain here, this L here, then uh the sum actually reduces to the location of the zero location of the polynomial times the size of the

summation domain. This is sort of because uh like you sum over roots of unity and you fold over things. And so, it just suffices to query uh P hat at zero in order to compute the sum. Uh this is if the degree is small enough. But, what happens if the degree is larger? Well, very roughly we split up the polynomial into two parts. Uh one that has small degree and the other one uh who that uh zeros out uh on uh whose sum is zero over the uh evaluation domain. Uh you can this is has something to do with the vanishing polynomial over this uh domain, but doesn't really matter. Uh

and so, then the prover can send these two polynomials and uh the verifier can can sort of check consistency. At very, very high level this is how the univariate sumcheck works. Uh and uh like I said here, uh I'm talking about regular univariate sumcheck, whereas we need a weighted version of that. Uh but minor changes can get us to uh a weighted univariate sumcheck. So, uh again, we wanted to uh te- to basically access C* at a certain location, uh say I.

And uh in order to do that, we noticed that the the C* I is just the sum of uh or weighted sum of this uh polynomial, and so we use this the univariate sumcheck in order to let the prover prove to us what the value is, rather than summing over everything. So, I hope that answers the question of uh before. Uh so, no, we we don't need to use FRI. We we use a univariate sumcheck, which is very, very efficient. Uh okay. So, uh now that we know how to access C*, uh we want to test that C* is uh low degree. So, we're going to do the same strategy that we had before. We let the uh prover send the polynomial that is

supposed to equal uh C* at all of the these locations in S. Uh so, we send V hat. The verifier samples a random row, and then checks that V hat and C* agree on this uh uh on this row, which uh again, to access C*, requires using the univariate sumcheck, and accessing V hat is this is just uh polynomial that is set by the prover. So, uh the verifier has access to that. Uh yeah.

Are there any questions about the the protocol? Okay. So, there's no more questions in the chat. So, guy, I think you can go ahead and proceed. Okay thanks. Um so, just a sketch of the analysis. So, if we look at all of the points in which C star agrees with B hat, so these are the locations in which C star is close to some specific low degree polynomial. Uh here they're marked in green. So, by this proximity gaps conjecture, uh this means that for every that for every CJ, there exists a low degree

polynomial CJ which agrees CJ hat, sorry, which agrees on this exact list of points. So, the picture is like this. So, each one of the CJs separately is close to low degree on exactly the same points that C star is. And then we do we have to do some kind of interpolation to get out of this a low degree bivariate polynomial Q hat that agrees with all of these rows that are in green. So, for every one of these rows in which C star agrees with B hat, uh this low degree bivariate polynomial with will

agree completely with the row. And so, we've managed to send Q hat at least in these locations. I don't know what happens in the rest of locations, but in the locations in which C star is close to B hat, uh this we've managed to send Q hat. Yes, that's my reason. Yeah, you got a question. Pratyush, you want to go ahead and just say your question? So, my question is could you quickly go over how you get the log log in number on the complexity of this?

Uh here it's all um So, first of all, here we're still in the polynomial IOP model. So, this is not an IOP. This is uh we're assuming that the prover can uh or has to send like actual polynomials in each one of its messages. So, this R hat is an actual polynomial, this V hat is an actual polynomial. Uh the reason that we uh we get So, here we have uh we're going to have uh constant uh query complexity. A constant number of rounds, we have four rounds uh plus uh if I go here, sorry.

Uh skipping ahead just to go back to where we were. So, we have some constant number of rounds. This is the protocol, the polynomial IOP altogether. Uh I just went back to to where we were at the start and put all this uh uh How do we send Q hat uh in in this uh box? So, hopefully that makes sense. Uh So, here we have a constant number of rounds. And the verifier only makes a constant number of queries. Uh I didn't say this maybe uh um but the univariate subject have a constant number of queries.

And uh uh But this is only one round of our recursion. So, here we're assuming that the prover sends polynomials of degree square root D. And we're showing how to uh verify polynomials of degree or that uh codewords uh that are supposed to be of degree D. And so, if we start with some constant uh say two, uh and you know, for two, you we have trivial uh low degree test. This will give us four, right? Because we have uh something for for two. And then the the low degree test for four, we can plug this in with the the new and another

polynomial IOP for uh um for 16 and for eight and so on, right? Um can I ask you a question? What what are you considering to be a unit time operation here? So if it's O uh log log D rounds um So any field operation is a unit unit time for me. Okay. Yeah, got it. Also, one quick thing here, you said the verifier uh I see that the verifier communicates in a constant number of messages, but the messages themselves the coefficients like they they kind of

do relate to like how many columns you have, perhaps, right? Because you're sending one alpha per column. So that's that doesn't seem constant, right? Or am I missing something? Uh this So this means that the verifier's running time is not going to be you know constant per per round or or or its message complexity is not going to be constant per round, but it's the number of queries that it makes is constant. Sounds good. number of symbols that it reads from the prover's messages is constant. Let me just add a small comparison to FRI. So in FRI, you go from in one like step of a recursion, you go from degree D to degree D over K.

And you can set K to be whatever you want. You can even set K to be square root D. Okay? And then in FRI, you would actually have log log D uh rounds. However, in FRI you pay a factor of K. So you'll need to read things of size K. Okay? So that's why like in practice, you can only set K to be like eight or 16 or something like that. Here, we managed to go from degree D to degree square root D and only paying like a constant. Like regardless of the Yeah, sorry. Hopefully I answered the questions that were before.

I you you answered mine, yes. Okay. Uh yeah, I think we're good to go. All right. So, uh So, again, we wanted to the prover to send over uh Q hat with this uh property. Uh and then the verifier to check Q hat at some location. And now we've shown how to in the polynomial IP model, how the prover could send or roughly send um Q hat. And this is exactly the protocol that we had before.

Uh now I added it to the picture again. So, we had this uh C star, we had this V hat, and we checked that they were um that they agreed on some points. Uh and uh So, now that now we know also that uh what the prover's going to do is send rows uh uh RI. So, when the verifier wants to uh look at Q hat at some location, it actually looks at the row, the right row at um the location uh of the column.

Uh and Okay, there is one very small problem uh with this protocol. So, so far actually I I haven't used in anything that I said, I haven't really used the conjecture. Uh I haven't used the fact that this part Yes, that this part, this green part here, is the same locations as this part here. Uh as as in in the C star area. Uh it does I haven't I have actually haven't used it. And uh uh the problem here is that what if I sample a location in this part two here?

If I sample a location that is not part of this green zone. So I wanted to compare Q hat, which is a some low degree bivariate polynomial with F. But I sampled outside of the the low degree area. The area that I could actually prove that the rows sent by the prover are, you know, agree with some bivariate polynomial. So in order to solve this problem, uh we can actually use the same I in this sub protocol as in the outside protocol. So remember I was the location that we're testing C star is close to V hat.

So now the picture actually looks like this. Cuz we're testing So now I'm using the same I here as as in here. Uh the picture is like this because uh the location if if the if the verifier accepts, then this location must uh must be part of this agreement domain of C star. Otherwise, the verifier would just reject, would just not agree with V hat. But because it agrees in this location, it must agree here as well. And therefore, we're actually this part in in this second part of the where the verifier checks uh agreement with F, it's actually in the area in which

whatever the prover sent agrees with a bivariate polynomial. So this is where we're using the this conjecture part uh for from the proximity gaps. Uh like I like I think Elan mentioned before uh in the paper we don't use this conjecture, but we get around it in some other some other slightly uh using some slightly weaker uh field but the conjecture we we really believe it to be true. Like, it should be true.

Um. So, uh, for the verifier track to be sound, wasn't that depending on the fact that I was chosen randomly? Uh, sorry, that J was chosen randomly. No, I think. Um. So, yes. So, it was depending on both I and J, but notice that I here is chosen randomly. This is also This is why I split it at the beginning. Right, but what easier here. What I'm getting at is that um, are we assuming that the the two choices of I are independent? Could there be some attack based on the fact that you've chosen the same I?

Uh, so, there was an attack if if if it wasn't the same I. Um. The fact that it's the same I sort of forces it the the the prover to send things that are I mean, this is part of the the the um, the soundness of security analysis. Um. Let me think. Um. Uh, okay, that's a good question. Generally, making randomness is correlated is very dangerous, okay?

Like that's Yes. Yeah. a good strategy for an attacker. Uh, no, here it's not not the case. We're um, choosing a random row, and then for this row, we're checking that, you know, the V is consistent with C star, and that this row is consistent at a random location with F. And so, you conclude that you have, you know, at least delta rows that satisfy these two properties. Okay? Like, if the verifier accepts with a, you know, some probability, then this fraction of the rows satisfies all the properties that you checked. And then from this All right, because yeah, because in in the practical protocol you'd be committing to these before choosing the random

Yeah, you're committing to everything yeah, before I exactly yeah. Yeah, and so that the the prover can't cheat by changing the thing that was committed to. Okay, good. Yeah, and then you take the rows that are close to F and close to V and you know that they they are close to F and they're close to a bivariate polynomial so you can like uh extract eventually a polynomial that is close to F from this. You extract a bivariate polynomial and then a univariate polynomial. Yeah, the the thing that was concerning me is that normally say using Fiat-Shamir then all the challenges have to be independent.

Um Uh the the Yeah, I'd Yeah, I'd I'd have to look at the proof. Okay. Uh yeah, so uh we have a a short analysis but basically it's just what Elan just said so I'm I think I'm going to skip it. Uh but it's it's basically just exactly what Elan said. If you know that the some fraction of rows has this property yeah.

Uh Now carry on. Uh Uh Just that if you have uh some delta fraction of rows if the verifier accepts with probability 1 minus delta then you know that you have a delta fraction of rows that are 1 minus delta fraction of rows that has this property that is both agrees with T uh with C star that Sorry, C star agrees with V on these locations and the uh the location agrees uh the row.

Uh so the the choice of the verifier agrees here as well. Uh And so, this means that there's a lot of rows in which you can uh F agrees with some bivariate polynomial. Uh and then you have to do some interpolation and you get uh univariate polynomial. Uh And so, you know that F is delta close to low degree. This is basically exactly what Elan said just with a bit more math. Yeah.

Yeah, you're thinking of Fiat-Shamir also like then you would need like better soundness than this protocol. You need to amplify this. This means that you choose like lambda rows and and do this, you know. I see. Yeah, that makes sense. The choice of the choice of the I1 up to I lambda, this is going to be like independent. Yeah. Got it. And you also need to prove one-round soundness and not just soundness. Yeah. Okay. Uh So this uh concludes the my talk. So, as uh to summarize, uh so we have uh high soundness IOP for NP with uh log log n rounds and log log n query complexity.

So, soundness is 1 over n and log log n rounds and query complexity. Uh we did this using a high soundness uh Reed-Solomon test. Uh and also required the development of uh high soundness polynomial IOP to IOP compiler. And uh if you think about it a little bit, you'll notice that actually what we did uh in the past few slides uh was a high soundness uh um bivariate Reed-Muller test actually. So, we actually verified uh that we can verify uh bivariate polynomials, not just univariate. So, we also get uh for free uh high soundness bivariate Reed-Muller test.

Uh for future work, uh there's a bunch of questions. so uh first of all, of course, uh what about practical implementations? This is all we did here was theoretical, so um are there could this be efficient practically? How would this compare to fry because we have significantly less rounds, but there's a lot of other things that are not efficient here. Uh what about we used uh bivariate polynomials very strongly here. What about more variables? Is that going to possibly buy us less rounds and less query complexity?

Uh there's improving this Polishuk-Spielman lemma that I mentioned earlier the the simpler test that we had uh that we didn't know how to uh you know, get something better. Uh but that would simplify this protocol. Uh and proving the proximity gaps conjecture, we don't need it for this paper, but it just seems a bit absurd that you know, that we don't have a proof for that. Like it's it seems like that should be true. Uh here I'm here in the Sorry.

I contacted authors of the the proximity gap paper. They all said that it should be true, but they're writing a proof will take a lot of time, so Yeah. I guess everybody is lazy, so Um Okay, and if anyone wants to know about how this compiler works, you you can contact me or Elan. I also have more slides about that if you know, if anyone is very interested in this specifically. Uh but yeah, that's it.

Uh and in general, I'm happy to answer any questions both now or later via email, what whatever people want. Awesome. Well, thank you Gal and Elan for for presenting this. It was really interesting uh, and sounds like a really uh, great work on the theory side and particularly hopefully will lead towards a lot of more practical uh, breakthroughs on the ZK side and and in other areas of cryptography. Um, before we conclude, I guess turn it back to the audience. Thank you for everyone who tuned in, by the way. We got a We had a few people filtering in, a few people filtering out during the course of the talk, but for those that are here, uh, do we have any remaining questions? We have a question from Prakash.

Uh, do you have a sense of how much work it would take to generalize this to multivariate polynomials? So, I guess it's actually just kind of asking about the difficulty of the second bullet for the future future work heading. Uh, so we we've thought about it a bit. Uh, we have uh, I don't think we have any good ideas yet. Um, So, so that would be um, kind of replacing square root with K's root for a K's root. And okay. That would be replacing square root with K's root. Uh, even so, on a theoretical level, replacing say, square root with 1/3 is not super interesting, but for a practical uh, case, it might be extremely interesting. So, even

improving from two to three, uh, let's square root to 1/3. Maybe I'll give a small comment about this. Yeah. So, here we go from univariate to bivariate and then back to univariate, okay? And we go from D to bivariate square root and square root and then back to univariate square root, okay? Now, suppose you go to a K-variate polynomial, then I think going from univariate to a K-variate polynomial of degree D to the 1/K, uh, I think that's like a reasonable thing, a little math, but that's not too not too bad. Then you want to go back from a K-variate polynomial to a univariate okay?

That is more challenging. It's not that it's not possible. The the the question is, what is the cost of going from a K-variate back to univariate, okay? you don't want this to be like higher cost than, you know, what you gained. Yeah, so so for example, if K was three, uh but that took more than um you know, um was it like two, three um times the effort than you it wouldn't pay off. Is that right? Yeah, so like one thing I know you can do, you can say, "Oh, let's take a let's say a three-variate polynomial and then you do some reduction, you reduce it to a bivariate polynomial, and then you reduce it to a univariate polynomial."

That would work, but then you have to compare, "Oh, why didn't I just do from univariate to bivariate, univariate, and then back to bivariate?" So I got a like a D to the 1/4 just with, you know, two rounds of this. So it's like really in the details, and yeah, I do believe that maybe for practical reasons, maybe like three variate is like, you know, a sweet trade-off. Uh I think I mean, it seems similar to the, you know, the arity of a Merkle tree. For for some hash functions, it works out as more efficient to use arity three, and so for some it doesn't.

Um so it would depend on the detail. Yeah, another I mean, it would also be interesting to directly uh I don't know, the multivariate polynomial low degree test. If uh you know, if you extend it to higher variables, I think the existing LDTs all have some shortcomings. So even even without the application to univariate polynomials, um maybe like if you can do something for like log-n variate like multilinear polynomials or something along those lines, um would that be within reach or Uh yeah, then you go to log-n, and the question is what can you do with a log-n variate polynomial.

Um so I don't know the answer of this is something we're in general looking into, but yeah, I don't have like a a good answer. Cuz you want to do something faster than log n, otherwise you would just run file. That's it. Yeah. But yeah, potentially yeah, maybe. Yeah. So I presume this gives you like a Reed-Muller approximate This would give you a Reed-Muller proximity test, right? Yes.

So currently we have just a bivariate, but we never worked on a on a general k-variate, but I believe that's possible. The question is the only like what is the payment as a function of k. Yeah. Yeah. Is this the paper about the lemma? The one I posted in the chat. Yeah, that's the Polishchuk-Zieveman lemma. Thanks. Yeah.

There's actually version of Polishchuk-Zieveman lemma for like the regimes we need here, but then they require like exponentially large fields and other stuff that are like, you know, don't make them really useful. Yeah, what what practical size of fields would you use here? Cuz I I know Fry can be used either on relatively small, say 64-bit, or large fields. Do you have any sense of which would be more efficient here?

I don't. Maybe Guy, do you have an answer? But I think this is like any Fry-friendly field should be friendly here as well. It's like the same kind of algebra that's done on the fields. Yeah, I I agree. It It It probably should be the same uh uh The errors are also relatively similar. Um I see. But again, this has no We We didn't try in this paper to look at practical implementation. So, it's very hard to to know whether things like on a practical level if they collapse if it's

better or worse than fry. I I don't know. Uh So, So, what's what's your sense of how long it will take for someone to to whether it's you or someone else to do the work of um uh solving the engineering problems? Yes, we are working on like a practical version. So, we have like a many improvements, practical like improvements. So, this paper was more or less trying to go to solve the sliding cell conjecture, which is like a long-standing open conjecture. Uh and and on the way we're like realizing that oh, this is actually like very practical.

And so, after we did that paper, we're working on like you know, a variant on this that in terms of the O notation and everything like doesn't change any of the results. But in practice like shaves off a lot of thing. Also like in this paper, the verifier runs in like polyan time. Okay, like we didn't even you know, say anything. It's just polyan time. So, of course we want to like you know, polylogan time verifier and a very efficient one. Yeah. Uh So, we have like many improvements, but it's just the beginning. I think it will take some time until we have like something ready to publish.

Okay. Yeah. I agree. Sounds very encouraging. Yeah, it Yeah, it it be great to have a people to uh yeah, take it and try to implement. Um Yeah, so so I'm assuming that like Fry, this uh if if it did result in a practical scheme, then it would be post-quantum secure. Yeah yeah. Uh yeah, this is a hash-based. So just as secure as your hash function. Yeah, it's the same as Fry.

Right. Uh internal uh the security. Yeah. And uh how much do you gain by log log log log D? You know, it's hard to say. Depends on D. Sometimes log D and log log D are roughly uh the difference between uh four and five. So uh Uh you don't always interesting. Could you switch from one strategy to another if it turned out that that the constants were such to make that a useful thing to do? Um so You can do a lot of like uh Use this for larger D and then go back to Fry.

Yeah, we were initially thinking maybe you do one round of our protocol, you reduce D to square root D, and then you just continue with Fry. Mhm. Oh, and you can do all sorts Actually, we think that the best thing is like some sort of combination of the two. Um uh but especially for large degrees uh well the trick is to gain, you know, the benefit We have the benefits of Fry already, and we have the benefits of this, and the trick is to take like both and and have something that is best. Uh but especially for large values of D, and I think D's getting larger in time, right?

Like we're seeing proofs for larger and larger computations. Uh so I think especially for large values of D, like maybe 2 to the 25, 2 to the 30, then uh you should like feel improvements of this protocol. Okay, like think of you have 2 to the 30th in one step, like you go to 2 to the 15th, which is like already quite small. Yeah. Yeah. Interesting. Yeah, and then when it's smaller the like the Merkle path is all all like, you know, you go from 2 to the 30th that has a Merkle path of length 30. In one step you go to 2 to the 15th as a Merkle path in length length 15.

Uh so the cost of the queries on the rest of the rounds are like negligible compared to the the first round. Yeah, it's it sounds as though you probably need a um at most two steps of this. Um Yeah, before it becomes very efficient. So have you looked into um like how to achieve negligible soundness error beyond just like like naive parallel repetition because that seems like it would be problematic, right?

No, so okay, so if you want negligible soundness error and yeah, you have to repeat the protocol, all right, in some way. Uh in FRI, this is very easy cuz you don't need to repeat the interaction. Like you don't do parallel repetition. You you do the interaction just once. Right. And then you just tell the verifier, oh, you know, how many like things you want to open and that amplifies the soundness. Here the situation is slightly different because we have to choose which row to continue with during the the protocol.

But if you know what soundness you want like in the beginning like and you know what soundness you want like that's the system. So you just know how many rows you want to choose. Okay? And then you take these rows and and you continue with them and you take a randomly linear combination of them and like you continue to the next uh to the next round. So uh So, in general, it's it's possible to amplify the soundness and to make this amplification like very very practical, that's not something we did in this paper and that's something you should work out in a practical scheme.

So, yeah. So, in a practical scheme, if you committed to the rows and then you're taking a um a random linear combination, then that just becomes a random linear combination of commitments. Is that right? If If you're using a homomorphic commitment scheme. Okay. Yeah, I don't know if you would get homomorphic schemes if you wanted post-quantum, then that's more challenging. All right, yeah. Yeah, that's a good point. Hm.

Yeah and also proving on the on soundness is slightly more trickier here. But, again, it's good to have trickier things in the proof and have a simpler protocol. I agree. Awesome. Uh any final questions for Galen and Alon? Okay.

Uh well, awesome. Thank you, guys. Thank you, everyone for for this great conversation. And uh thank you, Galen and Alon for presenting today. It's really great work. Thank you very much for being here and hopefully we can see you next time with for one of your future works and maybe a continuation in solving some of this these problems that you enumerate here. So, thank you very much. Thanks. Thank you. Thank