  We propose an intriguingly simple method for the construction of adversarial
images in the black-box setting. In constrast to the white-box scenario,
constructing black-box adversarial images has the additional constraint on
query budget, and efficient attacks remain an open problem to date. With only
the mild assumption of continuous-valued confidence scores, our highly
query-efficient algorithm utilizes the following simple iterative principle: we
randomly sample a vector from a predefined orthonormal basis and either add or
subtract it to the target image. Despite its simplicity, the proposed method
can be used for both untargeted and targeted attacks -- resulting in previously
unprecedented query efficiency in both settings. We demonstrate the efficacy
and efficiency of our algorithm on several real world settings including the
Google Cloud Vision API. We argue that our proposed algorithm should serve as a
strong baseline for future black-box attacks, in particular because it is
extremely fast and its implementation requires less than 20 lines of PyTorch
code.
