# Zero-Knowledge Proofs

University of Amsterdam course, January 2015
part of Master of Logic

#### News:

19 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

For links to slides and papers, see course schedule below.

## 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

Slides #1

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

Slides #2

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

Slides #3 (Powerpoint)

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

Slides #4

Interactive proof of 3-colorability
A survey of NP-complete puzzles by Kendall, Sparkes, and Spoerer

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

## Life after the "Zero Knowledge" project

If you got hooked on the world of zero-knowledge, you have several options after the course to pursue the topics of cryptography: