Instructor: Dakshita Khurana

TA: Amit Agarwal

Time: WF 3.30 - 4.45 pm

Location: Siebel 0216

 

The Spring 2023 offering will be an advanced topics course discussing recent research in the theoretical foundations of cryptographic proofs, including zero-knowledge proofs and probabilistically checkable proofs.

 

This course will assume solid background knowledge of cryptography. In particular we will assume that you have already taken CS 407 (or an equivalent course).

 

We will expect participants to understand and present advanced technical papers. If you have previously taken a cryptography course that is equivalent to 407, please email the instructor (dakshita@illinois.edu) asap with information about the course you've taken. If you have not previously taken a cryptography course, you will unfortunately not have the necessary pre-requisite background to participate in this course.

 

Rough breakdown of graded components:

 

Quiz: 10% of your grade

Participation: 10% of your grade

Presentation: 40% of your grade

Project: 40% of your grade

 

Tentative Schedule:

This is a tentative schedule and is subject to change. Please keep checking this page for updates to topics.

Many lectures will be in flipped classroom format, with links to videos posted below. Please watch these videos before class.

Date Topic H.W. Review Videos (to be reviewed before class) Papers
       
01/18

Introduction + Quiz

 

 
01/20
  • Introduction to Zero Knowledge
  • ZK for all of NP

Video 1: https://www.youtube.com/watch?v=6uGimDYZPMw

Video 2: https://www.youtube.com/watch?v=cQ-BI1WWzjU

 

02/25
  • Proofs of Knowledge
  • Constant round ZK for NP
  • Witness Indistinguishability
  • (Constant round) Statistical ZK for NP
  • Witness hiding

Video 1: https://www.youtube.com/watch?v=RvGsjnoYRRg&t=1s

Video 2: https://www.youtube.com/watch?v=cAI7Iw_bkZs

Video 3: https://www.youtube.com/watch?v=5O8ornUVgAQ

02/27
  • NIZK in the Hidden Bits Model
  • The Fiat-Shamir Transform

Video 1: https://www.youtube.com/watch?v=dE0KJxxe3xI

Video 2: https://www.youtube.com/watch?v=9cagVtYstyY

 
02/01

NIZK from bilinear maps - 1

Video 1: https://www.youtube.com/watch?v=_mAKh7LFPOU

Video 2:
 https://www.youtube.com/watch?v=_bT7rq8aweQ
 
02/03

NIZK from bilinear maps - 2

Video 3: https://www.youtube.com/watch?v=cmgGxWw2rP4

 
02/08 NIZK from Correlation Intractability/LWE - 1 Student presentation - Amit

NIZK and Correlation Intractability from Circular-secure LWE

02/10

NIZK from Correlation Intractability/LWE - 2

Student presentation - Amit

NIZK for NP from LWE

02/15

NIZK from subexponential DDH - 1

Student presentation - James NIZK from subexponential DDH
02/17

NIZK from subexponential DDH - 2

Student presentation - James NIZK from subexponential DDH
02/22
  • Lower bounds and limitations on ZK
  • Non-black-box ZK (Barak's protocol)
  • NBB ZK via Homomorphic Trapdoors - 1

Video 1: https://www.youtube.com/watch?v=OAPOzLfDqRg

Video 2: https://www.youtube.com/watch?v=85gWcuo0jp4

 

 
02/24

NBB ZK via Homomorphic Trapdoors - 1

Student presentation - Kabir

Weak ZK beyond the black-box barrier
03/01

NBB ZK - 2

Student presentation - Kabir Weak ZK beyond the black-box barrier
03/03

(No class)

   
03/08

ZAPs from NIZK Proofs

Student presentation - Maria This paper on ZAPs
03/10

ZK with superpolynomial simulation

Student presentation - Maria This paper  
03/15

No class/spring break

   
03/17

No class/spring break

   
03/22

Interactive Proofs 

Video 1: https://www.msri.org/summer_schools/931/schedules/30163

Video 2: https://www.msri.org/summer_schools/931/schedules/30164

Video 3: https://www.msri.org/summer_schools/931/schedules/30165

Video 4: https://www.msri.org/summer_schools/931/schedules/30166

 
03/24

Probabilistically Checkable Proofs - 1

Video 1: https://www.msri.org/summer_schools/931/schedules/30183

Video 2: https://www.msri.org/summer_schools/931/schedules/30184

 
03/29

Probabilistically Checkable Proofs - 2

Video 1: https://www.msri.org/summer_schools/931/schedules/30185

Video 2: https://www.msri.org/summer_schools/931/schedules/30188

 
03/31 Probabilistically Checkable Proofs - 3

Video 1: https://www.msri.org/summer_schools/931/schedules/30189

Video 2: https://www.msri.org/summer_schools/931/schedules/30190

 

04/05

No-Signaling PCPs and Delegation - 1

Student presentation - Fangqi This paper
04/07

No-Signaling PCPs and Delegation - 2

Student presentation - Fangqi This paper
04/12

SNARGs via Correlation Intractability - 1

Student presentation - Ruta  
04/14

SNARGs via Correlation Intractability - 2

Student presentation - Ruta  
04/19

Connections with PPAD Hardness - 1

Student presentation - Cruz This paper
04/21

Connections with PPAD Hardness - 2

Student presentation - Cruz This paper
04/26

Open problems session - 1

   
04/28

Open problems session - 2

   
05/03

No class

 

 

 

The intent of this section is to raise student and instructor awareness of the ongoing threat of bias and racism and of the need to take personal responsibility in creating an inclusive learning environment.

The Grainger College of Engineering is committed to the creation of an anti-racist, inclusive community that welcomes diversity along a number of dimensions, including, but not limited to, race, ethnicity and national origins, gender and gender identity, sexuality, disability status, class, age, or religious beliefs. The College recognizes that we are learning together in the midst of the Black Lives Matter movement, that Black, Hispanic, and Indigenous voices and contributions have largely either been excluded from, or not recognized in, science and engineering, and that both overt racism and micro-aggressions threaten the well-being of our students and our university community.

The effectiveness of this course is dependent upon each of us to create a safe and encouraging learning environment that allows for the open exchange of ideas while also ensuring equitable opportunities and respect for all of us. Everyone is expected to help establish and maintain an environment where students, staff, and faculty can contribute without fear of personal ridicule, or intolerant or offensive language. If you witness or experience racism, discrimination, micro-aggressions, or other offensive behavior, you are encouraged to bring this to the attention of the course director if you feel comfortable. You can also report these behaviors to the Bias Assessment and Response Team (BART) (https://bart.illinois.edu/). Based on your report, BART members will follow up and reach out to students to make sure they have the support they need to be healthy and safe. If the reported behavior also violates university policy, staff in the Office for Student Conflict Resolution may respond as well and will take appropriate action.

All members of the Illinois Computer Science department - faculty, staff, and students - are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. The Instructors of this course are also available for issues related to this class.

Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional well-being. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.

Counseling Center: 217-333-3704, 610 East John Street Champaign, IL 61820

McKinley Health Center:217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801

University wellness center: https://wellness.illinois.edu/