Mutual Correlated Agreement (Day 2), part 1

Transcript

Okay. >> Yeah. >> Hey, so I'm going to give a very high level overview just to kind of celebrate. I know we kind of had already a few discussions about the conjecture and correlated agreement and the mutual agreement gave yesterday. This is another overview with a bit of a personal like history. At the end, we're going to see kind of a formal definition, a few numbers, and feel free to ask questions. Should be kind of a short document, something long.

Okay, so just to set up some notation, we're talking about read. Okay, so we're going to have some function f. We're going to have the evaluation of the function. Okay, on some domain. So in every element here, 1 to three up to 16. Okay. The function on what is code has some parameters. We have the field that we fix the evaluation. Okay. And the rate of the code which is d / n the degree of the polomial. Okay. Over the size of the domain n when the domain is bigger then the rate becomes smaller. have more redundancy

but that makes it better for the verifier because it's easier for him to capture so I never know if smaller rate is good or bad okay for coding people like a small rate is bad it's more redundancy for crypto people like okay it's good you have less queries right so yeah so in steel steel is like improving rate shift to improve rate and this improve Okay. People told me that like nothing worse.

>> Okay. So, it depends how >> better for the verifier, worse for the prover. >> Yeah. It's better for the verifier, worse for the proof. Yeah. Okay. Okay. So, some of these slides were made by my student God and then later we have some slides made by Jako or at least some of these slides. Okay. So we have our function f we have the ination do okay and now we have in green this is kind of the part that agrees with some code so f is a arbitary function doesn't have to be a code okay a code is going to be when f is actually a function but

f could just be close to a function for close I mean for example here the green part agrees with some pol green part does not agree Okay. And then this delta is the distance from the code. Okay. In general, the distance is the the distance to the closest. Okay. So the distance could be small, the distance could be big. Okay. Actually in general we're thinking like the previous session when we take we took f of xus beta x right. So if beta if f doesn't equal beta zero then this quotient is actually going to be very

far. Okay. So it's going to look more like this. Well if half then it's the green part will be like a question. Okay. So now we're going to continue going to have mostly green kind of notation but in general okay what you should think in your mind is that one function f could be close to many different polomials.

Okay. So now we see kind of different colors and each one is a different pol that it's close to on a different region and even this drawing is not truthful because actually the places that that it's close to different polomials could intersect. Okay. So this is just a simplicity of of drawing. Okay. But they actually intersect and could be like intersect with many different polomials and that's actually what makes things kind of much harder. Okay. The drawings for now are going to kind of going to be in the in the unique decoding radius. So we're going to have one green area. But you always should think in your mind that we have many of these different green area with different colors.

Okay. So what is the limit? So now I have many functions here kind ofation change to C but the C is is the same F. Okay. Just because we're thinking of them as columns or some other thing but for now it doesn't matter. So we have many functions. We never want to allow the J test one function, right? What do we do? We want to batch them together. Okay, great. So we're going to take a random linear combination of all these functions to create this C star which is a random combination and then we're going to you know just test C star.

Okay. So we need some promise on let's say we tested C star and we found out that C star is very close to low degree. What does it tell me about all the CIS? Right, this is kind of the basic question we're asking. And this is exactly what the proximity gap gives us. And this is a theorem by Okay, anybody remember the >> safar?

Okay great. Thanks. So this actually started this kind of agreement I think already go back to GDW. So this is where they kind of had this initial result but okay we're focusing on this formulation. So they're saying if okay with high probability C star is going to be close to it. Okay.

So just before I continue obviously I cannot say anything worse case like maybe all the alphas are zero and then C star is just zero. Okay like regardless of this yeah it could be that C star is close to okay kind of have to say something probabilistic. I want to say if the probability of the alphas that C star is close to is bigger than some small epsilon. Okay. And we're going to see exactly what is epsilon currently just you know something and then it means that for every J every CJ is close. Okay. And actually it's very

important here it's the same distance parameter. Okay. So it kind of the GBW theorem kind of had this and here it was kind of two. So they they lost something and this last fourth line would be very bad because you have like many steps you're going to lose each time another factor. >> Just a very strong question about this statement. Um we're checking over all possible alphas. So is it really helpful to look at this as a probabilistic statement or just a counting like the set of alphas that >> counting it's the same >> you just want to say that the number of alphas that make this close is It's large enough

>> is it does >> it mean that all of them are close? >> Just in terms of like notation or even in how we describe the statement is it helpful to have as a probability or just like size of set >> probability does become helpful for higher dimensional statements when you're quantifying over not just a one-dimensional parameter but like something bigger. Then if you talk about count you have this you have a kind of q to the n minus one factor. In other words, that the expression looks more convenient when it's about probability because then you just have one Q in the denominator instead of you know if like let's say I don't know

K is a dimension of the challenge space you know something like epsilon over Q looks nicer than Q to the K minus >> in short probability is a normalized thing so it's always easier to look at something normalized I don't know where the alpha is coming from is it one alpha here it's kind of also counting is always kind of hard. I'm asking because I've seen a lot of people confused by the statement like you have this if then property and the if is conditioned on a probability being higher than something I can see how might confuse you >> in the book many times you just say oh it's let's define a set of all but for the definition

would it be interesting to accept some kind of distance degradation in order to beta epsilon. >> Okay, that's an excellent question. So, as I said, we started out with a distanceation, okay, by a factor of two and the error actually was was much better. Okay, that was fine for the GBW application for F and steering wheel. I I think like that wouldn't be so good. Maybe if you have a think if you if you by a factor of two that means like much more queries. I don't know if it's like volage. If you have a like additive loss here minus something, I think that would

be fine. Okay, fine. So you lose a bit in the distance like 0.1 or you know 01 and uh and maybe using that you can make the arrow go down and then I can use a smaller field. Actually that would be amazing. Yes. Like I think that when you do like the word like proof even if you lose a bit since you way of course switching to something with new fresh distance you're probably kind of fine. So you this is something that you can try to do to reduce the error but you have to analy >> no you're right but even in weird if you lose a factor of two I think you two is too bad.

>> Yeah 200 is bad. Is there any intuition what happens with with this thing when we adjust or like when it's like what happens so this should be okay this theorem is to for all of you in some regime okay obviously up to Johnson capacity I'm going to get to the regime in a second but inside the regime that like you're asking if epsilon changes does it become zero at some point >> I don't think it becomes modify epilon

if you modify >> if you modify then it's easier it's still not easy so how do I >> how to understand this when we make new small. It means that we claim some that the result is very very close to some. >> Yeah. But you start with something that is nucleus, you end with something that is close. So the two statements or one mu and a big mu and a small mu they're incomparable statements.

>> Yeah. >> You end with something smaller but you start with something smaller. >> Yeah. And for small it means like if if you appear very very close means that your inputs were also very very close >> and big epsilon means that multip means that you might have a good chance of this thing being close or maybe even a co CI looking back at the system right will be booster

error while the mu is the number of periods and typically turns out when when mu is like close to zero the color you go to zero the easier the thing is to prove when mu is larger things become harder to prove >> you well usually like you get like worse ep the way you prove these things you you find a mu that you care about then you do the proof and that gives an epsilon. So typically what happens is that uh the more mu grows the larger epsilon so the error becomes worse. For example, like in the coding the error is kind of like N / S in Johnson down something like N² F

plus terms and then up to capacity we don't know but you know of course you know epsilon is one but how to understand this when you say new grows epsilon grows what does it mean? That means like when new grows you you cannot state the form anymore. You can only for so this is stated like for any mu in a regime you have this okay so I'm not sure about like if you fix particular maybe you get some epsilon that kind of epsilon of mu that is slightly better I don't know such a

Maybe it helps at least for me it helps a lot at the beginning when I'm coming from the polomial world you know and enters and reads all along like two years ago and it helped me so so as a poly an equivalent statement would be if a random linear combination of polomials is of certain low degree then the same holds for each of it and the proof is actually in the polarity model quite trivial because if one of those initial one wouldn't speak of that low same same degree bound there is a coefficient which is non zero for a higher monomial and you can easily argue by simple and get something like 1 /

>> yeah yeah but it's a simpler statement because statement doesn't involve quant and the thing is now uh is now that we restrict not to or the fe we commit on something quite small domain the thing gets much more subtesting things. So first of all you can never assure that you 100% committed. It is a polomial only proximity first of all and second uh it's kind of hard >> to even quantify knowing that you you're

never sure you have a polom. It's kind of hard to quantify what can all happen just taking this random linear combination. I don't know this was no explanation but maybe the direction has saying like if I take an combination of actually actual polomials okay then the probability that the monial with the highest power is canled out is one over okay and if that happens I actually get a lower degree pol that's very easy to prove >> here it's harder because you're looking at you're saying Okay, the C star agrees on this three locations, right? I I I

want to show that all the CI also agree on some three locations. I don't want even the event that C star on four locations like I don't want even be slightly like even one element closer to thinking. Okay, >> jumping. >> So if I may say this again, when you say like when M grows, exon grows, you sort of say that when m grows, uh it's not enough to have just a handful of alphas uh for which uh this closeness holds.

You have to collect more alphas and only after you collect sufficient many alphas for bigger you have to have more. When you have more alphas, then it starts being true that uh the inputs are also closed but if maybe for some just a few outputs doesn't mean okay so this is the original statement this only tells me that taking random combination preserves the distance okay I had things that had some distance and the random combination also has the same distance in this paper they actually the a stronger property correlated

agreement. Okay, a strictly stronger property turns out to be very very useful. Actually, we use it in many places, not only kind of in batching and and testing. Okay. Yeah, obviously you can batch it only test. Okay. So, what it showed is that all the CJ is like this cannot be the picture. This is not reality. This does is not What happens when you take a random combination of things? If you would take a random combination of these things, actually you'll get something that's very very okay star would be very very far. What actually you can prove is that if C star looks like this, then all the what they show that all the CJs have

correlated agreement. Not only that they're mu close to low degree, they're new close to degree on the same set of elements on the same subset of our relation. So okay so the picture actually looks like this okay and all the CJs kind of correlated somewhere okay is the statement some kind of symmetrical respect of all you can swap star depends on C1 right there's no swapping >> C1 and C star is a function Right then you can also

tell me something about C1 and C I can like think of C2 as like C1 plus alpha C2 minus C2 or whatever. If you look at the statement just a linear combination and you can select any of those is combination of everything else with the same amount. You can write C1 as a linear combination

of C star and C2 of CCL and maybe apply the same result to get neutral but C star is not defined we start we don't have C star we after we chose alpha we have C star >> now we want to claim something so I I don't know what it means to kind of [Music] guess there is no precise rules on the position of the green square anywhere >> they can be. Yeah.

>> Okay. We can view it as a linear space and then we can say like if you have a linear space and a big fraction of this linear is close then any basis point any set of basis point any point actually okay so now I have this picture okay before I continue to mutual agreement this cannot be the picture this is false picture >> okay good if I have agreement on some domain then on this domain a random combination of polinomials is obviously

a polomial okay that's true for any alpha right with probability one okay it doesn't matter so obviously I should have the quality down here okay however remember we're not in the code like this I can have many green areas okay so nobody said that C star okay so think fine have a green area down below But it could be that C star has another green area. Okay. Nobody that says that anytime C star has a green area then the CIS also have the same green area.

Okay. So in actually this started actually in AC. Okay. This is a paper kind of already two years ago. What we had there is we kind of We kind of thought that what we what we have is mutual correlated and then during the we kind of realized that oh we actually don't have mutual so what is mutual according to agreement so we we did an ACY we kind of conjecture we didn't really conjecture it back then back then we kind of just modified not to work with mutual agreement it wasn't a practical scheme so we kind of didn't care of you know

having a big cost but conjecture that not only the CJs but also C star itself all of them should have correlated okay what it means is that the picture looks like this okay in the unique decoding radius it should look like this in the this decoding radius it looks like this for every color the greens are correlated the purple are correlated okay any place that C star is close to the green all the CI are close to the at the same place. C star in general is going to be close to the degree in many different places. Okay. And each and every one of them implies that all the CIS are close

to the degree the same. Okay. So this is M with high probability of the alpha. Okay. Except for some all the CIS and C are going to have the excuse me is the error is it the same from for all the kind of agreements that we talked about >> we'll see currently it's a conjecture right so yeah conjecture it's the same okay at the time of this talk it's a conjecture and we'll get into it in a second but okay so in ACY we kind of encounter this problem We didn't know what to do.

We just changed the whole analysis to to not have a quality agreement. But every time I give a talk about it, I'm saying like look, let's look at a simpler version of the protocol or just assume this conjecture and actually the protocol just okay later on it turns out that this property is actually very useful in practice and that's why we actually wanted to conjecture it and then started proving it. Okay. So before continue. I just wanted to show you that you can just see from the picture that this conjecture is true for the unique decoding variance. Okay, what do I mean?

I mean that it follows from from the standard theorem that the CIS have agreement. Why? Assume that CI has correlated agreement. We're in the unique decoding radius. So there's only one green area. Then we know that if all of them have correlated agreement, C have collated ag. And if he has collected a limit here, he cannot have another one. Okay, he cannot have two because we're in the unique decoding radius. And the distance of C star is going to be the same distance, okay, by the same. So C star is also going to be the decoding radius. So in the unique decoding radius, we have only one. Okay, so it's really like if only.

So this has to be the picture. Okay, where this thing it doesn't work is in the decoding like this okay I don't know that somehow C star you know by taking random combination kind of invented a new domain where it's close to a degree well the CIS are not close okay that's kind of not when we put something do we use like the same kind of technique approximate things.

>> Okay, that's a good question for people that actually pitch a can tell I start by conjecturing it and kind of so I got some students to read this paper and explain the proof to me and they never So in the unique coding radius I understand the proof and I think actually with the student we we wrote down like that's much simpler and kind of half the length okay for unique coding for coding I kind of have understand the not and

yeah I don't know I asked and like okay just go both tell me if it also satisfies the mutual cooperative agreement and I'll just you know cite it in my paper and that's it like communication and they like yeah obviously because no but yeah but no but and then I don't know life went on and I I didn't get like uh they said probably but not >> with high probability >> with high probability but I wanted them to like sit down and do it think a bit.

Yeah. But luckily we have amazing people and stuff. You'll see it in a second. Okay. So I just wanted to show the formal statement. If you look at the paper and you see this definition, okay, so we can kind of go over it. Okay. So we have a linear code. We have some J which is a proximity generator. Forget about this. This is just the thing that samples the alphas. Okay.

Some sometimes you just sample random alpha. Some sometimes alpha J is going to be some alpha to the J. Okay. So you kind of abstract this away with some generator but let's forget about that. So we say that it has mutual quality limit with proximity bound B star. This is kind of up to what distance you can do. Okay. Johnson capacity stop and you get some L. Okay. This is epsilon again in the paper we can have many epsilons. So we cannot just call it epsilon.

Okay. for every n volt okay that we take and for every distance that it's between one and between 0 and 1 minus b star okay so think 1 - 1 depending okay so the following holds what is the following okay so the probability that something hold is small okay so you have a small error of something holding So the probability that notice that there exists a set S S is the set the three dots the three green places okay the place that we're going to have to so

with hyper mobility we're not going to have any set S okay of the appropriate size okay obviously we're looking at some size okay distance okay such that what such that there exist a code in the code. Okay, so actually actual polomial such that if you look at this polomial restricted to S. Okay, only the S part is going to equal the random linear combination of the case. Okay, so this means that the C star is close to low degree on S. Okay, however, there exist at least one of them. Okay, that this one doesn't agree with any

code word you find on S. Okay, >> this means this means we do not have correl and the statement says that there's not going to exist such an S of the appropriate size. >> Yeah. So restating in accounting arguments um the way I usually say it is like the number of challenges that create agreement domains is small. >> What is the domain?

>> Uh this green stuff. So the number of challenges that agreement do >> exactly the number of challenges that make the right hand side of the drawing have more green squares than the left hand side is small. >> More. >> Yeah. more colors. >> So maybe one thing that that I first found confusing when I first saw this is a bit of the notation here because S is a set but U of S is treated as a vector here. So is kind of so for example these three location >> right but in in an ordered way >> the restriction of you to to this location

>> but it's in an ordered it's ordered right >> it's >> so if this U of s equals sum of something if the left is one to three and right is 3 to one they are not equal but but s is a set so it doesn't have an order that that is what confused me first >> okay so It's uh fine as all the >> I think it's >> I can take the blame on >> um I was just going to point out the same thing that Ben did. Uh is there a way of rephrasing this? Um because when you when you ask about probability you you care about random variables or

functions of random variables but now you're stating a probability about the existence of a set. So it's for me it's kind of alien to look at it that way and um have you ever thought of rewriting this? I did think of rewriting this and then I did and this is the result. >> So again this is a random variable right? So this thing is a random variable.

Okay so we have the inputs to the thing that we are fixed. Okay, this is the random variable and then we're kind of saying yeah what is the probability that this entire predicate of this variable is satisfied and yeah it's a strong statement because it says the probability that there exist a set right and just to make sure you cannot union bound you cannot say okay let's fix the set outside and then just union bound over all sets okay then you would lose kind of the size of s choose n okay which a huge factor.

I think you that there's maybe a way that maybe for some people would be simpler if you write it the opposite like the counter event let's say and then you write the counter event >> look I my recommendation in general okay in a crypto paper you always upper bound >> okay once you start lower bounding good events >> but no but I mean the the thing that you visualized is the counter Yeah. What is a hash function? The probability that you find the collision is small.

Okay. It means that most adversaries with high probability we won't find the collision. I never state it like this. Right? Except the bad event. But in your mind, you also think this is the bad event. So what is the good event? With most probability like no such set exist meaning all sets are going to satisfy both the >> right. But for just for the counter event you can actually write it as an implication. that maybe >> that closer to the correlation if and only if >> right it's an if or if it's like every set that satisfies one satisfies the other so it's a if and only if I agree because we know that if you satisfy the left side it satisfies the right side and this just says that if you satisfy

the right side it satisfies the left side so together you actually get in >> for >> so you can say in other words because I also in the beginning I recall that it was tough to parse the definition the work paper >> so so it's like small the bad event would be to bad event would be to find S for which the random linear combination coses with the current cohort but that set is want a set of correlated agreement because it

was for me hard to parse the third line >> that line some >> yeah doesn't agree with the code on this >> yeah I don't know the the intuition is on top you see the right >> squares the green squares on the right >> and you look at them and what you want is that if you see a green square on the right that means there are green squares on the left the statement says if you see a green square on the right The probability there will be no green square in some of the columns on the left is low.

>> Yeah. >> And the probability that there will be orange squares on the left but not on the right is also low. Right. You need to consider other other agreement sets. S >> that you every color on the right is also on the left. >> Exactly. >> Yeah. >> Okay. You need to add more colors. Any set that satisfies this, any color on the right, any set that satisfies this is also on the left in the same position. >> Exactly. I think this combination is is kind of nice up to maybe this or not. Yeah. This is an older set and then okay up to kind of this mathematical notation.

>> Have you ever thought of thinking of this problem as a B and problem >> like throwing combining the following terms. >> Look, it is similar in many cases. I actually worked very hard to prove that kind of correlated and mutual are are the same. And then you kind of go into all these probability counts and I actually can't prove it in some cases with a wall epsilon but like you're saying okay fine but essentially because of this strong requirement that we want there's no S then it's very hard you cannot union bound you don't know you

cannot fix S if you fix S then you're saying okay you can union bound over any other point to somehow be attached to S okay like some S and what's the probability that C star on some other point you know is going to be the exact polomial that S on cine that is small and you can unbound over N find you pay a factor of N but that is kind of if S is fixed And the hard part is here is not okay good. So we started by just conjecturing. Okay. So we said that yeah

mutual correlated agreement up to Johnson bound would have the same bound as the provable bound of mutual agreement. Okay. Of correlated agreement. So for correlated agreement the world is proven and this one is conjectured here at that point of time both of them are conjectures okay just two types of conjecture okay again for the unique coding like you can prove it easily okay this is a more recent state of affairs and maybe you can help me with citing the people that pulled this. So up to unique coding.

Okay, we know that this is correlated agreement and mutual agreement and both have the smallest error n / f. Okay, and n / f is almost tight. Actually the tight bound is n. This is actually okay. But if you forget about this mu, if you think of it, it's just a con. This is actually >> what is mu distance >> the distance like delta. So I mean there is delta on the left side and on the right side wait so I'm in deton >> yeah because so I said epsilon delta is

n it's so any delta in the index radius. So it just ignores delta but it has some bound of delta. >> That's that's the bound of >> okay that's the bound of delta 1us2. Okay. So I said if you want to be slightly more precise you can actually put in delta inside this expression. Okay. I think um n / can be attained exactly right. I think I think almost like I think delta can be a thing >> I think >> or I don't remember it's something close to >> but yeah that's very small because it's

not like decoding you have n you can pull both and the fact that the same is it proven or conjecture >> so in general in the general statement. I don't know anything here. Mutually or correlated, they might have different errors. It happens to be that we can put both with the same error. Okay, it happens to be like maybe it hints that they're equivalent. Okay, but I don't know how to show you genetically that they're equivalent. Okay, it just happened to be that I know how to prove colleg.

You look at the poof and kind of say, oh, the same almost the same also proves mutual the same. Okay. And the attacks all the same attack and then you it's kind of the best attack and you can match it. Then you have what's called the main that I don't like so much one and a half Johnson bound and the Johnson bound. Okay. So for both of them and now we know that they have the same error. Okay. For mut so what was conjecture on the previous side is now actually the so this is you don't remember now.

Johnson wrestle >> one and a half Johnson at the time right in the 1.5 Johnson the original 1.5 Johnson group >> this the original for much you say >> for just correlated deep fried the first 1.5 Johnson I think at the time >> that was the deep fried paper >> yeah deep fried I think the original 5 then they did the >> Yeah, they did the global analysis, right? I never uh recall the names.

Chinese team. >> Yeah. GKL. >> Yeah. >> And then this one also >> the like the the one in agreement is so BC and is why We're not sure it's ego. It's not. >> So currently what we know is up to the Johnson bound. Okay, we actually have an exact same error in both cases. This is, you know, a coincidence. Okay, I kind of think it's not a coincidence and they look I I I find it hard to believe that we have one and not the other. They look

like very tightly together, but we don't have this generic proof that one one implies the other. Okay. Obviously mutual implies correlated but not but okay. >> Yeah. >> If I understood correctly like the 1.5 Johnson is for gener more generic code than code and this >> yeah you're right. So this the Johnson B is for Solomon the one and a half is for any linear code. Right. And do we have something for NPS codes generically? I don't think I have something better than the one and the is also just I think the unique

decoding is also I think is also included. Yeah. Yeah. So what I wanted to say is that sometimes NF is is very nice because then you can take a smaller field. Okay. I mean you go to the listing coding you have like bigger errors. I want to point out slightly and not relevant to now to this talk but you can always do minding not only for the query phase but for all the rounds of the protocol. So even if you have a round in f or in some protocol that has some error you know

some d over f and you're kind of you want 100 bits of security okay and your uh your field is is not large enough okay and you lose some bits because of you can add blinding to every round of the protocol you can add like five six 10 bits of grinding it really doesn't cost a lot and then in some cases you can kind of reduce the take care of the extension field that you okay if you have if you take Godox you want only the second extension you don't want to take the third one okay and then maybe you have error D over F your D may be 30 okay you promise the client 110 bits of security so you're kind of

missing some 10 15 bits of security just add 15 bits of binding to this round and and you're fine here The E is sharp as a function of delta, right? Yep. Okay, correct. Yeah, I remember the other thing that was confusing me about it. >> So, yeah, is kind of I I can't really go up to Johnson. >> Yes. >> It is like the the optimal bound you can get up to one minus the Johnson minus EA. >> Yeah. >> Okay. And then you pay something that depends on EA. If you set EA to be zero, this error kind of becomes >> okay. The other thing that always confuses me about this, but this is sort of like obvious in some sense. E is less than one. So, big on the denom >> like 0.01 The other one is making small because NF is like

everything else. >> In practice, I saw people kind of ignoring that assume that >> that's why you should do the extra query for good luck. >> Extra credit for good luck. Exactly. >> Yeah. And finally we can conjecture but now we just why not conjecture the same error. Okay. We kind of have the same holes in in all the cases. This is the conjecture for the quality agreement. We just have more or less the same conure for the mutual. Okay. You can actually play with this simplifying.

How many bits can you add? Like is there a reason not to like push the security on the part? Like if you grind with WD bits, okay, you gain the W bits per that round. It means that the P will have to work to to two to the W hashes. Okay, but the honest does it once per round. So if you add like 15 bits of grinding, doing two to the 15 hashes on my math takes like 10 millconds or something like that, okay? Or 100 milliseconds and then you only do it once around. So if I add 15 15, I'm not paying 2 to the 45, okay?

I'm paying three times 2 to the 50. Okay. So just do three times I need to solve it. So that's what it cost to the honest and then you can add you you every round you can add a different amount. This round you can add three bits of binding. This round you can add 10 bits of like whatever you want. It makes sense. Thank you. >> This is notable only your big. So if if D is small compared to this small then you take your field can be small.

>> Yes. But then if D is small then >> okay if D is small to begin with and your field is 128 bits then okay >> I mean then when D is small then the pro work is already small. If you do if you add yeah becomes become significant. >> Again depending on the application sometimes don't care. In some cases, maybe you just want a big server creating poofs and he's willing to even have assets to, you know, do a lot of grinding. Okay, just wants to compress books to be smaller. Okay, maybe this is a server that kind of aggregates. So, he takes many PS and then he just want to aggregate them to one that is very small. So, he doesn't mind like doing a lot of lot of grinding and then creating a small and publishing it. So, depends

on the application. Typically, you're right. What I do is I measure the amount of hashes that Google does >> already. >> Okay. Without guiding and then I say okay let's add like 10%. >> Yeah. You can add the same then proof of work just double. >> Yeah. But I nobody wants to double. I add like 10 20% and I say that's a good amount of Okay. Yeah. Okay. So this is a conjecture and this is kind of the prices to I guess anyone in the life. It's not like somebody moves to the limit and unfinish it. We don't give him just mention like this changes the query complexity you want. So

if your rate is half okay then the number of queries you need to do if you're in the unique decoding you kind of need 308 queries. This is to get a bit of security. Okay. If one and a half Johnson this is the amount of query the Johnson bound it slightly goes down and then capacity bound it's exactly 128 okay why because every query gives you one bit of security because always half okay up to here it's say like ignoring the AA and stuff like that okay if you have a small then I do plus one okay plus everybody I think it's getting worse when we go from jobs >> I think

Okay. So, yeah, this is like a map. J, did you make this map? Yes. Okay. It's very nice. It tells you like which version you want to take. Okay. It depends on the parameters, right? Third square root is sometimes worse or better than over two. Okay. So, it depends on the >> because the batching >> and if you're comfortable with conjecture, you just take the capacity. That's always the best. If you're not comfortable with the conjecture, if you have Should you just take the exam? If not, you check if y is bigger than 0.23.

This is kind of the >> the question. Okay. Yes, you take. If not, you take the >> is the point that 1.5 can be worse than you. >> Yeah. >> Exactly. This is this is where >> I have one question. >> What happened with the number of words? >> Yeah. Good. So okay. So good. So here we kind of stated this.

So this is for L world right and we have the dependency on L. Okay. Now this depends if you take this depends kind of on your generator. If you take a two random linear combination then usually you don't settle this factor and if you take powers of alpha then suddenly the sponsor is has the degree L and not the degree one you kind of lose this factor of L. Okay in these results it's kind of this is taken for L= 2. Okay, this is for L= >> this with equal two. But I think these are the same results even for big L as long as you take a random combination.

Yeah. >> Okay. In practice, we don't like to take random combination. >> It should be absorbed by the whole philosophy, >> right? >> Yeah. In practice, we want like one alpha and then taking powers of this alpha, it's less hesit. But if you have many words, can't you apply the the like recursively split in two >> so for random linear combination >> I think that's I'm not sure I think but for powers of alpha >> or okay you can do it and then you have this >> use multilinear combinations of randomnesses it works black box uh also if you choose for

every component every separate randomness there are black box reduction to a single two polomials and one randomness case >> just will you have then not a button there >> I'm sorry >> I mean with this approach if you just split two can't you have better than a here >> yes I mean in this case l is l minus one is equal to one So notice that in this comes from this very specific choice of random mass.

>> Okay. So notice that here we define the generator to be one square up to alpha nus one. So that's why here we we need to pick >> anyway the relevance that should be given to the randomness that generator is secondary. >> What do you mean secondary? >> Like it's like the way you randomly combine the words uh it shouldn't matter. >> No, every generator has a different error. The best generator is to use two randomness. This is kind of absolute random generator. So you additionally have some error because you use less

random bits. >> Okay. >> Okay. you only use one random where instead of n random you expect to have more like there's much more constraint. So how do you how do you relate this uh slide with the one that we had before where there was no conditional force on the alphas? >> Yeah. So here I'm saying this is a L full gen. I say that it has mutual correlated with L if satisfies this definition >> and the conjecture was saying that for this specific gen we have this.

>> Okay. also just if 116 then kind of every query gives me four bits of security at least four bits of security and then when you go back to the capacity bound look we actually can only have 16 queries >> all of the number there are >> no why 16 >> I don't know >> no this is a mistake >> is it 128 by >> no you you divide by Okay. So, this number, >> no, it's not 16.

>> It's four bits. 128 over four. >> Wait, but you divided by two each time. >> Yeah, you divided by two. But >> then >> this is over one. This is 152. This should be 128 over three and this should be 128 over four. >> Okay, so this is 32 bits without grinding. If you do grinding, you can have like let's say 100, which is 25.

Okay, I'm sorry. I'm a theoretical guy. Number computing. Yeah, and if you only want 100 bits of security and use 30 bits of grinding, then you only need 70 bits of security here. And then if you have rate one over 16, you need only 70 over four queries. Okay, which is kind of already becoming less than 20. Okay, small numbers. >> Here the numbers are supposed to [Music] >> but it's the number of samples, right?

>> But that's right. >> What? >> No, >> 16 is not correct. 16 should be >> you just left the half number sample then the Johnson right that's what I recall either >> but the Johnson is not >> what >> it's half of the Johnson but the Johnson >> yeah I think the wrong I >> okay I'll fix the we'll fix the slides and then we'll listen I just want to finish with the last thing okay so in the weird paper we actually use mutual correlates agreement to pull this lema this coding the lema or something like

that and actually there we show that they're equivalent so this is if you assume the lema is correct then hold and vice versa so what is the lema I'll try to so don't look at the lema first let's look at the then we go we go up to time >> uh yeah Okay. So I'll just finish this slide and that's it. Okay. So okay. So now we have this quality the limit and this is the picture. Okay. Now what we can do is we can look at the list decoding of this world. Okay. Meaning all the code words that have some distance delta to C star. Okay. It has some decoding and there's many code

words there. Okay. So this is circle number one. Okay. Now we can look at the list decoding of each of the CIS. Okay, each one has a list decoding has a sub inter list. Okay. Yeah. Right. So yeah. So looking at it like as a one inter code. Okay. All of them. Okay. Now what the level says is that if you take these you take a random linear combination and now you do this decoding

you're going to get the same set of polomials as if you first took the list decoding of the CIS and then did the random linear combination. Okay. So you don't expect to get something different and this kind of I think it's a very nice that actually follows from agreement. You say something about this. >> It's super nice. And the other way you can think about is that if each element in the list decoding of the output is explained by an element in the list of interle code. So I kind of like you know one direction is obvious like if I have like things in the left hand side I can move them to the right hand side because

you know code words map to uh other code words. What's interesting is that whenever I look at something on the right hand side. I can explain it in terms of things on the left hand side. >> Can I see if I go to any way? >> Yes, you can like I have it in one of my slides. It's very >> Wait, right and left. You're talking about the below >> this. >> Okay. So, kind you start here and you can either go here or first take a random combination and then take a coding. Okay. or take a list decoding and then add little combination and you get the same set and yeah Jako sent it I think nicely if you

look at the C star you look at the list decoding you want to kind of explain why is this polomial close to C star you're like oh there is an explanation I go to the CIS I look at the list decoding oh it's it's there you decompose that polomial to to things okay I'm just going to finish with Thanks. [Applause]