Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks

This paper introduces the first property-preserving hashing construction for $\ell_1$-distance predicates, offering a highly efficient and robust method to detect perceptually similar images under adversarial attacks by forcing attackers to introduce significant noise that degrades image quality to evade detection.

The Gist

Imagine you are a security guard at a high-tech art gallery. Your job is to check if a visitor is carrying a painting that matches a "banned" list of images in your database. However, there's a catch: you cannot see the actual paintings. The visitor hands you a sealed, encrypted envelope (the hash), and you must determine if the painting inside is similar to a banned one without ever opening the envelope to see the image itself.

This is the problem of Perceptual Hashing. Traditionally, guards used a "fingerprint" system. If two paintings looked alike, their fingerprints were supposed to match. But clever thieves (adversarial attackers) found a way to add invisible "dust" to a painting. To the human eye, it looks the same, but the fingerprint changes completely, tricking the guard into thinking it's a new, safe image.

This paper introduces a new, super-secure system called Property-Preserving Hashing (PPH) to stop these thieves. Here is how it works, explained simply:

1. The Old Way: The "Fuzzy" Fingerprint

Think of old perceptual hashing like a fuzzy photo ID.

• How it worked: If you and your twin took a photo, the system would say, "These look 90% similar, so they are the same person."
• The Flaw: Because it was "fuzzy" (probabilistic), a clever thief could tweak their photo just enough to change the ID number, even though they still looked exactly like their twin. The system would say, "No match!" and let them through.

2. The New Way: The "Mathematical Ruler"

The authors propose a new system based on Property-Preserving Hashing. Instead of a fuzzy ID, imagine giving the guard a magic ruler and a sealed box.

• The Box: Contains a mathematical summary of the image (the hash).
• The Ruler: A special algorithm that can measure the "distance" between two boxes without opening them.
• The Rule: The ruler is programmed to say "MATCH" only if the two images are within a specific distance (like being within 1 inch of each other). If they are even slightly further apart, it says "NO MATCH."

The Magic: This ruler is so precise that it is mathematically impossible for a thief to sneak a tiny change into the image to trick the ruler. If the thief changes the image enough to fool the ruler, the change becomes so huge that the image looks terrible to a human eye.

3. The Secret Sauce: "Asymmetric ℓ1-Distance"

The paper uses a specific type of math called ℓ1-distance. Let's use an analogy of moving furniture.

Imagine you have a room full of boxes (pixels).

• The Attack: A thief wants to move a box from position A to position B.
• The Metric: The "cost" of the attack is how much you have to move the boxes.
• The Twist: The authors realized that moving a box forward (adding noise) is different from moving it backward (removing noise). They created a system that measures these two directions separately (Asymmetric).
  • Analogy: Imagine a bank vault. It's easy to push a heavy rock into the vault (add noise), but very hard to pull it out without leaving a trace. The system checks both directions to ensure the "rock" hasn't been moved enough to hide the fact that it's the same vault.

4. How They Built It: The "Polynomial Puzzle"

To make this ruler work, the authors turned images into polynomials (complex algebraic equations).

• The Process: They took every pixel in an image and turned it into a term in a giant equation.
• The Trick: They used a mathematical tool called the Extended Euclidean Algorithm (think of it as a super-fast puzzle solver). This solver can look at two equations and instantly tell you: "Hey, these two equations are almost the same, they only differ by a tiny bit."
• The Result: If the equations differ by more than the allowed "tiny bit," the system knows the images are different, even if the images themselves are hidden.

5. Why This Matters: Stopping the "Invisible" Attack

In the real world, hackers use Adversarial Attacks. They add tiny, invisible dots of noise to an image to make a self-driving car think a stop sign is a speed limit sign, or to make a face recognition system think a criminal is a celebrity.

• The Old System: The hacker adds a few invisible dots. The hash changes. The system says "Safe." The hacker wins.
• This New System: To trick the new "Mathematical Ruler," the hacker has to move so many pixels that the image becomes unrecognizable (like turning a stop sign into a giant, blurry blob).
  • The Trade-off: The hacker can either hide the image (keep it looking real) OR trick the system. They cannot do both. If they try to trick the system, the image quality crashes.

6. Speed and Efficiency

You might think doing all this math is slow. The authors show that their system is actually very fast.

• They can check a small image in less than a second.
• For big images (like high-definition photos), they chop the image into 1,000 tiny blocks and check them all at the same time (like a team of 1,000 guards checking 1,000 doors simultaneously).

Summary

This paper presents a new way to check if two secret images are similar without revealing what the images are.

• Old Way: "I think these look alike." (Easy to trick).
• New Way: "I mathematically prove these are within a specific distance." (Impossible to trick without ruining the image).

It's like upgrading from a fuzzy guess to a mathematical guarantee, ensuring that if a hacker tries to sneak a fake image past your security, they have to make the image so ugly that no one would want to use it anyway.

Technical Summary

1. Problem Statement

Context: Perceptual hashing is widely used to detect similar images (e.g., for copyright protection, face recognition, or content moderation) by generating compact hash digests that preserve visual similarity.
The Vulnerability: Recent studies show that perceptual hashing is susceptible to adversarial evasion attacks. Attackers can introduce small, imperceptible perturbations to an image (often optimizing for $\ell_2$-distance) such that the resulting image looks identical to a human but produces a completely different hash digest, evading detection.
The Gap: Standard perceptual hashing relies on probabilistic similarity guarantees, meaning there is a non-negligible chance that similar images produce different hashes. This "correctness error" provides the attacker with the necessary slack to craft adversarial examples.
Goal: The authors aim to construct a Property-Preserving Hashing (PPH) scheme specifically for $\ell_1$-distance predicates. Unlike standard hashing, PPH guarantees that if two inputs satisfy a specific property (e.g., distance $\le t$), their hash digests will always evaluate to "true" with negligible error, even in the presence of an adversary who knows the hash function parameters.

2. Methodology

The proposed solution is a novel PPH construction based on asymmetric $\ell_1$-distance and error-correcting codes derived from polynomial algebra.

A. The Predicate

The scheme defines an asymmetric $\ell_1$-distance predicate $P_{as}(x, y)$ for two images (vectors) $x, y \in \mathbb{Z}_q^n$:
$$P_{as}(x, y) = 1 \iff \|y \dot{-} x\|_1 < t_+ \text{ and } \|x \dot{-} y\|_1 \le t_- - \delta$$
Where:

• $x \dot{-} y$ is the element-wise operation $\max\{x_i - y_i, 0\}$.
• $\| \cdot \|_1$ is the standard $\ell_1$ norm.
• $t_+ + t_- = t$ is the total threshold.
• $\delta$ is a small integer parameter to reduce false positives in the non-robust setting.
• This asymmetric definition is crucial because it relates directly to the $\ell_2$-norm (Euclidean distance) used in most adversarial attacks via the inequality $\|x-y\|_2 \le \|x-y\|_1 \le \sqrt{n}\|x-y\|_2$.

B. The Construction (Polynomial Mapping)

The core of the scheme maps an image vector $x$ to a polynomial $\sigma_x(z)$ over a finite field $\mathbb{Z}_p$ (where $p > n$ is a prime):
$$\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i} \pmod{z^{t+1}}$$
Here, $a = (a_1, \dots, a_n)$ is a vector of distinct non-zero elements from $\mathbb{Z}_p$.

Key Mathematical Properties:

1. Key Equation: Based on Tallini and Rose's work, the scheme utilizes the identity:
   $$\sigma_x(z) \cdot \sigma_{y \dot{-} x}(z) = \sigma_y(z) \cdot \sigma_{x \dot{-} y}(z)$$
2. Evaluation Algorithm (evalh): To check if $P_{as}(x, y) = 1$:
   • Compute $\tilde{\sigma}_{x,y}(z) = \sigma_x^{-1}(z) \cdot \sigma_y(z) \pmod{z^{t+1}}$.
   • Run the Extended Euclidean Algorithm (EEA) on inputs $z^{t+1}$ and $\tilde{\sigma}_{x,y}(z)$.
   • Stop when the remainder $r_k(z)$ has degree $\le t_+$.
   • The algorithm outputs 1 if the degree of the corresponding cofactor $u_k(z)$ is $\le t_- - \delta$.
   • This effectively checks if the degrees of the "error" polynomials $\sigma_{y \dot{-} x}$ and $\sigma_{x \dot{-} y}$ are within the thresholds, which corresponds to the $\ell_1$-distance condition.

C. Security Model

• Robustness: The scheme is robust against 1-sided errors (false negatives: $P(x,y)=1$ but evalh returns 0). This is critical for preventing evasion attacks.
• Collision Resistance: While 0-sided errors (false positives) are theoretically possible, the authors show the probability is negligible ($p^{-\delta}$) for practical parameters.
• Inversion Resistance: Recovering the original image $x$ from the hash digest (the polynomial coefficients) requires solving a system of equations that is computationally infeasible ($O(q^n)$) without the secret vector $a$.

3. Key Contributions

1. First PPH for $\ell_1$-Distance: This is the first construction of a Property-Preserving Hash for the asymmetric $\ell_1$-distance predicate. Previous works were limited to Hamming distance.
2. Theoretical Bounds: The authors derive lower bounds on the compression ratio (hash digest size $m$). They show that for small thresholds $t$, their scheme achieves compression close to the theoretical lower bound ($m \approx t \log_2 n$), significantly smaller than the image size ($n \log_2 q$).
3. Feasibility Analysis: They prove that syndrome list decoding (a common technique for Hamming distance PPHs) is not feasible for $\ell_1$-distance because the size of the $\ell_1$-ball grows exponentially, making the list of potential candidates too large. Their polynomial-based approach circumvents this.
4. Adversarial Defense Mechanism: By enforcing a strict $\ell_1$-distance threshold, the scheme forces attackers to introduce noise large enough to violate the threshold to evade detection. This noise inevitably degrades the image quality (increasing LPIPS and pixel change ratios) to a level perceptible to humans, effectively neutralizing "imperceptible" attacks.

4. Experimental Results

The authors implemented the scheme using the Python library galois and tested it on the Imagenette dataset (9,459 RGB images, $224 \times 224$).

• Efficiency:
  • Small Images (28x28): Evaluation time is ~0.078 seconds.
  • Large Images (224x224): By dividing images into 1,000 blocks, evaluation time is ~0.0128 seconds per block (highly parallelizable).
  • Complexity: Hash generation is $O(nt^2)$, and evaluation is $O(t^2)$.
• Adversarial Attack Resistance:
  • Tested against FGSM and PGD attacks.
  • To evade detection (i.e., to make the $\ell_1$-distance exceed the threshold $t$), the attacker must increase the noise parameter $\epsilon$.
  • Result: At the threshold where the attack succeeds in evading the hash, the LPIPS (Learned Perceptual Image Patch Similarity) score rises significantly (e.g., > 0.5), and the pixel change ratio becomes substantial. This means the "evasive" image is no longer perceptually similar to the original, defeating the purpose of the attack.
• Robustness to Transformations: The scheme also resists simple transformations (brightness, contrast) unless the changes are severe enough to alter the $\ell_1$-distance significantly.

5. Significance and Conclusion

• Paradigm Shift: The paper moves beyond probabilistic perceptual hashing to deterministic property preservation with negligible error rates, closing the gap that adversarial attacks exploit.
• Practical Utility: The scheme is efficient enough for real-world deployment (sub-second evaluation) and can be parallelized easily.
• Security Implication: It demonstrates that it is possible to design image verification systems where security (evasion resistance) and utility (image quality) are directly coupled. An attacker cannot hide a malicious modification without making it visually obvious.
• Future Work: The authors note that while the scheme handles asymmetric $\ell_1$-distance robustly, extending this to exact $\ell_1$-distance or Euclidean ($\ell_2$) distance with full robustness remains an open problem. Additionally, proving the scheme is "provably hiding" (indistinguishable from random) is a future goal.

In summary, this work provides a cryptographically sound, efficient, and robust alternative to traditional perceptual hashing, specifically designed to counter the growing threat of adversarial input attacks in image recognition systems.