Abstract :

In this talk I plan to sketch the current landscape of complexity-based cryptography, emphasizing some of its celebrated highlights, but also its disappointing failures. While complexity-based cryptography has been quite successful in explaining its own failures, it has been less good at providing alternatives to them.

I will talk about some recent work (joint with Kunal Talwar and Andrew Wan) that attempts to bypass the current limitations of complexity-based cryptography. While the tools I plan to describe are far too weak for building useful cryptographic protocols, they may shed more light on the relation between complexity theory, cryptography, and the various obstacles that lie between them.