Overview
 Lecturer: Dominique Unruh
 Semester: Winter 2023
 Time: Monday, Wednesday, Thursday, 16:3018:30, not every slot every week (3h lecture, 1h exercise)
 Announcements / chat: See Moodle.
 Rooms: Monday AH5 • Wednesday AH1 • Thursday AH3
 Outcomes/content: Here
 Exam: Tue, 20240220, 11:00–12:30 (exam inspection) • Wed, 20240320, 11:30–13:00
Description
Cryptographic systems (such as encryption and signatures) are threatened by continued progress in the development of quantum computers. Many encryption and signature schemes used today rely on the difficulty of solving the socalled integer factorization and discretelogarithm problems. Those can easily be broken using a (hypothetical) quantum computer. We therefore need new cryptosystems that withstand this threat. The development and analysis of such “quantumsafe” cryptosystems is commonly referred to as “postquantum cryptography”. This lecture will give an introduction into this field.
We will study:
 Foundations of quantum computing necessary to understand the problem with existing systems, and the analysis of new systems.
 Postquantum secure cryptosystems: basic building blocks and how they are used.
 Security proofs: How to assure ourselves that the cryptosystems are secure?
 Existing candidates for future industry standards.
Lectures, times, and materials
The Sciebo folder with all shared files is here.
Lecture notes are here. Recordings by Video AG are here.
 Lecture 1, 20231016:
 General things. Intro. Quantum systems. Quantum states. Unitaries.
 Board photos, recording (very bad audio, see here and here for similar content in an older lecture)
 Lecture 2, 20231018:
 Unitaries (ctd.). Complete measurements. ElitzurVaidman bomb tester.
 Board as PDF or Miro board, recording by Video AG.
 Practice 1, 20231019
 Small quantum circuits. Polarization filters. Quantum Zeno Effect.
 Board as PDF or Miro board, recording.
 Lecture 3, 20231023
 Projective measurements. Composite systems. Tensor product of quantum states.
 Whiteboard as PDF or Miro board, recording.
 Lecture 4, 20231025
 Tensor product of unitaries and of measurements. Simple quantum gates. Classical functions as unitary. Simon’s algorithm (started).
 Whiteboard as PDF or Miro board, recording.
 Practice 2, 20231026
 Simple quantum circuits. Quantum teleportation.
 Whiteboard as PDF or Miro board, recording.
 Lecture 5, 20231030
 Simon’s algorithm (finished). RSA. ElGamal. Relationship period finding / factoring.
 Whiteboard as PDF or Miro board, recording.
 Lecture 6, 20231106
 Shor’s algorithm (for periodfinding). Mentioned: Grover’s algorithm.
 Whiteboard as PDF or Miro board, recording.
 Lecture 7, 20231108
 Learning with errors. LPR (LyubashevksyPeikertRegev) cryptosystem.
 Whiteboard as PDF or Miro board, recording.
 Practice 3, 20231109
 Homework 1 solutions. SISproblem and hash functions.
 Whiteboard as PDF or Miro board, recording.
 Lecture 8, 20231113
 Error correcting codes. Codebased cryptography: McEliece / Niederreiter
 Whiteboard as PDF or Miro board, recording.
 Lecture 9, 20231115
 INDCPA security. INDCCA security. Key encapsulation mechanisms (KEMs). FujisakiOkamoto (started).
 Whiteboard as PDF or Miro board, recording.
 Lecture 10, 20231120
 FujisakiOkamoto (continued). Quantum random oracle model (QROM, started).
 Whiteboard as PDF or Miro board, recording.
 Lecture 11, 20231127
 Quantum random oracle model (QROM, continued). Oneway to hiding theorem (O2H). Optimality of Grover.
 Whiteboard as PDF or Miro board, recording.
 Lecture 12, 20231129
 Security proof of toyFOvariant. Overview over NIST postquantum competition.
 Whiteboard as PDF or Miro board, recording.
 Practice 4, 20231130
 Homework 2. O2H theorem with multiple “marked” elements. Optimality of Grover.
 Whiteboard as PDF or Miro board, recording.
 Nothing in the week 49 December
 Lecture 13, 20231211
 Kyber a.k.a. MLKEM in the FIPS 203 standard.
 Whiteboard as PDF or Miro board, recording.
 Lecture 14, 20231213
 MLKEM finished. Identification schemes. MLWEbased IDscheme.
 Whiteboard as PDF or Miro board, recording.
 Practice 5, 20231214
 Homework 3. Recap: Polynomial rings.
 Whiteboard as PDF or Miro board, recording.
 Lecture 15, 20231218
 Soundness of MLWEbased IDscheme. FiatShamir transform. LWLEbased signature scheme (simplified).
 Whiteboard as PDF or Miro board, recording.
 Lecture 16, 20231221
 Signatures: Definition of EFCMA security, EFOTCMA security (onetime). Onetime signatures from hash functions (Lamport).
 Whiteboard as PDF or Miro board, recording.
 Lecture 17, 20240108
 Hashbased signatures (trees of public keys).
 Board photos, recording by Video AG.
 Lecture 18, 20240110
 Sphincs+ (rough overview). Zeroknowledge proofs: Intro. Sigmaprotocols. Graphisomorphism.
 Whiteboard as PDF or Miro board, recording.
 Practice 6, 20240111
 Reusing Lamportsignatures. EFNMA secure signature scheme (silly). Graphisomorphism identificationscheme.
 Whiteboard as PDF or Miro board, recording.
 Lecture 19, 20240115
 Definitions completeness, soundness, and zeroknowledge. Soundness of graphisomorphism protocol. Zeroknowledge of graphisomorphism protocol (classically).
 Whiteboard as PDF or Miro board, recording.
 Lecture 20, 20240117
 Quantum Zeroknowledge of graphisomorphism: problems and proof. Watrous’ rewinding lemma.
 Whiteboard as PDF or Miro board, recording
 Practice 7, 20240118
 Proof: the “aborting simulator” works. Example: Using zeroknowledge property in an identification protocol.
 Whiteboard as PDF or Miro board, recording.
 Lecture 21, 20240122
 Watrous’ rewinding lemma (finished proof). Symmetric crypto: Defininition strong PRP (pseudorandom permutation). Definition strong qPRP. EvanMansour block cipher. Breaking EvanMansour with superposition queries.
 Whiteboard as PDF or Miro board, recording.
 Lecture 22, 20240129
 Collisionfinding in hash functions: classical and quantum. Attacking EvenMansour without superposition queries.
 Board photos. Recording by Video AG will follow.
 Practice 8, 20240201
 Homework 4.
 Whiteboard as PDF or Miro board, recording.
Dates fixed till the end of the semester.
FAQ

Will there be materials online / a lecture recording? The content of the whiteboard, homeworks, and similar materials will be available online on this webpage. Submitting homeworks will be possible online. The exam is in person.

What form will the exam take? It will be a written exam. See above for date and time.