QIC891 Topics in Quantum Safe Cryptography (Spring 2016)
Module 1: Post-Quantum Cryptography
News
- Lecture 1 note posted, finally.
- Homework, lecture 4 note & slides posted!
- Lecture 3 handout & draft note, reading materials for lecture 1 - 3 postded.
- Lecture 2 handout and draft note posted.
- Lecture 1 introductory slides, handout on central problems posted! Lecture note will come soon.
- Resourse page is up and continues to grow!
- Course webpage is up!
Course Info
- Meeting: 10:30-12:00 on May 10, 12, 17, 19. All at QNC 1201 (attention: differs from initial announcement).
- Instructor: Fang Song (fang.song AT uwaterloo DOT ca)
About this module
Cryptography is facing devastating challenges in an era of quantum computing. Many public-key cryptosystems widely deployed on the Internet will be broken by quantum attackers due to efficient quantum algorithms such as Shor’s factoring algorithm. This calls for designing cryptosystems that (hopefully) can resist quantum attacks, a.k.a. post-quantum cryptography (PQC).
This module will give an overview of a few candidate directions on PQC. We will use public-key signature and encryption schemes as running examples. Instead of going over various constructions, I will take a unified approach by outlining general frameworks for cryptographic designs and showing how to instantiate them from each candidate direction. Quantum security of these new proposals will be discussed, which includes (quantum) hardness of underlying computational problems as well as formal security analyses in the presence of quantum adversaries (which have not received enough emphasis in the literature).
Check out the tentative schedule below.
Resources
- A (non-exhaustive & growing) list of study materials & references on post-qantum cryptography.
- Relevant readings will be specified for each lecture.
Policy
For academic credit
A short homework assignment will be handed out after the last lecture, which will be (typically) due two weeks after the end of the module.
In order to complete QIC 891 for academic credit, students must complete 3 modules and a project. You may only register in QIC 891 if you intend on completing 3 modules and associated homework and project by August 2016.
Permission numbers are required to enroll in this course. Please contact Monica Dey. Find more information here.
For CryptoWorks21 qualification
Students in the CryptoWorks21 training program may complete any eligible modules order to prepare for a CryptoWorks21 technical skills qualification exam on the module topic. Technical skills qualification exams will take place at the end of each module.
Students may also count these modules, including assignments and final project, towards academic credit as part of QIC 891.
This module is eligible for technical skill qualification. An exam (format TBD) will be given at a later point.
Tentative schedule
Tu May 10: Intro
[handout pqc candidate problems: pdf] - [Lec 1 Part I intro slides: pdf] - [Lec1 part II note: pdf]
- Setting the scene: threats to cryptography from quantum attacks. Two major aspects: 1) underlying hard problems are broken and 2) classical framework for security analysis falls apart.
- Introduce main proposals to resist quantum attacks based on: 1) point lattices; 2) coding theory; 3) multivariate polynomials; and 4) signature schemes using cryptographic hash functions.
- Central candidate problems for building PQC, e.g. SIS&LWE (lattice-based), syndrome decoding (code-based), multivariate equations (MQ-based).
Reading
- Watch tutorial videos from PQCrypto 2014 Summer School & PQCrypt 2016 Winter School.
Th May 12: Signature
[handout pqsign schemes: pdf] - [Lec2 note: pdf]
- Hash-based signature: Lamport one-time signature (OTS) & Merkle-tree construction. Recent developments for efficiency improvements, e.g., Winternitz OTS.
- Hash+: signatures from collision resistant hash function with homomorphic property (H).
- hard problems to H.
- H to identification (ID) schemes: Stern (code), Lyubashevsky (lattice).
- ID to signature: Fiat-Shamir transformation.
- Next Time Full domain hash in the random-oracle model using a trapdoor one-way permutation and instantiations: GPV (lattice) and CFS (code).
Reading
- Chapter 3 (generic construction from OWFs) & 8 (identification & Fiat-Shamir) of monograph on Digital Signatures by Jon Katz Springer (access it via library)
- Lattice identification schemes [LyuPKC08, LyuAC09, Lyu12]
- Code identification [Stern96]
Tu May 17: Public-key encryption
[handout pq pke schemes: pdf] - [Lec3 note: pdf]
- Trapdoor one-way functions: plain-text RSA and its siblings in the post-quantum setting: GGH/NTRU (lattice), McEliece/Niederreiter (code), HFE (MQ).
- Generic techniques to get CPA/CCA secure encryption in the random-oracle model:
- BR93
- Efficiency improvement: OAEP
- From weaker assummptions: Pointcheval, Fujisaki-Okamoto …
- Reading Direct constructions based on lattices
- Regev’s LWE encryption
- Fancy stuff: fully-homomorphic encryption, etc.
Reading
- Chapter 7 (FDH) of Digital Signatures by Jon Katz Springer (access it via library)
- Lattice trapdoors, signature & PKE [GPV08, Regev09, MP12]
- Random oracles, OAEP & more: [BR93, BR94, FO13]
Th May 19: Are they quantum-secure?
[homework: pdf, tex] - [Lec4 part I note: pdf] - [Lec4 part II slides: pdf]
- Hardness of the candidate computational problems against quantum algorithms. Worst-case to average-case reductions for lattice problems.
- Analyzing security in the presence of quantum adversaries. Challenges and techniques to deal with
- quantum random-oracle model.
- quantum rewinding (affects e.g., identification schemes).