Quantum Cryptography
Lecture spring 2022

Instructor Dominique Unruh
TA Raul-Martin Rebane (submit homework solutions here)
Lecture Period February 7 - May 24
Lectures Mondays, 12:15-13:45, Δ-2045 + online (Dominique; may sometimes be switched with tutorial)
Practice sessions
Tuesdays, 14:15-15:45, Δ-1019 (Raul-Martin)
Chathttps://zulip.cs.ut.ee/#narrow/stream/14-Quantum-Cryptography.202022
Course Material Lecture notes (old ones), blackboard photos, practice blackboard photos, and exam study guide.
Language English
Exam 2022-06-09, 14.00–17.00, Delta, room 2039
Contact Dominique Unruh <<surname>at ut dot ee>

Topics covered

See also the blackboard photos and the practice blackboard photos.
DateSummaryKnowlets coveredMaterials
Feb 07Quantum systems, quantum statesQStateVideo, Whiteboard
Feb 08Unitary operations, measurements in computational basis, Elitzur-Vaidman bomb tester, complete measurementsUniTrafo, CBMeas, PauliX, PauliY, PauliZ, Bomb, ComplMeasVideo, Whiteboard
Feb 14Projective measurements.ProjMeas, ProjMeasVSVideo, Whiteboard
Feb 15Quantum Zeno effect, polarization invariant under rotation.
Feb 21Tensor product. Composition of quantum systems / quantum states / unitaries / measurements.ComposQSys, ComposQState, Tensor, ComposUni, ComposMeasVideo, Whiteboard
Feb 22Quantum teleportation, Deutsch's algorithmDeutsch, CNOT, HadaWhiteboard
Feb 28Quantum state probability distributions (ensembles). Operations on quantum state probability distributions. Density operators. Operations on density operators. Theorem: Physically indistinsuishable iff same density operator.QDistr, PhysInd, QDistrU, QDistrX, QDistrM, Density, Density, DensityU, DensityM, DensityX, DensityPhysIndVideo, Whiteboard
Mar 01Backwards toy crypto, implementing boolean unitaries, observables.DensityWhiteboard
Mar 07Quantum One-Time Pad. Partial Trace.QOTP, ParTrVideo, Whiteboard
Mar 08Calculating Partial Trace, Indistinguishability of Global Phase, Tracing out buffer qubits in $U_f$ParTr
Mar 14Partial Trace (continued). Quantum One-Time Pad revisited. Quantum operations. Motivation for trace distance. Statistical distance.QOTP, ParTr, QOper, QOperAlt, SD, SDSumDef, SDPropsVideo, Whiteboard
Mar 15Finding Kraus operators for basic operations. Statistical distance of OTP with no zero key.QOper, ParTr, SD, SDSumDef
Mar 21Trace distance. Not in lecture notes: Optimal distinguisherTD, TDMaxDef, TDSD, TDPropsVideo, Whiteboard
Mar 22TD between distributions, TD between any two states, QOTP without 0-keys.SD, SDSumDef, TD, TDPropsWhiteboard
Mar 28Quantum key distribution: Intro. Security definition. Protocol overview. First step (distributing Bell pairs).QKDIntro, QKDSecDef, QKDProto, Bell, TildeNotationVideo, Whiteboard
Mar 29Prob. of measuring key after QKD. Alternate sec def of QKD. SMT from QKD.QKDSecDefWhiteboard
Apr 04Quantum key distribution: Bell test. Measuring the raw key.BellTest, BellTestAna, RawKey, RawKeyKeyDiff, RawKeyGuess, MinEnt, RawKeyEnt, RawKeyAnaVideo, Whiteboard
Apr 05Measuring the key with t errors.QKDSecDef, RawKeyGuessWhiteboard
Apr 11Error 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 18Shor's algorithm. Period finding. Factoring. Discrete logarithm.Fact, Period, FactFromPeriod, DFT, DFTAlgo, Shor, DlogAlgoVideo, Whiteboard
Apr 19Implementing the Quantum Fourier Transform. The von Neumann extractor.DFTAlgoWhiteboard
Apr 25LWE problem (computational and decisional). Regev's cryptosystem. IND-CPA security of Regev's cryptosystem.BinCompLWE, CompLWE, DecLWE, Regev, RegevCPAVideo, Whiteboard
Apr 26Example of Regev's cryptosystem. The Short Integer Solutions problem. Collision-Resistant hash functions from SIS.RegevWhiteboard
May 02Classical/quantum zero knowledge. Difficulty with rewinding in the quantum case.ProofSys, ZK, GIZK, QZK, QZKProblemVideo, Whiteboard
May 03Aborting simulators - classical and quantum.ProofSys, ZK, GIZK, QZK, QAbortSimWhiteboard
May 09Quantum rewinding. Constructing a quantum ZK simulator.QRewind, QZKAnaVideo, Whiteboard
May 10Zero Knowledge: Graph nonisomorphism, Hamiltonian cycles protocol, Schnorr's protocol.ProofSys, ZK, GIZK, QZK
May 16Commitment: Definitions. Impossibility of information-theoretically secure commitment.Video, Whiteboard
May 17Commitment protocol example, impossibility of it being perfectly binding and hiding.Whiteboard
May 23Schrödinger equation. Particle in an infinite potential well.PhysicalVideo, Whiteboard
May 24Solving the practice exam.QState, UniTrafo, ComplMeas, QDistr, Density, PhysInd, ParTr

Homework

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
2022-02-252021-03-04Homework 1Solution 1
2022-03-022022-03-10Homework 2Solution 2
2022-03-112022-03-18Homework 3Solution 3
2022-03-182022-03-25Homework 4Solution 4
2022-03-302022-04-06Homework 5Solution 5
2022-04-182022-04-26Homework 6Solution 6
2022-04-252022-05-03Homework 7Solution 7
2022-05-112022-05-18Homework 8Solution 8
2022-05-272022-05-03Homework 9Solution 9
2022-06-062022-06-07Homework 10Solution 10

Description

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:

Requirements

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.

Reading

[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.