Cryptography, both theoretical and applied, is one of the most successful areas in the intersection of applications and theoretical computer science. The vast majority of constructions (in fact, but more or less 10-15 examples) all the rest of the literally 1000s of constructions applied in 100s of different settings are black-box.

This course consists of two parts.

Black-box constructions (what we can do): we discuss in detail some of the most fundamental constructions in Private- and Public-key cryptography (e.g. El-Gamal, Yao’s public-key system from trapdoor permutations, and the Cramer-Shoup cryptosystem).

Black-box separations (what we cannot do): this is a unique topic for a graduate course. There are 1000s of cryptographic constructions, based on 10s of assumptions (and possibly many more variants of these assumptions). Are all these assumptions needed? We can only prove such a thing in some constructive way. For example, if we only allow black-box constructions, then what can we say about basing the construction of a one-way permutation on the existence of a one-way function? Why up until today there is no such construction? In other words, if we confine ourselves using black-box techniques to do cryptography do we really need all these “obscure” assumptions? The answers to these questions are yes, studied in the recently emerging and exciting field of black-box separations.