  Recent research works have shown that image retrieval models are vulnerable
to adversarial attacks, where slightly modified test inputs could lead to
problematic retrieval results. In this paper, we aim to design a provably
robust image retrieval model which keeps the most important evaluation metric
Recall@1 invariant to adversarial perturbation. We propose the first 1-nearest
neighbor (NN) image retrieval algorithm, RetrievalGuard, which is provably
robust against adversarial perturbations within an $\ell_2$ ball of calculable
radius. The challenge is to design a provably robust algorithm that takes into
consideration the 1-NN search and the high-dimensional nature of the embedding
space. Algorithmically, given a base retrieval model and a query sample, we
build a smoothed retrieval model by carefully analyzing the 1-NN search
procedure in the high-dimensional embedding space. We show that the smoothed
retrieval model has bounded Lipschitz constant and thus the retrieval score is
invariant to $\ell_2$ adversarial perturbations. Experiments on image retrieval
tasks validate the robustness of our RetrievalGuard method.
