- And for this work I'm going because it's kind of deep and there's a lot of background needed to understand what what is going on so I'm going to cover a lot of the ground that is due to other people and then I'll talk about the work that that we are doing and I chose this topic because. It's really pretty it's the constructions and the ideas are really interesting. And so all the talk title and even the justice to the song how to prove things elegantly so I don't know if you know what what this is I think it's some. Waldo convention. If you know the game where is Waldo is that it's a big puzzle it's a big noisy picture with a lot of things going on there and you're supposed to find the character called Waldo who looks like every one of these people I couldn't put the actual puzzle here for copyright reasons but you can imagine that that's what I'm talking about so now I want to pose. So this leads us to keep talking a few mediately and. Specifically to offer proof of knowledge OK so suppose you and your friends play Waldo and Suppose you found Waldo on the puzzle not on this puzzle on the real puzzle and you want to prove to your friends right so this actually really easy to do you just point toward them it is not interesting almost right it's a convincing proof that you found Waldo but. Let's make it a little bit more complicated and let's let's not ruin the game for our friends and try to prove that you know where Waldo is while not revealing where he is. OK So that's that's become a little bit more interesting and it has a lot of optic ation as it turns out in the area of cryptography OK So this is what's called zero knowledge proof of knowledge is. This concept or this this technique of proving that you know something. That other people don't know you don't want them to learn your secret your secret in this case is well this location so you want to prove that you know where world is but without revealing anything additional in fact about about where Waldo is so you can take this as there's a puzzle to think about you can ask your friends and kids sometimes kids solve this puzzle faster than adults and show all of the time so you can you can solve this puzzle with just just regular household objects that you can think about but I want to. This to cryptography and when you think about the kind of everyday things you do using cryptography one of the basic ones is authentic ation over when you should go shopping in. On Amazon or when you go to a bank and so suppose Ellis wants to go to the bank and she wants to withdraw one hundred dollars So what needs to be done in this case is that the bank of course have to authenticate the bank has to confirm that this is indeed their lease and a lot of the time surprisingly even today in some scenarios maybe not to the bank but when you call in for your credit card information these pacifically ask you what's your mother's maiden and what is your this other information so one way to prove who you are right is of course to reveal your passport but of course this is not the best idea because. The person who listens to you or the bank who knows all the passwords is vulnerable now to all kinds of attack the bank is formation with all the passwords can be stolen or the person who listens to you in the bank teller knows your password can pretend to be you later on so instead what you want to do in this is relation to the puzzle right and this is how things are done with cryptography is that instead of telling your password it is sufficient to prove that you know your password. OK makes sense and now we're going back to the zero knowledge property where. I want to prove that they know my password without revealing my password so that the very fire of the proof will learn nothing about about my past and then I cannot replicate this proof. To pretend to be me OK So in this case you can imagine the bank is holding a puzzle that Alice knows a solution to and nobody else knows a solution to this puzzle. And then Ellice will send a zero knowledge proof of knowledge of the solution and. The bank will know because the bank associates bank notes that only L. is not the solution to this puzzle so whoever proves that they know the solution is in must be Allison and everything is great. So there is a lot more to secure computation and in fact. Like I said I'm skipping huge areas to kind of to lead us to do with what really they can contribute in is. That we are working on. And. This area of secure computation it allows parties in general to compute any function privately so. If there is Ellison Bob and there was some private input A that she doesn't want to share. In the zero knowledge puzzle that would be her password for example right or a location of Bob and similarly Bob might have some input that he doesn't want to share but they want to compute on their joint input so it is possible to compute efficiently any function F.. Like so so that the parties learn the output of the function and nothing else is learned and this is you can kind of think about it as computing under inclusion. And we'll get to it to some details how this is done but for now is just believe that it's possible in fact it is possible so now. Because it's possible now I'm going to say well you can actually then proven zero knowledge anything you want and it's. Right so let me just phrase what I just said Magic Box of this this blue box here is a magic box that is implemented as a protocol between the players who want to compute the function there is no third player but it's kind of imaginary representation of what is going on where Elvis and Bob are bank in this in this picture they submit their inputs X. and. Y. into the box and out comes the output Z. That is the value of the function OK so we know how to do this and towards the end all give some glimpse of how this might work but for now I'm going to keep that in now I want to say that. If we know how to do this then we can prove in zero knowledge anything we want and indeed it is a very straightforward instance of general multiparty computation because we want to prove something when we want to prove that L. is knows some secret right it is sufficient to compute the following function securely the function takes two things as input X. is the statement so this could be a description of a puzzle W. is Ellis is witness so witness is the completion of complexity. Right so is here and will be a password and then the function simply computing a boolean output where the W. is a solution to the puzzle X.. OK so if we have a generic M.P.C. protocol then we just say well let's solve a specific M.P.C. protocol computing this function and then that gives us the knowledge proof of knowledge on anything we want and people looked in this not in generality for a long time and there are many many systems how to prove some very specific statements and surprisingly only very recently people realize that there is an obvious technique how to do this for an arbitrary function arbitrary bullion circuit very efficiently. I'm not going to tell you how to do that. So we're kind of almost done right because I told you that we can do everything so. I want to connect it to the rest of the talk so. I searched crypto and. Surprisingly the first non blog chain related or not blog non blog chain focused entry when you search for crypto in the random search engine that you see here is the number nineteen I was surprised. By the way this is not today's news is your watch and it's not the point is not six thousand it's a little more so. OK so fine so blog is a good use case we want to make. History or a positive way. So a blog chain is not an interactive proves So what we like to abbreviate is people pronounce it differently I say it music Bach interactive zero knowledge proof of knowledge OK. So what I described before is not known interactive. So I'm going to discuss the work that we did with. The people Jonathan Katz who's a professor and his student who just graduated showing. So we're talking about proof system so now I want to formalize give us life formalisation of what proof system is and then I'm going to lead to words how to build a non interactive proof systems and then describe with a very high level our protocol and describe what it does and what kind of practical impact it has so a proof systems is a framework in which you prove things you don't think of with classical proofs as proof that they're written on paper like your theory arms that you have to prove for your complexity class but think of it the interactive proofs that the proof or says something and then the very fire might send a message challenging it and then the prover has to continue acting in a consistent manner in a manner that is convincing to the very fire so there are two components there are two properties in the proof that you want to do this you want to consider and one is completeness you can tinker with there's a correctness property so this means that. The prove or can convince somebody over true statement so this kind of a natural property of what you want to have in the proof right and then is counter positive for the opposite the other property that is also very important is that it's called soundness which means that the prove or cannot convince or false statement and so those are standard notions of what we want to achieve and we're going to when we discuss proofs that we can refer to them. OK so. The N.P.C. is interactive in this kind of. Efficient M.P.C. is inherently interactive So what can we do with it with one message and likely well so in generality. You cannot apply a standard can try to send a transformation. But luckily there was a design that allows us to go from interactive to non interactive. When you apply to a special class of of interactive proofs. OK And this is what. This special class of proofs is. It's called Signal protocols because it's a two message protocol where the prove or opens up the communication and the prove or says something so that this message the first message kind of sets up the problem it may be that will say I'm proving this it will also generate some randomness and so this message will contain some kind of opening for Alice and then Bob will challenge Alice. And intuitively that means that is constructed the system. And that supposedly all of the parts of the system are true and this random challenge will ask Alice to open and in fact reveal that those parts of the system that she constructed are true. And if Ellis in fact succeeds then Bob has some confidence that. Well this time I didn't catch Alice and then doesn't give a full guarantee gives a probabilistic guarantee that Alice did not. Repeat this many times so let's say if this if the proof system is such that Ellis can cheat with probability half each time then repeating this experiment one hundred times and each time seeing that L. is succeeded in proving this reduces the probability of others cheating to two minus one hundred and that's fission for all reasonable people OK so that's great. And now the idea that if suppose that we have such a proof system in the end I'm going to show how we building such a proof system in a very interesting way from N.B.C. So suppose that. We have social proof system then we can collapse it into a non interactive system under some conditions OK sort of the main idea is that the random challenge the challenge that Bob is asking to check in opened this part of the cell is construction to check for correctness this challenge can be generated by Ellis herself we have to be careful we cannot allow a list to be wild and generate any challenge because she will maybe like this challenge more right and she builds a system knowing the challenge and she will say I'm going to challenge this not so we have to make some some constraints right and the way that we do it we apply a hash function in cryptography we like to call it random Oracle but for all the people is a hash function so this function computed on everything that there was constructed so far right. The output of the function can be random challenge that is used for Alice and then Ellis will open that part of her construction and Bob will be convinced with some probability that the tell us is correct in the US If you cannot open her construction correctly then Bob knows that their list is cheating. OK So this is this is a way to move from. From interactive to non interactive case and this is due to. A very celebrated result result so there's a couple of issues that there's many issues but there's a couple of issues I wanted to mention that they're high level and they're very interesting. So one issue is that still Alice has to approve or P.L.O. as he or she has a lot of power to choose even though she's limited to two make her challenge be. But you can choose different message him right so let's say she choose first message that you construct some. Construction to for you to set up the proof then she sees the message each of them and then she says No I cannot prove in that challenge so no she she always has the option of going back and changing her first message and then getting another each of them so this is kind of a problem but it's not really a problem. If the soundness error is negligible meaning that if Ellis can prove a false statement with very low probability with probability to two minus one hundred. Is fine it doesn't bother us you can keep. Doing it for for millenia if your probability of success is to two minus one hundred it will take a long time before she can produce. That will convince us right and by a long time I mean essentially infinite time for human purposes OK and there is another issue is that what they said that sometimes in our systems. The proof will be. Of meaning the soundness error doesn't have to be negligible it will be maybe one half right so with probability half Ellis can cheat right so then this choosing message M. does help Alice because she tries one she doesn't show as another one she expected to find one soon but actually it doesn't if we set it up right actually doesn't work because Ellis will have to find a sequence of one hundred of those messages. Each of them next one is uniquely determined deterministically set up from the previous one so you fellows. Say she set up nineteen experience that works for her and she needs to set up the twenty year and then. She finds out as well actually I have to change my AM then she has to go all the way back in the beginning and start from missing from the first experiment so that works. But. And another important property here is that we we need so this randomness. Has to be public in a sense that it cannot contain any secrets that in a generic. Very fire system the very fire might have so the system that we are. So this this general high level system that they described where Ellis constructs something that represents that you know is a solution and it's random Bob checks and you component of with that one does not have. To not have the need for secrecy around them so the public and the Mrs Fyne OK so now going back to the previous picture that I was showing that this doesn't work does direct application of the M.P.C.. To the two to create a Sigma protocol with the public randomness this doesn't work because the cryptographic protocols in a very essential way you secret randomness from both players so that that doesn't work and I don't want to spend too much time on this because it doesn't work so we're going to move on to something else. And so what we're going to do is we're going to design a public or so-called public or in zero knowledge Sigma protocols and then the. Trick. Of using the hash function works. So to do that I have to introduce a little bit of notation a little bit of crypto primitives but it's not too bad and they're all visual so that should be hopefully. Understandable for everybody so one thing I want to expose to introduce is the notion of commitment schemes commitment scheme is a user is a pair of protocols committed to reveal. And the idea here is that there are two player sender and receiver on the input X. this sender overcommitment. Does some computation X. that. Generates a string. With the following property. That strain that is generated called commitment of X. has the hiding property meaning that by looking at the commitment you don't learn the value of the commitment. You have no idea of what's inside this property one. Property two is the binding commitment is that once I generated the string. And I gave it to you I can only reveal what was inside that I sent in one way which is the way that I generated I cannot reveal I cannot put a X a quote zero here and then later say or do you feel it to be one so this was called commitment so you can think of a physical analogy would be if this were saves or log boxes with a log right I put the next or put the message here and a given physically to you. As a commit face and then later the only thing I can do is send you a key that unlocks the box as a message is there I have no power to change the only power I have is to reveal or not to reveal. So so that's commitment schemes. And well for in the digital world commitment schemes are more or less hash function so if you apply a hash function to your input that message I'm not going to discuss it's not quite but you can very easily massage it into something that is actually correct another thing I want to do is to introduce the notion of the party view in the secure computation. OK So so far we drew it as a box this the secure computation of the blue box in the beginning but. In reality it's a protocol and the broader call looks I don't know how to load different protocols differently but. In generality it's a bunch of parties who participate in the protocol and they exchanged messages with each other so this lines those arrows are communication channels and their messages sent on. Channels this is what. The structure of secure computation is. A part of you is going to say that the view of a party is. Everything that that party sees during the computation. OK So what are those things those two all these four things. Are random tape of the party or the. Randomness that this party might be using for the protocol that's number one. All the messages I guess input input of the party as well put all the messages that the party received. That's part of what the party sees all the messages that is sent the output and that's it. OK so I can actually get rid of these two because those two are redundant the messages that sent the output Those are. Redundant objects in the view because they're deterministically generated in. In the previous. Two objects so you can generate the message you sent a deterministic function from computed on the random input in the messages received it doesn't really matter actually for this discussion. OK So commitments and part of you can secure computation. So now I want to present a really it's not our work it's really beautiful. From two thousand and seven. It's a very theoretical paper I think it was in the folks or spoke and the the idea there is how you can use this M.P.C. by thinking about it in your head. And to use it to prove things to the very fire the idea is beautiful is simple. So here are our two parties prover in the very fire OK so the prove or has W. is the witness is the secret like a passport OK and X. is the. The statement The proof is proof for example the the puzzle I guess F. and X. the related if you can think of a function the checks the statement. That the W matches X OK so if it's just a function you can represent it as a bull in circuses or any kind of competition model so what the proof were does. Is that it's going to emulate secure computer in its head this so so far nothing is happening people are just sitting in their chairs they don't do anything to prove or start thinking really hard and what she's doing is that she is doing a secure computation of function F. on input W. an X. in the following way she takes eggs so she chooses. Petition on and parties I didn't tell you how it's done but you believe me that is possible because I told you it's possible. And. Now I'm explaining the parameters what goes in put to those parties OK So what goes in put every party gets an input X. each of these guys and then the input W. is now secret shared among all the parties so secret sharing is is it representing a secret you are taking to secure them breaking it up into pieces. In our case we only want and out of insecure sharing so that means that if you have and minus one if you have all those pieces right and you choose any and minus one of them you cannot reconstruct. No information about the secret but when you have any of them you have full information about the secret and this is very easily achieved by ex or secret sharing So the way that you do it if you want to share a bit among and parties and minus one parties will get random bits and the nth party will get the beer that is equal to the. You know to the right be that when your ex or it will get your secret OK So this is what's called the X. or secret sharing So what we do here is that that secret W is being secret shared among all the parties so now the property here is that together all these parties they no W But any subset of these parties don't know W. in fact have no information about W. OK so now L. This computes this function F. what the function F. does inside it takes all of these W. W Y one two three and so on reconstruct inside that function and remember secure computation doesn't leak anything what's going on inside the function. It's only only producing the output nothing else everything is inside of this magic box so what this function does is first thing it does it reconstructs W. from W. one through W. N. and then it evaluates F. in output zero or one on X.. OK so now the property is that if this is done correctly. Right then if output is one then W. is indeed the. Witness that Ellis knows it because L. is just input into the computation so now all we have to do is to convince Bob that this computer Taishan was done right. So what we're going to do. Is kind of a natural trick from here I mean natural for people who work in cryptography because this is what people do but. It is still a very interesting trick for haven't seen it so what people what you do now is that So Ellis every everything is done in her head so far nothing was sent what Ellis will do is that this blue box here is a commitment. So Ellis will. Be looking at each of the party she will create an object that consists of that party's view so everything that this party saw including its input share W. one W. right eggs and all the middle of the randomness and all the messages the party sent. Received OK she generates. Commitments and sends those commitments to Bob. So far nothing happens I mean so far nothing is revealed. Because those commitments fully hide what's inside of them right. Yes everybody's agreeing. Then and this is the part that corresponds to what I was saying the ball will randomly challenge some part of this structure that L. is constructed and if it was done right if checks passes. Check passes then I guess you didn't cheat and then if she doesn't pass then well OK you cheat. So what does he chooses randomly chooses a subset of these guys and says OK I saw your commitments now show me what was going on inside of these guys OK and Ellis will send the views of those parties back to Bob now. Bob Bob the very fire will collect all the views and check for consistency so specifically the things that need to be checked is that firstly the output has to be one right these guys the output is part of their view so they know the output so you can check that the output was once so this obvious thing to check because if you zero than right than the than statement is not true but beyond that the output is one you want to check if those were constructed correctly and right and if you can in correct construction of this cheating if you don't catch incorrect construction then what happens if you have some then then you have some confidence that this did not cheat and. Quantify the confident. OK so. People are nodding. So this N.P.C. in the head I'm going to keep this in this for the purpose of this talk means that we can do more efficiently so that some we can security notion is sufficient for this. So we have the city properties remember from the beginning we need to consider the zero knowledge property completeness and soundness OK So the zero knowledge property holds. Conditionally So if you have if you underlie didn't tell you what the M.P.C. protocol is but underlying If the underlying protocol is secure against T. corruptions which means that up to tea parties can be opened or seen by the adversary and adversary still learns nothing if that's the property of the underlying M.P.C. protocol then this year our knowledge is preserved here because Bob is opening Bob is asking to open tea parties so he sees the view he sees what goes on inside of tea parties but by they go and see of the secure computation protocol there is no information. About what actually is going on in this competition so this isn't always properties is preserved. Completeness is kind of obvious because if the statement is true and it was just behaves honestly then she will always pass this check that we just described. Because she just honestly emulates in her head what is going on and on Asli sense everything writes to Bob and Bob checks and is fine. And soundness and this is the quantification of what is the probability of Alice cheating. So depending on the protocol it depends on the underlying protocol there is could be a difference in exact in exact number but sort of looking at this in the generality. The worst case for us for the proof or is that the cheating is kind of distributed between two players between let's say this guy and this guy. Let's say the message OK if if some action was done by this guy then there's just one out of a probability of catching these guys. Divided by. Right because. Out of out of one but if you distribute the cheating for example this guy send a message and then this guy receives a message but it's a different message so there's another way to cheat in this protocol by by creating this disagreement between between the players and this kind of cheating can only be called if you open both players OK but it's also doesn't give us a bad probability if you write it out so what's the probability that their lives can cheat she can cheat if it least one of them is not opened right and if you calculate the probability of that that means one minus the probability that both are opened and that's a simple probability I'm not going to write it out but. I'm not going to say exactly but it's divided by N. under the assumption that C. is equal to one minus one if it's not then it's this and the protocol that there will presenting is actually we're going to have an efficient protocol for equals and minus one so the protocol that we're going to have is that you can open. And Party protocol that you can open and party in minus one party singular nothing. OK so. So this is the probability of cheating so if. Five Then you have probability two divided by five. Of your probability if NS equal to one hundred and you have to divide it by a hundred so. That's not sufficient probability unless your number of parties is to the power one hundred but this fine we can amplify the soundness by petition so if you have one out of two probability that would do the hundred times then we're going to have. Good confidence. OK So this is all kind of theoretical stuff and it's a paper in faux And so why why why we care in terms of in practical terms so it turns out it's actually concrete the fish and see when you do it right. Is very good. And it's a very interesting thing I think people didn't explore it at all I mean there was some prior work in this domain and we looked at that. It's really the costs of there are not very low they're decent but they're not very low but in this M.P.C. in the head model they're completely different because just the setting is different we get stuff for free that regular N.B.C. protocol have to pay a lot for and this is where the efficiency really comes so I. Going to keep. This one so this is an example that we can avoid public public key primitives for example for this work but we cannot avoid public key primitives in general for N.P.C.. So there's prior work I think it was maybe thirteen fourteen fifteen. Years there's two systems calls a cable and then and has. They implemented this pretty efficiently and they found the best tradeoff for their system was that and they will see the number of. Parties. Ellis immolates and her head. And it's kind of natural if you think about it because if you think of multiparty protocol Everybody sends messages to everybody. Grows then the total number of messages grows quadratically with the number of players OK and. So you're paying quadratic increase in cost but you're soundness error reduces linearly remember it was divided by N. so it was the best tradeoff and that's what we challenge in this work so what we do we we look maybe deeper I guess into a variety of N.P.C. protocols and find different ways how M.P.C. primitives map into the same N.P.C. primitives in this can be seen in the head world and we find some very significant optimizations allows us to run a design very cheap protocol that France for greater than three parties like a sixty four one hundred twenty eight and so what we get is that we get a lower sounds error. Perry pretty so that must be good right and exactly what this means is that well we have fewer repetitions for the same soundness right so we have to do we have to repeat instead of we're previous guys have to repeat one hundred twenty times we have to repeat maybe thirty times right each iteration cost about the same so we will factor three and that's roughly what what is happening and that results in a faster computations and the smaller. Size which is the most important thing so what are we doing here. We're considering M.P.C. with preprocessing So that's that's kind of the biggest departure from what was done before M.P.C. with preprocessing. It's considered in the general M.P.C. field. I'm not really buying it because the motivation for this is that sometimes you. You have spare time and you can do some computation before you know your inputs or before you know the function that you want to compute so you can do some more of that is independent of your input that prepares you. For for later and then you can really quickly solve the problem and the problem with that is that of course you spend a lot of time and usually a lot more time in the process of time but given your hint jumping ahead in the N.P.C. in the head the preprocessing is free. And that's kind of part of the of the magic sauce that the secret sauce that makes this efficient so with us. To explain. With pictures of what's going on with N.B.C. with preprocessing is that you can imagine that there is a trusted guy let's imagine there is a trusted guy first and he he goes online and he generates some. Some randomness at this given to all of these players with some. Correlations between between this randomness and then later we're going to use this correlated randomness to compute. OK so this there is this randomness the so there's secret states that are distributed to people and then the players come in where their inputs and then they start to. It's much faster and it's very efficient. So like I said in the regular M.P.C. this preprocessing is expensive because this generation of correlated randomness. Is expensive it involves a real. Expert. Tools. But here we. Go. It's actually really cheap it costs almost nothing. Because we have this preprocessing that we're going to use that our online stage can also be can benefit from this and can be very efficient. So now suppose we have the same P.C. with preprocessing protocol. Well it's not immediately compatible with N.B.C. in the head there's a couple of things but it's not too difficult to massage it into the into the right thing. So one thing to consider or to be aware of is that the prove or. So so in our in our case the prove or will generate and distribute preprocessing told the people but of course he can cheat in the process in achieving the preprocessing will result in cheating in the secure computation so we have to check it by correctness of preprocessing the way that we're setting up is that. You only to be to do it efficiently you can only do it by checking by opening all the parties so it's a little bit of a contradiction now we're facing because to open the preprocessing to check the preprocessing we have to open all parties but that violates the zero knowledge property right that doesn't work in the solution is actually is really straightforward here and this is that the preprocessing does not use the input W. OK it's independent of W. so I can generate the preprocessing. Generate one hundred preprocessing sets and you say open ninety nine of these fine I open everything there is still zero knowledge because I did not use my witness to generate the preprocessing and then the one that you did not opened that one I'm going to use for Secure Computing for the online face in the way that they described before so in pictures this is what is going on. This is basically what I just said Ellis will generate. She will act as this trust the dealer in the beginning and she will generate this preprocessing sets so this this is the entire preprocessing for for execution one and entire preprocessing for executive. Then Bob says open all. Fifty of or all but one randomly chosen. Ellis will open them if if she cheats so this is fully open there is no not and minus one out of N. is fully open so you can check everything that this was in fact constructed correctly. So else can cheat here if she is like ie if if she cheats in the preprocessing that the chose not to open right but that's she can do with probability one divided by AM So we do this phase one. And the Bob checks all of the. Minus one preprocessing and he says well OK I guess it's fine we can proceed and then Ellis will use. The remaining and open preprocessing new issues has full privacy in the protocol as we described before OK so. So this illusion is the same kind of as before except we are giving ourselves this powerful preprocessing tool and we show it I'm not going to have time to exactly show how we do it but. We do it in a very efficient manner. OK so. What I described at the high level is efficient zero knowledge because. The first phase opening them opening the things that you open a fine because there is they do not depend on the witness W. and the only secret the only thing here we have to protect is witness W. If you have some computation that does not depend on W. is not private this fine you can you can review it right and then the second phase is secure is your knowledge for the same reason as before the soundness is also easy to calculate Sun This means that you cannot prove the sun is means that if you're cheating you're going to be caught with some probability and it's also kind of the same. As before with the modification that now you have this first phase and you have probability one out of of the not being caught if you're. OK so I don't have too much time I have about ten minutes I want to very briefly go over it a very high level what the actual core of the protocol does. Luckily it's kind of very it's quite intuitive. So here is how we do. M.P.C. at the very high level so it's N.P.C. there's several kind of there's several fundamental approaches how to do it and the one that is most efficient here is M.P.C. from computing secure chairs so you can think of where there's a four step procedure so step one is that you look at your function that you're computing is a bully and circuit so fine that's natural you can always do that right and you function we can look at it as a Bill inserted. Then. We're going to secure a chair of the input there man all the players in the way that I described before. And then and this is the tricky step. We're going to go gave by gate. And we're going to keep this invariant where when we evaluate a gate we're we start because the inputs are already secret shares secret shared what we want we want to obtain a secret sharing of output of the gate OK so given the secret shares of the import we want to do some magic without revealing of what is going on without revealing true inputs on the gate we want to compute secret sharing of the output of the gate. It sounds like with magic but this actually is not too hard. So now in the next life kind of how it's done and then if if we know how to do it then we apply this to every gate of the circuit until we reach the output gate so now we have secret sharing of the output Gates Right now we. Just review it. In this exactly corresponds to learning the output we do not reveal the intermediate gaze because that's private information whatever goes inside the circuit is protected we cannot reveal it but the output sort of the output wires no gays the output wires is OK to reveal so once we obtain the shares on the up with what we just revealed. So let's. Break it exit out of an X. or sharing of of the bit X. So this will be in case of two party computation these could be just the two bits. There are random with the constraints the X. or two to be X. and so the standard X. or sharing. Actually So what I was saying is the secret the evaluation of the good elation of X. or gate is immediate If you look at it. Say this is X. or gate and this is. X. one is the share of X. is the value X. is a true value on this wire and Y. is a true value on this wire and disease what we want to calculate. Then X. one external are the shares of X. and Y. one Y. to his shares of Y. and so the party one will all share X. one and share Y. one and we want to give the party one shares you want well you can compute it. Simply by exploring your shares so the share of the output for party one will be X. one X. or Y. one and the share of the output for party two will be X. two X. or Y. two it's very easy to verify and it's kind of. It's always a pain to look at it an image and everything you have but once you just write it down it's simple algebra is the simplest way in you you write out. So this. I said this is the share. On the output wire of party one and the share own by output party or on party two you just open the parenthesis on rearrange them and you will see that this yes X. or of these two shares is equal to X. X. or Y. OK so now I just showed you not have but the quarter maybe of the magic that. How you can compute the gate. Without knowing the kitchen with only knowing the shares even without the communication you can proceed evaluating the X. or gate. And actually does generalize this you can you can compute. A linear combination of those just exorbitantly a combination with public multiplicative constants. OK So I think that we are low on time and I'm going to skip some of the lower level technical details of how exactly we manipulate the bits. And I'm going to go to. The result or are we going with this in terms of practicality. So this is this is a chart and I want to have some more specific numbers how this compares to prior work and so the resulting computation. That we have is this tool or Alliance and there are different because. This is the proof science and the proof size is different because we can choose how many parties we want to engage and for smaller number of parties it costs us less in computing because we need to emulate fewer parties in the head right but it's more. It's a more communication mean the proof is longer so this two lines this is the size of the proof for four sixteen parties which means less communication and this is the size of a proof of sixty four parties which means. More competition and this two lines our previous work and you can see that we are significantly better about factor three than prior work about in this range between three hundred gates and one hundred thousand gate circuits and what does this mean what do you get in that. To give you an idea is that their signature can be instantiated with the circuit size of one thousand and gates so we are well in the comfort zone for signatures. Compared to comfort zone meaning comparing to prior work. To give you specifics. This is the proof sizes that we have for four signatures that are size so signature is this is this column one thousand and Gates we need to compute the signature and the proof sizes are about thirty seven the best one is thirty seven killer bytes. With the computation time hundred twenty eight milliseconds and if you want to improve the competition time at the cost of communicating in a cost of signature size you can. You can do that. OK so I mention signatures I mention that. Part of this work is. Is up location to signature schemes and post quantum signatures so how. So why are we talking about post quantum what are reports quantum here standard signature schemes rely on public key primitives such as R.S.A. or defeat Hellman those have very deep very rigid algebraic structure inside and they are vulnerable to known attack for example is vulnerable to the short algorithm that you can factor integers in polynomial time we don't know how to do it fast enough and you are close to being fast enough but nevertheless theoretically. To quantum computer breaking R.S.A. the SO PRETTY MUCH many public E.O.P. aeration is the there in this domain but secretly operations such as hash functions and block ciphers and Shah they're not thought to be vulnerable to this and so the reason why our signature is. We say that it's post quantum secure is because we only use symmetric e primitives we do not use public appearances and that's that's a big deal it's really it's a high cost to avoid public key primitives. So. Let me tell you very quickly how you actually obtain a signature exactly how you obtain a signature from from this big picture that I described and it's actually really easy. Consider a block cipher aflat be for example a actually use a different block cipher because it's a smaller circuit size a circuit size is important here for us so let F. be a block cipher we choose a private key just a random string X. one hundred twenty eight and two hundred fifty six B.. Random string and the public key We're going to set to be a string that is equal to this block cipher are evaluated on the key X. that we chose one point zero. So now by the security properties of the block cipher by looking at why nobody can compute X.. Right because there's breaking in this breaking a if you see. Inclusion of zero and you can obtain a key from it everything is bad right there is nothing good thing you know you have to go shopping in a physical store even that doesn't work probably so so this is fine right so you cannot learn from public key and then Ellis is the only person who knows X. and so now what we're doing is that we put this circuit the check function that we proving in our head what what is doing is going to be the function that evaluates this. On the key X. on the point zero and it proves that is equal to Y.. That's the function that we are executing in our head there is the function that Alice is emulating and if the output is one then we know that Alice has X. right if the output is not one then well that's not it. OK And so everything everything everything that I was talking about there's kind of the combination that you can do it for signatures this is a very rich the signatures is kind of restricted functionality the only thing you can do with signatures is. The sign a message which is saying M L is basically what signature is that is a certificate that says Ellis signed this message this what we do is actually is much more powerful if you're not just signing a message you can prove arbitrary statements about yourself or about your about what you are what you know what you're certified to do so for example you can generalize this and you don't have to think about. But Ellis might have a certificate that is issued by D.M.V. or by the government says the age gender citizenship and so on and then when you prove things you can prove things like the signer of this message is a US citizen over twenty one. Right and the addition of this functionality is very trivial in terms of cost it will be almost the same cost as the. As the signature size that we discussed before so. In terms of comparing. For specific numbers with prior work so this paper we have signature sizes depending on the competition cause between thirty eight and forty five killer bites the prior war exam plus is one hundred eighteen kilobytes for a signature for a simple signature with all the parameters being the same so. Last use uses the same technology as us but we just optimize it using different different M.P.C. primitive. There is another scheme called Sphinx and their signature their base they're just doing a signature based on. Functions and their signature sizes forty one killer by so we're competitive with the other signature but we're much more for the size but we're much more powerful in terms of what we can prove. And so I have to conclude it is running. This competition for post quantum cryptography recognized and I think going to say and everybody recognizes that we need to look ahead a little bit. And. In this competition there's many submissions one of the submissions was by Microsoft Microsoft and others and so the bouzouki be possible those are the protocols from Microsoft and collaborators so they submitted their their work. As a candidate for for the post quantum signatures our work was concurrent but we didn't meet the deadline because it required a lot of technical implementation and so on but we presented our work recently and they know about it and they approached us for joining for the submission we agreed and we talked a nice the nice preliminary agree there's well and so we are in the process somewhere of. This war could be in the standardization process for post quantum signatures specifically So with that. Thank you very much this is my office if you if you want answers for the puzzle you can take my class which is and secure computation which covers. These topics as well as many other topics Thank you. Thank. You. We're doing. Well we use random Oracle in many places for optimization for example commitments. Talk to myself for example we do because we know that the inputs is high entropy so we don't do are. We just. Things like that.