Cryptography and Machine Learning

Course information

Schedule · subject to change

• 0Tue Oct 20IntroductionNotes 0

  Methodologies of machine learning and cryptography. Course overview. Recurring themes: definitions and guarantees, assumptions and proofs, relevance at scale.

• 1Tue Oct 20Cryptography and learningNotes 1Notes 1.5Visual 1Visual 1.5

  Pseudorandom functions and hardness of PAC learning. Circuit complexity; neural nets as threshold circuits. Learning parity with noise (LPN).

  • Goldreich–Goldwasser–Micali: How to Construct Random Functions
  • Kearns–Valiant: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
  • Blum–Furst–Kearns–Lipton: Cryptographic Primitives Based on Hard Learning Problems
• Tue Oct 27No class (elections).
• 2Fri Oct 30Discrete vs. continuous assumptionsFriday make-upNotes 2Visual 2

  LWE; worst-case hardness; generating fresh samples. Continuous LWE and Gaussian pancakes. Statistical vs. computational gaps.

  Builds on lecture 1

  • Peikert: A Decade of Lattice Cryptography
  • Bruna–Regev–Song–Tang: Continuous LWE
  • Diakonikolas–Kane–Stewart: Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
• 3Tue Nov 3Adversarial robustness in classificationNotes 3Notes 3.5Visual 3Visual 3.5

  Accuracy does not imply robustness. Gradient-based attacks and adversarial training. Certified and cryptographic robustness. Invariance attacks; adaptively robust random projections.

  Builds on lectures 1, 2

  • Bubeck–Price–Razenshteyn: Adversarial Examples from Computational Constraints
  • Madry et al.: Towards Deep Learning Models Resistant to Adversarial Attacks
  • Cohen–Rosenfeld–Kolter: Certified Adversarial Robustness via Randomized Smoothing
  • Bogdanov–Rosen–Vafa–Vaikuntanathan: Adaptive Robustness of Hypergrid Johnson–Lindenstrauss
• Tue Nov 10No class.
• 4Tue Nov 17BackdoorsNotes 4Visual 4

  Spectral signatures. Undetectable backdoors from signatures and hCLWE. Undetectability vs. power asymmetry; invariance backdoors in deep networks. Removal without detection.

  Builds on lectures 1, 2, 3

  • Goldwasser–Kim–Vaikuntanathan–Zamir: Planting Undetectable Backdoors in Machine Learning Models
  • Bogdanov–Rosen–Vafa: Statistically Undetectable Backdoors in Deep Neural Networks
  • Tran–Li–Madry: Spectral Signatures in Backdoor Attacks
  • Goldwasser–Shafer–Vafa–Vaikuntanathan: Oblivious Defense in ML Models: Backdoor Removal without Detection
• 5Tue Nov 24Hardness of score estimationNotes 5Visual 5

  Diffusion; sampling reduces to score estimation. Learning the score; hardness from hCLWE.

  Builds on lecture 2

  • Chen–Chewi–Li–Li–Salim–Zhang: Sampling is as Easy as Learning the Score
  • Song: Cryptographic Hardness of Score Estimation
• 6Tue Dec 1WatermarkingNotes 6Notes 6.5Visual 6

  Reliable detection; the red–green trick. Undetectable watermarks via keyed Gumbel sampling. Robust watermarks from pseudorandom codes. Watermarking diffusion models.

  Builds on lectures 1, 5

  • Kirchenbauer et al.: A Watermark for Large Language Models
  • Christ–Gunn–Zamir: Undetectable Watermarks for Language Models
  • Christ–Gunn: Pseudorandom Error-Correcting Codes
  • Gunn–Zhao–Song: An Undetectable Watermark for Generative Image Models
• 7Tue Dec 8Model extraction and low logit rankNotes 7Notes 7.5Visual 7.5

  Functional and distributional extraction. Outputs as equations; ReLU boundaries reveal hidden neurons. Distillation: training a surrogate on queried outputs. The extended logit matrix; low rank in trained language models. Model extraction from unrelated queries. Efficient learning from logit queries.

  Builds on lectures 1, 2, 6

  • Tramèr et al.: Stealing Machine Learning Models via Prediction APIs
  • Carlini–Jagielski–Mironov: Cryptanalytic Extraction of Neural Network Models
  • Canales et al.: Polynomial Time Cryptanalytic Extraction of Neural Network Models
  • Golowich–Liu–Shetty: Provably Learning from Modern Language Models via Low Logit Rank
• 8Tue Dec 15Cryptography for MLNotes 8Visual 8

  Encryption and homomorphic encryption. Secure two-party computation. Private vector search: PIR and encrypted matrix–vector products (EMVP). Private neural-network inference.

  Builds on lecture 2

  • Chor–Goldreich–Kushilevitz–Sudan: Private Information Retrieval
  • Henzinger et al.: SimplePIR
  • Benhamouda et al.: Encrypted Matrix-Vector Products from Secret Dual Codes
  • Vaikuntanathan–Zamir: Trapdoored Matrices and Applications
• 9Tue Dec 22Verifiable inference and trainingGuest lecturer: Ron RothblumNotes 9Notes 9.5Visual 9Visual 9.5

  Interactive proofs: randomized verification, sumcheck, layered circuits. Succinct arguments; zero knowledge. Provenance: authentication, proofs of provenance, homomorphic signatures, malleable proofs.

  Builds on lectures 6, 7

  • Goldwasser–Micali–Rackoff: The Knowledge Complexity of Interactive Proof Systems
  • Lund–Fortnow–Karloff–Nisan: Algebraic Methods for Interactive Proof Systems
  • Liu–Xie–Zhang: zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions
• 10Tue Dec 29Sketching learning algorithmsNotes 10

  The data deletion problem. Forward-mode automatic differentiation; sketching circuits via higher-order derivatives.

  Builds on lecture 3

  • Gunn: How to Sketch a Learning Algorithm · code
• 11Tue Jan 5AI safetyNotes 11

  Sandboxed evaluation of untrusted models. Sandbagging: strategic underperformance on evaluations; detection via noise injection. Heuristic arguments; the computational no-coincidence conjecture. Open problems.

  Builds on lectures 1, 4, 9

  • Tice et al.: Noise Injection Reveals Hidden Capabilities of Sandbagging Language Models
  • Greenblatt–Shlegeris–Sachan–Roger: AI Control: Improving Safety Despite Intentional Subversion
  • Neyman: A Computational No-Coincidence Principle
  • Tsimerman: AI Safety for Mathematicians
• 12Tue Jan 12Project presentations

  Final project presentations. Groups of 4–5 students; about 20 minutes per group.

• 13Mon Jan 18Project presentationsMonday make-up

  Final project presentations. Groups of 4–5 students; about 20 minutes per group.

Resources

• Shalev-Shwartz–Ben-David: Understanding Machine Learning: From Theory to Algorithms
• Bogdanov–Rosen: Pseudorandom Functions: Three Decades Later
• Peikert: A Decade of Lattice Cryptography
• Goldwasser–Vaikuntanathan: Cryptography and ML: Foundations and Frontiers (MIT 6.S976, Spring 2026)
• Bogdanov: Great Algorithms (CSI 4103/5138, University of Ottawa)
• Interaction with and tutoring by language models is encouraged, except for homework.