Binary Counterexamples

Transcript

Yeah. So, I guess people are maybe getting tired. The The slides going to have a lot of math. I want to do my best to show you all like say what's important, but also provide the details with some pretty diagrams. So, this is work joint with Scott, Justin, and Kai. None of them could be here today, so I'm going to give the talk. So, everyone in this room I think cares about hash based SNARKs. And the core of hash based SNARKs is the property that we know as proximity gaps.

What it does is that in the proof system, the prover is going to commit to some vectors. We don't know if those vectors are actually code words or not. And therefore, we have to test. The way we test is that we take a random linear combination of them. So, here you have F plus Z times G. F and G are the purported code words and G is a random challenge. Over the binary fields, the systems of which are implemented today, the domain the evaluation domain has to be taken to be of a particular time. And and yeah, they're additive. So, if you add

two elements of the domain, the result is still in the domain. And this enables fast additive FFTs. So, yeah. So, we focus on this core soundness analysis and that leads us to the notion of correlated agreements or the mutual kind thereof. So, we have for a single word, you can see how close it is to the code. And for two different words, you can see their correlated agreements, which are the the maximum over these two code words, where each of them can can be the same.

So, roughly it looks like this for the correlated agreements uh definition and property. You want that for any received words F and G, and for all but a small fraction, very small, hopefully, of the challenge, and for all the subset S uh of the domain, if the set S is large enough, uh T here is determined by this epsilon, um then uh the if the linear combination restricted to S is in the code, then both F and G, when restricted to the subset, is also in the code, or

rather in the uh the subset of the code that is cut out by the subset S. So, it's a little technical, uh but it is sort of the right property for the soundness analysis of many of these proof systems. Um so, when a challenge uh does not uh have this property, we call it an exceptional challenge. And the failure of MCA happens when you have some F and G such that their uh common agreement, the CA, is small, but there is a lot of exceptional challenges for which F plus uh Z times G is has much more agreement than F and G

alone. So, that's the bad event. Okay. Um in terms of prior works, I think uh Giacomo covered it quite well. Let me also just run it by very quickly. Um we know up to Johnson. This is over every field, every characteristics. Um it has been conjectured down to capacity. And we now know some uh good uh guarantees when uh either the field has large characteristic or if you pick a random evaluation domain.

Um and on the other hand, there are counterexamples. But these counterexamples are in some sense sort of in very particular cases. Um they either have the rates going to zero for for the family, or you have the gap above capacity going to zero. So, that's the prior work. And um back to binary fields, uh some of those results, they occur over binary fields, and in particular, um the the strong guarantee that Giacomo said in a prior paper uh in prior papers, only applied to

large characteristic. Uh they did not apply to find binary fields, but one could have hoped maybe we could do something to adapt the proof to the binary field setting. Right? So, maybe we can uh get the same uh the same picture over binary fields, and then we'll be very happy. Um that's the core question we set out to answer. Um and we show that actually we cannot do this. Uh binary fields uh in some sense has uh a lot of coincidences that allow for many counterexamples to arise. And we're going to show these uh the ones that we found.

Okay. So um our techniques, some of them uh follow prior works, but some are pretty new constructions. So, the first one that we show here, what we show is that uh this is near Johnson. Uh it's at rate right at Johnson. It's at rate 1/16. It holds for any additive binary domain. But, it only gives you uh quadratically many exceptional challenges.

So, in some cases, that that quadratic like if you have 128-bit field and you want 128-bit security, that can be a problem. But, if you raise it, then this doesn't really apply. Um yeah, we can also sort of generalize this a bit to have stronger counterexamples, but with a gap. Okay. The second construction is, I think, the most uh unexpected one. What it gives you is that at rate 1/4 for domains that have that is, say, a constant fraction of the base field, then you can get super polynomially many

exceptional challenge right above Johnson. So, it says that uh the proximity uh conjecture just fails utterly on this uh particular domains and rates. And finally, um the um the obstruction of the second construction is that this domain it has some um it needs to be dense within the field. We show that uh if you have arbitrary domains, you can have a different constructions that still have a lot of bad challenges.

Uh it depends on this parameter H, but if you set H be like three, four, etc., you're going to get many challenges. Uh the only downside is that it doesn't go all the way to Johnson. It only, uh, goes it's between Johnson and capacity, but it's still a fixed gap above capacity. The common starting point is an approach that's been sketched out in prior works. It's called power reduction. I'm going to show you in just a moment. And we we have formally verified all these results in Lean.

Yes. >> So, is there MCA and something together? Something similar for like, uh, list decoding as well? Or is it you focus just on MCA in this work? >> Um, so the second construction also give, uh, super polynomial list size. The first and third one I think it's not not as easy. >> I see. And do you know how the second one relates to like this BKW paper from 2006 on list decoding? Or we can talk later as well if, uh, >> Yeah. Yeah, I I think it gives stronger results. The, um, sort of the motivation, the construction have, uh, different ingredients.

>> Okay, cool. >> Yeah. Okay. So, these are the sort of asymptotic results. Uh, because of how general our domains are, we also have, uh, practical results. Or rather, we have practical obstructions to, uh, lowering the agreement threshold, so to speak. So, the most, uh, striking one with the Gold moment construction, we find out that the domain used by Binius 64, uh, you can barely go above Johnson.

This is Yeah, there's a s- special, uh, coincidence there in the sense that the domain of Binius 64, if you get a domain of size, say, less than 2 to the 32, then it belongs in the 32-bit subfield of the 128-bit field. That's the core property that we need in order to get this counter example to work. On the other hand, for LeanVM or Flock, uh the domain chosen does not have this property. It does not lie within any strict subfield.

And so, we need to use the uh decision tree construction. Uh here, you can see that the uh agreement, they sort of go closer to capacity than to Johnson. Okay. And also, I want to give more caveats that these are uh these don't really apply to the existing system. First of all, because they already have the uh they stay within Johnson. They have um rigorous bounds. And second of all, these constructions that we have we have an averaging argument, so that we show uh there exists a pair of code words. We don't show how to explicitly find those pairs.

Uh and we also don't like escalate this into an actual attack on a protocol. Yeah. >> And the total minus 29 is the soundness error. >> Yeah, this is a sound soundness error. So, very very low. Yeah. Cool. So, those are the overview. Um let me The rest will be uh on sort of explaining the constructions. And the way that we construct these is based on something called pole reduction.

What it means is that we need to find a family of a specific form. The format is as follows. You have a bunch of polynomial P's. What they have in common is they have a common high high degree parts, R. And they have varying low degree parts that we call CI. Um we want each of these PI's to have many roots in the domain. So, these polynomials become sort of the codewords that are close to the random combination.

You want these CIs to be distinct, naturally, and their degrees to be bounded. So, given this family, what we can do is that we can get set F and F and G to be of the following form. Then, we can do a sort of cancellation. So, we set the exceptional challenge to be CI at beta, where beta you just pick anything that is not in the domain. Okay. Um so, you do the cancellation to show that actually, um F plus CI G minus HI, HI is an actual polynomial.

That's going to agree on many points in the domain because this PI has many roots in the domain. Okay. So, that's the core uh core construction here. The difference uh specializations are just like, how do you choose these PIs? Okay. So, why is this a counter example? Well, you can sort of work out the arguments, but basically, uh there are two things. First of all, these ones, because of the pole, they are as far as possible from any degree K polynomial.

And second of all, it shows that uh because of the way that the cancellation work, they are their random linear combinations are close for many different uh ZI challenges. Of course, um we don't get uh this all for free. There may be collisions in these ZI. So, they they come from a family of these CI polynomials, but you evaluate them at a pole beta. And there may be many collisions. So, we also need to show that these family CI, they don't have that much collision.

If they don't have much collision, then actually we have we get many challenges. But if there are too many, then the challenge size is too small. So, once we establish all of these conditions for each of the uh construction, then we get the gap and the counterexample. Um so, let me give you a warm-up of how we can find this. So, one way to do this is to look at hyperplanes.

You have an additive domain D. It's basically like a subspace. Um and you look at all hyperplanes within the subspace. There are 2 * m - 1 of them. Uh you basically count all the affine hyperspace uh hyper-hyperplane. You you pick the the shift, which is like 0 or 1. And then you pick like which direction. And then there are n n - 1 directions. Okay. And for each of these hyperplanes, you get a polynomial CH, which is kind of like the error locator polynomial of that uh hyperplane. It vanishes on the hyperplane, so to speak.

Um and they vary. The point here is that all these there's a big degree gap, right? So, it actually fits uh the templates of power reduction. Yeah. So, so then we just pick uh we instantiate this template. And one nice thing is that there is no collision here whatsoever for these hyperplanes. Um so, they're all distinct. Um if you specialize them, you do get to Johnson. So, you have rate 1/4, Johnson is 1 1/2. Uh but the only downside is that there's linearly many challenge bad challenges, right?

You want You want to go a little bit more. So, in order to go more, you need to find a separate source of the um of the sort of like domains in which we can get to sort of the same formula. Okay? Um so, I have one slide here. Let me skip this one cuz I think it's getting long. Basically, you can do this with uh larger code dimension subspace of your domain, and that gives to you sort of a trade-off in how you can tune these things.

But I I don't want to go into details here. Um cool. Let me get to the the main construction, which is how do you uh inflate this linear to super polynomially many? And so, here we're going to work still with 1/4 rate. Uh you have a subspace. Now, you need the subspace to be uh large enough within the field that is captured by this uh condition with the parameter T. You can roughly think of T as like log of the field size.

And in the poor reduction um templates, we're going to pick some choice of R and some choice of the CI. But the more important point is where they're coming from. And turns out they're coming from quadratic functions. Uh you take a bunch of quadratic functions uh with two special properties. The first is that uh well, so first, quadratic functions corresponds to the coefficients the the matrix that defines them, right? You have these AGK that uh sort of defines the quadratic functions up to linear term.

You look at the matrix A. You're going to enforce two conditions. The first is that A has uh large enough rank or in fact rank exactly 2t, where t is this parameter that we're going to tune. And A also satisfies some equations. I'm going to show you later, uh but we call them gold moments uh equations. So, with such a determinants, we show there is a way to convert A, which is a matrix, into a polynomial on the domain that we call P.

So, for every every psi every psi corresponds to an A, and every psi also corresponds to a polynomial psi. We're also going to give uh not just P, but also the the C. And the point here is um you have all these things, and we we want to take the square roots of everything. In characteristic two, a polynomial has a square root if all of its uh powers are even. It's It's quite simple.

Um so, yeah, in in here you basically want to have the even challenge. Let me go to next slide. Yeah. So, one way to see this is in how you can determine A, and why is it that uh there's large enough number of A's. Uh essentially, you have these many uh iterations. The more t's that you have, the more that, you know, you have this fragmented picture, and the more counts that you have. Um so, this rank, it gives you the size of this set that is supposed to be sort of the set where it uh this function doesn't This quadratic

function doesn't vanish and we choose this agreement set to be closer and closer to uh, the one half Johnson bound. That's that's the the part that gives you this vanishing gap to Johnson. Yeah. So, that's the E. Um, how do you get stuff with with this E? Um, well, let's see this uh, polynomial C psi. Um, there's some this is where it starts to get technical, but basically you want this P psi to be zero on this E.

Uh, and because of the way that we choose this R, and by the way, I I think I'm not still quite sure why AI came up with this R and the C. Um, but it is sort of a lot of coincidence that somehow you have your rate which is one half and you have the original uh, subspace uh, vanishing polynomial of degree uh, N. And if you take square root, you're going to get N over two and that is rate one half.

So, for some some reason they all sort of coincide. Cool. So, you have this uh, P and you're going to need to have a polynomial H that sort of vanishes on these points that are uh, not E. Okay. And basically you you take the da da da and at the end what you have is that you need to have this uh, degree H to be uh, of a uh, of a certain kind.

This H um, is basically the um the uh, complement of this domain uh vanishing locator on the set E. And if you set this H to have the right degree, which a priori it does not have this degree, but if you do, then you get the the right counterexample. Okay. Uh right. So, now there's this whole dictionary that you can have between you have a function on on the domain with binary uh coefficients, and that can be translated to a

polynomial of the degree that corresponds to this function. So, there's two different views here. You have the domain, which you can think of as like a vector space. You you take some basis, and and that is a sort of a multivariate function. But then you have to convert that into a univariate polynomial on the same domain when interpreted in the larger like extension field. And there is a dictionary here. So, if the function is linear, then it corresponds to uh L, where L is uh it only has power of two exponents.

So, it's called linearized polynomial. Um that also corresponds to a label, uh where you basically determine this for the coefficients of the linear part in the in the L L function. Um and then you can determine sort of a bunch of relationships between these between these constructions. So, the the point here is eventually you can take uh linear combinations, you can take the products, and that gives you the way to aggregate into the quadratic function

and that gives you the function H. So, the point here is this H, it does not really have the the right degree unless you force it to. So, the way you force it to is that you have to impose some conditions on the matrix A. And these conditions are exactly the the gold moment equations I'm going to show in the next slide. Okay. So, you have the the derivative, you do some computations here and this there's the a lot of intricate math here that shows you that if you set

your equation this MK of A is equal to zero for many K, then you're going to have vanishing of both the top and the bottom coefficients of this polynomial. And when both of these vanish, then you have your degree of H prime, it's sort of have a very sharp drop. And that gives you the right degree condition that that is needed. So, yeah, this comes from a very very old paper of Robert Gold and you sort of differentiate that power function then you will get this moment equation.

Okay. All right. And then finally, you do a count. When when you do the count, you you want to show that you have your matrix A, it needs to have a certain rank and it needs to have certain vanishing equations. So, you bound it from both sides and once you bound and you work out the arithmetic, you get roughly that the domain needs to be dense within the field. Uh this is very very different from the domain of lean VM and flock where this does not apply.

So you can think of you have a 64-bit finite field but only a domain of size 2 to the 22. So there's a really really large gap here. Okay. Yeah. So this is a the construction in in a very very rushed way but I think you can find all of the details in the paper. Okay. And finally I want to show you the decision tree conjecture. This is the one that actually applies to lean VM and flock and that if you were to launch a better codes challenge for binary fields this is the one that

would go on the leaderboard. Um so here what we have is the the gap to capacity is much much smaller. We don't get all the way to Johnson not even close but we do have something that is noticeably above capacity. And the point here is the source now comes from a different different manner and call them decision trees of linear tests of these domain to the binary fields.

Uh I'll show you in the next slide what those tests look like. Uh but roughly for each decision tree you get another point in this pole reduction family. And and then you also need to bound the the collisions probability which isn't much and then you're done. So what do you do what do I mean by a decision tree? You take your domain you're going to separate it into many parts. Each test is an arbitrary linear functional.

Um so, once you separate into one, let's say with this S, then in each half you're going to test it with a different linear functional X uh X1 and Y1. And then you can continue each new part, you're going to test it with a new functional. So, in total there will be 2 to the 8 minus 1 uh tests uh where uh if your tree is of height H. And the point here is you now have have subdivided the domain into many small sets.

And you're going to take the product of the error locator polynomials corresponding to those sets. So, if you do that and you multiply all of them together, what you have is something that looks like this. So, you still have the top coefficients, you have a number of zeros. This is not too much of a gap. And then for the rest, you have your polynomial that is supposedly the product of everything. Okay.

So, that gives you almost all the way to rate 1/2. It turns out this gives you exactly 1/2 agreement, but less than 1/2 rate. And so, you can do a padding step uh with something that just vanishes on one of the small domains to get it the rate to exactly 1/2 and the agreement to be slightly more than 1/2. And the slightly more than 1/2 is what gives you the gap above capacity. Okay.

Um then you can do some the uh collision counts. The collision count turns out to not be very much. You basically preserve most of these uh original trees. They corresponds to distinct challenges and you can work out um sort of with the actual domains that people use how it's going to look like. Okay. So, um that's the end of the constructions that I I showed you and the takeaways here is that over binary fields a lot of things coincides. You have a lot of these powers of two

scenarios. You have many many things that give us a lot of ways to give these counterexamples. However, I think this in in some sense it it just means that there are things that we can potentially do in order to circumvent this. Although, I think being able to do so requires a either a vastly different analysis of existing protocols or you need to come up with new protocols all together. And of course our counterexamples here they don't cover everything.

It would be nice for us to have even better counterexamples for for the particular domains or rates that we don't cover yet. Yeah. So, you can see the paper on e-print on the complexity e-print and also the lean formalization. Thank you. >> [applause] >> Um how far away do you think the Kolmogorov complexity of the current paper is from the optimal? Like do you think there can be simplified? Do you think we are still kind of not understanding why this counterexample arises or do you think you know, this is as good as we're going to get?

>> Um yeah, I think it's it can get much better. So, the the version that we put out on ePrint is a lot better than the version that we had uh internally, you know, before we started cleaning up. Um the main thing, I think, is the connections to the um other constructions that I think coding theorists uh they may know a lot more about this than than cryptographers do. So, so that's sort of where I think we can lower the Kokuma complexity of of these proofs.

Yeah. >> Do you think that this is just a characteristic to me? Do you think that this is just a characteristic to issue or is it um could you do other similar counterexamples for like small characteristics in general? >> Yeah. Um so, some of this uh extends to small characteristic or or fixed characteristic. Uh some of it is still uh very special to binary fields. Um but but I think without the the specialness, you can still get a lot of things in fixed characteristic.

Yeah. >> Yeah, I I I kind of had the same same question of like how much is this an issue of binary fields versus an issue of additive domains? Um so, like indeed, like can is this a problem in additive domains in other characteristics? But also um if we took a multiplicative domain in the binary field, um would that be a solution or at the elliptic curve FFT domain? >> Mhm. Yeah. Um Yes, I think additive domains give you these um the locator polynomials that are linearized. That's the that I think is the main property. And additive also means you have a lot of subspaces within it uh that uh just work very nicely.

If Yeah, with multiplicative, I don't think we've looked into that yet. Um so, yeah, I I don't have any prior on that. >> Uh amazing work. I'll I'll be the first to say that this is mind-bogglingly um really amazing work. Um just a really basic question. Um I I'm trying to remember the this idea of um of a sparse domain or not. I guess the way I remember this is that by by choosing your domain to live in a smaller subfield, you can basically the twiddle factors become uh smaller um

which can make your NTT more efficient depending on how you implement your binary field. Um I guess in in CPUs, you might not really be able to exploit the smallness of the twiddle factors anyway. Um So >> Is it the the choice of domain? >> Yeah. >> The other benefit is >> Benefits somewhat marginal, but what's one thing that's nice is uh every the twiddle factors for every layer of the NTT in general change in binary fields, but with this choice of basis, they're a subset of the previous one. So you don't need to store as much data if you were

to precompute them out. >> You Yeah, it's like O of L instead of L squared or something. So um but it I I guess it is the lesson here that we should just bite the bullet and not use dense domains or something or I do you have an opinion on that? >> Oh, um no, I think the lesson here is you can use the the domain that that you're using just fine. Just don't go beyond Johnson. >> Yeah, okay. Fair enough. >> I think you get a lot of indication that you beyond Johnson for binary fields.

>> Too too sketchy to proceed. >> I I feel like there are I I said I disagree. I feel there is should must be some work around. Like, you know, in particular like even looking at the evaluation set, right? So, for this nice evaluation set, um you know, it's problematic. We know for random evaluation set, uh encoding is slow, but it's uh it's fine up to like what the exact errors are. And somehow we're hoping for a middle ground where you have good encoding and you have uh good proximity gaps.

Yeah. >> Are you You're saying that you would abandon you you would not have an efficient NTT and you're okay with that or what was it? >> If I can find a middle ground and also only do that for Sorry. Um I'd hope to find a middle ground where maybe uh so so we we could do uh multi-point evaluation in the extreme case of like a random evaluation set, we could do multi-point evaluation, but that sucks. So, I'm hoping for a middle ground and also maybe like, you know, I'm I'm I'm thinking kind of like a of a ZKVM where everything except the final proof maybe uses Johnson and then just the for the final compression, you anyway things are small, use a slower NTT.

Yeah. >> Okay. Well, Quang, thank you so much for this extremely dense impressive research. Thank you so much. >> [applause]