CIS 7000: Theory and Practice of Succinct Zero Knowledge Proofs

Basics

Instructor: Pratyush Mishra
Time: Tuesdays and Thursdays, 10:15AM-11:45AM
Location: Towne 311
Office hours: Thursdays 1-2PM, Towne 219B
Useful links: Ed Discussions; Canvas

Course Description

Zero knowledge proofs are a core object of study in cryptography that enable a prover to convince a verifier of the truth of a claim in an efficient and private manner. Despite their attractive properties, for most of their history zero knowledge proofs have remained of primarily theoretical interest. However, this has changed in the last decade with the development and deployment of very efficient zero knowledge proof systems called zkSNARKs. In this course, we will cover the mathematical foundations, implementation aspects, and applications of zkSNARKs.

Prerequisites

This course requires a basic background in discrete mathematics (at the level of CIS 1600), and a basic background in algorithms and complexity (at the level of CIS 3200).

Grading

Your grade in the course is determined by the following components:

• Assignments (15%)
• Regular attendance and participation (15%)
• Presenting a paper (25%)
• Completing a final project (45%)
  • 10% for project proposal (due on 10/10/23)
  • 15% for presentation
  • 15% for final report

Schedule

For classes marked as Lecture, the assigned readings are optional.
For classes marked as Discussion, everyone is expected to read the assigned readings are (with the exception of “presenter-only” readings, which are mandatory only for the presenter. Feel free to read them if you want to, though!)

Overview of course grade components

Reading assignments

Each class with a Discussion component will be accompanied by an assignment consisting of 1-2 short-answer questions about the assigned reading(s). These assignments will be posted on Canvas, and will be due before class.

Note: you are not required to read papers marked as “Presenter only” in the schedule below.

Attendance and participation

You are expected to attend lectures and participate in discussions, particularly for classes marked Discussion

Paper presentation

You will lead a 40-45 minute long discussion on a paper of your choice (from one of the classes marked Discussion). There will be a sign-up sheet on Ed for choosing papers. The discussion should include a brief presentation of the paper, interspersed with questions and discussion. An example split would be 25 minutes of presentation + 10 minutes of discussion + 5 minutes of feedback.

You can choose whatever presentation tools you see fit (chalkboard, slides, etc.). No matter the medium, you should aim for a presentation that:

• motivates the problem tackled by the paper (most likely in relation to the material I introduce before your presentation), and
• describes at a high-level the main protocol, idea, or system introduced in the paper.

See here for strategies on how to prepare for this presentation.

Final project

A core component of your grade will be determined by the final project. A project can be either a research project or a literature survey:

• Research project: You are expected to form teams of size 1-2 people and undertake independent research in the broader area of zero-knowledge proofs. I encourage using Ed to find project partners. I will post a list of potential project ideas to Ed.

  The ideal goal of this type of project is to make preliminary progress towards a result that can eventually be published at a major cryptography (CRYPTO, EUROCRYPT, TCC) or security (IEEE S&P, USENIX Security, ACM CCS) conference.

  Note: students are encouraged to use ongoing research projects, but in this case they must clearly delineate work that had been done prior to the start of the course and work that was done during the course.

• Literature survey: This is an individual project: you can pick any topic in the area of zkSNARKs (whether covered in the class or not), and write a survey of the existing literature on this topic. Your survey should pick a few relevant papers, summarize them in some depth, and provide a comparison between the chosen papers.

Both kinds of projects consist of the following deliverables:

• Project proposal (due on 10/10/23): A 2-3-page proposal describing the project, and containing the following details:
  • Teammates (if any)
  • Proposed research problem/survey topic
  • Initial study of prior work, with references that you plan to use. This is due on October 10th.
  • Initial plan of attack (for research projects), or outline of the survey (for literature surveys)
• Project presentation (due on either 12/05/23 or 12/07/23): The presentation should be high-level, and accessible to the entire class. It should contain the following information.
  • Research project:
    • Problem introduction, and motivation (with a clear threat model).
    • Brief description of why existing techniques are insufficient.
    • High-level explanation of your contribution, and what you plan to do before the final report deadline.
  • Literature survey:
    • Problem introduction, and motivation (with a clear threat model).
    • High-level overview of the important papers in the chosen problem space.
    • Explanation of the core contribution of 1 important paper, and how it relates to the other papers in the space.

  Regarding the duration of the presentation, a 1-person group should prepare a 9-10 minute presentation, while a 2-person group should prepare a 12-minute presentation. Expect 3-4 minutes of questions per group.

• Project report (due on either 12/15/23): The final report should be a single-column paper no longer than 8-10 pages (excluding references). It should contain the following information.
  • Research project:
    • Teammates, if any.
    • Problem introduction, and motivation (with a clear threat model).
    • Comprehensive related work
    • Description of contributions (protocol design, security proof sketch, system design, application design, etc.)
    • Brief description of implementation (if appropriate), and experiment design (and results, if any).
  • Literature survey:
    • Teammates, if any.
    • Problem introduction, and motivation (with a clear threat model).
    • High-level overview of the important papers in the chosen problem space
    • Detailed summary and comparison of the chosen papers.
    • Key takeaways, including open problems and future directions.