HIIT Foundations Friday event of 2023 organized on Friday 24 March starting at 11am in Unioninkatu 38, Hall A205 (“Topelia”) and followed by lunch at about noon.

Speaker: Prof. Chris Brzuska (Aalto University)

Title: Cryptographic (r)evolutions: From MiniCrypt to Obfustopia

Abstract:
“In 1995, Impagliazzo [1] conceived of several worlds to structure the landscape of average-case hardness. For cryptographers of biggest interest were MiniCrypt and CryptoMania. MiniCrypt is a world, where one-way functions (OWFs) exist, functions that are (1) easy to compute, but (2) hard to invert, on the average over a random input, but more “fancy” cryptography does not exist. CryptoMania is a world where one can generate a one-way function even with a trapdoor so that (1) computing the public function is easy, (2) inverting the function is hard on the average, but (3) inverting is easy when knowing the trapdoor. While such trapdoor functions were originally controversial, they soon became a solid building block of our internet security infrastructure. Moreover, the cryptographic community explored even more adventurous assumptions, first discovering the possibility of fully homomorphic encryption in 2009 and then indistinguishability obfuscation in 2013. Fully homomorphic encryption allows computation on encrypted data without knowing the key—and indistinguishability obfuscation allows to turn any program into an unintellegible version of it. We start our talk with a discussion of MiniCrypt. One-way functions are far more powerful than one might think at first sight and even allow us to build pseudorandom generators, pseudorandom functions and symmetric-key encryption schemes. We then move to the very adventurious world of obfustopia and explore the conceptual implications of indistinguishability obfuscation (iO). Clickbait version: 5 odd facts about indistinguishability obfuscation—you won’t believe the 1st and the 5th. :-)Preparation (optional):
Section 2 of Impagliazzo’s essay [1] is a very fun 6.5-pages long introduction to average-case hardness. I turned Section 2 into a popular science talk [2] a couple of years ago, where I explain P vs. NP, average-case hardness, MiniCrypt and CryptoMania in 15 minutes.
[1] https://www2.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
[2] The talk starts at min 2:30, the discussion of Impagliazzo’s 5 worlds starts at 8:30 and ends at around 23:00 https://www.youtube.com/watch?v=7H4qN73Y36Q “