# A Cryptographic Perspective on Mitigation vs. Detection in Machine Learning

arXiv: https://arxiv.org/abs/2504.20310 · HTML: https://mlsanity.com/paper/2504.20310/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 51 references that are in the map.
- First posted on arXiv 28 Apr 2025.

## Builds on (most cited first, 26 of 26)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Universal and Transferable Adversarial Attacks on Aligned Language Models](https://mlsanity.com/paper/2307.15043/) (2023)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Jailbroken: How Does LLM Safety Training Fail?](https://mlsanity.com/paper/2307.02483/) (2023)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [Tree of Attacks: Jailbreaking Black-Box LLMs Automatically](https://mlsanity.com/paper/2312.02119/) (2023)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Jailbreaking Leading Safety-Aligned LLMs with Simple Adaptive Attacks](https://mlsanity.com/paper/2404.02151/) (2024)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [Alignment faking in large language models](https://mlsanity.com/paper/2412.14093/) (2024)
- [Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discovery](https://mlsanity.com/paper/2302.03668/) (2023)
- [Are aligned neural networks adversarially aligned?](https://mlsanity.com/paper/2306.15447/) (2023)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [AI Alignment: A Comprehensive Survey](https://mlsanity.com/paper/2310.19852/) (2023)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Exploring the Landscape of Spatial Robustness](https://mlsanity.com/paper/1712.02779/) (2017)
- [Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory](https://mlsanity.com/paper/1711.01244/) (2017)
- [Adversarial Examples that Fool both Computer Vision and Time-Limited Humans](https://mlsanity.com/paper/1802.08195/) (2018)
- [Trading Inference-Time Compute for Adversarial Robustness](https://mlsanity.com/paper/2501.18841/) (2025)
- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them](https://mlsanity.com/paper/2107.11630/) (2021)
- [Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples](https://mlsanity.com/paper/2007.05145/) (2020)
- [Oblivious Defense in ML Models: Backdoor Removal without Detection](https://mlsanity.com/paper/2411.03279/) (2024)

## Built on by (most cited first, 1 of 1)

- [Proofs of Ownership for Machine Learning Models](https://mlsanity.com/paper/2606.30423/) (2026)

## Abstract (arXiv)

In this paper, we initiate a cryptographically inspired theoretical study of detection versus mitigation of adversarial inputs produced by attackers on Machine Learning algorithms during inference time. We formally define defense by detection (DbD) and defense by mitigation (DbM). Our definitions come in the form of a 3-round protocol between two resource-bounded parties: a trainer/defender and an attacker. The attacker aims to produce inference-time inputs that fool the training algorithm. We define correctness, completeness, and soundness properties to capture successful defense at inference time while not degrading (too much) the performance of the algorithm on inputs from the training distribution. We first show that achieving DbD and achieving DbM are equivalent for ML classification tasks. Surprisingly, this is not the case for ML generative learning tasks, where there are many possible correct outputs for each input. We show a separation between DbD and DbM by exhibiting two generative learning tasks for which it is possible to defend by mitigation but it is provably impossible to defend by detection. The mitigation phase uses significantly less computational resources than the initial training algorithm. In the first learning task we consider sample complexity as the resource and in the second the time complexity. The first result holds under the assumption that the Identity-Based Fully Homomorphic Encryption (IB-FHE), publicly-verifiable zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK), and Strongly Unforgeable Signatures exist. The second result assumes the existence of Non-Parallelizing Languages with Average-Case Hardness (NPL) and Incrementally-Verifiable Computation (IVC) and IB-FHE.