Overview

  • Lecturer: Dominique Unruh
  • Semester: Winter 2023
  • Time: Monday, Wednesday, Thursday, 16:30-18: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, 2024-02-20, 11:00–12:30 (exam inspection) • Wed, 2024-03-20, 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 so-called integer factorization and discrete-logarithm 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 “quantum-safe” cryptosystems is commonly referred to as “post-quantum 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.
  • Post-quantum 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, 2023-10-16:
    • 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, 2023-10-18:
  • Practice 1, 2023-10-19
  • Lecture 3, 2023-10-23
    • Projective measurements. Composite systems. Tensor product of quantum states.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 4, 2023-10-25
    • 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, 2023-10-26
  • Lecture 5, 2023-10-30
    • Simon’s algorithm (finished). RSA. ElGamal. Relationship period finding / factoring.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 6, 2023-11-06
    • Shor’s algorithm (for period-finding). Mentioned: Grover’s algorithm.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 7, 2023-11-08
    • Learning with errors. LPR (Lyubashevksy-Peikert-Regev) cryptosystem.
    • Whiteboard as PDF or Miro board, recording.
  • Practice 3, 2023-11-09
  • Lecture 8, 2023-11-13
    • Error correcting codes. Code-based cryptography: McEliece / Niederreiter
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 9, 2023-11-15
    • IND-CPA security. IND-CCA security. Key encapsulation mechanisms (KEMs). Fujisaki-Okamoto (started).
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 10, 2023-11-20
    • Fujisaki-Okamoto (continued). Quantum random oracle model (QROM, started).
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 11, 2023-11-27
    • Quantum random oracle model (QROM, continued). One-way to hiding theorem (O2H). Optimality of Grover.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 12, 2023-11-29
    • Security proof of toy-FO-variant. Overview over NIST postquantum competition.
    • Whiteboard as PDF or Miro board, recording.
  • Practice 4, 2023-11-30
    • Homework 2. O2H theorem with multiple “marked” elements. Optimality of Grover.
    • Whiteboard as PDF or Miro board, recording.
  • Nothing in the week 4-9 December
  • Lecture 13, 2023-12-11
  • Lecture 14, 2023-12-13
  • Practice 5, 2023-12-14
  • Lecture 15, 2023-12-18
    • Soundness of MLWE-based ID-scheme. Fiat-Shamir transform. LWLE-based signature scheme (simplified).
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 16, 2023-12-21
    • Signatures: Definition of EF-CMA security, EF-OT-CMA security (one-time). One-time signatures from hash functions (Lamport).
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 17, 2024-01-08
  • Lecture 18, 2024-01-10
    • Sphincs+ (rough overview). Zero-knowledge proofs: Intro. Sigma-protocols. Graph-isomorphism.
    • Whiteboard as PDF or Miro board, recording.
  • Practice 6, 2024-01-11
    • Reusing Lamport-signatures. EF-NMA secure signature scheme (silly). Graph-isomorphism identification-scheme.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 19, 2024-01-15
    • Definitions completeness, soundness, and zero-knowledge. Soundness of graph-isomorphism protocol. Zero-knowledge of graph-isomorphism protocol (classically).
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 20, 2024-01-17
    • Quantum Zero-knowledge of graph-isomorphism: problems and proof. Watrous’ rewinding lemma.
    • Whiteboard as PDF or Miro board, recording
  • Practice 7, 2024-01-18
    • Proof: the “aborting simulator” works. Example: Using zero-knowledge property in an identification protocol.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 21, 2024-01-22
    • Watrous’ rewinding lemma (finished proof). Symmetric crypto: Defininition strong PRP (pseudo-random permutation). Definition strong qPRP. Evan-Mansour block cipher. Breaking Evan-Mansour with superposition queries.
    • Whiteboard as PDF or Miro board, recording.
  • Lecture 22, 2024-01-29
    • Collision-finding in hash functions: classical and quantum. Attacking Even-Mansour without superposition queries.
    • Board photos. Recording by Video AG will follow.
  • Practice 8, 2024-02-01

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.