6.5630 Adv Topics in Cryptography

Jump to Today

Summary:

This course is about the evolution of proofs in computer science.  We will learn about the power of interactive proofs, multi-prover interactive proofs and probabilistically checkable proofs.  We will then show how to use cryptography to convert these powerful proof systems into computationally sound non-interactive arguments (SNARGs).

 

Deliverables: 

1. Each student will be ask to scribe one lecture.  The notes should be done on overleaf using the following link: https://www.overleaf.com/5748531451dhgcswsrgfjp

2. We will also have one Pset that will go out on November 17th and will do on December 1st.

  

Syllabus:

  1. Interactive Proofs and the Sum-Check Protocol (Sept. 8)    
  • Definition of Interactive Proofs (IP)
  • The Sum-Check Protocol.
  • Interactive proof for #SAT

Reading:  ProofsArgsAndZK.pdf (georgetown.edu)  Chapters 3.1,  4.1 and 4.2

Lecture notes:  Lecture1

2. Doubly efficient interactive proofs (Sept. 15)

  • Definition
  • Example of doubly efficient IP for counting triangles in a graph
  • Low-degree extension
  • Doubly efficient IP for all bounded depth computations (the GKR protocol)

 Reading: ProofsArgsAndZK.pdf (georgetown.edu)  Chapter 3.5, 4.3, 4.6 and   

ECCC - TR17-108 (weizmann.ac.il)

Lecture notes: Lecture2

3.  Continuation of the GKR protocol and corollaries (Sept. 29)

  •  IP=PSPACE

Lecture notes:  Lecture 3

4.  Guest lecture by Oded Regev on a new quantum factoring algorithm.  Not to be missed!  (Oct. 6)

5.  PCP via GKR and Interactive Arguments (Oct. 13)

  • Probabilistically checkable proofs (PCP):  definition and construction from GKR.
  • Definition of interactive succinct argument for NP.
  • Definition of a Collision Resistant Hash family.

Lecture notes: Lecture 5.pdf

6. Crypto day (Oct. 20)

7.  The Kilian-Micali Protocol (Oct. 27)

  • Cryptographic building block: Collision Resistant Hash (CRH) functions with local opening:  Definition and Construction.
  • The Kilian-Micali Protocol, given a CRH and PCP.
  • Analysis

Reading:  P:TEXSICOMP˘-4 8495 8495 (mit.edu)

Lecture notes: Lecture 7.pdf

8.  Fiat-Shamir paradigm and Zero-knowledge Proofs (Nov. 3)

  • Eliminating interaction via the Fiat-Shamir paradigm.
  • Random Oracle Model (ROM).
  • Proof of the soundness of the Kilian-Micali protocol in the ROM (more generally, proof of soundness of any constant round protocol with negligible soundness).
  • Zero-Knowledge Proofs (ZKP).
  • ZKP for NP:  Specifically for the Hamiltonian Cycle NP complete language. 
  • ROM fails for this ZK proof, since it does not have negligible soundness and the sequential repetition is not constant rounds.

Lecture notes: Lecture 8.pdf

9.  Soundness of the Fiat-Shamir Paradigm in the standard model (Nov. 17)

  • Definition of CI hash functions.
  • Existence in the ROM and simple counter example in the plain model.
  • Positive results for CI in the plain model from LWE (implies first NIZK from LWE)

Reading: 1248.pdf (iacr.org)

10. Succinct non-interactive arguments for Batch NP (BARGs) from LWE (Dec. 1)   

11.  BARGs implies SNARGs and connection to non-signaling PCPs (Dec. 8)

  • Hash & BARG paradigm for constructing SNARGs
  • Local Soundness
  • Local soundness implies correctness only if the language has a (computational) non-signaling PCP.

Reading:  808.pdf (iacr.org) and Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs (iacr.org)

 

 

Course Summary:

Course Summary
Date Details Due