Mutual Correlated Agreement (Day 2), part 2

Transcript

Thanks. >> Okay. Uh I'm going to make it simple after one hour session uh on neutral correlated agreement. Actually I mean not focus so much on my concrete findings of my work. I would focus let's say one one of the aspects that led my my quite technical work on proof acceptance of what secure so I call just here the correlated agreement because uh okay left and right so okay sorry okay just just just recap >> what's correlated agreement what's a

correlated agreement theorem a cat >> don't even have a picture of a cat. >> It's correlated. >> Okay. So given given two words F is final f so finite f word over domain D. Uh if with notable probability the random linear combination C is the skull I choose. So the probabilities in the scal choosing from for for few of these these are only the accommodations close to the code then also and I I just encode and cipher correlated agreement as the vector wise the the interle code

interle word uh correlates with uh with a pair of poloms that's what correlated says but just vector wise vector wise equality. Okay, so that's correlated agreement. Uh and uh the thing is if you just go all three of all the theorems uh starting from the very first uh up to to the proximity gaps paper the way it's stated uh is um oh I see I did the wrong computation here so I cannot click through. So no, so it's always the full slide. Sorry. So so so as stated it

seems like that the agreement sets between the random linear combination and it's close polomial or closest polomial to make it simple that this agreement set and the agreement set where we have correlated agreement the left hand side in in in in your slides that there is no relation between them. That's why you al also see in a slides the first picture right you know on the right hand side we have green area here then the green area of cor place but the thing is that's only seemingly the case that's only seemingly the case it's just the way how it's stated if you go behind the curtain if you look into the proofs

it's uh there's one let me just go back uh there's one central technique or let's say one one central property that is that is obtained before doing the final step that ded uses correlated agreement and that's correlated agreement what I call colarity approximates in short and what is what it says is the following again we start with the two words u0 or u1 or over the domain with no type of probability small probability the random linear combination is close to some polomial that does nothing new yet then a fraction of these polomials of this proximates

lies on the line. So gives you already also the pictures of how how like proximity gaps is often explained when not using the notion of probability the lie on the line and uh the funny thing is sorry for this at once I can recompile it this is just just one one no sorry let's let's keep with it so before I mess it up yeah So okay so so the main thing is this is really the property from which you derive eventually correlated it's a stronger property uh and and the way how you do

it I would like to go through that proves it's it's really super simple elementary proof and uh yeah so colinear so actually the way how correlated be stated loses a lot of information and uh the funny thing is this element are true standard argument I will demonstrate this works also under under other uh in other environment mean it's under con so correlated agreement under constraints for example when I proved baseball secure in LDR I needed something I called the soup code correlated agreement theorem or or in in

let's A correlated agreement theorem for constraint resolving codes. Something like if the random linear combination is close to a polomial satisfying certain linear constraints then al then then the components of the linear combination have correlated agreement with P1 P2 which also are not just polomials but satisfy the same linear conraint. So, so that was really helpful to to do the analysis of base fall or fraas and lately also were um so also weighted cuts as the weighted

correlated theorem is used by by all these Friday protocols which have a uh which have a correlated type of testing like one sample where you check along it's uh use this one sample to to check all these consistency relations between the four links not just of one round but of many rounds. So that's it also can also considered like a correlated agreement agreement theory on the constraints and uh more lately when I was writing this two white paper multi-dommain fry is a bit pain in the neck when you consider it also in LDR when when we want to prove it sufficiently secure well let's say meaningful secure So that's uh it's

it's it meets your expectation in practice in terms of security parameters. There was even another uh correlated agreement theory on the constraints what which I call a set specific stop cut was necessary. So uh in short um it's colinearity property a fraction of the approximates are colinear this is this will turn out to be well once I show you now this this very element turns out to be a local version of the picture we have when we have this uh from from a slide it's a local version someense of mutual correlated

agreement and in fact it turns out to be a component in all the proofs I know about mutual correlated agreement instead of the ones of others Chinese team or now most recently the Johnson bound for solo codes >> what does local mean here >> it's like uh I will come back to that later in more detail but it's just like uh that you only focus focus on a fraction of the pro approximates. So you focus on one line. The way how you prove mutual correlator agreement is at some sense to to you keep track of all the possible lines where you approximate

might see to be situated on. So it's just a one instead. It's a kind of you can say ma correlated agreement theory in other words would be list correlated agreement theory >> sorry >> list correlated would be just a different name for it. Okay sorry for this thing so so just look at the top. Yeah. So I will now give you give give you give you some of an intuition uh about the standard argument. So what is the presumptions? So so so this here is is is is my collection of my fraction of

approximates uh which I found already. Oh okay super cool the lie on the line and the line is written as one polomial plus c times the other pol right that's like yeah the line and then just Considered the agreement set here, the correlated agreement set between between my two words I start from and the two polomials that span the line and my claim is if this fraction of approximate is large enough that's the size of S the index set from my yeah the size of S larger than the domain size N is the size of D

Then we already know that's exactly the picture of Elon's slides. We already know that this correlated agreement set is equal identical to one of the agreement sets in my collection of proximates and it's it's really a threeliner. I mean you can present it as a threeliner yet it's always something I love to revisit uh because there are refinements of this of all flavors useful refinements I just present here the simplest way to argue and it is so so so assume assume it it's

not the case what does it mean so assume that all the agreement sets from my proximates that of the line are not equal to a to the to to to the to the correlator itself. Means there must be always a point outside A. Right? And it means if you look at the disagree correlated disagreement set just the complement of A it means AC each AC has a point in there. Right?

Now fix a point in the disagreement. Let's forget for a second what I said before. So just look at the disagreement point fix the point here and ask yourself uh for how many changes Z I can cancel out this agreement which means you know if if you just take U0 in indeterminate Z we don't know yet what it going to be and plus you want the random linear combination symbolically also the same for the two polomials because we said Here at this point C there are unequal these are different linear polomials. Therefore they can have only one root in common or in other words that root or let's say

one root in common that was bit precise. can have only one value where left and right is little right hand right hand side where you coinc so in other words there's at most one Z where you where inequality gets equality or where we had correlated disagreement and end up with agreement of the Romania combination so this is a separate observation For any correlated disagreement, any point of correlated disagreement, there's only one C that cancels out that arrow

that disagreement. Sorry. Yeah. And now let's go back. What is the assumption? Let's assume that it's not the case that A equals sum of the agreement sets of my approximates. So that means all agreement sets must be different to A. All agreement sets therefore must have a point in that set. Since these agreement sets But it's an agreement set means it must

correspond to a Z cancels out already. Since this cancel is unique, it means that for each different AC uh there must occupy different different regions of my of my disagreement set and consequently there cannot be too many of these C's. Uh actually it's bounded by the size of the disagreement set. We don't know how large it is actually. So it's at least bound to the size of the domain and that's how you argue.

So that means uh if let's let's rewind here. So if all of my agreement sets would be different to a then the side says set of then the number of approximately I'm talking about cannot be large. That's that's the so if it's already that larger then we must have equality of one of those sets which is exactly the mual correlated agreement setting in a local fraction because if you look more carefully at definition of m correlated agreement it's like not thinking just about one line here

or a fraction approximate lies on one line. more likely to give up all the possible lines that might host different fractions. >> If you work in a world where you do like Q plus Z, Q1 plus Z square, like you have sort of a large number of things you're combining, you're going to have to add some factors here, right? Like you get like >> Yeah. Yeah. If you use not just random linear combination linear but with powers of C, it's the degree of the polom. Is that what >> Yeah. Yeah. Yeah, I'm trying like is that going to mean there's going to be a factor difference between the multi and the standard correlated agreement in sort of more general case?

>> I'm not can you repeat >> is is that factoring lead to a difference between the like isn't this argument trying to go from correlated agreement to inter correlated agreement? No, this is just a general thing actually when I when I conclude from I have a fraction of approximates the line of the line but this is like the ancestor motion. >> Oh I see >> which shortly gives me just in a few lines correlated agreement. I see I see I see >> and looking just to just to give an idea this is really you can see in almost all the correlated algorith themsel application which only goes up to uh to ud over three uh two3 of the mid

distance or the double trussing cut which was I think in the fry in the fried paper no fry improved paper this improve worst case to average something uh and then the 1.5 Johnson cut which was in a deep fried paper it's it's all there it's also for the result one calls up to Johnson uh and and and all the others that were subsequent uh the only the only proof I saw where it's not needed is actually the UDR the confer analysis of the proximity gaps paper because there you get directly disability.

So, so but this is just to name these words for those who who went over it. Yeah. So, so you can say for me personally colinearity or fraction approximates that's for me the anist notion the core notion behind correlated agreement and for that reason I was also able to prove certain protocols of course I agree with Ja mra corator really helps a lot in arguing in high level protocol security this protocol are complex so we're happy to have something more easier but strictly speaking it's not needed for for some of the protocols at least the ones I was looking the private protocol fry doesn't need mated agreement to be

proven secure in LDR and for the same reason they fault and varants like work so this is just in a short in a short overview here it's yeah sorry again for for the not properly rendered stepby slides Uh, but that's that's roughly what I wanted to say. >> I have one question.

Seems to me that >> seems to me that um maybe when we think of this correlated agreement uh problems we tend to focus too much on the places in which the words coincide with code words whereas uh the role of the uh number of alphas that satisfy the condition is neglected. Um maybe in in your slides uh you were able to deduce that inequality of cardalities because you were able to to find a map from the complement of the agreement set with S.

You had this bound in which the size of S was less than uh the size of the complement of the green set. What I'm trying to say now is how do we control that in case we have more um more sets it's bit more difficult of course and actually like u I needed to learn that global view this is the question like where you could where you could think of several lines where different fraction approximate liance and how how to incorporate that. It's not not really

some obvious. >> No, it's not. >> So, uh in in my recent proof for for the for for uh up to Johnson for it codes, it's a little bit more obvious because these these lines you could have are predetermined somehow algebraically by the factors of the Google pol. So, so you see the impress, but it took me a while. I I got I got from Hades like a pre-print of her work for pre-cut farm or so. And I was banging my head on on the table for like a day or two to understand this global approach even like that you have in the

notion of much agreement like that that could be everywhere. That was for me going through the the old school uh a new way of thinking about it which was really hard to switch for me. >> I have one more question. Um what was it? >> I'm good. >> What can we do about your son?

give us your >> I'm the wrong guy to ask here. So you need to really ask people like and >> so I really don't have any intuition and and I I personally the first thing I would do just to say something is look at the publication that does this decodability for random codes up to capacity because for me even this is possible you know so I remember what was the role of the uh of the bound in in these slides.

>> Which one? >> The ones that you just presented like where where the delta appears >> I'm not sure that I understood the question. So which bound >> from your your proof? >> I'm trying to >> um where's the uh the regime? >> The thing is to obtain a a to find a line where a notable fractual approximates line that's already actually if you have this you essentially so the difficult is really that there is a that that fractional approximate to prove that there's a fractual approximate which is colinear that's the difficulty and that's where

the regime enters >> okay okay >> that's that's that's really >> I get >> so all I wanted to say Here most of the proofs really prove just the line the existence of a line which hosts a sufficiently large fraction approximate and then do always that's why I call it standard argument it's not my argument you see it in all these groups maybe different words slight variations but this is actually >> I wanted to reiterate something that we we mentioned So for the unique decoding we have a very small error. It's kind of n / f and

that is very useful in some cases. It would be nice to have something that we can prove let's say up to json down that maybe does not preserve the exact distance. So you start with delta you end up with delta plus some distance. Okay. So you lose a bit in distance but the error goes down. So even this relaxed version of correlated agreement or doesn't actually matter both of them. It would be actually very nice to prove it. >> Thank you. We have our first break now.