Perceptual hashing is widely used to detect whether an input image is similar to a reference image with a variety of security applications. Recently, it has been shown to succumb to adversarial input attacks which make small imperceptible changes to the input image yet the hashing algorithm does not detect its similarity to the original image. Property-preserving hashing (PPH) is a recent construct in cryptography, which preserves some property (predicate) of its inputs in the hash domain. Researchers have so far shown constructions of PPH for Hamming distance predicates, e.g., the predicate which outputs \(\varvec{1}\) if two inputs are within Hamming distance \(\varvec{t}\) . A key feature of PPH is its strong correctness guarantee, i.e., the probability that the predicate will not be correctly evaluated in the hash domain is negligible. Motivated by the use case of detecting similar images under adversarial setting, we propose the first PPH construction for an \(\varvec{\ell _1}\) -distance predicate. Roughly, this predicate checks if the two one-sided \(\varvec{\ell _1}\) -distances between two images are within a threshold t. Since many adversarial attacks use \(\varvec{\ell _2}\) -distance (related to \(\varvec{\ell _1}\) -distance) as the objective function to perturb the input image, by appropriately choosing the threshold t, we can force the attacker to add considerable noise to evade detection, and hence significantly deteriorate the image quality. Our proposed scheme is highly efficient, and runs in time \(\varvec{\mathcal {O}(t^2)}\) . For grayscale images of size \(\varvec{28 \times 28}\) , we can evaluate the predicate in \(\varvec{0.0784}\) seconds when pixel values are perturbed by up to \(\varvec{1 \%}\) . For larger RGB images of size \(\varvec{224 \times 224}\) , by dividing the image into \(\varvec{1,000}\) blocks, we achieve times of \(\varvec{0.0128}\) seconds per block for \(\varvec{1 \%}\) change, and up to \(\varvec{0.2641}\) seconds per block for \(\varvec{14\%}\) change. Furthermore, the time to process the entire image can be considerably improved since the scheme is highly parallel.
