# Adversarial Examples from Cryptographic Pseudo-Random Generators

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2018.

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

- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [Detecting Adversarial Examples Is (Nearly) As Hard As Classifying Them](https://mlsanity.com/paper/2107.11630/) (2021)
- [Calibration and Consistency of Adversarial Surrogate Losses](https://mlsanity.com/paper/2104.09658/) (2021)
- [On the Existence of the Adversarial Bayes Classifier (Extended Version)](https://mlsanity.com/paper/2112.01694/) (2021)
- [Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition](https://mlsanity.com/paper/2103.09947/) (2021)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [Computational Asymmetries in Robust Classification](https://mlsanity.com/paper/2306.14326/) (2023)
- [Provable Adversarial Robustness in the Quantum Model](https://mlsanity.com/paper/2112.09625/) (2021)
- [Identifying and Exploiting Structures for Reliable Deep Learning](https://mlsanity.com/paper/2108.07083/) (2021)
- [mathscrH-Consistency Estimation Error of Surrogate Loss Minimizers](https://mlsanity.com/paper/2205.08017/) (2022)

## Abstract (arXiv)

In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the problem. More precisely, we constructed a binary classification task for which (i) a robust classifier exists; yet no non-trivial accuracy can be obtained with an efficient algorithm in (ii) the statistical query model. In the present paper we significantly strengthen both (i) and (ii): we now construct a task which admits (i') a maximally robust classifier (that is it can tolerate perturbations of size comparable to the size of the examples themselves); and moreover we prove computational hardness of learning this task under (ii') a standard cryptographic assumption.