Test of Time 2013 Award

Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters:
Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits

This remarkable paper gave the first candidate solution to the problem of general-purpose software obfuscation. The ideal obfuscator would convert any computer program into an equivalent program that gives no information about the original program apart from its functionality. While such an obfuscator would have extremely powerful applications, earlier work showed that it is impossible to achieve, and introduced instead a weaker notion called indistinguishability obfuscation (IO): the obfuscated versions of any two equivalent programs are indistinguishable. It remained unclear both whether IO is achievable, and whether it would be useful.

Amazingly, this paper showed both. It was the first to give a candidate solution with heuristic evidence that it satisfies IO.  Moreover, it was the first to give a significant application of IO: it showed that IO can solve the central open problem in functional encryption. Since publication, a long sequence of follow-up works have shown that IO can be used to achieve a variety of objectives in cryptography for which no other approach was known.