|
| Instructor | Dominique Unruh |
| TA | Raul-Martin Rebane (submit homework solutions here) |
| Lecture Period | February 6 - May 23 |
| Lectures | Mondays, 12:15-13:45, Δ-1022
(Dominique; may sometimes be switched with tutorial) |
| Practice sessions |
Tuesdays, 10:15-12:00, Δ-2045 (Raul-Martin) |
| Chat | https://zulip.cs.ut.ee/#narrow/stream/312-Quantum-Cryptography-2023 |
| Course Material | Lecture
notes, recordings, blackboard photos, and exam study guide. |
| Language | English |
| Exam | 2023-05-25, 10:00–13:00, Delta room 1008 |
| Contact | Dominique Unruh <unruh@ut.ee> |
| Date | Summary | Knowlets covered | Materials |
|---|---|---|---|
| Feb 06 | General intro. Quantum systems, quantum states | QState | Video, Whiteboard |
| Feb 07 | Unitary operations, measurements in computational basis, Elitzur-Vaidman bomb tester | UniTrafo, CBMeas, PauliX, PauliY, PauliZ, Bomb | Video, Whiteboard |
| Feb 13 | Complete measurements. Projective measurements (subspace view). | ComplMeas, ProjMeasVS, Hada | Video, Whiteboard |
| Feb 14 | Quantum Zeno effect, polarization invariant under rotation. | ComplMeas, ConjTrans, Dirac | Whiteboard |
| Feb 20 | Projective measurements (projector view). Tensor product. Composition of quantum systems / quantum states / unitaries / measurements. | ProjMeas, ComposQSys, ComposQState, Tensor, ComposUni, ComposMeas | Video, Whiteboard |
| Feb 21 | Using tensor product and proj. measurements. Quantum teleportation | ProjMeas, Tensor, ComposUni, ComposMeas, CNOT, Hada | Whiteboard |
| Feb 27 | Quantum 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, DensityPhysInd | Video, Whiteboard |
| Feb 28 | Density operators. Implementing boolean unitaries | QDistr, QDistrM, Density, DensityPhysInd, Toff | Whiteboard |
| Mar 06 | Quantum One-Time Pad. Partial Trace. | QOTP, ParTr | Video, Whiteboard |
| Mar 07 | Backwards toy crypto. Calculating Partial Trace. Tracing out buffer qubits in $U_f$. Impossibility of FTL communication. | ParTr | Whiteboard |
| Mar 13 | Motivation for trace distance. Statistical distance. Trace distance. Quantum operations. | SD, SDSumDef, SDProps, TD, TDMaxDef, TDSD, TDProps, QOper, QOperAlt | Video, Whiteboard |
| Mar 14 | Trace Distance of lecture example. QOTP with no zero-keys. Replace as Kraus operator. Trace Distance between arbitrary states. | QOper, ParTr, SD, SDSumDef | Whiteboard |
| Mar 20 | Quantum key distribution: Intro. Security definition. Protocol overview. | QKDIntro, QKDSecDef, QKDProto | Video, Whiteboard |
| Mar 21 | Prob. of measuring key after QKD. Alternate sec def of QKD. SMT from QKD. | QKDSecDef | Whiteboard |
| Mar 27 | Quantum key distribution: First step (distributing Bell pairs). Bell test. Measuring the raw key. Min-entropy. | Bell, TildeNotation, BellTest, BellTestAna, RawKey, RawKeyKeyDiff, RawKeyGuess, MinEnt, RawKeyEnt, RawKeyAna | Video, Whiteboard |
| Mar 28 | Measuring the key with t errors. Equivalence of the alternative QKD security definition. | QKDSecDef, RawKeyGuess | Whiteboard |
| Apr 03 | Error 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, QKDWrapup | Video, Whiteboard |
| Apr 04 | Last bit of key deleted or set 0. Error correction after randomness extraction. Extracting too much from a key. Problems with deterministic randomness extractors. Lattices (briefly). The SIS hash function. | ECC, RandExtC, UHF | Whiteboard |
| Apr 10 | Shor's algorithm. Period finding. Factoring. Discrete logarithm. | Fact, Period, FactFromPeriod, DFT, DFTAlgo, Shor | Video, Whiteboard |
| Apr 11 | Using period finding to solve discrete logarith. Implementing the Quantum Fourier Transform. | DFTAlgo | Whiteboard |
| Apr 17 | LWE problem (computational and decisional). Regev's cryptosystem. IND-CPA security of Regev's cryptosystem. | BinCompLWE, CompLWE, DecLWE, Regev, RegevCPA | Video, Whiteboard |
| Apr 18 | Example of Regev's cryptosystem. Solving SVP using SIS. Using a short basis to make a trapdoor. | Regev | Whiteboard |
| Apr 24 | IND-CCA security. KEMs and hybrid encryption. Fujisaki-Okamoto transform. | IndCca, KEM, HybEnc, IndCcaKem, FO, FoSec | Video, Whiteboard |
| Apr 25 | Quantum random oracle model. Simplified Fujisaki-Okamoto example. O2H Theorem. | QromIdea, QromEx, O2H | Video, Whiteboard |
| May 02 | FO with implicit rejection. Applications of O2H. Semi-classical oracles. O2H on a set of inputs. | QromIdea, QromEx, O2H | Whiteboard |
| May 08 | Classical zero-knowledge proofs. Difficulty with rewinding in the quantum case. | ProofSys, ZK, GIZK, QZKProblem | Video, Whiteboard |
| May 09 | Aborting simulators - classical and quantum. | ProofSys, ZK, GIZK, QZK, QAbortSim | Whiteboard |
| May 15 | Quantum zero-knowledge. Difficulty with rewinding in the quantum case. Constructing a quantum ZK simulator. | QZK, QRewind, QZKAna | Video |
| May 16 | Zero Knowledge: Encryption input protocol, Hamiltonian cycles protocol | ProofSys, ZK, GIZK, QZK | Whiteboard |
| May 22 | Schrödinger equation. Particle in an infinite potential well. | Physical | Video, Whiteboard |
| Out | Due | Homework | Solution |
|---|---|---|---|
| 2023-02-13 | 2023-02-20 | Homework 1 | Solution 1 |
| 2023-02-20 | 2023-02-27 | Homework 2 | Solution 2 |
| 2023-02-27 | 2023-03-06 | Homework 3 | Solution 3 |
| 2023-03-06 | 2023-03-13 | Homework 4 | Solution 4 |
| 2023-03-13 | 2023-03-20 | Homework 5 | Solution 5 |
| 2023-03-20 | 2023-03-27 | Homework 6 | Solution 6 |
| 2023-03-27 | 2023-04-03 | Homework 7 | Solution 7 |
| 2023-04-03 | 2023-04-10 | Homework 8 | Solution 8 |
| 2023-04-10 | 2023-04-17 | Homework 9 | Solution 9 |
| 2023-04-17 | 2023-04-24 | Homework 10 | Solution 10 |
| 2023-04-25 | 2023-05-03 | Homework 11 | Solution 11 |
| 2023-05-08 | 2023-05-15 | Homework 12 | Solution 12 |
| 2023-05-15 | 2023-05-22 | Homework 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.