ZK Study Club - MPCs

Transcript

all right um cool well I think we're gonna get started on this week study club thank you guys for joining the I think I'll just go right into it the video that we decided to do this week was the video from Nigel smart but it's actually a bit of an old video 2013 it was him speaking at Google and he's talking about multi-party computation this is not necessarily like in the zero-knowledge context as you just pointed out well thank you for pointing it out but I think what I've been looking for is some sort of piece of content where they go step by step through like how a multi-party computation works and this was a video

that came up a few times I when I chose the video I hadn't like super super deeply gone into the video I just sort of watched through it it seemed like it covered a lot of ground which it does but I also learned as I do go deeper into it this is also you know a person who like this is Nigel smart and he has a protocol and he's kind of trying to showcase this protocol and this is a bit of a dated video so I don't know if it's the perfect example of multi-party computation but I do think it was like it it was cool to do anyway and I think that this would be potentially one of many explorations of multi-party computation for me at least and I'd like to do more of this on study club yeah

and the reason that we can definitely like the reason why multi-party computation could be relevant just generally in the $0.00 space is that you know it is the basis of the trusted set up it comes up a fair bit and I thought it would be really good to understand you know exactly what this thing is on the most basic level so let's start off with a little bit about multi-party computation as he described it so at the time in 2013 there were three cases that he knew of in in the world in a while one was a medical case which would be this ability to share databases without revealing all information there was this sugarbeet example that he got really

excited about where there and how you wonder if that's actually still happening but sugar beet auction where they were using NPCs to encrypt the amounts that buyers and sellers would want to buy and sell and then there was an Estonian startup aggregate research project he didn't go into much detail on that one but these were the cases that he described as potential use cases for NPCs he then gives sort of a brief on the theory behind f h DS and npcs in this talk he starts with NPCs and describes them and then talks about this way that they used FA cheese to be able to create this very specific protocol

which he called hulls Speedy's or something I'm gonna get to it in a bit alright so with FA cheese this is the way that it works you have party a who has some data they encrypt this data and send it to party B party B compute misses data and sends it back encrypted to party a party a then decrypt this result the idea with fhe the problem with it is it has one big computational cost but it has zero communication costs and it can only at this point deal with very very simple functions it was it was apparently created in 2009 NPCs are from the 80s with MPC's parties compute a function on

inputs together so here you imagine a group of individuals maybe who each have a piece of data that alone are kind of useless but together could actually like allow for this system to work there's no like so but that smaller piece of data that each individual would have would not reveal anything about this like master key or this master piece of information that only the group could create the nice thing about NPCs is there's zero computational cost but there are high communication costs and I wasn't completely clear on what that was at this point but I think later on the way he describes it is if you are doing multiplication copy to

with NPCs there's these packets and it's not about the volume of data but rather the amount of packets being sent back and forth so he there is one point about this that this is a little bit of an open question still for me I didn't really just understand what communication cost is here he also says that NPCs can only defend against semi honest adversaries so and I don't know if this has changed in like the way that NPCs have developed since then but what he said here is is like if you're doing some sort of NPC voting system you wouldn't necessarily be able to protect against some disruption that would actually prevent the voting in the first

place you have to assume that like the participants are still participating on a semi honest basis even if they're going to be acting adversarial also in the NPC model you can only tolerate one bad egg out of three yeah and the other thing that he said here is like I kind of I skipped over here but it's like no info is revealed to parties so this is true as long as but he gave an example with this isn't the case which is like say you have a voting pool like ten people and you know that you might be the only person voting in a certain direction and then you vote and then it comes out that there's been like one vote in one direction then you are aware that that's your vote and you can actually predict what other people did

but this is like not necessarily revealing the individual votes as they're happening so it's only with the outcome in certain cases where you could potentially derive some information all right both of these could be used for anything for anything so for anything for any computational thing theoretically and both could be made err tolerant I don't know what this means SPD's ed that's it s speed is this is the protocol that this is kind of this entire presentation centers around and this protocol is actually the combination of those two methods the main focus of this presentation is gonna be on NPCs that's where I spend most of

my time because what I wanted to learn and yeah as mentioned when we get into the fhe part I don't have as many notes and maybe you guys can me out a little bit or we just skip it for now because it's so specific to this all right so the Pratt in practice what is it like here's the description of kind of the NPC makeup you have n parties where in this case n minus one parties could be malicious and it would still be okay there's a global secret key alpha which is a part of and that is the sum of all pieces held by the participants this global secret key alpha yeah I mean this is gonna be coming up throughout the whole thing the

one thing I wasn't entirely clear about in this is is the global secret key the gold are we always just trying to decipher this global secret key I think so but it wasn't always clear so no sure their nose will not decipher it not like not share it but like do you need this global secret key like I what I'm not clear on is like with a lot of this stuff I mean as we get it I think this is this is gonna become more clear my question will become more clear but it's like is the goal to always just secretly make the secret key like is that what all of this is always for us in the Z cache example it would be no you were like you needed this key is just for

this computation it's the thing that makes it secure it's a random number here okay we're not interested in finding out when visiting caretaking something else I don't know who we reveal at the end to them I've got the right answer yeah something else we're trying to compete ok so then okay so each so in this case the global secret key this is this alpha and each party I would have a piece of this global secret key the Alpha I and the combination of all of these pieces of the global secret key would equal the global that the larger global one I should just say

pieces of the secret key equal the global secret key these pieces can never be shared and later he refers to it as the Mac key think I'll mention it when that happens okay then he talks about secret sharing the data here we have like the F P which is all the data X is a is included in or it's a part of I don't know if this this is where you're gonna see like my lack of knowledge with just like math symbols but I'm assuming that this means like it is a it doesn't mean it equals the full amount it just means it lives within correct it's it's encased in or something anyway I'll keep going so here we have the he

just fine sorry worried about to say something yeah Jeff was just saying about yeah so this FP is it's it's a finite field okay yeah that's what I thought okay so this max so then you have the X is in the finite field this Mac is the message authentication code that's what he defined it as and it is kind of from what I understood it's like made on the value of x so it's related to a value of x here it's defined as gamma which you see I had to spell because I wouldn't

have known how to pronounce that gamma sub I of the X something so each party owns a part of the data share so out of these the larger X you would break this down into a number of different X's and you also have a part of this larger Mac which is also broken down and shared the thing I didn't fully get here was it seems like there's a strong relationship between this Mac and the X I like I is it because it's just like function of that X so it's like so here I mean I can kind of show you here it's actually like gamma 1 not gamma of X to the 1 or X sub 1 this no one could work out so no one

knows what alpha is but how we have these two things the sheriffy the original data and the share of the pack yeah how related by this alpha that no one knows and we need some mysterious process to set this up for more data the mysterious process to do computation while keeping it true maybe at the end we can reveal everything in that case we see them in a work properly yeah if the final thing satisfies this yeah and so here yeah this is this idea here where it's like they I mean here's the place where you actually see the Alpha appear again and alpha - I listen I have a question for you why did he introduce

the message authentication code after all he said in the beginning that it was for semi honest adversaries so adversaries without which are pretty restricted and power and so malleability should not play a role for this for this setup and I was under the impression that this is all about chosen ciphertext attacks and malleability saw attacks on the integrity of the data is this true or has despair I can see it's matching the integrity so the cellular waste is a dishonest adversity we can stop the computation what they can't do if you have even have one up on this person if

we get to the end and it all works out then we know that it was zero knowledge any information except the result oh so he's he's all about zero knowledge I see I said well I mean if you think of the trusted setup model it's by zero knowledge maybe alistair do you mean zero knowledge zero knowledge or do you mean like just no knowledge that what he described it yeah you said earlier that no one knows anything about this computation except for the answer hmm dad that's zero knowledge it's a different model than a zero knowledge proof where the proven would know and the better

I wouldn't know anything except for the that the proven you yeah right but here no one knows all right so um I'm gonna keep going yeah I had I mean I had a little question here about whether or not this so I don't think it is but it was this is actually more to do with like math depictions when it says Y sub 1 to Y sub n would it also would it equal Y I X or is that something else this is why I was a little bit confused here this is just like us more of like a how you depict things I don't know if you guys noticed is that everyone has it

has it has a P correct could I write that is basically what I'm trying to say nobody does a mutant n okay okay I'll pick it up okay um so you have these two pieces uh he talked a little bit about how if you wanted to share a public code you would set party 1 to V public code and then every part party I not equal to one would set their X what do you call it data share to zero and then you would end up with alpha I times this V and it would equal the get gamma V kind of like right here so this is where you actually

see it just the one time this is maybe why I got a little bit confused I wanted to just be like me I want to say alpha times x equals gamma I X but I guess that's not really the case this is the thing when you initialize you set this to be true but later on in the middle of the computation visit this it will not be true because you won't even know what he is you know who don't even know what most X are we know this expert but this isn't a public code so this is the idea that you would just basically like share this right it would just be like we're not gonna take away one of these pieces but still somehow preserve this alpha this global secret key right sure yeah we know this but this

other things in between we know nothing right yeah so they're not they cameras camera is something different in general okay so then here he makes an aside because this is basically the part that links I think to the fhe here he says this aside so like he's gonna give you these a B and C they're gonna be pre processed and you want this aid these a B and C's to function such that the C equals a times B so you when you look at this it's like this this he didn't really explain very much in detail I know that even like Matthew and I talked about this

unfortunately Matthew couldn't make it today but he shares some notes about it he was like he didn't really understand this part and I realized now I'm going very deep into it that like this is basically just gonna come back later from the fhg description he describes how he does all of this pre-processing yeah so this is we have these sheds but no one knows CA oh baby yeah but my question here is like is this say you weren't doing this fhe combo what is this stuff I mean it could we're gonna talk about it soon as we get a little bit further on and we actually bring in the a B and C but I'm curious about like what would that be if it wasn't this pre-processed pre-processed version and this is where I hope that this whole this whole structure isn't only built

this way because he needs to use these pre process things but rather he's replacing something that you would always use for a multi-party computation what is it oh yeah we don't actually know so he's gonna talk about that later in the talk no he sort of he shows the slide yeah they're just pretty processing don't worry about it comes up soon okay so then we go back to this computation so now we're gonna call computation compeition and this actually

is another question that I have about just generally MPC's in this presentation when so he says here there's computation take the form of an arithmetic circuit over the fine field it it's any computation that so any computation is equal to a series of additions and multiplications of these elements it equals a set of universal gates if you share it so a lot of this seems just sort of like preamble that I don't know if like I didn't know if there's that much that I needed to really like pay attention to here it seemed like these are the parameters of the system we're gonna do some computation there's this thing called a circuit which he kind of doesn't he just

like we're just gonna use a circuit for for ease of use and and that kind of confused me because I'm not used to this language I actually asked Rob yesterday or two days ago like why why that happened and he kind of explained that often like he sort of he suggests he's at least the way he suggested it but this is what it was actually useful when they use the word circuit here I was actually confused in general I'm not used to hearing that term but as I understand it you actually should think of it like an electrical circuit so you should think of it like the and ORS and or like all of those kinds of circuit creations and then assume that that's

happening somewhere but I still don't really get how that works together but I'm gonna leave all this because I want to I kind of want to like I think that would be that might be a more general question unless you have a quick thought on that I'll stir well I mean you did go to these okay something like there were some books on how to program with the Starks and it's the same thing here we can do automatic circuits over finite fields very easily it's not I did go to the summit but I didn't get to watch all the talks cuz I was like anyway alright so uh okay so let's go into addition

Gary talks about add addition there was the he says here that adding is trivial and easy you can locally add very easily if you want to achieve some said rosette equals x plus y here he's sort of saying through that's very brief quick kind of thing but Z Zed equals x plus y it's not only the Z sub I would also be this and then he sticks that X plus y into the function that we were looking at oh actually no yeah actually yeah does he stick it into here this is where he's sticking it in I guess so

yeah we add the gammas up as well yeah that's it that's sort of not described here but yeah I guess you just do both and then you would send them back or there you don't send anything yeah yeah you add the pieces for the the data and you had the pieces with the Matt mhm I think here okay so it's both of these things I guess well I guess it would depend on the implementation so like you have an MPC what I what I was curious about here is like say you had an MPC like the trusted set up would it I don't know which one they do in the trusted set up do they just add or do they multiply and I guess they do one of those two things and this would describe how you do that do all sorts of funky

things I just um look at that paper I'll have to take a look okay and then here they say the linear secret sharing scheme means that we can secretly share values that when we secretly share values we can locally compute any linear function of it for free I didn't really get why that he said free but I guess it meant easy I guess that meant like computation free or communication communication communication free okay oh because you're going happy you don't actually have to send it anywhere okay [Music] is that what is that what that meant

before I think you would sort of define that let me just double check yeah that computation cost is that just the sending or the the communication cost is just the sending around or things you know I guess okay so the communication is free so then he makes a side note here which says that you can partially I think yeah I think when you take so when he talks about communication cost he actually means the protocol so the rounds that you need to do all the sort the protocol so answer request request also request answer how many of these rounds you need in order

to to have all the information that's that's the communication sauce and that and that actually so he in the next one he compared this addition she then multiplication and he talks about these packets it's not really clear like in I didn't see it as very clear in multiplication that there's anything being sent back and forth because again I thought like I thought that that was more of an the fhe part where you do a back and forth between a like someone who commits and verifies and you know like a rather that the person a encrypts and sends to person B who computes and sends it back that to me sounded like a round but are you doing round in a

different way there cuz I'm a communication everyone send something to everyone else that's happening in this multiplication but not in the addition for the deities okay so no rounds here okay so now he introduces this concept of partially open opening a share X which where you would give a way part of it here you actually reveal the X but not the gamma not the Mac and the reason you can't reveal the X and the gamma is if you did both then you would actually be able to discover the alpha like you described and that would be bad but here if what's interesting here it's like you partially open a share X but I don't I'm

not clear if it's X I or if it's X total if it's like you actually share that leaves out of X I yeah don't walk together we get eggs yeah but here I mean in this one apparently you don't need to you don't actually need to you don't need to share all of the excise like you don't have to put them in together to make X you'd rather and you absolutely don't want say you only want to share random numbers yeah but in this case you are actually sharing I think the total X no you don't know you're not but you're partially opening something but it should be something that doesn't give away any information okay so it's

weird because he actually thought he said you reveal the X but not the gamma will the excise and that that allows you to reveal that allows you do you excise and I gives you X it's just a template so everything will no no that's okay here when he wrote it this way I kind of I was wondering if that again was a pre-processed and related to this decades later fhe stuff that he was gonna talk about definition this X who knows what it is it's it's available right yeah but do you know I mean I'm just using because he talked I mean he

mentioned the square brackets and I thought that that was sort of a signifier like it sort of indicates that we share in this we have this this people have the pieces of this and the pieces of the map of this okay that's what it means and I mean okay yeah for me it wasn't very clear if this was actually occurrences records like that can also mean vectors sometimes go brackets like that cause I mean yeah this means that we have chest yeah but here is that what this means here too like but let's go back for one second to this this a part here we do this pre the computation on here to be explained

later and so here this is why the question came up to me like here this data was pre-processed and here are three letters surrounded by the square brackets and then the only time we see it again is here and so I thought does this also signify like that means that we have the shares if these a B and C oh you also have those got it how nice of mocking process which we'll get to but not really because I didn't take enough notes on actually how to do that but maybe we can talk about it a bit all right so then we have the multiplication this is funny because he was like the multi described the addition is easy the multiplication is hard and then you get to the multiplication he's like the multiplication is easy so arrow both each multiplication requires this

interaction and this I guess is this packets that you were talking about the rounds this partially opening it's what we're gonna communicate that that's communicating you'll have to reveal the Exide something to each other leave everyone else next time yeah okay and this is what takes time the process of sending not the amount contained within it so to multiply x and y to obtain Z you have to take this new triple so you're bringing back those three things that we had before the a B and the C off this precomputed list I was wondering I guessed that there was more than just the three but I don't know each sort of says takes it off those precomputed lists

yes sure there probably are more a although he only shows the creation of three in his example later on would be doing minion over night Pierre we do in power okay oh yes you're right he did say that okay something it is there are more all right so then you partially open this X minus a and this was also like the way he worded it and the way I understood it was like you actually subscribe the X minus a not you partially opened the X and then subtract a that's that's

the way I understood it so you partially open both of them you know both of you just you subtract and then you you partially open X minus a oh so wait cause it oh yeah because you can do addition and multiplication know what suppose back to kids tell people it looks you're supposed to be a secret okay so you partially open this basically or that is the results from partially opening you get I come now what is this same balloon I actually looked them all up and wrote them down but I but I forget now that is that that's an epsilon epsilon that's it okay so it's you get the epsilon which is a

neat which he bolts X minus a that's funny like do not I mean in doing so you partially open X minus a the way you describe it your so you're saying you'd never see X you never see X yeah okay so you wouldn't be able to calculate either of these but that's why they wanted them we can't calculate the other server yeah yeah and a in this case he there describes as a random value and this X minus a is a one-time pad I didn't understand that term but it is you know it's the crypto thing where you saw some

random thing with your thing and that gets do something completely random so one-time card is two people have the same random string and they can wear this one thing completely random us it's the completely secure crypto system as well communicates pro status a encrypted dated before that as you can't add a to later it's perfect it just doesn't you know it's a symmetric crypto system where the the keys figures detective I wonder so okay I mean it's basically a stream cipher so to speak

but we all know this is a simplification because one-time pads actually don't exist in reality because once you use it twice you one-time pad you might reveal the key of course yeah that's the point these things are one pint pads these abt me beforehand Emil only use them once how is it guaranteed that you that you don't use it twice or three times or whatever because we only use the triples once because they won't time hands again and if a party use it twice is then everything corrupted so the holes using twice so by using it it's it's a single

honest person then it's impossible to use it twice ah a single honest person change it and then they never reveal where share mm-hmm they only do this one calculating with it then no one will ever discover any information of her AI and it doesn't matter if they know the rest of the data they still can't anything from using the so you couldn't unless they met every single person used it twice I don't know so you just sort of mentioned this to you said it said AI and I'm wondering like when we look at this this sort of ABC is this like would

this also be broken down on some level or is this absolutely says always okay the square brackets a indicates that everyone has an AI and a gamma-ray yeah which add up to the my things yeah and yeah you're sending it maybe we get to this later but like where do you where do you send stuff like here it's I hate the triple you partially open you create your epsilon in your row this is partially Athens descending so you compute X I minus a I don't compete sex on lines and then they said that's what everyone and that's where you get this because it's exactly the combination yeah okay okay this is every this is everything should this be I or this should be if it's true yes I but the total is also

true okay yeah that's fair you can see okay cool I think they did the thing that I would have would pay about this notation as I'm concerned is why aren't they partially opening X minus a all in one square bracket [Laughter] maybe it's because you have both like everyone has both and so you each do maybe it would look more like it's the sum it is only the sum yeah we do actually partially open X minus a and not X or a it's just that

the square brackets is all very clear but whatever it may be okay but this is good to hear so it is actually like it's each so like but where does the sending happen so this is let me fit actually let me finish this and then we can talk about these four steps I'll just move this down so they're on the same page okay so this was this how to multiply to obtain said you take the triple you partially open X minus a to get up salon you partially open Y minus B to get row you locally compute the linear function which is free as mentioned because it's addition and mostly I guess it's like over here there is I mean okay so anyway but where

is the back and forth where is the sending and so you would say that it's all here because the open X minus a and 1 minus B what actually happens is the new transmitted by X minus a X I - a I and why I minus bi to everything and see that in a peer-to-peer fashion right therefore the N square communication cost because it has to be arrived by inaudible is N squared is really there everyone she said the message soon as you get to everyone it's all different message to everyone which really helps

in imitation and this is where I'm curious if this is so this whole part that's precompute this is again this goes back to that question it's still an open question of like in a more standard MPC build where there is any connection to FA cheese what is here what is used here instead of these pre compiles you've got to have you got these have got to be random numbers from so it got a bit so you've got to do something modest you might not do it beforehand like this but you've got to do something to get me from magic to Gay's yeah get these it works I see and so it could be but it's like yeah I I I would

be curious to explore like what kind of randomness we just did I actually just recorded this week an episode on randomness and super awesome and now I'm curious like how like what kind what level of randomness what kind of randomness this would actually look like or what it would be but this is something that I think I'm gonna explore on my next MPC journey all right so I'm gonna keep going so this he sort of says I have a question here because you never actually revealed how we do the back how do we get the Mac of Zedd does he say it down here wait no no we certainly didn't say that in the video at all it's a oh yeah your oh you mean up here so this is this

question right yeah so then the question is for this multiplication operation so for addiction we see how everyone gets their and lack of the new thing so multiplication where do people get the Mac with addition you feel like we see it why were you so it was with addition we don't need it the addition that the Mac a we just add the Mac's as well okay it's this thing that adds up to like a secret key time to the data okay but we don't know the secret key and so I got no idea for this multiplication how do you compute the matter people don't know the max of everyone

else's max of X I'm gonna say hi we don't share X I'm gonna say we never have the math of X of X minus a so how do we get a Mac let's just look at the talk ya seem to be so I guess I it's pasta maybe it's because this fhe build only works for addition for no wait no wait you need it still right because you'll need it I don't know I mean maybe what you do is you guys to do the same

thing again for the max or what if you don't what if you don't touch the Mac at all but you rather use it only in the verification no no no but you you we need to compute this Mac of the set otherwise we come verify it right we need to keep you the back of the set and we need to do so in a way that doesn't give away the the shared secret so I think what we could do is just reveal a new treble and do the same thing but if you look at this like this process that

we just went through to create the X Suzy hmm so we would need to be an equivalent basically we would need this right we need like gamma that thinks it no no then how do you calculate the Mac that the max adds up to other times they switch we don't know what else rates so we somehow have to use the max for x and y sub yeah like if I bring because it's it's still like it's gonna be this again right it's gonna be this somehow right always true we get ya now maybe we open another training to do

the same trade with with the map that we did with the actual data yeah I mean do you just but then in that case do you use the same precomputed list you use the same triple weapon two different if it matter what to use a different triple it's supposed to be a one-time pad possibly you could do something like that and possibly that's enough although would it matter like okay so why would you not be able to use the same triple if you think it was like one random number broken off into multiple little random numbers shared among the entire group why couldn't you reuse your random number on both Maya and your and your Mac well you might be able to put it's not clear I mean it's just what in this case look suspect when he says one-time happy actually means one-time

means but I think he's also losing it thank you it's also just in the group it's not actually an X or Z I'm not sure like two - yeah it's yeah it's an addition which is also it's protective so it's the same thing um and yeah you could just use another triple I get it you didn't say you didn't say let me describe so then he goes on to say this would be secure and not reveal any info and be better than other solutions I guess he means other solutions other than NPCs wit and because we were using addition and multiplication with addition of multiplication obviously you can compute anything so then he talks

about so then this is now we're getting into despair vacation part and so it's so interesting by the way we are already 46 minutes in and I am only at the verification so I think it is good that I didn't spend as much time on the fhe because I wouldn't get through it at all but let's go through this and then kind of pool some of these open questions that still exist okay so the very so let's talk about this verification of the correctness when you have okay let me just get into it for a second okay so now so this is interested so now you're actually checking this is why I wondered if like you don't do it you

just use it to check but I think you're right that you've need but actually when we going back to this when you do addition do you actually need to add B max at all like isn't the addition just on the data no you go the max as well why aren't the magazine like up here you have to add the max but that doesn't for the addition you have to help the max as well so at any point when we have this grabber I think say we have a share what that means is everyone has a thing that adds up to this everyone has a thing that everyone has a Mac thing to all the times this but okay that because we

don't know alchemy but get it so getting in here is really odd because here it says interactively check just the max values this is what he talks about Jeff uncheck this means we need to check the max okay without revealing something which would without leaving the secret because even build the secret then we could Forge everything else with you yeah okay so here to check the Mac each player I eat yet that's like they become players here each player I has a set of partially open values T and here you have I don't know what's the J here actually so this is a this is the

partially what is the a here huh so it's a very good question why you switch from I to J because yeah well I has the the pieces from everyone else that's okay here he has both so maybe that's why he didn't want gamma okay our second things you bi you think this should be I so do we have a share the Mac values of the a yes how do you get this yeah I don't know this is the Mac value of alpha-i that's what we know he meant this he did like

this like I know it when I was I was following it it's I'm gonna have a hard time explaining this right now because I didn't take I don't know if I let me let me just try to look at it again your eye has a set of partially open values I guess these these are not the values though are they oh wait this is how wait if I added myself so let's get rid of it each of these each one of these has a sheriff Mack value you got the back tell you what what is Dharma and AJ a time and why do we have this everyone every player at value the AJ's value so wait wait this is a is a I think it's still

referring to this then we haven't so the question is about 3j does everyone have a different value of y right now right yes so we have this yeah and it is so each player has a partially open value a and here later on we say something like I guess my adding a particle value randomness hmm verify the correctness of a whole load of T different values JJ's nothing to do with people okay yeah this is actually but here's and here's another strange thing because mmm you know how just before we made this assumption that these are random why then would you need to generate random value RJ here at the very end so

basically this is like this is what we have I we don't exactly understand what this this is right now but then it says at the very end who generate random value our J you know and then multiply it by this a I know that like if you make a random number and multiply with a random number you get a random number but why would you need to do this yes Vista it's not relevant it's the next bit it's the max yeah so this is the thing that we we don't want to reveal gamma of AJ yeah because if we reveal that build or shared the Mac then everyone be able to work out the secret key so really real

light even if we didn't reveal anything else I know everyone revealed their share of the Mac of this number we all know then they can add them all together and work out out oh yeah right throughout the times the other thing we want the thing you don't want to do is to reveal the secret kids accepted to possibly the last these values are probably coming from some commit reveal process we got beat you to that hair I think you don't want people to know them either right but yeah I mean you don't care actually that's why I actually I think in because is it possible because he did this sort of shg on these A's that they're actually a little bit more they're not quite so random I mean it'll be I guess

it would be encrypted what would come out it's still be is about that because we said they run the AJ's in no random let the things we're trying to verify yeah we what is the age days are still referring to the each of the A's that everybody would have appear so so so these AJ's are the outputs of the computation we want to make sure this computation it's been done correctly is okay so we're going back in to here and right I'm just trying to follow the math of these like just the letter Z relation with the ads of multiplies and I would try to work out did we do it correctly and so we take our a like our individual a yeah okay and then we also have this

share of Mac value which is gamma of this a this piece of a and then each player also has a share of a Mac key which we know alpha J in this case at the very end we generate a random value we then multiply it by this AJ and sum them up that's right and they can I guess that then gives us but this next thing we do in secret it with the max yeah sweet okay and then he says Sigma yes it like everyone themselves with their alpha I and this

gamma ray and then everyone transmits Sigma I so every yeah they player I know self right that's the how people question and to know everyone knows enough to calculate Sigma I and the hope is that it doesn't reveal anything that we didn't want you here but you do get this then is this something that's generated and shared so no need to calculate our own Sigma I okay using parts of the secret without even revealing it oh is this which is the part okay is this the part that it's like is there a part that is shared and compared in

order for us to make this verification like this a is now seemingly the whole a we said that the end is the signals those are things we share mm-hmm yes yeah okay got it the A's will be a public as of the AJ's but the these max we added up to get this this we've used in the calculation of these Sigma's their secret mm-hmm and in order to protect them we've multiplied them here by random and so this is nothing this is not traceable in any way and we've also multiplied this one by random so even though no it's not divisible Department as you know here creation yeah okay and so with our our

piece this is still just like it's it's because it's still here it's like our piece I think right so that's how each of the match yeah that's our piece of the map where o is our piece of the secret and then we just add up a synchronized ever broadcast zero then the claim is it works correctly I don't quite sure yeah absolutely yeah here you here you would actually you'd have to send it all to well I guess you wouldn't actually have to look at it you just basically send it all together at it which we've already figured out or dislike yeah this is

obviously need to commit reveal because otherwise we could just send the thing if everyone else wrote for everyone else to send it we can send the thing that makes it Sarah before but if you do that then it should be fun maybe so the claim here is that if we will commit Mobility Sigma rise and add up to zero then everything must have gone correctly because yeah we have known what to do there's anything better for us to be more do the calculation physically all right so now here's the thing it's like I'm gonna I'm gonna finish off roughly what I mean I took notes on the rest of it but basically it's at this point

where he goes into the pre-processing processing and the fhe I didn't take very many notes because yeah it's just like it was like a whole new chapter and I really wanted to focus on this stuff which already was like pretty pretty much a challenge for me but I'm glad I feel like I followed it for the most part and then he talked about like this use of passwords and how there'd be this really great use case for passwords in 2013 that he thought would be good but what I think we should do now because the only have a few minutes left is I'd like to go back to this whole thing and just take out because there's like for me there's already some really clear questions and that is sort of the same question I had at the beginning but

it's like it's about dude would these like what are these if they aren't done through this FHP model what would they normally be like where do they come from there is an area so so basically we in order to use this protocol we need some crazy way to get this and possible you do you think that construction of the MPC Park is reliant on this fhe part existing or do you think that it is it's like plugged in this version of it looks to rely on this yes okay so how do we do NBC without this well I think we need a lot more rounds to do this multiply huh you have

and this is why and this is where this is where he saw he sort of saved some some computation or he makes it faster somehow because there's this other part that's done he kind of describes it as like baking overnight it's like done on its own time parallel right this is the key thing here it's parallel so if you have if you actually did all this at the time it wouldn't be any faster than just doing the fhe yourself yeah probably but we can completely paralyze all this computation communicating with do to generate these triples you can do them all at the same time my question will be

I was under the impression he's using fhe just as a black box that's what I thought too yeah and and the pre-processing is actually for computing the circuit in some fhe special way so that the provider actually does not learn anything about this circuit but I'm there that's what I'm pretty interested in I have to say mmm but I didn't go through it hmm so I had originally thought of it as a black box like when I went through this I thought I don't know if black box would be I thought it was sort of like plug I don't know how to describe this but kind of like something

that could be plugged in or or replaced reduction is you had another way to get these triples yeah like using MVC then you'd be able to use it as well right yeah is a triple is a triple in this case like unknown is this like a term that is like well known a triple or is it just like three things it's just three things that's that's what I thought but is it like I guess that the dynamics of this like what a exactly what if they have any sort of quality other than randomness if they are random this is something that I still want to figure out what here is the a and B of random and there we needed completes me and C is somehow that that's actually what he

seemed to have done right like if you in the fhe part he does something on it to create a he does something to create B and then I think he multiplies them to crazy or so he does something together between a and B CH crazy yeah let me n that's that's what I think as well and and I was under the impression that it has to be three because the binary gate has two inputs and one output so a B and C is the output so multiply a and B and you get see some holes yeah some necklace I was thinking that actually after we went through that as well or even if there's this idea of like more that you would always like you do it in triples I mean they're here they do say take the new triple so it does seem to

be like those sets it's not that there's like you could because you wouldn't be multiplying I don't think like x times y times something else to equal something you'd always multiply to t equal something and then you could do other multiplications after so you'd need these three to match those three right that's at least though I mean that's what I wear straight to add match this degree because you have you have two inputs and one output yes you you would need these this triple sure maybe it's unrelated though we'll pointed at the binary gates we need triples yeah okay so that's that's one of my this still

sort of might remain sort of one of my my questions is like could we in the case like you just described if we had some other mechanism to create this a and B and C and related in this way but wasn't fhe could that be plugged in and if we don't use this what does it look like that's what I'm really curious about now and then the other one the big what was the other big question that I oh yeah and I think your Mac and the multiplication example it's still really really a big question mark yeah and there's another question mark for me because he he used a yes as some sort of fun very famous example maybe and I didn't I didn't understood why he didn't make use of a yes because as he said

it's it's highly nonlinear and and it is in addition to this it has structure lots of structure that makes it easy to to pre-process somehow but in the end I didn't understand why AES is such a good idea because you will learn so much if you use oh if you compute a yes at a third party site you see all the all the steps in between and how to make sure that no secret in between is revealed makes it for me not the best example but maybe the most compelling it's example in order for the Sarah knowledge part you know I secure every every layer so to speak it sounds

like this I kind of got it like this would be a place where this specific protocol could make things better like I don't know that he was saying that this is like a good starting point but that his speed is could be used there to make it better because like that's at least that's how I got it yeah is the question is is a something like your benchmark of maybe it wasn't 2013 this is a bit of a history lesson while we're doing this because it's like six years ago I actually don't know I own I this is totally not I haven't explored this space at all do you guys know anything about that

Alistair or Jeff do you guys know anything about AES and password stuff I mean AES block cipher okay and you know that 28 bits why and it does I mean it's a certain permutation so say it is it the case that everyone has a P simply yes that the symmetric key thus although it's symmetric cryptography no one actually knows the key that would be passed with vegetation so sure it would be used in like you know deriving some

sort of password or macking a password or whatever it tends to be used in a lot places yeah okay so it is actually you know maybe they'll actually maybe they're actually running yes in the NPC that would be cute I mean it wouldn't do the reason to do that is because it's small enough I mean it's only happening 20 you know it's it's it's small enough that maybe you can actually do it and actually see the computation succeed but it's also you know that it's so far from what the NPC is using under the hood that it's something that you're able to do like real symmetric crypto in your

MPC but just a tiny bit of it I think normally when you use AES you use it you know I mean you it's it's small and fast because you use it on a lot of stuff not always sometimes only a small bit you know yeah I found it highly interesting because um I thought the model is like this AES was running on a cloud server and everybody knows it's a public it's a public cipher but the but the secret key maybe is the secret key of the of the cloud provider and but he does not get unencrypted data he does not get plaintext from all the participants but encrypted data and by by encrypting this

again in some sort of a cloud fashion we need to make sure that nothing is revealed in this computation and nothing is leaked on the other hand but I'm not sure about this well you say what you do here you do a yes everyone has a piece of the routine and no one at know actually knows EAS key hmm okay so we could generate passwords as in some people someone gets there faster if they split it up they send it to one of each of these people and then compute the a s of his password to tell them and install that somewhere and then if this person the same person comes to organ again you can do the same computation and get the same thing and

that means and we verify the computation that means if they're the same person but no one actually knows they've had any problem that makes sense as long as one person's honest there were never gets a complete password all right they just have had this AES encryption of it and they can make that public because no one knows the AES key after Jeff do you guys have any open questions left on this I know we didn't touch the FTP at all but yeah that's telling I know it looks moving oh really good me neither

actually so a lot of this I could follow there's parts where you can see like I would basically just need to go back to the video like this part like I did actually understand it when he explained it but I'm having trouble repeating it like I remember following the logic and being like oh yeah okay that that's sort of and so I think I'm gonna just revisit that myself but um yeah is there anything else that you think sort of is still open no I look at Polly's multiplication works but other than that I think the oh wait we wanted to know this we wanted to know this part right this is how this came to be wasn't that's something that you were

kind of curious it was like how does it actually get derived at all in the first place yeah a big slice didn't get one they admitted that the these are you different people no are you trying to multiply X my voice all right this explains how you get the shares of the Zed but not how you get the shares at the max except I possibly do as I said process so no yeah I mean you have yeah I felt like there wasn't are two questions here one is like how you do the multiplication with the Mac yeah element but wasn't one of your other questions when you when we talked about how each party owns a part of data share X and a part of Mac and it's somehow like did you understand that how these were derived from each other I guess

they're not derived from each other so what they're not is that we we set it up originally so that this this holds and then we do some computations on these values which keep this property I oh yeah actually because the man already exists at the beginning yeah said if they have this property because no one there the secret it's probably the ones that no one there's been a book about the intermediate values mm-hm I've done this correctly but but at the same time no one well no here we actually get away with multiplying some

secret values okay let's yes because that's what we do the original say yeah we might do the same thing to the map that's probably true but yeah I'm surprised he means Yeah right even is this may be something I don't know hmm well I'm going to I'm gonna unscreened share there I'm back oh yeah okay Oh Sun setting very bright sorry um I think if there's anything do you guys have anything else you want to share because I think we're a little bit over time um I would really like to do another NPC example now now I'm not really sure the current state the

current things that won't you be looking at here are to be honest I mean there's a lot of different NPC techniques and I don't know but merely to be honest but yeah I almost wish I kind of wish that there was like eight what I'd like to see is a very detailed explanation basic one that tends to be the root of many others like I would like to just have that basis of like this is how it all works like I mean I got a little bit out of this the fact that there's this verification there's some there okay so there's some cobbled circuits that's a very fairly old technique I'm not sure how popular that is today things there's other things which made

me this sort of thing that you were looking at here but I'm not sure where you do this and you do this NPC and then you're get and you have these some random values added that messed things up but then in the end once unblinded some of the computation then somehow you're guaranteed that the the things that you were some of them because certains you could use sort of small random values and you're guaranteed that at the end there's some discrete log problem that you can solve which shouldn't be too hard if the parties were honest I think the answer pops out immunitech communities that one

somewhere there's already meant to I guess I never got around to that anyway but those are both fairly old techniques I don't know what the more modern stuff is my guess is that the more modern stuff might be swinging more to use towards using zero knowledge proof more heavily because they I mean if you look I mean so looking at what C cache recently did and I know that they've really like optimized distrust to set up but I don't know if it's because they've optimized like on an MPC or if they've done other things like around it so there's two things going on there

there's the sad one custom setup and then there's all sonic which is a new thing that side yeah so there's sapling which has it's yeah things in it but then you also have you have the trusted set up as itself it's like a design thing that they created like that I don't know that that's I don't know if it's related to the cryptography within sapling no III haven't read this paper I probably should my suspicion is it's not that hard what they're trying to do is I mean what they're trying to do essentially is to make the trusted set up but see they're basically they are making it more

asynchronous so but I think all they did is they stuck in musics that you've done everything they started more about right funded highly interesting to to see why they come came up with their specific construction this could be instructive yeah okay if you if everyone important a certain number of people simultaneously and I think what they're doing here is they inserted zero knowledge proof that the right places so that they so that it can run more asynchronously so so that you could contribute to the trusted set of parameters and have a zero knowledge proof that your contribution is honest it wasn't corrupting sorry well you were just saying something there we could make actually two more sessions

one is more the application side like in zero knowledge MPC for education I mean and the other is going back in time to Yahoo's goblet circuits for the multi-party computation and and Craig Gentry's work on on fhe this could only more the groundwork that might be really good okay so let me get this down what was the what was the name you just said Craig so this the one for grant what impart aside the two party computation basically is yall's covered circuits why a a oh yeah and the other is correct gentry I think around 2010 was this breakthrough with fully homomorphic

encryption oh yeah this this is basically the starting point for this then and then doing a Z cache like I think the MU trusted but especially I mean etches both would be interesting but like a missionary why they exactly choose this NPC construction for the assembling trusted set up exactly you may be curious actually I'm sure that there's at least particles where they describe this but um this would probably be a paper I don't know I although maybe there's some talks or something that

they've given on the topic as well but uh this is cool maybe yeah very very pragmatic approach they took maybe it's very theoretically sound I I don't know would be interesting to hear Zook whose opinion on this as well yeah I think I mean I I would I would really love to talk to the person who designed it though cause like there's there's like a crew of like 300 yeah um yeah I know I'm really I'm really curious to explore this and like thank you guys for also going through this session even if it's a little bit off-topic I think it at least starts to build a

little bit of a model and that is something that I hope is helpful so I'm actually I'm gonna stop the broadcasting now because I think we can keep talking but I'm just gonna shut this off so this will be the video thank you all for being here