Adversarial Examples from Cryptographic Pseudo-Random Generators

Sébastien Bubeck, Yin Tat Lee, Eric Price, Ilya P. RazenshteynarXiv 2018 · OpenReview

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.

Introduction

The vulnerability of deep learning models to adversarial examples—small, targeted perturbations that induce misclassification—remains one of the most significant hurdles to the deployment of robust AI. While various hypotheses have been proposed to explain this phenomenon, ranging from insufficient training data to the inherent high dimensionality of input spaces, a growing body of evidence suggests that the bottleneck may be fundamental: computational complexity.

This paper explores the "computational hardness" hypothesis. We demonstrate that even when a "maximally robust" classifier exists and is computationally efficient to execute, it may be mathematically impossible for any efficient learning algorithm to discover it. By framing the learning process as a cryptographic challenge, we show that the difficulty of achieving robustness can be decoupled from the availability of data.

Methodology: The Cryptographic Trapdoor

To rigorously test the limits of learnability, we construct a synthetic binary classification task based on tools from theoretical computer science. The core of our construction is a Trapdoor Pseudo-Random Generator (PRG), specifically the Blum–Blum–Shub (BBS) generator.

Data Distributions

We define two distinct data distributions:

  1. $D_0$ (Noise): A uniform distribution over bit-strings, representing pure random noise.
  2. $D_1$ (Structured): A distribution generated using the BBS algorithm.

The Role of the Trapdoor

In cryptography, a "trapdoor" is a piece of secret information that renders a computationally hard problem easy to solve. In our construction, the trapdoor consists of the prime factors of a large composite number $N$.

  • With the Trapdoor: An observer can easily distinguish between $D_0$ and $D_1$, effectively acting as a perfect, robust classifier.
  • Without the Trapdoor: To any polynomial-time algorithm, $D_0$ and $D_1$ are statistically indistinguishable.

This setup allows us to create a scenario where a robust classifier is "hidden" behind a mathematical wall. The mapping from input to label is a "hard" function to compute unless the learner possesses the secret key.

Key Insights

Existence vs. Learnability

The most significant contribution of this work is the formal separation between the existence of a robust classifier and its learnability. We prove that the presence of a perfect model in the hypothesis space does not guarantee that a standard training process—even one with access to ample data—will ever converge upon it.

Maximal Robustness

Previous theoretical work often focused on hardness in the context of small perturbations. Our construction goes further, demonstrating a task that is "maximally robust." This task can tolerate noise levels comparable to the size of the input examples themselves. Despite this extreme level of potential robustness, the task remains unlearnable under standard cryptographic assumptions.

Sample Complexity is Not the Barrier

A common critique of model failure is the lack of sufficient training samples. However, we show that the sample complexity for our task is quite low ($O(n)$). This confirms that a learner can have more than enough data to statistically define the problem, yet still fail because the required computation is intractable.

Results

Our primary result is a theoretical proof based on the Quadratic Residuosity Assumption, a foundational pillar of modern cryptography. We prove that:

  1. No polynomial-time algorithm can achieve better-than-random accuracy on the constructed task.
  2. The "computational statistical distance" between the valid data and random noise is effectively zero for any efficient learner.
  3. A gap exists where a task admits a maximally robust, efficiently computable classifier (given the trapdoor), but finding any non-trivial robust classifier is impossible for a general-purpose learner.

Conclusion and Future Directions

While our results are based on synthetic mathematical distributions rather than natural image datasets, they provide a rigorous proof-of-concept. We demonstrate that computational hardness alone is sufficient to explain the existence of adversarial examples.

The challenge for future research is to determine if "natural" datasets contain structures analogous to cryptographic trapdoors. If the features that define a "cat" or a "dog" are computationally hard to extract in a robust manner, then the struggle for adversarial robustness may be a permanent fixture of machine learning, bounded by the laws of computational complexity rather than the limits of our datasets.

Summary updated

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.
BibTeX
@misc{bubeck2018adversarial,
  author = {Sébastien Bubeck and Yin Tat Lee and Eric Price and Ilya P. Razenshteyn},
  title = {{Adversarial Examples from Cryptographic Pseudo-Random Generators}},
  year = {2018},
  eprint = {1811.06418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.06418},
}
Figure