Obfuscation: The season 4 Finale

For many of the famous open problems of theoretical computer science, most researchers agree on what the answer is, but the challenge is to prove it. Most complexity theorists (with few notable exceptions) believe that P≠NP, but we don’t know how to prove it. Similarly, most people working on matrix multiplication believe that there is an Õ(n²) algorithm for this problem, but we’re still stuck at 2.3728596. We believed that primality checking has a deterministic polynomial-time algorithm long before it was proven and we still believe the same holds for polynomial identity testing.

The story of cryptographic obfuscation is different. This story deserves a full length blog post (though see my now outdated survey), but the short version is as follows. In 2001 we (in a paper with Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang) showed that what is arguably the most natural definition of obfuscation is impossible to achieve. That paper explored a number of obfuscation-related questions, and in particular left as an open question the existence of so-called indistinguishable obfuscators or IO. Since then there were arguably more negative than positive results in obfuscation research until in 2012, extending some of the ideas behind fully-homomorphic encryption, Garg Gentry and Halevi gave a heuristic construction of multilinear map, which one can think of as “Diffie Hellman on steroids” (or maybe LSD..). Then in 2013 Garg, Gentry, Halevi., Raykova, Sahai and Waters (GGHRSW) built on top of these maps to give a heuristic construction of IO.

The GGHRSW paper opened the floodgates to many papers using IO to achieve many longstanding cryptographic goals as well as show that IO provides a unified approach to solve many classic cryptographic problems. The fact that so many goals were achieved through heuristic constructions was not very comforting to cryptographers. Even less comforting was the fact that several cryptographic attacks were discovered on these heuristic constructions. The years that followed saw a sequence of constructions and breaks, giving cryptographers an “emotional whiplash”. Everyone agreed that IO would be amazing if it exists, but whether or not it actually exists depended on who you asked, and what paper in the eprint archive they read that morning…

The “holy grail” in this line of work is to base obfuscation on a standard assumption, and ideally Regev’s Learning With Errors (LWE) assumption. Of course, we don’t know that LWE is true (in particular LWE implies P≠NP) but if it’s false it would bring down so much of the field that cryptographers might as well pack their bags and do machine learning (or try to sabotage progress in quantum computing, since the only other standard assumptions for public-key crypto are broken by fully scalable quantum computing).

We have not yet achieved this holy grail (this is only the 4th season) but as described in this quanta article, there has been a remarkable progress in the last few months. In particular, Jain, Lin and Sahai (JLS) (building on a long sequence of works by many people including Ananth, Matt, Tessaro and Vaikuntanathan) obtained IO based on LWE and several standard assumptions in cryptography. This is arguably the first “heuristic free” construction, and is a fantastic breakthrough. However, there is still work to do – the JLS construction uses not just LWE but also a variant of it that is not as well studied. It is also based on pairing-based cryptography. This is an area that has thousands of papers, but for which known instantiations can be broken by quantum computers. However, there is yet more hope – in another sequence of works by Agrawal, Brakerski, Döttling, Garg, and Malavolta, Wee and Wichs, Gay and Pass a construction of IO was achieved that is “almost” heuristic free. It still uses one heuristic assumption (circular security) but has the advantage that apart from this assumption it only relies on LWE.

One can hope that in the next season, these two lines of work will converge to give a construction of IO based on LWE, achieving a “meta theorem” deriving from LWE a huge array of cryptographic primitives.

Want to learn more about these amazing advances? Want to know what’s next in store for IO? Fortunately there is a virtual Simons symposium on indistinguishability obfuscation coming to your computer screen on December 10-11. Authors of all the papers mentioned will join together in coordinated presentations to give a unified view of the field and the challenges ahead. We will also have a historical opening talk by Yael Kalai, as well as a talk by Benny Applebaum on the computational assumptions used, followed by a panel discussion with Yael, Benny and Chris Peikert. Finally, like every proper crypto event, there will be a rump session, though you will have to supply your own beer.

See the schedule of the workshop and you can register on this page.

Hope you to see you there! Bring your favorite programs to obfuscate with you* *_{Disclaimer/fine print: Due to large constants and exponents, we do not recommend the compiler be used on programs that are more than one nanobit long.}

Image credit: MIT