As promised, here are the notes I developed for the (too brief) lecture that I gave in our final meeting. Zero-knowledge
This is what I would have covered today in class: KEMs-and-DS
To go with it, here is a video that proves the result claimed in the KEM notes, i.e. that the composition of a secure KEM and a secure IV-based encryption scheme gives a secure PKE scheme. Note that the underlying IV-based encryption scheme need only be secure against adversaries asking a single query, meaning that even something like CBC/CTR with a fixed IV works!
I’m really sorry, but this morning one of the rooms in my house flooded. I have to cancel class. I will put up screencast videos today to cover what I would have covered today –KEM-DEM schemes and the beginnings of digital signatures. Again, I’m very sorry! Please email me question or concerns if you have them.
In advance of lecture (Thursday 4/12), in which we will introduce the idea of a key-encapsulation mechanism (KEM), I’ve prepared a video that shows how to build a KEM from RSA, and gives a proof that it is a secure KEM in the ROM. We’ll see in lecture how to build an efficient PKE scheme from a KEM and a symmetric encryption scheme. Thus, you’ll see how to build a provably secure PKE scheme from RSA, via this design paradigm and the results of this video.
I’m posting the video now also because it is a second example of doing proofs in the ROM, and will be useful for a problem on HW5.
Let’s move it to 4/15.
I was unhappy with the way my lecture went today (although happy that an error in my notes/proof sketch was caught by one of you!) and so I’ve rewritten up my notes for this lecture. Here they are Hashed El Gamal from CDH.
I wanted you to have a clean version of the games for this proof, because you may want to use the same trick –of using the random oracle as a way to collect hash queries, looking for one particular “winning” query– for one of the problems on HW5…