CS2590: Advanced Cryptography

The focus of this semester is zero-knowledge proofs and arguments. Starting from seminal works that introduced and formalized zero-knowledge, we will discuss different zero-knowledge protocols. We will see their applications in various settings such as identification protocols, secure computation and cryptocurrencies. We will then discuss more recent works on zero-knowledge succinct non-interactive arguments. [ zk-SNARGs and SNARKs]

Instructor: Anna Lysyanskaya (anna@cs.brown.edu)

Course TA: Apoorvaa Deshpande (acdeshpa@cs.brown.edu)

Meeting Times and Location: Tuesdays and Thursdays 10:30-11:50 am, CIT 101

TA Hours: Tuesdays 3-5 pm, CIT 102 (Apoorvaa)
Thursdays 3-4 pm, CIT 501 (Prof. Lysyanskaya, by appointment)

Latest Updates:

• Problem Set 1 is out. It is due on February 21 in class. [Link]

• Sign-up sheet for presenting is now available. Please sign up before February 4. [Link]
• Course syllabus PDF file is now available. [PDF]

---

Course Syllabus and Schedule:

• Jan 24, 2019: Class Cancelled
• Jan 29, 2019: Course Overview
• Jan 31, 2019: Introduction to zero-knowledge, Definitions [Papers]
  • Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems [link]
    O Goldreich, S Micali, A Wigderson, JACM, 1991
  • Zero-Knowledge: A tutorial by Oded Goldriech [link]
• Feb 5, 2019: Lower bounds on zero-knowledge [Papers]
  • On the Composition of Zero-Knowledge Proof Systems [link]
    O Goldreich and H Krawczyk, SIAM Journal of Computing, 1996
  • How to go beyond the black-box simulation barrier [link]
    B Barak, FOCS 2001
  • Definitions and properties of zero-knowledge proof systems [link]
    O Goldreich and Y Oren, Journal of Cryptology, 1994
• Feb 7, 2019: Round complexity of zero-knowledge protocols [Papers]
  • How to Construct Constant-Round Zero-Knowledge Proof Systems for NP [link]
    O Goldreich and A Kahan
  • Zero Knowledge Proofs of Knowledge in Two Rounds [link]
    U Feige and A Shamir, CRYPTO 1989
  • Which Languages Have 4-Round Zero-Knowledge Proofs? [link]
    J Katz
• Feb 12 and 14, 2019: Sigma protocols and Discrete-Log-based protocols [Papers]
  • Efficient signature generation by smart cards [link]
    C Schnorr
  • On Sigma Protocols (Survey Paper) [link]
    I Damgard
  • A signature scheme with efficient protocols [link]
    J Camenisch and A Lysyanskaya, SCN 2002
• Feb 19, 2019: No Class (President's Day)
• Feb 21, 2019: Fiat-Shamir Transformation [Papers]
  • How to prove yourself: Practical solutions to identification and signature problems [link]
    A Fiat and A Shamir, CRYPTO 1986
  • On the (in)security of the Fiat-Shamir paradigm [link]
    S Goldwasser and Kalai.
• Feb 26, 2019: Non-interactive zero-knowledge [Papers]
  • Non-interactive zero-knowledge [link]
    M Blum, A De Santis, S Micali, G Persiano, SIAM Journal on Computing, 1991
• Feb 28, 2019: Multi-prover Non-interactive zero-knowledge [Papers]
  • Multiple Non-interactive zero-knowledge proofs under General Assumptions [link]
    U Feige, D Lapidot, A Shamir, SIAM Journal on Computing, 1999
• March 5, 2019: NIZK Constructions based on bilinear maps [Papers]
  • New Techniques for Non-interactive zero-knowledge [link]
    J Groth, R Ostrovsky, A Sahai, JACM 2012
• March 7, 2019: Efficient Non-interactive Proofs for Bilinear Groups [Papers]
  • Efficient Non-interactive Proofs for Bilinear Groups [link]
    J Groth and A Sahai, EUROCRYPT 2008
• March 12, 2019: Randomizable and Malleable NIZK Proofs [Papers]
  • Randomizable Proofs and Delegatable Anonymous Credentials [link]
    M Belenkiy, J Camenisch, M Chase, M Kohlweiss, A Lysyanskaya, S Meiklejohn, CRYPTO 2009
  • Malleable Proof Systems and Applications [link]
    M Chase, M Kohlweiss, A Lysyanskaya, S Meiklejohn, EUROCRYPT 2012
• March 14, 2019: Fully Homomorphic Proofs [Papers]
• March 19, 2019: Computationally sound proofs, probabilistically checkable proofs (PCPs) [Papers]
  • Computationally Sound Proofs [link]
    S Micali, FOCS 1994
• March 21, 2019: Succinct NP Proofs [Papers]
  • Succinct NP Proofs from an Extractability Assumption [link]
    G Di Crescenzo and H Lipmaa (2008)
• March 26 and 28, 2019: No Class (Spring Break)
• April 2, 2019: Succinct Non-interactive Arguments of Knowledge (SNARKs) [Papers]
  • The Hunting of the SNARK [link]
    N Bitansky, R Canetti, A Chiesa, S Goldwasser, H Lin, A Rubinstein, E Tromer, Journal of Cryptology (2017)
• April 4, 2019: Implausibility of basing SNARKS on standard assumptions [Papers]
  • Separating Succinct Non-Interactive Arguments From All Falsifiable Arguments [link]
    C Gentry and D Wichs
• April 9, 2019: SNARKS from Quadratic Spanning Programs [Papers]
  • Quadratic Span Programs and Succinct NIZKs without PCPs [link]
    R Gennaro, C Gentry, B Parno, M Raykova, EUROCRYPT 2013.
• April 11, 2019: Efficient SNARKS from bilinear assumptions [Papers]
  • On the Size of Pairing-Based Non-interactive Arguments [link]
    J Groth, EUROCRYPT 2016.
• April 16, 2019: Subversion SNARKs [Papers]
  • Subversion Zero-Knowledge SNARKs [link]
    G Fuchsbauer, PKC 2018.
• April 18, 2019: Updateable CRS and Applications to zk-SNARKs [Papers]
  • Updateable and Universal CRS and Applications to zk-SNARKs [link]
    J Groth and M Kohlweiss and M Maller and S Meiklejohn and I Miers, CRYPTO 2018.
• April 23, 2019: Bulletproofs [Papers]
  • Bulletproofs: Short Proofs for Confidential Transactions [link]
    B Bünz and J Bootle and D Boneh and A Poelstra and P Wuille and G Maxwell, IEEE SnP 2018.
• April 25, 2019: STARKs (Transparent SNARKs) [Papers]
  • Scalable, Transparent, and Post-quantum Secure Computational Integrity [link]
    E Ben-Sasson and I Bentov and Y Horesh and M Riabzev
• April 30, 2019: Last Class (Concluding Remarks on ZK Proofs and Arguments)