Chickens and Eggs

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?

12 thoughts on “Chickens and Eggs

  1. As a graduate student who has taken Mihir’s course, I highly recommend his structure. (As for his course, it was simply amazing.)

  2. I chose to teach randomized algorithms instead (variant of cs174, in berkeley-speak), and have my students (and me) implement Christos’ 2SAT algorithm and Karger’s min-cut algorithm.

  3. That’s a great motivation for coming up with good combinatorial (non number theoretic) one-way functions! Then one won’t be stuck with examples of one-way functions that are too good.

    Anyway, I think I am still in favor of doing things in the right order (Goldreich’s order).

    I took cryptography with you and David Wagner in 2002 and here is what I remember. The beginning was very confusing – the definition of public-key encryption didn’t fit on a single whiteboard. (I hadn’t seen long definitions like that before.) And RSA was new, so trying to figure out how it works and what it has to do with the definition at the same time was difficult.

    For a while I found these concepts that need long definitions unpalatable.
    Maybe it is fun to start informally with RSA or block ciphers as a motivating example but trying to put it in context from the beginning can be confusing.

    (Looking back at your 2002 syllabus the Goldreich-Levin theorem was taught on Jan 31 and then one-way functions on Feb 14. Why?)

    I like starting with the egg. Yes many will find the chicken tastier but it is not so good on an empty stomach…

  4. I agree that starting with OWFs might be too abstract.
    Here’s what I would do (I think that it’s quite similar to Katz-Lindel):

    1. perfect secrecy (one-time pad)
    2. computational indistinguishability as a relaxation of perfect secrecy + introduction of PRGs and stream ciphers

    3. Stateless encryption – PRFs/PRPs as block ciphers
    (it’s nice to describe PRFs as PRGs with exponential stretch)
    + practical and theoretical constructions (i.e., DES/AES and GGM).

    4. using PRFs for MACs.

    5. Minimizing the assumptions: OWFs/OWPs => PRGs

    6. Public-key cryptography (starting from trapdoor permutation)….

    I think that transition from perfect secrecy to computational secrecy (or from one-time pad to stream cipher) is natural and smooth. Also, it is still related to practical constructions.

  5. As Benny says, the order that things are done in Katz-Lindell (and in my course) is *not* what you describe. (See Both start with an emphasis on cryptography – namely how to define security – not on the complexity-theoretic assumptions.

    The definition of a OWF comes almost a month into my course, and even later in Katz-Lindell. My outline is very similar to what Benny describes, except I move Item 5 between Items 2 & 3 and move Item 4 on MACs later, to be done together with digital signatures.

    The reason I don’t take PRFs/PRPs as a basic starting assumption is that it seems to eliminate much of the “surprise” that I felt when I learned cryptography – that one can start with very simple and plausible complexity assumptions and achieve amazingly strong notions of security.

    I also don’t buy your point about OWFs. Multiplication is an easy candidate to describe right away that doesn’t obviously come with a trapdoor, and there is also a simple candidate OWF based on subset sum.


  6. I taught our senior-undergrad Crypto course for the first time from Katz-Lindell last Fall. Of course, an undergrad class at Maryland is very different from a grad class at Berkeley, but here are my comments for what they are worth. I like the book. One thing I learnt, though, is the need for regularly solving concrete problems (say, textbook exercises) in class. As andrej says, the type of reasoning in such a course is new for most students (and was, for me, the first time I encountered it). Thanks to you and the commenters for the various pointers to courses and to Oded’s papers: I plan to study these for my next-time teaching of the course.

  7. Thanks for all the comments, and keep them coming.

    The idea of starting from the definition of pseudorandom generators as a computational analog of one-time pad is very appealing.

    Sorry for misrepresenting Salil’s syllabus (I had looked at the course description instead of the syllabus page) and the order in the Katz-Lindell book (which I haven’t received yet).

  8. We decided to switch the order in Katz-Lindell for exactly the reasons you mention.

    Also, especially in response to andrej, I think it’s important to keep in mind that a crypto course (especially at the undergrad level) should serve people other than theorists. For someone interested in security (or just interested in understanding how things work in real life) going through one-way functions is irrelevant, and it makes sense to de-emphasize it.

    Luca, I would be happy to send you a desk copy of our book. =) You may find it does what you want.

  9. For what it is worth, here’s the course I taught some time back. I’m afraid the next time around it will probably look very different, to make it attractive to non-theory students.

    I have found the IND-* definitions too technical to motivate. I try to use a “UC”-style definition (I call it SIM-*) which is somewhat more direct.

  10. I chose to teach randomized algorithms instead (variant of cs174, in berkeley-speak), and have my students (and me) implement Christos’ 2SAT algorithm and Karger’s min-cut algorithm.

  11. DRE BEATSI chose to teach randomized algorithms instead (variant of cs174, in berkeley-speak), and have my students (and me) implement Christos’ 2SAT algorithm and Karger’s min-cut algorithm.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s