# Quantum Cryptography

Lecture spring 2023

 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 <at ut dot ee>

## Topics covered

DateSummaryKnowlets coveredMaterials
Feb 06General intro. Quantum systems, quantum statesQStateVideo, Whiteboard
Feb 07Unitary operations, measurements in computational basis, Elitzur-Vaidman bomb testerUniTrafo, CBMeas, PauliX, PauliY, PauliZ, BombVideo, Whiteboard
Feb 13Complete measurements. Projective measurements (subspace view).ComplMeas, ProjMeasVS, HadaVideo, Whiteboard
Feb 14Quantum Zeno effect, polarization invariant under rotation.ComplMeas, ConjTrans, DiracWhiteboard
Feb 20Projective measurements (projector view). Tensor product. Composition of quantum systems / quantum states / unitaries / measurements.ProjMeas, ComposQSys, ComposQState, Tensor, ComposUni, ComposMeasVideo, Whiteboard
Feb 21Using tensor product and proj. measurements. Quantum teleportationProjMeas, Tensor, ComposUni, ComposMeas, CNOT, HadaWhiteboard
Feb 27Quantum 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
Feb 28Density operators. Implementing boolean unitariesQDistr, QDistrM, Density, DensityPhysInd, ToffWhiteboard
Mar 06Quantum One-Time Pad. Partial Trace.QOTP, ParTrVideo, Whiteboard
Mar 07Backwards toy crypto. Calculating Partial Trace. Tracing out buffer qubits in \$U_f\$. Impossibility of FTL communication.ParTrWhiteboard
Mar 13Motivation for trace distance. Statistical distance. Trace distance. Quantum operations.SD, SDSumDef, SDProps, TD, TDMaxDef, TDSD, TDProps, QOper, QOperAltVideo, Whiteboard
Mar 14Trace Distance of lecture example. QOTP with no zero-keys. Replace as Kraus operator. Trace Distance between arbitrary states.QOper, ParTr, SD, SDSumDefWhiteboard
Mar 20Quantum key distribution: Intro. Security definition. Protocol overview.QKDIntro, QKDSecDef, QKDProtoVideo, Whiteboard
Mar 21Prob. of measuring key after QKD. Alternate sec def of QKD. SMT from QKD.QKDSecDefWhiteboard
Mar 27Quantum key distribution: First step (distributing Bell pairs). Bell test. Measuring the raw key. Min-entropy.Bell, TildeNotation, BellTest, BellTestAna, RawKey, RawKeyKeyDiff, RawKeyGuess, MinEnt, RawKeyEnt, RawKeyAnaVideo, Whiteboard
Mar 28Measuring the key with t errors. Equivalence of the alternative QKD security definition.QKDSecDef, RawKeyGuessWhiteboard
Apr 03Error 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 04Last 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, UHFWhiteboard
Apr 10Shor's algorithm. Period finding. Factoring. Discrete logarithm.Fact, Period, FactFromPeriod, DFT, DFTAlgo, ShorVideo, Whiteboard
Apr 11Using period finding to solve discrete logarith. Implementing the Quantum Fourier Transform.DFTAlgoWhiteboard
Apr 17LWE problem (computational and decisional). Regev's cryptosystem. IND-CPA security of Regev's cryptosystem.BinCompLWE, CompLWE, DecLWE, Regev, RegevCPAVideo, Whiteboard
Apr 18Example of Regev's cryptosystem. Solving SVP using SIS. Using a short basis to make a trapdoor.RegevWhiteboard
Apr 24IND-CCA security. KEMs and hybrid encryption. Fujisaki-Okamoto transform.IndCca, KEM, HybEnc, IndCcaKem, FO, FoSecVideo, Whiteboard
Apr 25Quantum random oracle model. Simplified Fujisaki-Okamoto example. O2H Theorem.QromIdea, QromEx, O2HVideo, Whiteboard
May 02FO with implicit rejection. Applications of O2H. Semi-classical oracles. O2H on a set of inputs.QromIdea, QromEx, O2HWhiteboard
May 08Classical zero-knowledge proofs. Difficulty with rewinding in the quantum case.ProofSys, ZK, GIZK, QZKProblemVideo, Whiteboard
May 09Aborting simulators - classical and quantum.ProofSys, ZK, GIZK, QZK, QAbortSimWhiteboard
May 15Quantum zero-knowledge. Difficulty with rewinding in the quantum case. Constructing a quantum ZK simulator.QZK, QRewind, QZKAnaVideo
May 16Zero Knowledge: Encryption input protocol, Hamiltonian cycles protocolProofSys, ZK, GIZK, QZKWhiteboard
May 22Schrödinger equation. Particle in an infinite potential well.PhysicalVideo, Whiteboard

## 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
2023-02-132023-02-20Homework 1Solution 1
2023-02-202023-02-27Homework 2Solution 2
2023-02-272023-03-06Homework 3Solution 3
2023-03-062023-03-13Homework 4Solution 4
2023-03-132023-03-20Homework 5Solution 5
2023-03-202023-03-27Homework 6Solution 6
2023-03-272023-04-03Homework 7Solution 7
2023-04-032023-04-10Homework 8Solution 8
2023-04-102023-04-17Homework 9Solution 9
2023-04-172023-04-24Homework 10Solution 10
2023-04-252023-05-03Homework 11Solution 11
2023-05-082023-05-15Homework 12Solution 12
2023-05-152023-05-22Homework 13

## 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:

• Basics of Quantum Computation
• Breaking Crypto with Quantum Computers
• Quantum Key Exchange
• Quantum Commitments (Possibility/Impossibility)
• Quantum Zero-Knowledge
• Everlasting Security
• Quantum Time Vaults

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

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