Instructor: Daniele Micciancio Lectures: Tuesday, Thursday 12:30-1:50pm, in CENTER 223.
The topic covered in the Advanced Cryptography course in Fall 2018 will be Zero Knowledge proof systems. Zero knowledge proofs are a fundamental tool in the construction of cryptographic protocols, and are part of the fundamental background of both researchers and practitioners seriously interested in cryptography and security. Informally, a zero knowledge proof system is an interactive protocols involving two mutually distrustful parties, by which one party (the prover) convinces the other (the verifier) that a certain assertion is valid, without revealing any additional information.
This course starts from the basic definition and examples of zero knowledge proof systems, and explores a range of advanced topics, including concurrent zero knowledge, non black-box simulation, non-interactive zero-knowledge, and connections with complexity theory. The study of Zero knowledge proof systems (as well as almost everything in modern cryptography) is based on computational complexity. So, this course will have a strong computational complexity flavor, and is expected to be generally useful to anybody interested in theoretical computer science. While concentrating on zero knowledge proofs, we will explore many general issues that come up in the construction of any secure protocol. Typical examples are compositionality issues (does the protocol remain secure even if many instances of it are executed sequentially, in parallel, or in an arbitrary concurrent setting?), and limitation of black box simulatability paradigm (is there any substantial difference between being given the ability of executing a computer program, or being given reading access to its code?)
Reading and homework assignments will be posted on this pages and we progress through the course. The course assumes as prerequisite a good working knowledge of the definitional framework of modern cryptography (security definitions, computational assumptions, proofs of security, etc.) as typically provided by graduate level (and some undergraduate level) introductory cryptography courses.
For the first part of the course, we will use Oded Goldreich’s book (available electronically through UCSD library) as the primary reference. We will only cover chapter 4, on zero knowledge proof systems, but you can also look at the rest of the book as a general reference on the foundations of cryptography.
Foundations of Cryptography, O. Goldreich, Chapter 4: Zero-Knowledge Proof Systems.