>>Hi. Um, and thank you for inviting me to speak at the Entity Research Summit. And congratulations for NTT for setting up the neuroses club in the area. Okay, so I'm gonna talk about fully by deniable encryption and multiply the competition. And, uh, this is joint work with park from Harvard. And Santa will bring a, uh, she structurally right now in Russia during the rest. Um, so So so consider thesis, uh, two kids, which maybe some of you still remember its violence for check the incredible kids. And they are want they want to talk to each other privately without her mother learning what talking about. So here they are using this lead pipe, which is that cannot be secure Channel and and violent can say to that track that she doesn't want to do her homework and check it was the watch movie. And she knows that the judge will understand what she says. We hear what she says, but her mother, their mother, is not going to anything because it z this lead pipe. She doesn't know what they're talking about. Um and and and we know how to implement this actually in without lead pipes in the software will Do you have encryption, which, you know, you know, for I know, uh, 40 for the last 40 years or so, but actually for many more s. Oh, this is great. Encryption gives us private communication against, uh, eavesdropping adversary. So passive adversaries s but But you know that mothers can be more than passives. What if the mother he goes and asks Pilot that? What did you talk? What do you say to judge it So you know, if valid, really said, you know, used this'll end pipe. She can say whatever she wants to say. I actually said that I was study, and then the mother goes to judge. I can ask him what did about tell you, and she said that she was studied and the mother still cannot tell anything about what happened. She doesn't know trillions. Death was sent or not. Um, in fact, even if violence said that she was studying and and Jackson said something else that you know, she said she was she rather watch movie. Even then the mother doesn't know who was right. I mean, not from the pipe music. Look them in the eye and not this way, but not from the communication she doesn't. Andi. In fact, we could go on like this, and, you know, the lead type doesn't help at all to understand what really have. And this is really another very important form off this really secure channels that it doesn't allow external parties. Course, there's, uh, certain what really happened. Even when they asked to see all the internals of all the parties. In fact, even further, the Violet Jack Jack have no way to actually convince the mother that this is what happened. Even if you want, right, they have no way of actually proving to the mother that they said this and not the other thing with this lead pipe. So the question is can be obtained a similar effects with, you know, software encryption. Uh, can we have an encryption scheme that has the same sort of properties? So we know that Peoria, the total encryption doesn't have this property. That encryption leaves traces. So there's this cipher text that that the mother of the course of seized. Then when the mother goes toe the parties and you know the ballot judge, you can ask him uh, give me. Show me your randomness. Show me all the internals. I want to see what really? How you generated the text and how you decrypted it with no money. Encryption is only one way that, but inject, checking opened the suffer text, and therefore, there is no real privacy anymore. Um, so So this is the case. So so really to do to address this issue? The this this concept of deniable encryption that was considered, uh, you know, many years ago. Andi idea here is that you wanted encryption scheme that provides, uh, protection of privacy. Uh, on ability, toe keep private. You really, really, really value. And maybe, ah, fake or lie about what you say in a convincing way, even against such a course. Uh huh. So and so? So the idea is that, you know, So they actually do you think of three types here, So there is centered in apple. So we're just going us to center off the off the message. You know how How did you encrypt the message? Show me your encryption. Andalus Suing The decryption key is public. Um, and if you go to the receiver and ask him show me your decryption key. I want to see how you decrypted. And you can also think about natural case where the course actually goes to both parties and ask them for the for the internals and compares one against the other. Right? So this is the bite inability concept. Andi, you can, of course, naturally generalize it. Not just to encryption to, say, two party competition soon here, Violent and Jack. Jack. You know, uh, maybe not even trust each other fully, But they want toe compute together, you know? Or, you know, do they actually know a kid they both know and rapes in school, Right. So, So, So violent has her own list of kids, and she knows grapes and injection to, and they want to do this to Paris ST secure competition to figure out if they keep the both. And so if they have this ideal trusted party or stay for somewhere where they can actually do the security applications uh um, securely then they can, of course, learned the answer without learning anything else. And also, if the mother comes in after the fact and ask them, you know who I see that you were trying to figure out who very school, you know. So tell me what you did. Tell me your inputs them you are supposed to give me all the randomness. And And I want to know for the kids that you know, that vaping school. So if they were using such such a physically, I didn't secure gadget then, uh, then they can say You know why? You know? So So what is the state of, I don't know, anybody Invasion did Jack this theater and I got nothing into something or nothing. Jake Jackson. Consistency and off course. Mother has no way of knowing if this is true. No. And even if, uh, injected decides to tell the truth and actually tells is really important. Really put real randomness. And, uh, no randomness here and violent tells still here. Nothing. Nothing that the mother has no way of knowing which one is like. She clearly some of one of them is language. Doesn't know which one. I mean, chicken again looked deep in the eye, but not from the communication. She cannot figure out. Um, so s so we want to get something like that for for two party competition. Uh, and and and again, eso again, again, again. The case that, you know, one is like going to the truth is still don't know. Um, so the question is there a protocol that that one is still behavior, and, uh, incredible. How do you define us? Uh, and the point is that, you know, Okay, 11 further thing toe. Think about, you know, this doesn't shouldn't end with two parties can think about three or more parties on, uh, and the same thing happens. You know, just maybe the trust structure, the consistency structure becomes more complicated. Uh, you know, you could buy groups of people which is consistent with each other and not without, um Okay, so So what are our results here? So first result is regarding encryption. So we come up with the first bite, the novel communication protocol. It's not encryption because it's three messages. Uh, so it is three messages, and it is this way need a reference string, which is like, programs in the sky. And but it's a short registering. I mean, one short programs that everybody in the world uses for the encryptions for the entire duration of time. and our assumptions are some expansion, Leo in one functions, uh, and on. But just to say that what was done previously? It was just senator deniable or receiver deniable, um, And then and nothing that we do is that actually way define and also obtained this extra property, which we call off the record inability which talks with you about the case where, as I said before, that one party, uh uh, is saying one thing and the other practicing nothing they insisted. So they cannot. There is no way for them to frame each other. Um, and the way the other result is regarding a multiparty function evaluation on Dhere, we come up with the first all deniable secure function evaluation for quote Well, you know, I mean, I mean that the protocol with the adversary or the coarser expect to see all off the transcript of the competition, including all the randomness in all the internal state of all the parties eso superiors results in this area always assumed that you know, either the course only can concourse on some of the parties or if you can force all the parties and there is some some physical gadget, uh, which is crucial information about the personnel puts and you know, nobody can see inside, so no, here, we actually that the Attackers see everything. Uh, because they think they see everything on we can still provide inability onda protocol. Also, our protocols also withstand inconsistencies. Mean the case off this off the record style that one party says one thing partisans don't think. But this is only in the case of two parties and only for functions where the input size is polynomial in play. Put size. Uh, domain. Um, so in this actually interested open question how to extend it beyond that. Uh, so just to say that this is kind of it's a surprising thing that you can even do such thing, because what it allows you to do is actually such to completely rewrite history. Eso you during your competition on. Then somebody comes, and that will show me everything that happened. All the runners, all the entire transcript, the competition from beginning to the end. And you can now tell them something else. Not something that really happened. I mean, they see, you know, the public messages they see it on thistle is un contestable, but you can show different internals that there are very different than what really happened. And still nobody can catch you. So it's really some sense. Uh, who knows what's really happened? Um, so anyway, so So this is the, uh this is the result. Let's just say a few words about fully deniable encryption. Uh, just toe give a more detailed So So So So, how do you define this? Fully deniable encryption. So first I want to say that, you know, if you just, uh if the parties have appreciate key then, uh, deniability is with these because what you know, you just in orderto cryptic message just want some part of the key. And this one temple is completely deniable, right? Because you can just take this self a text and claim that it was any message encryption off any message off your choice. But just, you know, extra it. But just coming up with the key, which is the Solvents Architects as a message of futures. So this is completely diamond by both parties, and even it's off the record because if the two parties say different things, there's no way to know what's right. So Eh, so what? But it means that, you know, the hard part is actually had to come up with this shirt key, uh, in a deniable way. So you can actually later argued that this key was an, um so s so we need kind of deniable key exchange, and then this is what we do. So we come up with this idea by by the application of what? This what this means. So it's a protocol, you know, for two parties, uh, change, keep with messages and which gives you the ability to life. Somebody asked you which was key and claim it was anything, uh, later. So more formally. So we have two parties. One You know, this is the key change protocol for one party, and this is the kitchen for the other party in each party also is equipped with this faking algorithm. This is s faking arctic. I keep, you know, Senator, receiver, Even though it's not teach change, it's affecting and breaking. Allows you to come up with fake randomness. That demonstrate kills anything and we want correctly since semantic security as usual and we want toe this s fake takes a transcript and the randomness and the old key in the nuclear that you want. Andi comes up with fake randomness such that, uh um and this is you know, that that consistent with this new key, k prime and the same for the receiver. It comes up with a new randomness. The assistant to the crime and the requirement is that, uh, the attack. I cannot tell the difference between the experiment when you know the key key was exchanged. These transcripts respecto the real key or the case where the key was exchanged, and then the faking accurately going folk What? The adversary seizes the actual transcript, but then opening to a different. So there's a distinguished group. Um, And then what if the parties that were okay then there is another requirement there that says that even if the parties you know, one of them face, the other one doesn't and they then you can't tell which one will effect in which one wants to tell the truth. Onda point is that this to this to produce properties together really give you what you would like for my dearly your channel, even with respect toe courses. Um, so just to point out that you know this, this properties hold only if the parties in the follow the protocol during the execution actually choose randomness is they should. Otherwise things does work. In fact, otherwise, there's nothing that could work because the party's chief from the beginning and just use the terroristic protocol instead of randomized or just, you know, just randomness, which is predetermined. And, of course, nothing you can do. Uh, however, you know, there are, of course, interesting situations where it is. You know, it's reasonable to trust that the parties are actually using the randomness Aziz instructed during the execution of the protocol, for instance, we're thinking about voting this something can be forced, uh, by the voting booth, but you know, other situations. But this is kind of like essentially eso maybe another minute to say a few words about, you know, just like construction. How it kind of works in, you know, in general. So So we have, like, a three months, three rounds protocols. So we have four programs, you know, two from each party don't to deal with the three messages. Then we have a faking program for each party, so the way it works, you know, first, the violent here is has this is Harris randomness and actually chooses the key that they're going Thio agree ahead of time. It inputs to the first program which is going to think of it is the office care program black box program. And there's the message. First message is basically a harsh appear f off the K and then the, uh and then the responder gets this message has its own randomness and outputs. Another message, which is the hash off the first message agronomists. And then the third message now is going to be a new encryption off the key on the hashes and the end to a previous messages. This is, ah, company encryption off this one long spring and then the fourth with the fourth program just takes the randomness off the receiver and the two messages and put it in. And then I'll put the key, which is decrypted essentially the Crips, the subtextual from here in the old checks, right? And then the faking programs. What they do, they just take those. The transcript and the cookie and the new key and the striking program here are puts a new randomness for the senator and this one There's a new randomness for the receiver and the way it does near random estrogen offering work eyes, uh, is again It's kind of fact natural a t least the face of it. It uses the seeking hidden triggers idea off, off, so high in waters for descending on the inability that, you know, trigger each one of those programs toe put actually write message even when you get this, uh, crime on eventually this k problems are Well, the problem is that this scene in triggers, you know, give you local consistency for each problem by itself. This was this was the east their goal. But there is no global consistency about those six programs together and and get the six programs together to be consistent with the fact that the key would actually keep prominent K is high in contribute. And this is something that we become the main challenge of this work. This also, I did this three messages because if you have only to then there is no way to get a double consistency. Ah, s O s. So this is, uh this is the test on just to say about, you know, the future. So definitely we want stronger than ability for for MPC. As I said, we just give partial results there on. Then there is kind of, like some very interesting questions. One is like in general, You know, we know that your is very nice, but in many cases, we actually can do things without, uh but in this situation with prosecution, but maybe the inability of one of the very few cases where actually, we don't have any other way to do things out of the Neo. Is it really essential? Can we prove it? You know, and if not, can we do without? Can we get around CRS? Can you actually do with public friend of mysterious? Uh, you know, and more generally? Uh, no. We actually, uh, sweated a lot. You know, spit blood. In order to make this thing work with Leo and because I always really hard to work with, you know, would agree toe, find some some some general set of tools to work more easily. I was there. Um, Louis, thank you very much on death's

>>thank you so much that sake for inviting me to the Entity Research Summit. And I'm really excited to talk to all of them today. So I will be talking about achieving indistinguishability obfuscation from well founded assumptions. And this is really the result of a wonderful two year collaboration with But now it's standing. Graduate student I use chain will be graduating soon on my outstanding co author, Rachel Lynde from the University of Washington. So let me jump right into it. We all know that constructing indistinguishable the obfuscation. Constructing Io has been perhaps the most consequential open problem in the foundations of photography. For several years now, they've seen over 100 papers written that show how to use Iot to achieve a number of remarkable cryptographic goals. Um, that really expand the scope of cryptography in addition to doing just remarkable, really interesting new things. Unfortunately, however, until this work, I told the work I'm about to tell you about all known constructions of Iove. All required new hardness, assumptions, heart assumptions that were designed specifically to prove that Iowa secure. And unfortunately, uh, this has a torture of history. And many of the assumptions were actually broken, which led to just a lot of doubt and uncertainty about the status of Iot, whether it really exists or doesn't exist. And the work I'm about to tell you about today changes that state of affairs in the continental way in that we show how to build io from the combination of four well established topographic assumptions. Okay, let me jump right into it and tell you how we do it. So before this work that I'm about to tell you about over the last two years with Rachel and Ayush, we actually constructed a whole sequence of works that have looked at this question. And what we showed was that if we could just build a certain special object, then that would be sufficient for constructing Io, assuming well established assumptions like L W E P R g s and M C zero and the 68 assumption of a violin. Your mouths. Okay, So what is this object? The object first starts with a P. R G and >>S zero. In other words, of trg with constant locality that stretches end bits of seed to M bits of output where am is ended one plus Epsilon for any constant Epsilon zero. Yes, but in addition to this prg, we also have these l w we like samples. So as usual, we have an elder Bluey Secret s which is random vector z b two k, where K is the dimension of the secret, which is much smaller than any way also have this public about vectors ai which are also going to be okay. And now what is given out is are the elderly samples where the error is this X I that is just brilliant value. Uh, where these excise air Also the input to our prg. Okay, unfortunately, we needed to assume that these two things together, this y and Z together is actually pseudo random. But if you think about it, there is some sort of kind of strange assumption that assumes some kind of special leakage resilience, property of elderly, we where elderly samples, even with this sort of bizarre leakage on the errors from all debris, is still surround or still have some surrounding properties. And unfortunately, we had no idea how to prove that. And we still don't have any idea how to prove this. Actually, So this is just a assumption and we didn't know it's a new assumption. So far, it hasn't been broken, but that's pretty much it. That's all we knew about it. Um and that was it. If we could. If this is true, then we could actually build. I'll now to actually use this object. We needed additional property. We needed a special property that the output of this prg here can actually be computed. Every single bit of the output could be computed by a polynomial over the public. Elder Louise samples Why? And an additional secret w with the property that this additional secret w is actually quite small. It's only excise em to the one minus delta or some constant delta gradients. Barroso polynomial smaller from the output of the prg. And crucially, the degree of this polynomial is on Lee to its violin e er can this secret double that's where the bottle in your mouth will come. Okay. And in fact, this part we did not approve. So in this previous work, using various clever transformations, we were able to show that in fact we are able to construct this in a way to this Parliament has existed only degree to be short secret values. Double mhm. So now I'm gonna show you how using our new ideas were actually gonna build. That's a special object just like this from standard assumptions. We're just gonna be sufficient for building io, and we're gonna have to modify it a little bit. Okay? One of the things that makes me so excited is that actually, our ideas are extremely simple. I want to try to get that across today. Thanks. So the first idea is let's take thes elder movie samples that we have here and change them up a little bit when it changed them up. Start before I get to that in this talk, I want you to think of K the dimension of the secret here as something very small. Something like end of the excellent. That's only for the stock, not for the previous work. Okay. All right. So we have these elderly samples right from the previous work, but I'm going to change it up instead of computing them this way, as shown in the biggest slide on this line. Let's add some sparse hair. So let's replace this error x i with the air e i plus x I where e is very sparse. Almost all of these IIs or zero. But when the I is not zero is just completely random in all of Z, pizza just completely destroys all information. Okay, so first I just want to point out that the previous work that I already mentioned applies also to this case. So if we only want to compute P R g of X plus E, then that can still be computer the polynomial. That's degree to in a short W that's previous work the jail on Guess work from 2019. I'm not going to recall that you don't have time to tell you how you do it. It's very simple. Okay, so why are we doing this? Why are we adding the sparse error? The key observation is that even though I have changed the input of the PRG to the X Plus E because he is so sparse, prg of explosive is actually the same as P. R. G of X. In almost every outlet location. It's only a tiny, tiny fraction of the outputs that are actually corrupted by the sparse Arab. Okay, so for a moment Let's just pretend that in fact, we knew how to compute PRGF X with a degree to polynomial over a short seeking. We'll come back to this, I promise. But suppose for a moment we actually knew how to compute care to your ex, Not just scared of explosive in that case were essentially already done. And the reason is there's the L. P n over zp assumption that has been around for many years, which says that if you look at these sort of elderly like samples ai from the A, I s but plus a sparse air e I where you guys most zero open when it's not serious, completely random then In fact, these samples look pseudo random. They're indistinguishable from a I r r. I just completely uniform over ZP, okay? And this is a long history which I won't go because I don't have time, but it's just really nice or something. Okay, so let's see how we can use it. So again, suppose for the moment that we were able to compute, not just appeared you've explosive but appeared to you that well, the first operation that since we're adding the sparse R E I This part the the L P N part here is actually completely random by the LP an assumption so by L P and G. P, we can actually replace this entire term with just all right. And now, no, there is no more information about X present in the samples, The only place where as is being used in the input to the prg and as a result, we could just apply to sit around this of the prg and say this whole thing is pseudo random and that's it. We've now proven that this object that I wanted to construct it is actually surrounded, which is the main thing that was so bothering us and all this previous work. Now we get it like that just for the snap of our fingers just immediately from people. Okay, so the only thing that's missing that I haven't told you yet is Wait, how do we actually compute prg attacks? Right? Because we can compute p r g of X plus e. But there's still gonna be a few outputs. They're gonna be wrong. So how can we correct those few corrupted output positions to recover PRGF s? So, for the purpose of this talks because I don't have enough time. I'm gonna make sort of a crazy simplifying assumption. Let's just assume that in fact, Onley one out the position of P r g of X plus e was correct. So it's almost exactly what PR gox. There's only one position in prg of Ecstasy which needs to be corrected to get us back to PR gox. Okay, so how can we do that? The idea is again really, really simple. Okay, so the output of the PRG is an M. Becker and so Dimension and Becker. But let's actually just rearrange that into a spirit of them by spirit of them matrix. And as I mentioned, there's only one position in this matrix that actually needs to be corrected. So let's make this correction matrix, which is almost everywhere. Zero just in position. I j it contains a single correction factor. Why, right? And if you can add this matrix to prg of explosive, then we'll get PR dribbles. Okay, so now the Onley thing I need to do is to compute this extremely sparse matrix. And here the observation was almost trivia. Just I could take a spirit of em by one maker That just has why in position I and I could take a one by spirit of them matrix. I just have one in position J zero everywhere else. If I just take the tensor product was music the matrix product of these two of these two off this column vector in a row vector. Then I will get exactly this correction matrix. Right? And note that these two vectors that's called them you and be actually really, really swamped their only spirit of n dimensional way smaller than them. Right? So if I want to correct PRGF Expo see, all I have to do is add you, Tenzer V and I can add the individual vectors u and V to my short secret w it's still short. That's not gonna make W's any sufficiently bigger. And you chancery is only a degree to computation. So in this way, using a degree to computation, we can quickly, uh, correct our our computation to recover prg events. And now, of course, this was oversimplifying situation, uh, in general gonna have many more areas. We're not just gonna have one error, like as I mentioned, but it turns out that that is also easy to deal with, essentially the same way. It's again, just a very simple additional idea. Very, very briefly. The idea is that instead of just having one giant square to them by sort of a matrix, you can split up this matrix with lots of little sub matrices and with suitable concentration bound simple balls and pins arguments we can show that we could never Leslie this idea this you Tenzer v idea to correct all of the remaining yet. Okay, that's it. Just, you see, he's like, three simple >>ah ha moments. What kind of all that it took, um, that allowed >>us to achieve this result to get idol from standard assumptions. And, um, of course I'm presenting to you them to you in this very simple way. We just these three little ideas of which I told you to. Um, but of course, there were only made possible because of years of struggling with >>all the way that didn't work, that all that struggling and mapping out all the ways didn't work >>was what allowed us toe have these ideas. Um, and again, it yields the first I'll construction from well established cryptographic assumptions, namely Theo Elgon, assumption over zp learning with errors, assumption, existence of PR GS and then zero that is PR juice with constant death circuits and the SX th assumption over by linear notes, all of which have been used many years for a number of other applications, including such things as publicly inversion, something simple public inversion that's the That's the context in which the assumptions have been used so very far from the previous state of affairs where we had assumptions that were introduced on Lee Professor constructing my own. And with that I will conclude, uh and, uh, thank you for your attention. Thanks so much.