  Adversarial examples are a type of attack on machine learning (ML) systems
which cause misclassification of inputs. Achieving robustness against
adversarial examples is crucial to apply ML in the real world. While most prior
work on adversarial examples is empirical, a recent line of work establishes
fundamental limitations of robust classification based on cryptographic
hardness. Most positive and negative results in this field however assume that
there is a fixed target metric which constrains the adversary, and we argue
that this is often an unrealistic assumption. In this work we study the
limitations of robust classification if the target metric is uncertain.
Concretely, we construct a classification problem, which admits robust
classification by a small classifier if the target metric is known at the time
the model is trained, but for which robust classification is impossible for
small classifiers if the target metric is chosen after the fact. In the
process, we explore a novel connection between hardness of robust
classification and bounded storage model cryptography.
