« search calendars« Beyond Crypto: A TCS Perspective

« On Optimal Algorithms and Assumption Factories

On Optimal Algorithms and Assumption Factories

August 19, 2018, 9:40 AM - 10:30 AM


Corwin Pavilion West

University of California, Santa Barbara

Boaz Barak, Harvard University

Throughout most of history, cryptographic schemes have been developed through a "cat and mouse" process whereas a cryptographer would propose a scheme, a cryptanalyst would break it, a new scheme is proposed, and so on and so forth.

Starting in the 1970's, a new paradigm of "provable security" emerged, where the security of cryptographic schemes would be based on a few basic computational assumptions or "axioms". However, given our current knowledge, coming up with these axioms is still more art than science, and recent years have seen a partial return to the "cat and mouse" process, with a proliferation of both assumptions and attacks.

In this talk I will describe an alternative approach for coming up with axioms, which is arguably more "disciplined", using conjectures on the optimality of classes of algorithmic techniques. We will illustrate the approach in the context of recent proposed constructions of indistinguishability obfuscators.

Part of the talk will be based on joint works with Zvika Brakerski, Ilan Komargodski and Pravesh Kothari, as well as with Sam Hopkins, Pravesh Kothari, Aayush Jain, and Amit Sahai.