zkStudyClub: Reed Solomon Proximity Gaps & Disproving Existing Conjectures

Transcript

Hello everybody. Uh welcome back to another edition of ZK Study Club. Uh today is going to be a little bit special because we have not one but two uh sets of authors and two papers on a similar topic that we'll be presenting here today. And so without further ado, I'll let the authors introduce themselves and then we'll go one after the other present this work and have a conversation about um about this topic of uh proximity uh proofs for Reed Solomon uh codes. So with that, Ben, I'll let you and your team introduce themselves and we'll pass it over to Alistister and Elizabeth.

>> Uh, sure. So I'll start. Um, [clears throat] yeah, Ben Diamond. I've I've worked in cryptography for um, six, seven yearsish. Uh, my original my origins were in pure math and um, you know, maybe going back into that a little bit these days. So experimenting, working in a lot of different areas right now. So, um, yeah, that's all I got. >> Cool. Um, I'm Angus Gruin. Uh, I my origins were also pure maths. I I get the the sense that this might be a common theme of the authors. Uh, I've been working in sort of cryptography for about three or so years. Um, I guess I'm

one of the main people working on Plunky 3. So sort of developing these these very uh low-level libraries for use by by lots of teams. >> Awesome. Go for it, Alistair. >> Hi, I'm Alistair. My background is theoretical computer science rather than maths, but I did learning theory, so I'm kind of comfortable with this probability stuff. And my path to cryptography was went via blockchain. Um I've been working you know um on polka dot for six years.

Um and in the process of of doing blockchain research I picked up lots of cryptography. Um that's me. >> Hi my name is Elizabeth Kes. Um I am also working at web3 foundation with Alistair. We've been working together for about two years. um mostly on stuff for polka dot also some threshold crypto which I'm going to talk a little bit about which inspired this work uh my background is also in math also but PDS so kind of unrelated I came into cryptography kind of halfway through my PhD um yeah that's it for me >> okay awesome thank you guys so much for your intro and like I said we're going to because of the special uh two team format we're going to start with um the

presentation by Ben and Angus and then uh we've got some content from Alistair and Elizabeth too. I think we're just going to kind of see how it goes in terms of questions that you guys have in the audience and uh you know where where the discussion leads. But with that um thank you all for being here and taking the time um early or late depending on what time zone you're calling in from. And yeah, Ben and Angus, please take it away. >> Okay, cool. I think I was going to start. Um, Ben and I might jump back and forth a bit a bunch and then also I think Alistister and Elizabeth might jump in. So, we'll sort of just just see what feels good. Um, I guess we wanted to start off by giving a little bit of background for the problem. Um, I'm

assuming I guess we're sort of assuming a relatively high level of uh of background already. sort of we're hoping that people have some a sense of sense of what this problem is already, but we wanted to just sort of show a couple of slides to try and at least jog the memory of of exactly what what these this problem is talking about. Um, so so [clears throat] what are we what are we dealing with? So we're dealing with linear codes. And so I think the way that you visualize linear codes probably depends a lot on exactly sort of what where what you're using them for. But at least for for Ben and I and I think this will sort of come come through in our in our talk. The nicest way to v visualize them is sort of this this picture we have of you can

sort of imagine a larger space. So here we have three dimensions but in general you have many more and your code subspace is this sort of line of distinct points and this picture is a little bit um misleading because of course uh this is sort of working in over the real numbers. makes things look continuous whereas in reality we're working over finite fields but in practice this is a reasonably good picture to keep in mind if you have these sort of isolated points that have some distance between them and very much what what Beni's work is about is sort of taking these points and sort of blowing up these these balls around each point and asking sort of how big is the intersection how well firstly how big is the ball and secondly how how big is the intersection

um but then more than just linear codes what we're interested in is read Solomon codes. And so read Solomon codes are a pretty special type of linear code that basically rely on this quite nice oopsies. Okay, sorry. So that we we would call the beat space the word space and then the code subspace the code word space and this comes up as sort of when we're picking words and and similar. Um okay so the we're mostly care about read solvent codes and what re solventment codes rely on is this very very nice uh sort of bjection between polomial coefficients and polinomial interpolations and so this is sort of the the degree two case it's sort of well known that if you have a polinomial of degree three it's uniquely determined

by two points but more generally there's this sort of famous statement that if you have a polinomial of degree less than k it is uniquely of degree k minus one is uniquely determined K points and this basically lets us construct these codes where our subspace are evaluations of these lowderee polomials uh and and these turn out to have a whole bunch of really nice properties that I'll I'll rough I'll very briefly get into. So to give some sort of uh actual I guess symbols um we're going to fix our finite field and a subset and then fix an integer. Um and so the retorman code it depends precisely on what is the size of this uh subset D uh sorry on what is the structure of the

subset D but for actually Ben and my work and I think also for Elizabeth and Alistair's work it actually doesn't matter so in general the codes depend on this D but for us we can just sort of ignore this and instead just have an integer here and this actually won't won't give us any problems and so then our code word space is the set of evaluation vectors so basically you assign some element of f to each point in d. Um and so you can sort of easily see that the number of different uh the size of our value of our code word space is n to the^ of f. um where here the size of f I guess should be q if that's and similarly our code subspace is going to be basically we take polinomials of

low degree so degree less than our fixed ink k and we look at the evaluation vector uh of of those polinomials uh and you can also you can easily work out that number of code words is sort of this this much smaller factor so you can you can sort of take a ratio here and see that assuming that k is a lot less than n most things aren't code words uh yeah >> wait So, so is this a typo? Is the first thing supposed to be word space rather than code word space? >> Uh, yeah. Sorry. I think we I think bed and I were working on these. Yeah. So, this is you're completely right. I'm sorry.

>> Yeah. Yeah. Uh I think I guess you can sort of Yeah, I guess this is the word space I suppose in sense it's the the larger space where the code words live. Um but I think based off the previous slide there should be Yeah, I'm sorry. Um yeah so the first one is is the full set of the full set of points of the whole space and the the code space subspace and you can see that if n is bigger than k most points are in the uh are not are not in the code subspace and in fact the vast majority are not um and so one of the most important uh aspects of codes that we care about is this sort of distance property. So the hamming distance. So what is the hamming distance? The Hamming distance just says how far apart are sort of two evaluation

vectors. So you can see here we have sort of two strings and these would have Hamming distance three because there are three points they differ at. And in particular we don't care about say how big the difference is. So you sort of the fact that this is like 86 difference of two whereas the others have difference of one is immaterial to us. We just care how many points do they disagree at. And the reason the hamming distance is very interesting is that for read solomman codes uh you have these naturally very large having distances. So in particular because a polinomial to be less than k is uniquely determined by k points. So there are two statements.

So firstly the minimum distance between code words has to is going to be n minus k plus one. And the way to think about this is this is this turns out to be equivalent to the question how many zeros can a polinomial have without being zero. And by our our statement up here we can see well you can have at most k minus one zeros. Once you have k zeros then this uniquely determines your polinomial and therefore you have to be zero. And so you can have at most k minus one zeros which means that the minimum distance to the z the mining distance to the zero polinomial is n minus k minus one which is this thing.

Um and this means that we have the unique decoding radius which is n minus k12. There may be a factor of there. There might be some minor plus or minus one errors that I apologize in advance for or Ben may have gone through. >> Correct. It's good. >> You fix this. Okay. I think what I initially wrote to say >> this is true if NK are even. If it's not, maybe you need something else. But it's fine. It's written. >> Great. Great. Um, but the point of the unique decoding radius is that if your distance to a code word is less than n minus k on two, then the code then you could can only be close to a unique code word. And this is actually the region where lots of our proximity gap results are. I won't say easy to prove but easier to prove. Sort of while you're in

unique decoding things just sort of work. Uh and then outside of this you called list decoding where all of a sudden you have to worry that you might be close to multiple code words at once. Um the other thing to note about this this definition you get is you not only get a minimum distance, you also get a maximum distance. And indeed the maximum distance um of any point to the code is n minus k. And this is firstly a little bit strange. This is actually smaller than this minimum distance that I wrote up above. But the key thing to note here of course is that any code word actually has distance zero. So the fact that like code words are far apart. If you take something that isn't a code word, it actually turns out that it can be at most n minus k. And the reason for this

is exactly this this same statement above of you can just pick a locations and that defines a polinomial. So that that is in the code and so you can always find a polomial whose distance is at most n minus k. Okay. Uh, and this is this I guess is what we call the capacity because this is where basically all proximity gaps results become meaningless because everything's close to the code. Technically, they still become true. They're just vacuous. Um, okay. I think I'm jumping to Ben for a bit.

>> Yep. So, let me try to take over. >> I can stop sharing. >> Okay. I think we should be good. Um, do you see proximity gaps? Okay. So, uh yeah, let me just keep um keep running uh pick pick it up where we were. So, um our our result is about a phenomenon called proximity gaps which sort of sits on top of coding theory uh but is is really a kind of really a canonical coding theoretic phenomenon.

Okay. So, here here's a a very abstractified code. Okay. So this box is the word space and these three dots are the code words. Uh and as Zena said, we're interested in what happens when we blow up a ball of varying radius around each code word. Uh here you can see the balls don't intersect at all. Uh this picture you can think of as as unique decoding. Um eventually the balls will start intersecting and here's a p picture of of so-called capacity. Okay, so at this point the balls completely fill the space. This is the radius such that every word uh is is can is within some ball. So this radius turns out to

be n minus k just like Angus just said. Now proximity gaps is a question about how uh lines can interact with with uh the union of of these balls. So essentially if you're within the blue it means you're close to the code is what we call it close to some code word. Um, of course, which code word you're close to depends on which circle you're in. But what we what we're interested in is is the is the union of all blue circles. So to be close to a code word, doesn't matter which one. Now, if I draw an aphine line, that line, a couple things can happen. It it can consist entirely of closed points. It can live entirely in the blue area or maybe none of it can or maybe a small amount of it can. Uh

and and the other thing that can happen is some some non-trivial proportion like let's say half. Okay. What what proximity gaps means is that we we like these three on the left. We don't like this. Uh we say that a code has proximity gaps if these three things can happen and this one can't. That's kind of what we're what we're after. Now there are two parameters that are important. First is what what what is the radius around the balls and the other is what is the proportion that we allow to be covered. Uh if that proportion isn't one, it should be something small. And then what is that small thing? I like to think of that as the false witness probability. It's the probability that a line that isn't close

uh it's the proportion of the the non-closed line that consists of of false witnesses to the closeness of the line. Okay. Now, one of one important thing we do in our paper and and actually literally the identical same theorem was was stated and proved by um by Elizabeth and Alistair is that proximity gaps are related to the kind of generic covered proportion. Right? So, we want to reduce the problem of proximity gaps which is about fon lines to something even more fundamental which is how much of the word space is covered by the blue balls.

Uh and the way we do that reduction is what's is by using what's called a a deep hole which is a point a word that is as far as a word can be from the code. That's this uh little red point here. And the idea is that uh if too much of of the word space is covered uh by the blue balls then um then then a line we must be able to pick a line that commenurately hits that mass. So it couldn't happen that the mass was very large but every line missed it. Right?

This is a kind of classic averaging argument. Okay. So um jump into the slightly more technical part of um of the talk and and we're very time limited so I'm just going to blast through this as quickly as I can. So this is the conjecture from um BKICS 23 that we uh disprove. So what what this line sweeping argument shows is that if this conjecture were true, then this would also be true, right? Pick a Z, pick a radius that's less than the covering radius, then the proportion covered uh the proportion that's close to the to the code should be bounded

from above by this polomial expression for some exponent C star. So we show that this can't be true. Um and um for which Z. So in a way it becomes more impressive if you disprove this even for smaller Z, not just N minus K minus one but even smaller things. And and we do um disprove this for for uh for for Z that drift away from N minus K minus one by an unbounded function. And also our K is unbounded. So this is a bit more technical but this is effectively what we do prove in our paper.

Uh just to to clear some terminology. So as Angusa said this is the covering radius aka capacity. Uh what we're going to do is pick a ball radius Z that is um less than capacity. And uh so so here's our our proximity parameter ball radius. Same thing. Uh it's convenient to give a name to this guy. H. H is how far Z is away from N minus K. So uh what we want to do is is disprove it not just for any old K and H but ideally for as large a K and H as we can. Uh and indeed we we we we do get K and H something like N to the uh

sort of a little bit less than root N to the 1/2 minus epsilon something like that. So, um I think Angus was gonna take over again here. Is that correct? >> Yeah, I can jump in. >> Yeah. So, just >> um >> All right. Can I steal it from you? Uh >> wait. This one. Okay. Attempt. It's back. >> Start Angus. Maybe just a good natural hesitation. Does anyone have any questions up to this point for Angus on the presentation? All right, I hear someone unmuting, but I'm not sure if they have a question or they're just unmuted. Um, okay, cool. All right. Uh, I guess I

guess you're good to proceed. >> Okay, great. Um, okay. So, I I think one of the nice things about this result that that I'd like to try and get through to people is that there is actually it's possible to really see what's going on here intuitively. So I think Ben Ben in a moment was going to go through uh we'll go through the maths of how we actually get this uh how we actually prove this rigorously. And of course you know you don't want to mistake intuition for proofs but I I think very much if you asked like why do we think this is true ignoring the proofs I think there's sort of some very nice pictures you can get um by looking at at how this uh how this theorem behaves in in some sort of

special limits. So in particular what what we want to think about is what happens when you take read solvent codes and set k equals 1. So k equals 1 means that the degree of our polinomial has to be less than one i.e. has to be zero i.e. our polinomials have to be constant. And so that means our code words just look like so called repetition codes. So you can see our code words are just some value repeated uh for the whole of the whole code. And in in this special case uh sort of everything you get everything gets simpler. So if we take a random uh word uh let's define this sort of repetition r of you to be the maximum number of times that it's some that anything repeats

um then the distance from our random word u to our read sol minus this repetition. And so we can take sort of two limits. We can say we we set K equals 1 and we can also set our shortfall H to be one. And so now what happens is well what does it mean for something to be n minus two away? Well, it says what's the probability that two of use's entries are identical? And this is actually a restatement of a reasonably famous problem. Uh this is this is exactly the birthday paradox.

Uh, and I guess this is maybe one hint already that that maybe sort of these shortfalls aren't too hard to come across because I think the key point of the birthday paradox is that it's more likely to have these matching birthdays than you might expect. And and really this is sort of what's what's also going on here that sort of it's more it's it's more likely to get these sort of close points than I I think the community sort of naively expected when we sort of first wrote down these conjectures or at least first worked with all these conjectures.

Um there's one other thing that we want to do which is sort of makes makes it easy to estimate and this is sort of a this is a slightly technical assumption which just turns out to sort of very well nicely capture what's going on. Um so so this is this is our ground truth. So what we have here is you can imagine each of these balls there should there's sort of a point a code word at the center and these are like the balls around the code word and what what we're trying to measure in this random word situation is what is the probability if we drop a random a random word in this square what's the probability it lands in one of these balls and we can restate this in this sort of

totally slightly bizarre way we say okay what about instead what if we drop lots of different uh random words, lots of random words in, but only ask about a single ball. And you can ask, well, how how do these two probabilities relate? And I mean, if anyone has any guesses, um you're welcome welcome to say them now. >> Uh are they the same? >> So, not quite. Um that's a good guess. The answer is like so the answer is basically yes but for for various limits um for various limits sort of the ground truth will be a little bit higher or a

little bit lower. So in particular, one one reason that you can expect the ground truth that these these can't quite be the same is that if our balls are small enough that we're in unique decoding, then we know that actually no point can land in two balls. And so you end up with this uh you end up that the the independence has to be uh overounting sorry has to be is is underounting is a little bit too low. Sorry. Um on the other hand as as your rate approaches capacity then we have these huge intersections between our balls and our independence ends up being a little bit high. So it goes up and down. But the key point here is that as you can see on this graph. So this is basically the

probability of getting this is I mean this is the birthday paradox roughly. This is the probability that you have two two people whose b with the same birthday where on the um x-axis we have sort of the number of people in the room. And we have sort of three three things here. So uh in this nice case we can actually compute the true probability. We can't all usually do this unfortunately because it's a little bit complicated but at least here we can. And then we also can compute what would the what is happens if we use this independence assumption and what happens if we use this independence plus this plus on assumption that is very useful for uh actually making uh visual visualizations. And the takeaway from this graph is that these lines are basically identical. like you can sort

of see that there's there are places where there's a little bit of difference but it's it's never more than one or two%. So sort of the the information you get by staring at say the independence and pson graph uh covers basically everything you might want like it gives you a very good intuition for what is actually going going on in reality. Um and so then you can say well so far we've looked at this n equals2 case but how do we generalize from this? So the first thing we might want to do is basically um consider what happens if we ask for more than two birthdays to be the same. We could ask for three or four

or five. And so then you can get plots a bit like this. So what's happening here is we have sort of we're plotting various shortfalls and these lines are basically corresponding to uh the probability of finding uh oh sorry the the percentage of the space covered by balls of the of the radius of radius zed and you can see once again as n rises sort of for each of these these lines sort of this red line is sort of the birthday paradox this blue line would be sort of the generalized like a triple birthday paradox where you have three birthdays on the same day The green would be four birthdays. But you can see that these are actually uh these go to one sort of relatively fast. And this is even only

in the k equals 1 case. And so like as we see here like any so here our q is only 365. So n being 313 is maybe a little bit unrealistic. But we can see that like as n gets large what you find is that uh a lot of words actually have quite a lot of these duplicates. And the sort of interesting case is that when you start making k bigger what you find is this gets even more pronounced. So when when k is 60 here there's sort of two features about this graph.

Firstly you'll note that our shortfalls as opposed to being like 1 to five are now sort of 20 to 30. So our shortfall is getting much larger, which says that our our balls need to be much less big before they're still covering the whole space. The other thing you might notice is that these graphs end up looking basically like step functions. So as n increases, sort of the the percentage of of the sorry the percentage of the space covered by these balls as n is increasing looks like sort of 00001. And so trying to estimate where this um trying to estimate where where this sort of step is uh is is a very good indicator for where these sort of random techniques are going to start working.

Um and so in particular on if you stare at this graph you can see if it yeah for n 134 and so note here like as opposed to the last case we had to take n up to like 300 here n's only 134 but most words are more than 20 close to the code. Um and here 20 compared to 365 is like a reasonably high percentage. Obviously these graphs all change a bit as Q gets larger and so cubing 365 is a little smaller than anyone would use for a uh for for a zero knowledge system. It's also unfortunately not prime but you could actually make these same graphs with Q much much bigger or or you can sort of start to compute things numerically.

Um and yeah again okay again once again if we get n to be similar to where we were before our words get very close. Okay, so basically what this comes up with is that we can come up with a sort of the following linear graph for what's going on. So let's lock in our row and we can first work out where is our unique decoding. So this is the section where proximity gaps is just sort of solved. This this section works very well indeed. We actually know it's to be true in a slightly larger section which is list decoding. So here the blue section is where you have this situation that you might be close to more than one code word but you're still not close to too many code words. Things sort of

things work quite well and this sort of cuts off at this one minus root row because this is where some particular um work by Gurus Swami cuts out. I mean this was this was sort of the original Eli Benason at all paper about proximity gaps. Um similarly we know that there's no hope of getting proximity gaps past capacity. So once you get to capacity proximity gaps are sort of immediately vacuous just because you can't find any points far from the code. So there sort of there's nothing to say. And so basically the proximity gaps conjecture has been about this sort of this this region. And what we've sort of shown is that there is this uh this this this cutoff. So this this value below basically this is the estimate of where

these step these step functions are occurring. Um and so in this case it it cuts off you know a small segment of the space where it basically says that uh we can't get proximity gaps past this point from uh these random words arguments. And to be clear this is a little bit more of the space than we explicitly show. we sort of we have a proof that needs requires some technical details uh that and so only works up to these sort of cube root ends not this sort of log behavior um but I think it's sort of reasonable to expect that the this sort of this holds a bit a bit further out and I think actually also Elizabeth and Alys's work u gets closer to to these

these sort of thresholds >> yes the other >> I'm yeah so this this this expression log 2 e of a row times row I'm not sure that it's tight >> um because the naive thing gets you something more like h2 of row which is at a half or at a small thing closer to log 2 over row than e over row [clears throat] and somehow you seem to be slightly out here which is odd because you did all this stuff to much greater detail than than we did.

>> Yeah, I'm not sure. It may be. So, I think we did some stuff to very high detail. I think some of the um the estimates we sort of played a bit fast and loose because I think we originally had the paper up and someone immediately asked us, hey, what what does the values look like in uh in real world settings? And we're like, oh yeah, we should we should try and write something for that. Um but yeah, I'm not sure. I I certainly agree that that this that this bound is is a bit loose is probably is probably somewhat loose. It's not clear to me exactly how loose it is.

>> I think the is very close and this is very close to the classic cury entropy estimator. >> Um and this is a like a bit higher than that which is the problem if you're trying to bound it. Yeah. >> So maybe >> uh I mean it might be kind of interesting. Sorry to pick a little improv here, but I mean Alistair, given this potential difference between these two thresholds between your work and theirs, maybe this could be a good jumping off point into covering a bit of your work. I want to be conscious, Angus. I I know you were like on a roll there and you have other stuff, but I do think it is kind of given this is a point of difference potentially or at

least a point of conversation. >> Um I don't know, maybe Angus can carry on. This is uh we still have >> Yeah, we got plenty of time too. Okay. So, maybe maybe we'll we'll do that. We'll we'll put a we'll put a pin in that and come back to this point. Uh any other questions for Angus and Ben at this point in the presentation. >> Cool. This is great. Keep going, Angus. >> Okay, great. Um I'm actually uh about to hand off back to Ben, but I guess this is the final show slide I want to show a bit. And so, this is basically what happens if you take that previous slide um previous slide and just look at different values of row. And as Alistair mentioned, so this red line is sort of the region that we've we've sort of cut out. As Alistair mentioned, it's

possible that yeah, this red line is is not quite the right one. Um, you might want to have something a bit closer, but unless I'm missing something badly, it shouldn't it shouldn't look massively different. My sense it should be similar. So it's it's it's small. It's a relatively small difference, unless I'm I'm misunderstanding that. Um and so what what's this show? What does this show? Well, here we we're basically plotting um row against uh I think it's EDA. Yeah, row against basically EDA and our green region is unique decoding where things work well and our blue region is is this one root row. So this is where we have proximity gaps proofs uh and we sort of know that

we have proximity gaps for resolment codes. Um the black region is capacity where everything's doomed. And so this white region is sort of the the remainder of what is the conjecture actually asking about. And essentially uh what what Ben and I and then also um Alistar and Elizabeth's work shows is that is that you can't there's no way we can cover in this whole white region with with sort of a with a good color that there is some sliver of this white region near near very near the capacity which is just impossible precisely for the reason that actually you get to the point where most of your code words are close to your code well before you get to capacity. Um there's

sort of not this like smooth or this we don't have these steps at capacity. Uh on the other hand actually it is true if you let your Q be really really large. Um so you can see here we have this log 2 on the bottom uh there's even if you use these other formulas you get something similar. Um if you let Q be really big like super exponential in N then you actually can go up to capacity. So this this was a recent uh paper of Guraswami and Royale which said that actually you do get proximity to up to capacity provided you're willing for your queue to be sort of super exponential in N which is unfortunately not particularly relevant for crypto purposes but is is interesting from a mathematical perspective

um but very much when you're this isn't true when your Q is large but not sort of unbelievably large compared to the other variables uh what you find is is that you you you have this sort of little carve out you have to take out where where you simply not be going to be able to get any proximity gap results past this point. Um now I'm going to hand over to Ben who's going to talk about some of the more technical aspects of things. Um I guess this also be a decent point if there's any sort of anything intuitively that Alistar or Elizabeth want to share or chat about before we sort of jump into the more technical parts of the work.

No, our plan was to do the technical bits after you do the technical bits and then go back to untechnical bits at the end. >> Okay. Excellent. It's like a sandwich. >> Nice. We'll do two talks in opposite order. One will go top to bottom, the other bottom to top. Sounds great. >> Lovely. >> Okay. So, I I think we're getting a bit squeezed on time, so I might have to just kind of speedrun this. Does that sound right? >> Yeah, give it I'd say >> if you have the next 10 minutes, Ben, take the time within the 10. Um, >> hopeful that the text that was set I mean that that puts you guys at 45 minutes and you guys said some context too. So, I'm hopeful that with that

>> Alistair and Elizabeth can take what what time remains, which is almost half um to uh to take it back and then hopefully if folks have questions, they can just ask them throughout. Um, hopefully that's okay with the audience and folks in the audience, please do ask questions if you have them and also feel free and put them in the comments if uh if you'd like and I can read them. All right, go for it, Ben. >> Okay, great. Well, let's do this. So, I I I think the moral of of what Angus just said is that if you believe if you believe the independence assumption, you should already be convinced that this conjecture is just not true, right?

because um these these really nifty Desmos uh charts were computed with the independence assumption right that is what let us compute them so exactly now the real world is more complicated you have to actually deal with intersections and things like that uh but if you do make the independence assumption you just need to know the ball volume and then we use the pluson approximation for that and that's how we got these so if you believe those two this conjecture is is toast. Uh now just just by looks you can see how close they really are. Uh but sort of the the the main body of our paper involves uh not

making this assumption but actually proving um proving sort of rigorously that uh the union of of these um heming balls is uh is is sort of large even for radi that are are are much less than covering radius. So uh what what I'm going to be be saying now is is sort of the rough sketch of of how it is that we do that. So our our goal again is is a random word close to the code meaning is it contained uh in the union of a bunch of balls of radius Z where um Z is prescribed. So um the first step that we do is this kind of inclusion exclusion trick right so if we're interested in the volume of a

union um we can lower bound that volume by taking the kind of brute sum ignoring overlaps and uh subtracting these kind of pair-wise um intersections and this will give us something smaller than the truth. Now if even that's big then then we've done what we need. So we actually just essentially take these one at a time. The first thing we turn to is is the ball volume. If we have that, we just multiply that by Q to the K and we get a first order estimate. Uh to do that we we do a bit of um a bit of math. Uh as we say in the paper, the main idea here is something like how the

pson approximation of the binomial distribution gets um derived. um we get this really sharp estimate which is better than the classical one essentially because uh it's better and worse right so uh what this fancy notation means is that if you take the ground truth here and you take our expression here they might not be close but they can be made close so whether they're close or not will depend on what Zn and Q are uh for some ZN and Q they might be way off but if we choose ZN and Q such that these expressions get small then the ratio between the ground truth and our estimate will go to one right so it's a

controllable >> how bad this last number looks >> wait say again >> why is this thing no bigger than one n minus z^ 2 zed over n^2 >> uh what why is it no bigger than >> this is where our condition about like n minus zed being sort of oh n cub comes This is this is like >> Oh yeah. So we need Z to be nearestish to N, right? Z should be something like N minus cube root of N or something. >> But well but isn't Z the number of errors.

>> Uh >> Z is the Z is the B radius. >> It is it is the radius. >> Yes. But are we talking about N minus K here or what is N? >> K is also small. K is also growing cube root of N. So >> you need K to be small to make this work. K. Well, not >> yes, relatively small. K needs to be something like cube root of N. Uh, and and Z will uh N minus Z will also be a constant factor difference from from K. >> Why would K be cube root of N? Don't people use codes with like K is equal to >> that's kind of the point, right? So our our counter examples require rates that go to zero and also shortfalls that go to zero. Relative rates and shortfalls.

interesting because I think ours don't. Okay. >> Your K can be your your row can be constant but your shortfall goes to zero like ours does. >> Yes, the shortfall goes to zero. >> Yeah. So that's a nice feature of of your proof for sure. By the way, I mean like hey K being a constant proportion of N is not required by the conjecture, right? So not even if you even if for you know k equals 1 uh you could already disprove the conjecture that way although again our ks do grow to infinity just um more slowly than n does >> right it's just a k constant factor of n

sort of k is equal to n but something is what I'd expect the parameters people would use in snarks in practice and we try to stick to those even if they don't make sense for our thing >> yeah I agree It's nice if you can disprove it for constant K uh constant row. That's nice. We didn't uh like in our rigorous portion but um um yeah maybe our techniques could be adapted. We're not sure though. So uh should I carry on?

>> Yeah. Uh go for it Alistister. Just a point in that. I mean I think one question that naturally comes up at least in my mind is yeah I mean for real world parameter sets that people choose it's like kind of where do you know what is the takeaway for that right so I think this probably gets more to the area that you're going to cover in the light of how it sounds like you did your proof um is like the you know possibly the relevance in terms of picking parameters for these systems and how that this conjecture or this this disproving of the conjecture impacts you know choices of those parameters. But yes, Ben, please continue. I promised you 10 minutes and I'm I'm taking your time by talking. So keep going.

>> Sure. Sure. Sure. Okay. So, um this is a chart that tabulates how our estimate performs. Um for for n= 365 and Z very close to N. Um you can show that actually it it does better even than the kind of classical estimate based on entropy does. So I think that's you know independently interesting that we have a really good uh ball volume estimate but it also does prove useful for a proof. So um turn to intersections uh this I'm going to have to truly speedrun but um basically there's a lot of combinotaurics here. If I want to understand how two balls intersect sort

of by translation, I can move one to be zero and and consider intersections between zero and uh nonzero code words and and moreover if I sort of scramble v but keep its weight the same the number of nonzero components then that doesn't affect the intersection. So it it suffices to understand how many weight w codewords there are and uh how big these intersections are. So um the one place in the paper where we actually use MDS is where we uh bound from above how many code words of weight w there can be for for each w um bigger than or equal to d.

Uh to actually talk about the intersection we we need to do a bit of um bit of cominatorics. Here's a kind of visual proof of of this bounding. uh and um our our main theorem about intersections uh basically combines those two lemmas and then does does a bit more kind of analysis to uh to show that there there's a double sum that comes out containing terms with a kind of multinnomial coefficient and then something that depends on Q. uh and for as long as you make these controllers go to zero then we can show that one sum and will dominate this sum and you get really a quite simple expression here.

Uh so here's the ground truth here's the estimate and then the these are the controllers. Okay. So what's what remains for us to do is to let n go to infinity and and then for each n to tell you what q should be tell you what k should be and what z should be and um to uh to to to let this thing uh go asmtoically. Now um k might not be an integer q might not be prime or prime power. There's a kind of technical uh we need to deal with this. This interestingly go goes number theoretic in a way that we didn't expect but we find to be interesting just to guarantee that primes or prime powers exist in in these

intervals. Um I can talk more about that if people have questions. So our main theorem is that if we specialize uh n q k and z in that way then our controllers do go to zero. So our estimates become asmintoically sharp and um the the intersection uh the intersection the contribution becomes negligible goes to zero relative to the first order estimates. So we can uh certifiably rigorously throw away the intersections and the sum term asmtoically outpaces 1 / n which is kind of the benchmark uh we need to hit since we set q to be n to the c star plus one. The the the decay rate to beat is is n to the c over q

which is 1 nth. Um so here here's a visual proof of the kind of final accounting. Uh you can see that in the red is is the full ground truth. It's so close to the orange you can barely see the difference. Orange is first order. So throwing out intersections and um uh and then finally we we bound this from below in a number of steps. We finally end up with something that uh that that uh sort of on on its face out outpaces uh one overn. And that's enough to disprove the conjecture.

So here based on our our more heristic analysis we we do suggest a new parameterization. If if you want to gain say 100 bits of security then you're going to need more than 100 queries say at the rate one half uh case. Uh and finally we propose an amended conjecture. I think this is still still kicking. I don't think this has been disproven by the subsequent work of um Beneson Swastik Ori and and others. So um we can talk about that too. So uh I think that should be about 10 minutes. I can I can uh call it at this point.

>> Well, as speedruns go, that was that was that was good. Uh impressive. Thanks for covering 12 or 14 pages of proofs in 10 minutes. Uh I don't know if there was enough uh time there for people to actually get enough to ask questions, but I'll pause in case folks do have questions. >> That last conjecture. Yeah. So what I would have loved is you have a large enough end, but you never tell us how what it is. >> Everything else is concrete. >> Well, here's the thing. Um >> um and it makes it difficult. >> No. Yeah, I I would love that too. I would love to know everything. Um now we put that there uh just uh just like in theory if n is too small then

then the very technique of of our paper and yours could just make uh the false witness probability kind of unduly high right it could make it sort of abnormally high and then as n as n sort of matures and gets big enough this thing will will sort of conform to to a more reasonable exponent. So what we what we want is for implementers to get a C that actually reflects uh the the kind of limiting behavior not something artificial that happens early on. That's why we did that. Now it we could have tossed out this enlarge enough condition. That wouldn't make this conjecture that can't make it go from true to false. Um it's only there so that um C can be set in a more sharp

way. And same with K. We could have killed both N and K and just said N to the C over Q, but that C might end up bigger than it needs to be if we did that right? >> Yeah, of course. Of course. But having uh the issue again is that if n isn't large enough in practice like people probably use ns that are quite a lot smaller than q's if they're 2 to 128 or some other >> I can I can just maybe a comment here that's useful. So the thing that turns out to be really nasty for this conjecture turns out it's it's not exactly about n that causes things to be a disaster. The issue is that like when if you can have set up situations where

like k equals 1 or or h equals 1 then you start to get really really big um powers for sort of basically silly reasons. Um and so I think you can like actually write down the what you want for n and you basically you want n to be large enough such that like both h and k are sort of bounded a fair way away from one. I agree that's sort of not I think we did have expressions we wrote down using our sort of huristic bound at some point but they weren't they weren't super clean.

>> Okay. Okay. Anyway, yeah I >> mean my my my response is like if you don't like that get rid of it. The conjecture will keep its truth value. You just might end up with a C that's bigger than you like. And so in other words what usually happens in real life >> if you don't have a large enough N is wrong. No C just increase C or K in order >> small N >> there's some no so in particular the um the domain in a sub field case >> was um which you know with the recent paper of Fenzy and Sasso it is enough to your large enough N was escaping that and if you don't then it doesn't work.

Oh man, now Daryl's got a question. Never get into your paper, Alistair. I'm sorry. Uh Darra, go for it. >> Yeah. Um so speaking as a an implementer um and designer, um it doesn't matter if the the precise expression is is not very clean. It just matters that you've got code that um can calculate it. Um so it as long as you can write a um a parameter estimator that that people can use that um uh says whether specific parameters are um are okay or not then >> yeah sufficient even if it's a if it's a really nasty and hairy conjecture.

>> So so we put a concrete conjecture in our paper and uh two papers have come out since proving it wrong >> and now we're going to put an updated concrete conjecture [laughter] and you can change the numbers. >> Yeah. Yeah. Uh >> yeah, I mean I think I think at least for us the thing that we care about more than necessarily this conjecture is I think if we go back a slide or two is the we do put some concrete numbers in uh the sort of query numbers. Um and I guess this is sort of more of what our our concrete in some sense statement is. Um because I think when we're trying to work out how to fix the conjecture like there's I mean I think it's one of these things that Alistair pointed out right was that our counter example

already works in this slightly unrealistic setting. Um and so it it I guess it seems like in order to truly fix the conjecture you need to start uh like finding ways to to sort of slice away these sort of very unrealistic settings. And I think this has also come up in some of these counter examples that have come out since our paper of we start having counter examples which work with very specific choices of like domain sets. Um which which aren't used in practice and it's sort of can be hard to work out exactly how they relate to um I'm still I'm still hung up on this idea that taking that out could make the conjecture false. Right? Like let's say

I'm going to prove that our conjecture implies the version of it with that taken out right like fix some case where our conjecture holds whatever that effect of n is let's say it's like a trillion or like a google or something right like surely if you take the cases where n is less than that point then the the false witness probability kind of can't be too large right because um it it must be it must be at most some quantity that depends on on the effect of you know capital N like a Google. So just let C and K be so enormous that you kind of encompass that and then and then let it run and and you you should still you should still have the conjecture be

true in that case, right? Does this make any sense? >> I think so still. So the issue is seeing pay can be huge but they they can't deal with uh this exponential blow up which you um would have got after the um list decoding capacity band. So the issue is um how this is a function of eater. Um >> yeah like I thought that the thing that was saving us in some of these was that we c and k are functions of row and eater as opposed to being >> yes >> having to be fixed for all like I I think that really one take away from here is that we you probably don't want to you may well not be able to fix and

have the same thing for all rowita. Well, that's totally not what we're claiming. We the whole whole point is that RK and RC should should change if Row and EDA change, right? So, >> yes, >> if if you if you don't allow that, you're back at square one. You you've essentially recovered the the original conjecture that we disproved, right? In fact, if you like you see here how how row and and ADA must be positive. Like if you if you eliminate that like requirement and let them be zero, you've essentially you've essentially recovered the classical conjecture.

In other words, they have one K they have one C that's supposed to work for all row and ADA. Whereas we force we force the the code families rates and shortfalls to be bounded from below by what? Well, by by constants row and ADA that you can choose. But but your K and your your C and your effective N will then change if your row and your ADA change. I mean that's effectively the whole point of of our conjecture. >> But here nothing depends on Q. >> No, not on Q actually, >> right?

>> I mean I mean there is a minor Q dependence obviously in the >> get Yeah, exactly. >> Right. >> Yes. Okay. That that the thing is is that that's not anyway. Um >> yeah, we can chat more. Hey, may maybe I can present something before we >> Yeah, >> let's present. Oh, Justin Justin's got a question. Justin, you want me to say it? >> Is it fair to say that the conjecture attack is non-constructive? So, >> I have sights on on on this exact question. >> Oh, well, okay. Well, >> attack I I think should be considered non-constructive, but yeah.

>> Well, no, it is constructive in cases. You can make our attack constructive in like if you let row be small like if if you can find situations where like row goes to one then our attack is is constructive like and this does turn up in worse situations where where >> in practice yeah I actually think it's still a reasonable um assumption that uh that the uh the snarks under the uh previous conjecture are actually uh computationally sound with addition additional computational assumptions.

>> Yeah, >> this no and the reason for that is this this problem of finding these close code words is uh not something we have an algorithm for. >> Unless unless K is small, right? If K's like 01 like if K is like less than eight or something then actually you can do sort of >> there are weird cases where you get down to small enough things that this maybe is doable. But >> well because the conjecture is asmtoic in nature. So I don't see how any finite any single uh any single counter >> we we should let Alistister talk. We can come back to this.

>> Uh all right you've heard way more than than you bargain for. >> I didn't mean to interrupt you guys but I do want to make sure mainly I'm just conscious of Alistar and Elizabeth and Alistar saying some good points and I think it's a great discussion but I want to make sure that we get the other half here uh because I you know to round out the picture. So Alistister uh going to you and I think we're switching to Elizabeth at some point. I guess Alistar you just you just do that when it feels >> let's see if we we we we get anywhere. Um okay I have some slides. Um where are we? Yeah. So the the the first thing that's kind of um different is I think that what's going on with proximity gaps is not too different from what's going on with list decoding. And

um this phenomena was you know known about in the 1950s. Coding theory is an old subject. Um so there is for adult by by Peter Ellias in the 1950s. There is some threshold which is below capacity below which um there are some codes that list decodable and researchers added more things to this. um you know the original example is a random code that's not even a linear code. So it doesn't even make sense to do correlated agreement. Um and um above this band everything uh has a an exponentially size list.

Um, and most of what what what we're trying to do here is to try and argue that this behavior for list decoding also happens for correlated agreement and these proximity gaps. Um and yes, just like um Ben and Angus, uh we uh showed that there was a proximity gap if um the proximity gap fails if uh the chances of a random um word being uh close to the code is too high.

So we just need to get uh the random code. Here is our result of the random a random word a different f. RF is there Z. Uh we get a complicated expression um and which involves this this HQ of delta we we saw in the list coding capacity bound. Here's what it is. And it turns out that in some regions um these two numbers aren't that far from each other.

Um, but uh you'll have to trust me on that one because I don't have pretty graphs. And I think we can get it from the discussion that this probably is closer in more regions than um the previous papers result even though we thought this thing would be a lot less tight. And uh yeah to simplify okay we we're talking about a difference in row of about 1 / log q um when um the rate is a half it's very close to one over log q and all of this is very

tight. Um, so if you have, you know, 128 bit field, it's one over 128. And I'm not even sure why this makes too much difference. But, uh, that's what we get. Um, so there there's the bigger font version. Um, and the technique is basically these listed coding. Um, uh, capacity bound analysis worked with with sort of Hamming balls. Um, as Ben and Angus explained, uh, we were doing things in terms of disagreement sets, sort of equivalent to the agreement sets. We've seen agreement sets in other results on correlated

agreement. Um, and we're working we work with um disagreement sets of size F where the actual disagreement might be smaller than the set. And this means that our approximations end up being wrong if stuff is closer to the word. If we we it's basically if you have lots of things in a list and some of these things are closer than your back bound f then then they then there are lots of disagreement sets. Uh there are more disagreement sets than there are nearby words and this means we overestimate some things but makes every formula simpler.

Um but I should rush through all the techniques because we don't have much time. Um basically the the the thing is counting them with disagreement sets. We want to look at the expectation and variance of this. Um just like Ben and Angus' thing, we we we want to look at the uh the uh the probability of single set of disagreements and intersections. And we don't look at three way three ways or more uh because that would just be too complicated. And this probably gives a very similar answer to what you get um by inclusion exclusion up to pair wise intersection which is what they did. Sounds kind of surprised. Yeah, the answer is slightly different because I suppose it' be very similar.

Uh the nice thing about the these disagreement sets is that everything is easy because of lang interpolation. Um so if you take a random word in one of these sets, well if you interpolate everything on this domain of size n minus f, you end up with a random polinomial degree n minus f minus one. And when is it this polinomial degree k minus one? Well, when the top n minus k minus f coefficient is zero, probability q - n minus a yeah, okay, I need a brackets here. This this has brackets, right? Q minus brackets k - f. Um, and there's n choose f of these sets. And this is, you know, multiplying quite a small number by a very large number.

Um but at some point uh because um you know n can be like uh closer to 2 to the n um if n minus k minus f is small then uh and typically this is going to be bigger than q and this and then and in this region you know we end up with this um this decoding capacity error. I don't know if any of that makes any sense. Um especially not if I try and do this this fast as well.

Now when you are looking at the intersection of two of these things which is so in other words we have we have a random code word. We're looking at two specific sets and we're asking what's the probability over this random code word that these two specific sets uh disagreement sets both have you know code words that agree on the on the with the rest of the word. Um if the disagreement sets have a um you know intersect by a lot and they have a small union their union is below n minus k minus one plus one this is the um minimum distance of the code then the two code words you get for the with these two things have to be the same.

Um and this is kind of bad for us but um the probability sort of goes down uh with um you know the intersection is smaller the probability becomes uh irrelevant uh but the nice thing >> so just on the like on the previous side that could be Q to the minus open PN N minus K >> minus those parameters. Yes. >> Yes. Exactly. Yeah. Okay. >> Yeah. missing the the the the parameters which missing the parameters it would make the whole thing make sense. Sorry.

Yeah, that's kind of rough. And the same same thing goes on here with this n minus k minus uh f intersect frime. Same thing. Um but the nice thing here is that if um as it you know if if these uh sets are almost as big as um you know if f is close to n minus k then then these sets almost uh you know the union of almost all of these sets is going to going to put us over n minus k. Uh and then these two things are independent which uh simplifies the analysis a lot.

Um so in particular we have this formula for the expectation and then if you look at the variance if everything had been independent right if we have you know the bonies with probability P then they have variance P * 1 - P and we add some independent ones we just add them all together and the variance will be smaller than the expectation but because we had this uh annoying case where we get the same polomial uh there's this sort of error term which is this horrible Um originally I had this first term but then I realized and then and it was very great for when Q was massive compared to N. Q is much bigger than N square. This term is just close to one and

disappears. Um and our original application involved um cubing uh an elliptic curve uh group size and uh then we didn't have to worry about this. But in actual people's applications q's lots could be a lot smaller and n square can be bigger than q and then we have to mess around and maybe this square root actually gives us something. >> Can I ask um this min I don't like I have to confess. So can you tell us like what the cases what are the two cases represented by this?

>> Okay. So so it it really depends um on how big this f minus fubic term is. um if it is much smaller than one um then this first term in the min >> well I I can see that by reading it off but >> and everything is very close to one and this term is almost irrelevant >> but if it's big then you you want this term um and what's not so obvious is how this how this compares to nf and q to the n to the k minus f Um but it turns out that um if Q is and N are the same then actually this this

this first term in the min would be um a constant factor. Um it would lose you instead of having one over log q you would get like uh one over 2/3 of uh two over three log q. Uh but this square root saves you makes it go away when everything's large. um and makes everything tight when when everything's large. Uh but I don't have graphs showing this. Uh but I believe it's the case. >> But like is there is it an artifact of a proof step you have where there are like let's say two different cases that can happen.

>> Um not so much. It's it's we had something horrible that looked like an exponential series but we had a factorial squared in the denominator and we didn't know how to approximate this. Um and one thing is just to ignore the square and then you get the first term and then you do something cunning and get the second term. No, it's an artifact of the proof. They're not two separate cases. Um but as you we get some hypergeometric series that we have no idea how to solve and and uh like I looked at moment generating uh fun formulas for concentration inequalities for the

hypergeometric function and moment generating functions for that and then there's uh something called modified bessel functions of the second kind and I've got no idea uh but I couldn't find any anyone who' actually solved this thing so I did something brute force Um, so that's where this thing actually comes from. Um, but then we get the complicated formula and everything's fine anyway. Um, and I can explain maybe why we get pair wise independence, but I'm not sure anyone cares. So that's kind of um conjectures.

Okay, so people were doing things based based on this eater which is you know uh one minus the rate and error decoding uh fact that the analogy with the list decoding um capacity result from from the 50s indicates that we should uh just replace this u k of n turn with the this cure entropy which is actually within like one over uh log P. Okay, I have P here. Um, of uh this anyway.

And basically the idea is that we we substitute this into the listed coding conjecture and the correlated agreement conjecture and the mutual uh correlated agreement conjecture and they're possibly all fine as far as we know. Um, but we first suggested putting in this HQ overn. However, now two papers came out uh proving that this doesn't necessarily work for extension fields. For prime fields, it does work um with uh you know hb k where p is the size of the field. Um and what we believe is true for prime fields when when you know if we're not

dealing with uh binary fields which we really have no clue about. Um if you start to have the the these two the 3 two to the 32 bit primes then probably what you want is um just to have HP where P is the characteristic and this will lose you one in 32 maybe from uh the error the the fraction of errors you can cope with which is not too bad. I I was going to ask um what should our intuition be for the shape of uh HP? I I know you said you didn't have graphs but um roughly >> ah yeah no I could have done some some some some some great graphs like I have a whole load of inequalities for this thing

um so HP co HP of delta is approximately for P being big is approximately H2 of uh delta um over log uh p log 2p indeed um and this h2 is this binary thing. It's um just a standard thing that goes up to one and a half. It's number of uh it's it's the entropy in bits of a of a boni. And if that has a half, it's it's exactly one bit and then it goes down to zero um in on either side including it goes close including for

row close to one. Um um yeah, in general HP KN is is close to K overn like within with log 2 and the other difference is this H2 thing which is um unlike things like H2 if delta is greater than equal to 4 delta 1 minus delta. Is it fair to say that the graph for for x [clears throat] x=, you know, k overn looks like if you took if you took the graph of y equals x and then you you sort of made it a little of a bit of a bump um over that, right? And then if you drive q to to infinity, it should get more and more squished and

and converge to to to to x. Is that a fair statement? Um yeah, if you drive Q to to exper to infinity to infinity, it goes to X. The difference in between it and X is H2 over log Q. H2 is the thing you probably you want to have a graph for. And that goes up and up and down in between and one. >> Um and then I take X plus uh one over log two of Q. I I should get I should get two lines of the same slope.

that will contain the the graph of the entropy function >> and in the middle at a half very close to a half. >> Exactly. It's going to start >> uh going to go back to the bottom >> the top of these and it goes down on either side >> goes to infinity these are just going to converge to each other like that. >> Sure. I have a we have like a bunch of inequalities in the paper for exactly this reason. Um like I have claim one or two or something is getting banned on this. That's what I'm telling that's what I'm saying now is that essentially >> um yeah so there is a special case um which which is one of the things I was trying to discuss for for your thing that um uh well there are sort of two special cases one is is the um the copy

habok at all thing uh for binary fields um the other is the subfield case and the subfield case is particularly uh annoying because It happens all the time in practice like um so I I think that um um Euron Jim Posen's Vineas uses uh you know if I have a domain of size two to 16 you end up with a sub field of size two- 16 >> uh and this applies to that. Um likewise um as um Pensy and Sanso pointed out the people who are doing these 32-bit fields often do uh effectively do fry in some extension field of size 128 but the

domain is in this sub field. Uh so this subfield thing just happens all the time in practice and the problem is um the the what uh dependent Sanso pointed out uh which is that there's an obvious part here which is that if you have a domain that's in a sub field and then you consider the read sol over the the larger field. So if the smaller thing has big lists, uh then so is the larger thing. Um it's it's obvious because one is contained in the other and and the list is not going to get any bigger if you add more

elements. Um and as a result the um the list decoding capacity bound for the smaller field applies. So that's why we're suggesting h HP for characteristic P because you your if at least for the case where your domain is smaller than P but maybe your large N case in in for for Ben and Angus' conjecture is enough to uh get rid get rid of this problem although it's not so obvious um >> about that I think >> and that's why we we we we're now going to modify this thing to suggest this HP Darra >> yeah so what What I'm hearing is sub fields are complicated. Um would it be

fair to say that if you're using um extension fields then you should be more conservative on maybe to the proven parameters or um that conservative >> if you're using like a a tooth to 32-bit field that the binary field case is the really hard one. If you're using this uh this due to 32-bit fields that people use, you know, baby bear and koala bear etc. then this one over 32 uh is something you you should you can probably live with.

>> Well, so you should be more conservative just maybe not by >> Yeah, you don't need to be in incredibly conservative, right? This number will come out fine. >> You you you'll have to use uh less than one over 32 less errors. But if your error rate is already like um it's going to already be bigger than that probably you're not going to have row as one over 32. >> Um >> so I I mean not to narrow you down because that this is very complicated but how confident are you that this is the correct fix for the subfield case? Um, right. So, I don't think this is Yeah, I I'm okay. We don't know like um I I made a two weeks ago or three weeks ago or something like that and it's

already broken. >> I say this now, maybe it'll be broken in three weeks. Uh but um yes, I'm fairly confident. Um what actually I'm worried that we don't have a clue any sensible sort of maximal conjecture to say for the binary field case. uh we don't know but um but to the 2D2 bit fields this conjecture should be fine and um I don't think it's going to be broken straight away >> so >> okay thank you >> I want to jump in real quick uh maybe just to ask Elizabeth was your co-author Alistair since we have eight minutes left or seven now uh Elizabeth do you have anything to add u we don't have a

ton of time to go through slides if you prepare them but I guess maybe I'll just ask at this point do you have any you'd like to add on the discussion? >> Yeah, I mean I kind of wanted to summarize. I was going to discuss a little bit about where this problem came from, which is actually work on threshold signatures that we did earlier this year. Um, I guess I just wanted to highlight as a summary that basically what we do in our work is disprove the correlated and mutual correlated agreement conjectures which Ben and Angus also have a nice result on. Um we also give these improved conjectures and um interestingly though basically in this this region that we're discussing this kind of uh near up to capacity region um we're still not entirely sure that

snarks that are operating in this region aren't still secure in the sense that we basically reduced the problem both in our threshold signatures work and in this work to bounded uh distance decoding. So Al yeah uh you just want to jump ahead to that slide. So basically list decoding requires you to find everything that's in a ball but bounded distance decoding just requires you to find one thing. So we kind of reduce everything to this bounded distance decoding in that region and it's possible you could have some assumption there um where snarks are still safe and adaptive security threshold signatures is still safe. So I guess we just want to say as some future work that people might be interested in to look at this bounded distance decoding and a particular quantum attacks. Um and then

if so we do have an attack uh if if someone proves something there and I just want to say also that if somebody proves something about bounded distance decoding not necessarily for the field sizes for snarks but maybe for threshold schnore they would actually also be showing a very interesting separation result between static and adaptive security. So it's like a long-standing open problem in NPC as well. So I just want to plant that seed that anybody who's working in the space if you want to take this look at this adjacent space of bounded distance decoding that would be really helpful on on a number of fronts not just for snarks and yeah that's it. Yeah, there was two more things I wanted to explain. Uh yeah, one of them was this one. Uh I can try and give some detail, but the other one is

that uh we have two more results um in our paper beyond the one the one that's equivalent to Ben Angus one. One of which is uh that list decoding uh list the failure of list decoding implies the failure of correlated agreement. um which uh at least for some parameters. The other one was uh this this sub field um question we were just talking about. Um so so Fenzy and Sanso were having a big discre um discussion of the consequences of of of of listed coding failing in this example. Well, correlated agreement also fails which isn't too surprising like the these

things often happen fail at the same time. Um but yeah the the bounded distance decoding um issue. So yeah if you want to actually forge snarks with this which is what Justin was asking about. So what you typically have is you have something like some quotient that um you know you have something that should be zero on some domain. D is here's not the uh is a conflict with the domain for for the um the code. This could be a different d um you have a snark you want to prove something some polomial expression disappears on some domain um and then you're sound but uh to prove anything else you can get it something unound so

now you have something which is a rational function and not a polomial but if you're taking some linear combination of that with other uh words say random words this gives you something which um is a combination of something that's far and under previous assumptions it should be far But um maybe there's a nearby code. The only issue is you can't find it. Can we actually find this thing? Uh there's no algorithms. So basically, yeah, this problem is is bound to distance decoding. It's one element from the list. The list decoding fails beyond the list of coding capacity. The listed exponential, but maybe finding one element is easy. Um but we really have no clue. Um there are hardness results. Absolutely

none of them cover the uh the case. is interesting. Um, and [clears throat] we're not even sure that, you know, MP hard is useful. Um, there are plenty of problems that are MP hard in the worst case, but the average case is easy. Um, and there's one person that one one paper that um did something on discrete logs for extension fields, which isn't uh postquantum, uh, but it also doesn't really apply. It's more useful, but it still doesn't quite apply. We really have no idea uh about whether the whether um boundaries decoding of random words is is is hard or easy. It looks hard.

Yeah, that's all I wanted to say. >> Awesome. Well, that was an amazing rap. Uh Elizabeth, thank you. And then and Alister, thanks for adding the uh the comments at the end there. Uh I know actually Antonio, who you referenced a couple time um was on he who wrote another paper on this topic, was in here and then left. Uh Justin's still in here. I know Antonio's doing stuff at the EF. So I don't know Justin, if you have anything to briefly about that paper. No, Justin's got something else to add. So um I'll just read it to the four authors. Besides working on attacks, are you also looking to improving provable improving provable security? So I'll let you guys answer the last few minutes and then we'll wrap.

>> Um in my case, no. It looks really hard. I might I I might actually have conjectured some of the things that um Guruswami and and Goyle actually proved. Uh but now they proved it. I really have no idea. >> Yeah, I think I'm the same as Alison. I mean, I'd love to to extend the the proven security gap like there there is still this large gap between one minus root row and other things, but it's uh >> Yeah. >> Yeah. Unfortunately, not personally. I I think we the latest result um from from swastik at all is quite good in that direction. So um

you know outside of us there is stuff getting done but I'm not I'm not doing it right now. >> Um I I noticed another paper relevant to the hardness of um distance decoding. I I don't know how it relates to the other ones um or or whether it's for the right uh parameters just posted that in chat. You see I mean just a very quick note on this. So I know that often when people ask about these things the the place that everyone likes to point to is the um that eat mini example and basically about can you can you get sort of can you break the conjectures there and I think it is probably worth noting that like if you if you give like us control over like

picking some slightly unrealistic parameters I think you can actually use Bener my attack to slightly get to to sort of break the star conjecture like so like this attack like there are weird there are weird sort um regimes where even though BDD is very hard in general, if your code is low, if your code uh is low, well K is low, if your code of dimension is low, then then it's actually not too bad. >> Cool. I this seems odd like the list decoding failure relies on on the um >> so the argument is is that the the the the number of combinations is very small and so it can cancel out your

probability being small when your combin when your list of combinations is so large like we need um this thing is is is not going to work. Uh >> I mean yeah I can copy my attack into chat if you want like it is a very silly attack in some ways because it like we set Q to be we set Q to be small we set N to be like this basically the size of Q but the point to be that like you can actually like when K goes to one you can actually just go and compute these things um sometimes like I'm not claiming this attack actually works in realistic parameter settings but like there is it's certainly not true that these attacks are unnecessarily uncomputable in all cases.

Right? Just in the real examples >> maybe to summarize because we got to wrap up here. So maybe I'll just say because Justin asked the question, hey this is not a constructor or constructive type of attack. And I guess like the answer is I mean the bound for you know the conjecture the original conjecture just dis just proven the bound has been moving pro moved lower in certain maybe cases. There are reasons to believe that an attack could be made constructive using exactly the technique you pointed out Angus or some variant of it. But in general, as Alistair and Elizabeth and you guys pointed out, there's still kind of a lot of open questions about how these things are employed in practice realistically in the parameters that are used. So I think there's something sorry to interrupt there to be said on this constructor thing which is that if I

take if I take a deep hole and 10 or let's say a hundred completely random words and I let uh the proximity parameter be something where if the proportion of random words that are close is is if I can bound that from below and I can it's it's a it's a constructive but random attack where you don't know which one is the is the one that actually attacked it. But it's still constructive. It's just a so-called Las Vegas algorithm that will only >> it's more that we have this close thing.

If I'm actually trying to like um I I do this combination and now we're doing fry with it in order to do fry with it. Do I need to know what the polomial is this close? Probably. Um without that um things get more difficult. I like again we do some more combinations. I need to >> Well, first of all, are we attacking Fry or are we attacking a snark or are we attacking I mean, it it matters. >> What um what what what the naive thing to do here with this this proximity gap failure is um with with this snark what what you do is you have a a bunch of things which are supposedly polinomials. I take a random combination of those and then I do a lowderee test on just that.

>> Sure. >> Or maybe several random combinations if um my soundness isn't good enough. Um and for this specific thing you would need to be able to then run do do fry on the result and for that you would work if you knew what the the nearby code word was uh it would be a low degree polinomial you can go do fry and you just have to your test for in order to operate was never never queries one of the things which is uh where you are far away >> where you're not equal yeah >> true >> also um so if a component fails um then people are not going to want to use things based on that encoded uh component even if there is not a

feasible attack. Um so in some sense for but the problem of designing um schemes and designing parameters the fact that you can't find an attack on the snark if that is the case uh doesn't matter. Um >> yeah, >> you want the >> or whatever it is >> ourselves live off the fact that the attack was not known. Um and and other words like insections that haven't been proved in general.

>> Yeah. I feel like one takeway you should like this is I guess Ben and Mai's point I think that we tried to emphasize is that I think that I think a reasonable take away from all these papers is that is you should try and use proven security. >> Sure. I guess this gets philosophical and is anything proven in cryptography it is people NP right but um I I think that you know if if there's any takeaway from this Angus and I have been shilling the the the proven security regime but uh you you can take that for for uh for what you will >> well no I mean this is I mean I'm gonna wrap up here thank you everyone uh for joining and all the authors I appreciate you guys being flexible in this a non-standard format but I But it was a

very good discussion. You know it was really interesting to hear different perspectives and I think it illuminated this topic which I mean hopefully as the audience can see I mean this is a very dense topic and in many ways I think this like these boundaries are not well understood and the complexity that you know that often times these systems contain when they're deployed you know maybe is not as secure as we potentially believe and there's a lot more work as Elizabeth you hinted at to potentially go down and and and learn more about that and it sounds like there's a bunch of other papers and authors we should invite on uh on the next iteration of ZK study club now that picking it back up. So with that, I just want to say thank you very much to everyone uh for joining and thanks for taking the time and thank

you the authors for presenting today. >> Thanks Alex. >> I'm really glad that we are picking CKO back up. It's it's one of the most enjoyable sort of deep tech things that I watch. >> I know Darren, I've I've enjoyed the chance to see you again and have and have have the benefit of hearing all of your very intelligent questions. I guess what thing I missed the most personally is I didn't have that before. So, uh, so thank you for participating as as I I counted on you two for, uh, for this one here. All right. Thanks everybody. >> Thank you.

Sip.