(Fall 2018) CSCE 689 - Special Topics

Foundations of Post-Quantum Cryptography

Announcement

  • <2018-09-29 Sat> A LaTeX template for scribe notes [TeX PDF].

  • <2018-09-29 Sat> Information about project available on Project page.

About

  • Prerequisite: maturity in algorithm analysis and mathematics (espeically linear algebra, basic probability thoery and group thoery). This course will involve reading and writing lots of mathematical proofs.
  • Syllabus: PDF
  • Instructor: Prof. Fang Song @ HRBB 427B
  • Email: fang.song “AT” tamu.edu. Start your subject line with “F18-PQC”
  • Lectures: T/TR 5:30 – 6:45pm @ HRBB 126
  • Office hours: W 10:30 am - 12pm and by appointment
  • Text: no required ones. We will primarily follow lecture notes and read research papers.

Schedule (subject to change)

Week Date Topic Reading
1 Tu,08/28 Syllabus, intro, qubit Aaronson Lec9 HTML
Watrous Lec1 PDF
  Th,08/30 Aggie GameDay, class cancelled  
2 Tu,09/04 Tensor product, dirac notation Watrous Lec2 PDF
  Th,09/06 quantum circuit model, Deutsch’s algorithm Watrous Lec3 PDF, Lec4 PDF
3 Tu,09/11 Simon’s algorithm Self-study Deutsch-Josza (Watrous Lec5 PDF)
Watrous Lec6 PDF
  Th,09/13 Grover’s algorithm Watrous Lec12 PDF, Lec13 PDF
4 Tu,09/18 Overview of quantum-safe crypto Son’PQC14
Video: Son16@AsiaPQC
  Th,09/20 Case study: PRF/PRP
Superposition attack on Luby-Rackoff
Trevison Notes [5, 6, 15]
KM’ISIT10
5 Tu,09/25 Superpositon attacks cont’d
Quantum-secure PRF
Zhandry’FOCS12
Supp: Zhandry’ePrint16
  Th,09/27 Small-range distribution
QPRF cont’d
Zhandry’FOCS12
6 Tu,10/02 Oracle Indist.
GGM PRF from PRG
Zhandry’FOCS12
Trevison note 14
  Th,10/04 Quantum query complexity BBBV97
Supp.: Son17
7 Tu,10/09 Polynomial method Childs LN 13
[Thm.3.1,3.2 Zhandry’Crypto12]
  Th,10/11 Case study: hash functions
Generic security
[8.1,8.3 Boneh-Shoup v0.4]
8 Tu,10/16 Hash functions: quantum security HRS’PKC16
  Th,10/18 More on hash functions
Collision finding
Zhandry’QIC15
9 Tu,10/23 Iterated hash
Random Oracle model
[8.4,8.10.2 Boneh-Shoup v0.4]
BDF+’Asiacrypt11
Supp: M.Green Blog posts
  Th,10/25 Case study: Full-Domain-Hash signature Trevisan note 22
[Sect.5.3 Zhandry’Crypto12]
10 Tu,10/30 Techniqes for quantum RO [Lemma1,31Unruh’JACM15]
[Lemma5 ES’TQC15]
Supp: AHU’ePrint18
  Th,11/01 More on QRO  
11 Tu,11/06 Attacks due to Entanglement Watrous Lec20 PDF
CSST’AC11
  Th,11/08 Attacks due to quantum side information GKKRW’SICOMP08
TSSR’ITIT11
12 Tu,11/13 Cryptographic protocols
Case study: coin-flipping
DL’Asiacrypt09
LN’Africacrypt11
  Th,11/15 Project presentation
Proofs of Knowledge
Watrous’SICOMP09
Unruh’EC12
13 Tu,11/20 Project presentation
Quantum rewinding
ARU’FOCS14
  Th,11/22 no class
Thanksgiving holiday
 
14 Tu,11/27 Project presentation
Quantum-secure PRP
Czumaj’STOC15
  Th,11/29 Project presentation
Post-quantum threshold crypto
BGG+’Crypto18
15 Tu,12/05 Redefined day
Thursday class
 

Homwork and Exercise