Quantum Cryptography

Lecture spring 2021

Instructor Dominique Unruh
TA Raul-Martin Rebane (submit homework solutions here)
Lecture Period February 10 - May 26
Lectures Wednesdays, 16:15-17:45, Zoom (link in Slack chat) (Dominique; may sometimes be switched with tutorial)
Practice sessions
Tuesdays, 16:15-17:45, Zoom (link in Slack chat) (Raul-Martin)
Course Material Lecture notes (old ones), blackboard photos, practice blackboard photos, and exam study guide.
Language English
Exam May 30, 12:00 – 15:00. (Reexam will be scheduled later.)
Contact Dominique Unruh <<surname> at ut dot ee>

Topics covered

See also the blackboard photos and the practice blackboard photos.
DateSummaryKnowlets coveredMaterials
Feb 10Quantum systems, quantum states, unitary operations.QState, UniTrafo, PauliXVideo, Whiteboard
Feb 16Small exercises with single qubits. Polarization invariant under rotation.QState, UniTrafo, Hada, RotaWhiteboard
Feb 17Measurements in computational basis. Elitzur-Vaidman bomb tester. Complete measurements.CBMeas, Bomb, ComplMeas, CompBasisVideo, Whiteboard
Feb 23Light filters as measurements. Improved bomb tester. Quantum Zero effect.Bomb, ComplMeasWhiteboard
Mar 02Initializing using measurements. States from prob. distributions. Equivalent definitions of unitary.ComplMeas, ConjTrans, DiracWhiteboard
Mar 03Projective measurements. Tensor product. Composition of quantum systems / quantum states / unitaries / measurements.ProjMeas, ProjMeasVS, ComposQSys, ComposQState, Tensor, ComposUni, ComposMeasVideo, Whiteboard
Mar 09Using tensor product and proj. measurements. Quantum teleportation.ProjMeas, Tensor, ComposUni, ComposMeasWhiteboard
Mar 10Deutsch's algorithm. Quantum state probability distributions (ensembles). Operations on ensembles. Density operators.Deutsch, QDistr, PhysInd, QDistrU, QDistrX, QDistrM, DensityVideo, Whiteboard
Mar 16Distinguishing incorrect toy crypto. Density operators. Creating unitaries for boolean functions.QDistr, QDistrM, Density, DensityPhysInd, ToffWhiteboard
Mar 17Operations on density operators. Theorem: Physically indistinsuishable iff same density operator. Toy crypto protocol is secure. Quantum one-time pad. Density, DensityU, DensityM, DensityX, DensityPhysInd, QOTPVideo, Whiteboard
Mar 23Unitaries and measurements on density ops. Observables.Density, DensityUWhiteboard
Mar 24Partial trace. Quantum operations.ParTr, QOper, QOperAltVideo, Whiteboard
Mar 30Tracing out buffer qubits in $U_f$. Trace as a quantum op. Replace operation.ParTr, QOperWhiteboard
Mar 31Statistical distance. Trace distance. Short mentions not in notes: Fidelity. Optimal distinguisherSD, SDSumDef, SDProps, TD, TDMaxDef, TDSD, TDPropsVideo, Whiteboard
Apr 06Trace distance of biased distributions. QOTP without 0-keys. TD between any two states.SD, SDSumDef, TD, TDPropsWhiteboard
Apr 07Quantum key distribution: Intro. Security definition. Protocol overview. First step (distributing Bell pairs).QKDIntro, QKDSecDef, QKDProto, Bell, TildeNotationVideo, Whiteboard
Apr 13Prob. of measuring key after QKD. Alternate sec def of QKD. SMT from QKD.QKDSecDefWhiteboard
Apr 14Quantum key distribution: Bell test. Measuring the raw key.BellTest, BellTestAna, RawKey, RawKeyKeyDiff, RawKeyGuess, MinEnt, RawKeyEnt, RawKeyAnaVideo, Whiteboard
Apr 20Alternate sec def for QKD (continued). Measuring key with t errors.QKDSecDef, RawKeyGuessWhiteboard
Apr 21Error correcting codes. Error correction step in QKD. Strong randomness extractors. Universal hash functions. Privacy amplification in QKD. Finished QKD security proof.ECC, QKDCorr, Chain, QKDCorrAna, PrivAmp, RandExtQ, UHF, LHL, PrivAmpAna, QKDWrapupVideo, Whiteboard
Apr 27Last bit of key deleted or set 0. Error correction after randomness extraction. Extracting too much from a key. Problems with deterministic randomness extractors.ECC, RandExtC, UHFWhiteboard
Apr 28Shor's algorithm. Period finding. Factoring. Discrete logarithm.Fact, Period, FactFromPeriod, DFT, DFTAlgo, Shor, DlogAlgoVideo, Whiteboard
May 04Implementing the Quantum Fourier Transform. The von Neumann extractor.DFTAlgoWhiteboard
May 05LWE problem (computational and decisional). Regev's cryptosystem. IND-CPA security of Regev's cryptosystem.BinCompLWE, CompLWE, DecLWE, Regev, RegevCPAVideo, Whiteboard
May 11Example of Regev's cryptosystem. The Short Integer Solutions problem. Collision-Resistant hash functions from SIS.RegevWhiteboard
May 12Classical/quantum zero knowledge. Difficulty with rewinding in the quantum case.ProofSys, ZK, GIZK, QZK, QZKProblemVideo, Whiteboard
May 18Aborting simulators - classical and quantum.ProofSys, ZK, GIZK, QZKWhiteboard
May 19Quantum rewinding. Constructing a quantum ZK simulator.QRewind, QZKAnaVideo, Whiteboard
May 26Schrödinger equation. Particle in an infinite potential well.PhysicalVideo, Whiteboard


Your current amount of points in the homework can be accessed here (as soon as the first sheet has been corrected).
Out Due Homework Solution
2021-02-212021-03-01Homework 1Solution 1
2021-03-012021-03-08Homework 2Solution 2
2021-03-082021-03-16Homework 3Solution 3
2021-03-152021-03-23Homework 4Solution 4
2021-03-222021-03-30Homework 5Solution 5
2021-03-292021-04-06Homework 6Solution 6
2021-04-052021-04-13Homework 7Solution 7
2021-04-122021-04-20Homework 8Solution 8
2021-04-202021-04-27Homework 9Solution 9
2021-04-262021-05-04Homework 10Solution 10
2021-05-032021-05-11Homework 11Solution 11
2021-05-102021-05-18Homework 12Solution 12
2021-05-182021-05-25Homework 13Solution 13


In quantum cryptography we use quantum mechanical effects to construct secure protocols. The paradoxical nature of quantum mechanics allows for constructions that solve problems known to be impossible without quantum mechanics. This lecture gives an introduction into this fascinating area.

Possible topics include:


You need no prior knowledge of quantum mechanics. You should have heard some introductory lecture on cryptography. You should enjoy math and have a sound understanding of linear algebra.


[NC00] Nielsen, Chuang. "Quantum Computation and Quantum Information" Cambridge University Press, 2000. A standard textbook on quantum information and quantum computing. Also contains some quantum cryptography.

Further reading may be suggested during the course. See the "further reading" paragraphs in the lecture notes.