1st Semester 2014/15: Zero-Knowledge Proofs

Instructors

Maaike Zwart, Suzanne van Wijk, and Christian Schaffner
If you are interested in this project, please contact the instructors by email.

ECTS

3

Description

"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.

Organisation

The project will consist of approximately six lectures, accompanied by exercise classes. The lectures and exercise classes will be spread out over three 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 small groups. 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.

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.

References

Website: For further information, please consult the project website.