Title: Complexity-based cryptography: A match that was once made in heaven


Speaker: Andrej Bogdanov
CUHK

Date: Friday  April 17, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

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.