Lattices (W2–W4) — read upstream

Weeks 2, 3, and 4 follow chapters from the upstream cryptanalysis book Elements of Cryptanalysis. Read them in order before each Tuesday.

Week	Chapter	Direct link
W2	Ch 40 — Lattice Problems — SVP, CVP, and LWE	https://bnaskrecki.faculty.wmi.amu.edu.pl/crypto/book/part14_lattice_crypto/ch40_lattice_problems.html
W3	Ch 41 — ML-KEM (Kyber) — Design and Implementation	https://bnaskrecki.faculty.wmi.amu.edu.pl/crypto/book/part14_lattice_crypto/ch41_ml_kem_kyber.html
W4	Ch 42 — Attacks on Lattice-Based Schemes	https://bnaskrecki.faculty.wmi.amu.edu.pl/crypto/book/part14_lattice_crypto/ch42_attacks_lattice.html

Lab focus per week

• W2 lab. Implement LLL from scratch on small bases. Use it to break the Merkle–Hellman knapsack you built in W1 (Chapter 46, Exercise 46.5).

• W3 lab. Toy LWE keygen / encrypt / decrypt. Run a reference Kyber implementation (pip install pqcrypto); measure key/ciphertext sizes and timings for ML-KEM-512, 768, 1024.

• W4 lab. Sign / verify with a Dilithium reference implementation. Run a small Kannan-embedding attack on toy LWE (the code in Ch 42 §42.3 is ready to use). Then run Albrecht’s lattice-estimator against the three ML-KEM parameter sets and reproduce the published “core-SVP” security levels.

What to skim vs. read carefully

• Skim the historical Ajtai/Regev recap in Ch 40 §40.1 — Adam covered the worst-case/average-case reduction in his complexity lecture.

• Read carefully the Gram–Schmidt / LLL construction in Ch 40 §40.3–40.7, the NTT in Ch 41 §41.3, and the primal/dual attack analyses in Ch 42 §42.3–42.4.

• Try the exercises Ex 40.4 (knapsack-via-SVP) and Ex 42.3 (decryption-failure boundary) — both will appear, paraphrased, on the exam.