Cryptography hinges on assumptions which, 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.
Chris Brzuska specializes in cryptography, and works at the intersection of cryptography with verification, IT security and complexity theory. He is a faculty member at Aalto University, Finland. Before, he was a faculty member of TU Hamburg, a post-doctoral researcher at Microsoft Research Cambridge and Tel-Aviv University. He obtained his PhD in 2012 at TU Darmstadt, advised by Marc Fischlin.