TAU CS 0368-3414: Seminar on Foundations of Provable AI Security

Dr. Or Zamir       Spring 2026

Today’s AI systems are remarkably capable but often untrustworthy: we don’t really know why they make decisions or whether we can rely on them, especially when trained or hosted by others. This seminar will explore emerging works in which ideas from cryptography and complexity theory, where we developed a rich set of tools to argue formally about security, can bring mathematical rigor to AI trust and safety.

Participating requires a background or feeling of comfort with theoretical computer science (proofs, rather than experiments). Some background in cryptography or machine learning is ideal but not necessary for students who are willing and able to catch up on basic definitions from these fields that will come up.

The course requirements include reading, understanding, and presenting one paper in class, as well as three short (two-three paragraphs) reflection assignments throughout the semester.

The seminar will run for 12 weeks. In each week, two students will prepare a pair of related talks (one hour and one hour) on the same paper or on closely related papers. In some weeks, the natural split is between different parts of one paper; in other weeks, the pair should divide a main paper together with one related/background paper.

Reference Material

Students do not need to already know all of the machine-learning or cryptography background needed for every topic. However, before picking a topic, it is a good idea to look at the reference material below and make sure you are comfortable catching up on whichever background your topic requires.

• Related MIT course: Cryptography and Machine Learning: Foundations and Frontiers (MIT, Spring 2026). This is a closely related course currently being taught at MIT, and its schedule and resources give useful context for many of the topics in this seminar.
• ML background: MIT Intro to ML lecture notes.
• Cryptography background: MIT Crypto × ML scribe notes on cryptography basics.

Core Presentation Topics

• Topic 1: Undetectable Watermarking for Language Models. The basic cryptographic notion of watermarking language-model outputs without detectable degradation in quality. [Main paper: Undetectable Watermarks for Language Models] [Related: A Watermark for Large Language Models] [Background blog post]
• Topic 2: Robust Watermarking via Pseudorandom Codes. How pseudorandom error-correcting codes (PRCs) yield stronger robustness guarantees for watermarking and related tasks. [Main paper: Pseudorandom Error-Correcting Codes] [Related: Edit Distance Robust Watermarks via Indexing Pseudorandom Codes] [Further development: Improved Pseudorandom Codes from Permuted Puzzles] Suggested scope: focus mainly on the early sections of the PRCs paper and use the related papers as context or extensions.
• Topic 3: Undetectable Steganography for Language Models. Hiding arbitrary secret payloads inside model outputs, with provable indistinguishability guarantees. [Main paper: Undetectable Steganography for Language Models] [Related: steganography section in Pseudorandom Error-Correcting Codes] [Optional consequences: Chain-of-thought monitoring / agent collusion (first sections only)]
• Topic 4: Verification of PAC Learning. Interactive proofs for verifying that a learned hypothesis is approximately correct, sometimes with much less data than learning itself. [Main paper: Interactive Proofs for Verifying Machine Learning]
• Topic 5: Adversarial Examples and Computational Hardness. A theoretical view in which robustness can rely on hardness assumptions. [Main paper: Adversarially Robust Learning Could Leverage Computational Hardness] [Optional background: adversarial examples lecture notes] Suggested split: one talk on the adversarial-examples background and formal setup, one on the computational-hardness construction and implications.
• Topic 6: Undetectable Backdoors in Machine Learning Models. A theoretical framework showing how a malicious trainer can plant a hidden backdoor while remaining computationally indistinguishable from a clean model. [Main paper: Planting Undetectable Backdoors in Machine Learning Models] Suggested split: one talk on the black-box signature-based construction, one on the white-box / learning-paradigm-specific construction and implications for robustness.
• Topic 7: Backdoor Mitigation without Detection. How to remove backdoors while avoiding an explicit detection step. [Main paper: Oblivious Defense in ML Models: Backdoor Removal without Detection]
• Topic 8: Cryptographic Hardness of Learning. Showing that some concept classes are PAC learnable in principle but not efficiently learnable under standard cryptographic assumptions. [Main paper: Cryptographic Hardness of Learning Halfspaces with Massart Noise] [Background: Continuous LWE]
• Topic 9: Private Inference / Private Search. Cryptographic protocols for querying powerful systems while hiding the user’s data or query. [Main option: GAZELLE: A Low Latency Framework for Secure Neural Network Inference] [Alternative option: Private Web Search with Tiptoe]
• Topic 10: Model Extraction Attacks as Cryptanalysis. Exact or near-exact recovery of model parameters from query access, viewed through a cryptanalytic lens. [Main option: Cryptanalytic Extraction of Neural Network Models] [Advanced option: Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting]
• Topic 11: The Computational Intractability of Filtering for AI Alignment. Formal limitations on using external filters or judges to separate safe from unsafe behavior. [Main paper: On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment] [Related consequences: Bypassing Prompt Guards in Production with Controlled-Release Prompting]

Optional Topics

• [Optional Topic A] Impossibility of Strong Watermarking. A negative-result companion to the watermarking block. [Main paper: Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models] Should be placed after Topics 1-2.
• [Optional Topic B] Verifying Properties of Distribution Samples. A more general verification topic, adjacent to PAC verification but focused on properties of unknown distributions. [Main paper: Doubly-Efficient Interactive Proofs for Distribution Properties] Should be placed after Topic 4.
• [Optional Topic C] Models That Prove Their Own Correctness. A modern direction connecting learned models with proof generation and per-instance guarantees. [Main paper: Models That Prove Their Own Correctness] Should be placed after Topic 4 or near the end of the seminar.