Notes from ZK lecture

As promised, here are the notes I developed for the (too brief) lecture that I gave in our final meeting. Zero-knowledge


Notes on KEMs and digital signature schemes

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!

RSA-based KEMs

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.

Lecture notes for 4/5 (Hashed El Gamal from CDH)

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…