>>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.