Thank you so much for inviting me to the NTT Research Summit. And I’m really excited to talk to all of you 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 my outstanding graduate student Aayush Jain, who will be graduating soon, and my outstanding co- author, Rachel Lin from the University of Washington.

So let me jump right into it. We all know that constructing indistinguishability obfuscation, constructing IO, has been perhaps the most consequential open problem in the foundations of cryptography for several years now. There’ve been over 100 papers written that show how to use IO to achieve a number of remarkable cryptographic goals that really expand the scope of cryptography in addition to doing just remarkable, really interesting new things.

Unfortunately, however, until this work, until the work that I’m about to tell you about, all known constructions of IO required new hardness assumptions, hardness assumptions that were designed specifically to prove that IO was secure. And unfortunately, this has a tortuous history and many of the assumptions were actually broken, which led to just a lot of doubt and uncertainty about the status of IO, 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 a fundamental 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 Aayush, 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 LWE, PRGs in NCº, and the SXDH assumption of bilinear maps.

So what is this object? The object first starts with a PRG in NCº (NC zero), in other words a PRG with constant locality that stretches N bits of seed to M bits of output where M is N¹ plus Epsilon, plus any constant Epsilon greater than zero.

But in addition to this PRG, we also have these LWE-like samples. So as usual, we have an LWE secret s which is just a random vector, z p to the k, where K is the dimension of the secret, which is much smaller than N. We also have this public vectors A_i which are also [unintelligible].

And now what is given out, are these samples where the error is this X_i  that is just Boolean value (where these Xi’s are 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 LWE, where LWE samples, even with this sort of bizarre leakage on the errors from LWE, is still pseudorandom, or still has some pseudorandom 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 an 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. And that was it. If this was true, then we could actually build IO.

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 LWE samples Y and an additional secret W with the property that this additional secret W is actually quite small. It’s only a size M¹ minus delta for constant delta greater than zero. So it’s polynomially smaller from the output of the PRG. And crucially, the degree of this polynomial is only 2, it’s bilinear, in this secret double. That’s where the bilinear map will come in.

And in fact, this part we did know how to prove. 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 these polynomials exist that are only a degree 2 in these short secret values [unintelligible].

So now I’m going to show you how using our new ideas were actually going to build a special object just like this from standard assumptions which is going to be sufficient for building IO. And we’re going to have to modify it a little bit. 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.

So the first idea is let’s take these LWE samples that we have here and change them up a little bit. In this talk, I want you to think of K, the dimension of this secret here, as something very small, something like n to the epsilon. That’s only for this talk, not for the previous work.

All right. So we have these LWE samples from the previous work, but I’m going to change it up. Instead of computing them this way, as shown in the previous slide and on this slide, let’s add some sparse error. Let’s replace this error X_i with the error e_i plus x_i, where e is very sparse. Almost all of these e_i’s are zero. But when e_i is not zero is just completely random in all of [unintelligible], it just completely destroys all information.

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 PRG of x plus e, then that can still be computed the polynomial that is degree-2 in a short W. That’s previous work, the JLMS work from 2019. I’m not going to recall that to you, I just don’t have time to tell you how you do it but it’s very simple.

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 e is so sparse, PRG of x plus e is actually the same as PRG of x in almost every output location. It’s only a tiny, tiny fraction of the outputs that are actually corrupted by this sparse error.

So for a moment, let’s just pretend that in fact, we knew how to compute PRG of x with a degree 2 polynomial over a short sequence. We’ll come back to this, I promise. But suppose for a moment we actually knew how to compute PRG of x, not just PRG of x plus e. In that case we’re essentially already done. And the reason is there’s the LPN over Z_p assumption that’s been around for many years, which says that if you look at these sort of [unintelligible] examples – a_i  [unintelligible] but plus a sparse error, e_i where e_i is mostly zero, but when it’s not zero it’s completely random, then In fact, these samples look pseudorandom. They’re indistinguishable from a_i [unintelligible]. They’re just completely uniform over Z_p. And this has a long history which I won’t go because I don’t have time, but it’s just really nice assumption.

So let’s see how we can use it. Again, suppose for the moment that we were able to compute, not just the PRG of x plus e but the PRG of x.  Well, the first observation, since we’re adding the sparse error e_i, this part, the LPN part here, is actually completely pseudorandom by the LPN assumption. So by LPN over Z_p, we can actually replace this entire term with just r_i. And now note, there is no more information about x present in these samples. The only place where x is being used is as an input to the PRG and as a result, we can just apply the pseudorandomness of the PRG and say this whole say thing is pseudorandom and that’s it. We’ve now proven that this object that I wanted to construct is actually pseudorandom, which is the main thing that was so bothering us in all this previous work. Now we get it like that, just with a snap of our fingers, immediately from LP.

Okay, so the only thing that’s missing that I haven’t told you yet is wait, how do we actually compute PRG of x? Because we can compute PRG of x plus e, but there are still going to be a few outputs that are going to be wrong, so how can correct those few corrupted output positions to recover PRG of x?

For the purpose of this talk, because I don’t have enough time, I’m gonna make sort of a crazy simplifying assumption. Let’s just assume that in fact only one output position of PRG of x plus e was correct. So it’s almost exactly equal to PRG of x. There’s only one position in PRG of x plus e which needs to be corrected to get us back to PRG of x.

So how can we do that? The idea is again really, really simple. The output of the PRG is an m vector, it’s a dimension m vector. But let’s actually just rearrange that into a square of m by square of m 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 y.  And if we can add this matrix to PRG of x plus e, then we’ll get PRG of x.

So now the only thing I need to do is to compute this extremely sparse matrix. And here the observation was almost trivial. I could take a square root of m by one matrix, and this has y in position i, and I can take a 1 by square root of m matrix that just has 1 in position j and zero everywhere else. If I just take the tensor product, the matrix product of these two of this column vector and a row vector, then I will get exactly this correction matrix.

And note that these two vectors, let’s call them u and v, are actually really, really small. They’re only square root of m dimensional, way smaller than m. So if I want to correct PRG of x+e, all I have to do is add u tensor v , and I can add the individual vectors u and v to my short secret w it’s still short; that’s going to make w sufficiently bigger. And u tensor v is only a degree to computation. So in this way, using a degree to computation, we can quickly correct our computation to recover PRG of x. And now, of course, this was oversimplifying the situation, in general we’re going to have many more errors. We’re not just going to have one error, like as I mentioned, but it turns out that is also easy to deal with, in 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 root of m by square root of m matrix, you can split up this matrix with lots of little sub matrices and with suitable concentration bounds, simple balls and bins arguments we can show that we can never [unintelligible] this idea, this u tensor v idea, to correct all of the remaining errors.

That’s it. You see, there’s like three simple ah ha moments was all that it took to allow us to achieve this result, to get final, standard assumptions. And, of course I’m presenting them to you in this very simple way, with just these three little ideas, but of course they’re only made possible because of years of struggling with all the ways that didn’t work. All that struggling and mapping out all the ways didn’t work, was what allowed us to have these ideas.

And again, it yields the first IO construction from well-established cryptographic assumptions, namely the LPN assumption over Z_p, the Learning with Errors assumption, existence of PRG in NC⁰, that is PRGs with constant death circuits, and the SXDH assumption over bilinear maps, all of which have been used many years for a number of other applications, including such things as public key encryption, something as simple as public key encryption. That’s the context in which the assumptions have been used in the past. So very far from the previous state of affairs where we had assumptions that were introduced only [unintelligible] construction IO. And with that I will conclude. And I thank you for your attention.

Thanks so much.