Zero-Knowledge Proofs
News:
23 Oct 2014: created this page19 Dec 2014: substantial updates, including learning outcomes and course schedule with rooms
15 Jan 2015: various updates, added "life after" section
Contents of the course
"I found Waldo!", cheered Alice to Bob. Bob didn't believe her, but he also didn't want Alice to point out the whereabouts of Waldo, as this would spoil his game. How can Alice convince Bob that she found Waldo, without revealing Waldo's location? This is the idea of a zero knowledge proof. A proof that reveals nothing but the fact that some statement is true. In this digital era, security and cryptography are flourishing research areas. With more and more private information being stored digitally (bank accounts, hospital databases, ...), it has become important to disclose only very specific information to very specific people. Zero knowledge proofs provide the means to ensure a database query reveals only the answer to the query, and nothing else. In authentication protocols, zero knowledge proofs are used to verify a person's identity, without gaining knowledge about the password he or she uses. Zero knowledge proofs can even be used to prevent cheating in online voting or auctions. This project will cover the basics of zero knowledge proofs. We start with a short introduction on Turing machines and complexity theory, including the classes P and NP. After this introduction, we will work towards the formal definition of zero knowledge proofs (for which we need the notion of interactive proofs) and consider various examples. We end the course with an assignment in which you have to find your own zero knowlegde proof for some well known problem.
Intended learning outcomes
At the end of the course, you will be able to:- Design your own Turing Machine
- Tell the difference between the complexity classes P and NP
- Prove to your friends that you found Waldo
- Fool your friends into thinking that you know the magic words to the cave
- Apply several definitions of Zero-Knowledge proofs, and tell the difference between these definitions
- Construct Zero-Knowledge proofs for every NP problem
- Give a direct Zero-Knowledge proof for your own favourite NP problem
Prerequisites
This course is intended to be accessible for everyone in the Master of Logic. Specifically, we expect no prior knowledge about complexity theory or cryptography.Material
- Oded Goldreich, Foundations of Cryptography, Volume I, Cambridge University Press, 2001
Organisation
The project will consist of four lectures, accompanied by some exercise classes and homeworks. The lectures and exercise classes will be spread out over the first two weeks. At the end of the third week, students will present their own zero-knowledge protocols for various well known problems.
This project is worth 3 EC. They are earned by handing in several small exercises and a larger assignment. The latter can be done in pairs. The groups will present their solutions to the assignment to each other at the end of the course. Class participation will also contribute to the assessment.
Course schedule January 2015
| Date | Content | Homework |
|---|---|---|
| Tue, 6 January 2015, 11:00-13:00 |
Lecture 1: Turing Machines Turing's 1936 paper On computable numbers, with an application to the Entscheidungsproblem |
CWI, Room L236 |
| Tue, 6 January 2015, 14:00-16:00 |
Exercise session 1 |
Homework #1 |
| Thu, 8 January 2015, 11:00-13:00 |
Lecture 2: Zero-Knowledge |
CWI, Room L236 |
| Thu, 8 January 2015, 14:00-16:00 |
Exercise session 2 |
Homework #2 |
| Mon, 12 January 2015, 11:00-13:00 |
Lecture 3: Zero-Knowledge |
CWI, Room L236 |
| Mon, 12 January 2015, 14:00-16:00 |
Exercise session 3 |
Homework #3 |
| Thu, 15 January 2015, 11:00-13:00 |
Lecture 4: ZK proofs for NP Interactive proof of 3-colorability
|
CWI, Room L236 |
| Thu, 15 January 2015, 14:00-16:00 |
Exercise session 4 |
Final Assignment |
| Mon, 19 January 2015, 11:00-13:00 |
Question & Answer session |
CWI, Room L236 |
| Thu, 22 January 2015, 11:00-15:00 |
Student presentations ZK Proofs for Hamiltonian Cycles by Michiel den Haan Slides ZK Proofs for Sudoku by Pietro Pasotti Slides |
CWI, Room L236 |
