Fetching the paper…

Reading the bibliography…

2018

Adversarial Examples from Cryptographic Pseudo-Random Generators

Bubeck, Sébastien, Lee, Yin Tat, Price, Eric et al.

Original
PDF
Post on X

Understand

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.

Adversarial Examples from Cryptographic Pseudo-Random Generators · Around

Built on

Trapdoor pseudo-random number generators, with applications to protocol design
Umesh V Vazirani and Vijay V Vazirani · 1983
Earlier work this paper cites.
A simple unpredictable pseudo-random number generator
Lenore Blum, Manuel Blum, and Mike Shub · 1986
Earlier work this paper cites.

Similar

Computational complexity: a conceptual perspective
Oded Goldreich · 2008
Cited alongside, same era.

Then

Adversarial examples from computational constraints, 2018
Original
Sébastien Bubeck, Eric Price, and Ilya Razenshteyn · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…