CS 292G: Post-Quantum Cryptography

(Spring 2025)

________________________________________________________________________________________________________________

[WEEK 1]

• March 31: 

  1. Introduction to the course

  2. Short integer solutions problem (and its variants) 

  3. Application to collision-resistant hash functions

  4.  Lattice trapdoors

Additional Reading: Section 1 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L12.pdf, Section 2 and 3 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L12.pdf, https://www.dropbox.com/scl/fi/ut6wnu8w7kzlcy882vpve/Lecture-10.pdf?rlkey=dz4mb88b3zo8h1n7cdnylgkyp&e=2&dl=0

• April 2: 

  1. Digital signatures

  2. Learning with errors 

  3. Public-key encryption: two constructions

Additional Reading: Section 2.1, 2.2, 3.2 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L13.pdf

________________________________________________________________________________________________________________

[WEEK 2]

• April 7: 

  1. LWE: different variants, search-to-decision reductions

  2. LWE and SIS

Additional Reading: Section 2.4, 2.7 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L13.pdf

• April 9: 

  1. Learning with Rounding

  2. Pseudorandom Functions from LWR

Additional Reading: https://eprint.iacr.org/2011/401.pdf

________________________________________________________________________________________________________________

[WEEK 3]

• April 14: 

  1. Reductions between LWE, SIS and lattice problems

Additional Reading: https://people.csail.mit.edu/vinodv/6876-Fall2015/L13.pdf (Sections 1,2)

• April 16: 

  1. Introduction to lattices

  2. Shortest vector problem, closest vector problem 

Additional Reading: Section 1, 2.2, 2.3 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L1.pdf, Chapter 2.1, 2.2, 2.3 from https://eprint.iacr.org/2015/939.pdf

_______________________________________________________________________________________________________________

[Assignment 1] 

_______________________________________________________________________________________________________________

[WEEK 4]

• April 21: 

  1. LLL algorithm

Additional Reading: https://people.csail.mit.edu/vinodv/6876-Fall2015/L3.pdf (Section 3), https://people.csail.mit.edu/vinodv/6876-Fall2015/L4.pdf (Sections 1,2)

• April 23: 

  1. Introduction to Ideal lattices

Additional Reading: https://www.youtube.com/live/Lo-_ZBqGa7I?si=JuaquWE2PESn4H5X

_______________________________________________________________________________________________________________

[WEEK 5]

• April 28: 

1. Ring-SIS and collision-resistant hash functions

Additional Reading: Sections 10.1, 10.2, 10.3  https://people.csail.mit.edu/vinodv/CS294/lecturenotes.pdf (pages 95 to 97 not covered)

• April 30:

  1. Ring-LWE

  2. Error-correcting codes

Additional Reading: https://people.csail.mit.edu/vinodv/CS294/lecturenotes.pdf (Section 10.4), https://www.cs.cmu.edu/~odonnell/toolkit13/lecture10.pdf, Hamming code puzzle (https://dept.math.lsa.umich.edu/~jchw/HammingCodes&ColouredHatsHandout.pdf)

_______________________________________________________________________________________________________________

[WEEK 6]

• May 5: 

  1. Learning Parity With Noise

  2. Private-Key Encryption

  3. Public-Key Encryption

  4. Collision-resistant hash functions

Additional Reading: Introduction (https://link.springer.com/chapter/10.1007/978-3-642-27660-6_9), Public-key encryption (https://www.iacr.org/archive/asiacrypt2012/76580482/76580482.pdf), Collision-resistant hash functions (https://eprint.iacr.org/2018/279.pdf and https://eprint.iacr.org/2017/1260.pdf)

• May 7:

  1. Group actions: basics

  2. Key-exchange, pseudorandom functions, public-key encryption

Additional Reading: https://eprint.iacr.org/2020/1188.pdf

_______________________________________________________________________________________________________________

[Assignment 2] 

_______________________________________________________________________________________________________________

[WEEK 7]

• May 12: 

  1. Quantum query security

  2. Case study: pseudorandom functions

Additional Reading: https://eprint.iacr.org/2012/182.pdf

• May 14:

  1. Case study: pseudorandom functions (continued)

  2. Digital signatures with quantum query security

  3. Encryption with quantum query security

Additional Reading: https://eprint.iacr.org/2012/182.pdf, https://eprint.iacr.org/2013/088.pdf

________________________________________________________________________________________________________________

[WEEK 8]

• May 19: 

1. Quantum random oracle model - Part I

Additional Reading: Introduction to quantum random oracle model (https://eprint.iacr.org/2010/428.pdf)

• May 21:

1. Quantum random oracle model - Part II

Additional Reading: Quantum versus classical random oracle model (https://eprint.iacr.org/2020/1270.pdf, https://arxiv.org/pdf/2204.02063)

_______________________________________________________________________________________________________________

[WEEK 9]

• May 26: Holiday

• May 28:

1. Quantum random oracle model - Part III 

Additional Reading: Compressed oracle technique (https://eprint.iacr.org/2018/276.pdf, https://arxiv.org/pdf/2010.11658)

_______________________________________________________________________________________________________________

[WEEK 10]

• June 2: 

1. Shor's factoring algorithm

Additional Reading: Nielsen-Chuang textbook 

• June 4:

1. Regev's factoring algorithm and its optimizations

Additional Reading: https://arxiv.org/pdf/2308.06572, https://arxiv.org/pdf/2310.00899

_______________________________________________________________________________________________________________

[Assignment 3]