CS 292G: Post-Quantum Cryptography
(Spring 2025)
CS 292G: Post-Quantum Cryptography
(Spring 2025)
We will address the following question in the course: How do we protect cryptographic systems against quantum computers? We will study cryptographic constructions that are conjectured to resist quantum attacks. We will also study the insecurity of some constructions against efficient quantum attackers.
There are 3 parts to this course:
Part I (6 weeks): Post-quantum cryptographic assumptions and applications
Part II (2 weeks): Quantum random oracle model, Post-quantum security of generic primitives (for example, pseudorandom functions)
Part IV (2 weeks): Quantum attacks on cryptographic assumptions
Lecture hours: MW 11:00am to 12:50pm
First day of lecture: March 31st
Lecture hall: Phelps 3526
Instructor's office hours: by appointment only
Digital communication with the instructor: via Slack only.
________________________________________________________________________________________________________________
[WEEK 1]
March 31:
Introduction to the course
Short integer solutions problem (and its variants)
Application to collision-resistant hash functions
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:
Digital signatures
Learning with errors
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:
LWE: different variants, search-to-decision reductions
LWE and SIS
Additional Reading: Section 2.4, 2.7 from https://people.csail.mit.edu/vinodv/6876-Fall2015/L13.pdf
April 9:
Learning with Rounding
Pseudorandom Functions from LWR
Additional Reading: https://eprint.iacr.org/2011/401.pdf
________________________________________________________________________________________________________________
[WEEK 3]
April 14:
Reductions between LWE, SIS and lattice problems
Additional Reading: https://people.csail.mit.edu/vinodv/6876-Fall2015/L13.pdf (Sections 1,2)
April 16:
Introduction to lattices
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:
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:
Introduction to Ideal lattices
Additional Reading: https://www.youtube.com/live/Lo-_ZBqGa7I?si=JuaquWE2PESn4H5X
_______________________________________________________________________________________________________________
[WEEK 5]
April 28:
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:
Ring-LWE
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:
Learning Parity With Noise
Private-Key Encryption
Public-Key Encryption
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:
Group actions: basics
Key-exchange, pseudorandom functions, public-key encryption
Additional Reading: https://eprint.iacr.org/2020/1188.pdf
_______________________________________________________________________________________________________________
[Assignment 2]
_______________________________________________________________________________________________________________
[WEEK 7]
May 12:
Quantum query security
Case study: pseudorandom functions
Additional Reading: https://eprint.iacr.org/2012/182.pdf
May 14:
Case study: pseudorandom functions (continued)
Digital signatures with quantum query security
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:
Quantum random oracle model - Part I
Additional Reading: Introduction to quantum random oracle model (https://eprint.iacr.org/2010/428.pdf)
May 21:
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:
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:
Shor's factoring algorithm
Additional Reading: Nielsen-Chuang textbook
June 4:
Regev's factoring algorithm and its optimizations
Additional Reading: https://arxiv.org/pdf/2308.06572, https://arxiv.org/pdf/2310.00899
_______________________________________________________________________________________________________________
[Assignment 3]
Participation: 20%
Asking insightful questions
Answering questions
Regularly attending classes
Assignments: 30%
3 assignments: lowest one dropped
If you have a medical issue that could prevent you from completing the assignment, please notify me immediately
Research Report OR Scribing: 50%
Scribing: if you take up this option, you should sign up for scribing at least 3 classes. If you are not working in theory or do not have a mathematical background then I recommend that you do not sign up.
Research report: more instructions will be provided in the first lecture.
Extra credit if you take up a research project.