Adversarial Examples from Cryptographic Pseudo-Random Generators

Abstract

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.

arXiv comment4 pages, no figures

References in corpus (1)

• Adversarial examples from computational constraints

Cited by in corpus (15)

• Theoretically Principled Trade-off between Robustness and Accuracy
• Adversarial Robustness May Be at Odds With Simplicity
• The Limitations of Adversarial Training and the Blind-Spot Attack
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Lower Bounds for Adversarially Robust PAC Learning
• How Hard Is Robust Mean Estimation?
• Computational Limitations in Robust Classification and Win-Win Results
• Calibration and Consistency of Adversarial Surrogate Losses
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Adversarially Robust Low Dimensional Representations
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
• Query complexity of adversarial attacks
• Adversarial Examples and Metrics
• A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks
• Derivation of Information-Theoretically Optimal Adversarial Attacks with Applications to Robust Machine Learning