Chris Brzuska lecture at TU Eindhoven

Date:   Thursday 16.11.2017, 10-11 hr. 

Place: Filmzaal de Zwarte Doos + Lounge, Eindhoven.

Speaker: Chris Brzuska

 

 

Abstract:
 

Cryptography hinges on assumptions that, if true, imply that P is not equal to NP. Therefore, cryptographic assumptions are unlikely to be proven true in the near future.

Yet, not all cryptographic assumptions are equally likely to be true. In 2005, Russell Impagliazzo gave an invited talk titled "A personal view of Average-Case Complexity" where he distinguished between the (minimal) "MiniCrypt" world where One-Way Functions exist and the (more adventurous) "Cryptomania" world where One-Way Functions with trapdoors exist.

Since then, the cryptographic community has become substantially more adventurous. In 2009, Craig Gentry suggested a candidate fully homomorphic encryption (FHE) scheme. If FHE exists, numerous long-standing open crypto problems could be solved. In 2013, Garg, Gentry, Halevi, Raykova, Sahai and Waters suggested a candidate construction for a yet more adventurous primitive called indistinguishability obfuscation (iO). If iO exists, it solves numerous further big open problems in cryptography. Sceptics call this world "Obfustopia".

Yet, iO is not only a strong assumption, but also a conceptually intriguing object. iO is mutually exclusive with other cryptographic assumptions that were believed before... ...and (unlike most of cryptography) iO exists if P equals NP! In the talk, we will discuss the conceptual oddities of iO.