Having nearly extinguished my sabbatical credit, this semester I am teaching CS276: Foundations of Cryptography.
As in the 2002 edition, the course will teach, in some order, the progression from one-way functions to pseudorandom permutations, the use of pseudorandom permutations to do private-key encryption and authentication, the notion of trapdoor permutations, the notion of commitment scheme and zero-knowledge proofs, and the use of those tools, plus possibly random oracles, to achieve various notions of security for public-key encryption and signatures. Finally, a few bewildering lectures on multi-party computations.
What is the right order in which to teach all this? The “logical” order is roughly the one outlined above, which is also the order in Goldreich’s books
, in the Katz-Lindell book, and in many courses, including Jonathan’s and Salil’s.
A problem with this approach is that incoming students, who want to see how to design a cryptographic protocol and reason about it, are treated to week after week of purely complexity-theoretic results. Furthermore, there is a problem in motivating the notion of one-way functions because the most likely candidates are block cipher (i.e., pseudorandom permutations) constructions and number-theoretic functions. But motivating one-way functions with block ciphers defies the whole purpose of constructing block ciphers from one-way functions, and the number-theoretic candidates mostly come with trapdoors and are better introduced when talking about trapdoor permutations.
Our 2002 syllabus was organized by starting with trapdoor permutations and public-key encryption, and doing the one-way function theory and the private-key encryption later. Our reasoning was that students had already seen (usually, several times) RSA and the notion of public-key encryption, and could be immediately confronted with the point of modern cryptography by showing what kind of problems arise if one uses plain RSA to do deterministic encryption. Then the notion of message indistinguishability and semantic security arise quite naturally, and when later one gets to the theory of one-way functions it is good to already have an intuitive grasp of indistinguishability.
This year I would like to try something different (which is similar to the order in Mihir’s and Boaz’s courses) by starting with the definition of block cipher / pseudorandom permutation, showing how to do private-key encryption and authentication using block ciphers, and then showing how construct block ciphers from one-way permutations. (Perhaps giving number-theoretic candidates of one-way permutations.) Then continuing with trapdoor permutations and public-key encryption.
The idea is to keep a logical order in which the cleaner private-key theory is done first, but also to give the students a chance to see functioning protocols right away.
What would you do?