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

Cet article propose la première construction de hachage préservant les propriétés pour les prédicats de distance $\ell_1$, offrant une garantie de correction forte contre les attaques par inputs adversariaux tout en maintenant une grande efficacité computationnelle pour la détection d'images similaires.

L'essentiel

Le Problème : Le Camouflage des Faussaires

Imaginez que vous êtes un gardien de musée (le serveur) qui possède une collection précieuse d'images (une base de données). Votre travail est de vérifier si une nouvelle image présentée par un visiteur (le client) est une copie ou une version légèrement modifiée d'une œuvre déjà connue.

Pour protéger la vie privée, le visiteur ne peut pas montrer son image originale. Il doit envoyer une "empreinte digitale" numérique (un hachage). Normalement, si deux images se ressemblent, leurs empreintes doivent aussi se ressembler.

Le problème actuel :
Les "faussaires" (les attaquants) ont trouvé un tour de passe-passe. Ils peuvent modifier une image de manière si subtile que l'œil humain ne voit aucune différence (une image de chat reste un chat), mais ils réussissent à tromper le système de vérification. L'empreinte digitale change complètement, et le gardien pense : "Ce n'est pas la même image !" alors que c'est le cas. C'est ce qu'on appelle une attaque d'évasion.

La Solution : Le "Sceau Magique" (Property-Preserving Hashing)

Les auteurs de ce papier proposent une nouvelle méthode, appelée Hachage Préservant les Propriétés (PPH).

Imaginez que, au lieu d'une simple empreinte digitale, nous utilisions un sceau magique basé sur des mathématiques complexes (des polynômes).

• L'idée clé : Ce sceau ne cache pas l'image, mais il encode une règle mathématique précise : "Si l'image A et l'image B sont très proches l'une de l'autre (à moins de X pixels de différence), alors leurs sceaux magiques diront OUI, peu importe qui les regarde."

Contrairement aux méthodes actuelles qui disent "peut-être que c'est pareil" (avec une petite chance d'erreur), cette nouvelle méthode dit : "C'est mathématiquement impossible de tromper le système sans rendre l'image méconnaissable."

Comment ça marche ? (L'analogie du Puzzle)

1. La Transformation : Chaque image est transformée en un immense puzzle mathématique (un polynôme).
2. La Comparaison : Pour vérifier si deux images sont proches, on ne compare pas les images directement. On utilise une formule magique (l'algorithme d'Euclide étendu) qui compare les pièces du puzzle.
3. Le Résultat :
   • Si les images sont proches (les pièces s'ajustent bien), le système dit "1" (Oui, c'est une similarité).
   • Si les images sont différentes, il dit "0" (Non).

Le génie de cette méthode, c'est qu'elle est robuste. Un faussaire qui essaie de modifier l'image pour tromper le système se heurte à un mur : pour réussir à tromper le sceau magique, il doit modifier l'image autant qu'un peintre qui repeint tout le tableau. L'image devient alors moche et inutilisable.

Pourquoi est-ce important ? (La Guerre des Pixels)

Les chercheurs ont testé leur système contre des attaques connues (comme FGSM et PGD) qui ajoutent du "bruit" invisible aux images.

• Avant : Un faussaire pouvait ajouter un peu de bruit (comme un grain de poussière) et passer à travers.
• Avec ce système : Pour tromper le sceau, le faussaire doit ajouter tellement de bruit que l'image ressemble à un tableau abstrait illisible. La qualité de l'image s'effondre.

C'est comme si vous essayiez de falsifier un billet de banque. Avec les anciennes méthodes, vous pouviez changer une lettre. Avec cette nouvelle méthode, pour changer le résultat de la vérification, vous devriez remplacer tout le papier par du carton, ce qui rend le billet inutile.

Les Résultats Concrets

• Rapidité : Le système est très rapide. Même pour de grandes images, il peut vérifier la similarité en quelques centièmes de seconde.
• Efficacité : Il fonctionne bien sur des images en noir et blanc (comme les chiffres manuscrits) et en couleur (comme les photos de paysages).
• Sécurité : Il empêche les attaques d'évasion tout en gardant les données privées (le serveur ne voit jamais l'image originale, seulement les résultats mathématiques).

En Résumé

Ce papier présente un bouclier mathématique pour les systèmes de reconnaissance d'images. Il rend la tâche des pirates informatiques si difficile que pour tromper le système, ils doivent détruire la qualité de l'image qu'ils veulent protéger. C'est une victoire de la sécurité et de la vie privée, rendue possible par des mathématiques élégantes qui transforment des images en puzzles impossibles à tricher.

Résumé technique

1. Problématique et Contexte

Le problème de la détection d'images similaires :
Dans de nombreuses applications de sécurité (reconnaissance faciale pour le contrôle frontalier, détection d'images illicites dans le cloud), il est nécessaire de vérifier si une image soumise est similaire à une image de référence stockée dans une base de données, sans révéler les images elles-mêmes pour des raisons de confidentialité. La solution traditionnelle est le hachage perceptuel (Perceptual Hashing), qui génère des empreintes numériques similaires pour des images visuellement proches.

La vulnérabilité aux attaques adverses :
Récemment, il a été démontré que les schémas de hachage perceptuel sont vulnérables aux attaques par évasion. Un attaquant peut ajouter un bruit imperceptible à une image (en optimisant une fonction de perte basée sur la distance $\ell_2$) pour créer une image qui semble identique à l'œil humain mais qui produit un hachage totalement différent, échouant ainsi à la détection de similarité.

La limite du hachage perceptuel :
Le hachage perceptuel repose sur des probabilités : deux images similaires produisent le même hachage avec une probabilité élevée, mais cette probabilité n'est pas garantie à 100 % (l'erreur de correction n'est pas négligeable). Cela laisse une marge d'erreur exploitable par les attaquants.

La solution proposée :
Les auteurs proposent d'utiliser le Hachage Préservant les Propriétés (Property-Preserving Hashing - PPH). Contrairement au hachage perceptuel, un PPH garantit que la propriété (ici, la distance entre deux images) est préservée dans l'espace des hachages avec une probabilité d'erreur négligeable. L'objectif est de concevoir le premier PPH pour une prédicat de distance $\ell_1$ asymétrique, rendant les attaques par évasion beaucoup plus coûteuses en termes de qualité d'image.

---

2. Méthodologie et Construction Technique

La proposition centrale de l'article est une construction de PPH basée sur les codes correcteurs d'erreurs pour la distance $\ell_1$ (Tallini et Rose).

A. Définition du Prédicat

Le système utilise une distance $\ell_1$ asymétrique. Pour deux vecteurs $x$ et $y$ (représentant des images), on définit :

• $x \dot{-} y$ : le vecteur dont le $i$-ème élément est $\max(x_i - y_i, 0)$.
• Le prédicat $P_{as}(x, y)$ retourne 1 si $\|y \dot{-} x\|_1 < t_+$ et $\|x \dot{-} y\|_1 \le t_-$, où $t = t_+ + t_-$ est le seuil de similarité.

Cette asymétrie est cruciale car elle correspond à la nature des perturbations adverses (qui modifient les pixels d'une manière spécifique).

B. Construction du Hachage (Algorithme)

La méthode repose sur l'encodage des images sous forme de polynômes sur un corps fini $\mathbb{Z}_p$ (où $p$ est un nombre premier $> n$).

1. Échantillonnage (samp) :

   • On choisit un vecteur aléatoire $a = (a_1, \dots, a_n)$ d'éléments distincts non nuls dans $\mathbb{Z}_p$.
   • Pour une image $x = (x_1, \dots, x_n)$, on construit le polynôme $\sigma_x(z)$ :
     $$\sigma_x(z) = \prod_{i=1}^{n} (1 - a_i z)^{x_i} \pmod{z^{t+1}}$$
   • Le hachage $h(x)$ est la représentation vectorielle de ce polynôme réduit modulo $z^{t+1}$. La taille du hachage est $m \approx t \log_2 n$.

2. Évaluation (evalh) :

   • Pour vérifier la similarité entre $x$ (stocké sous forme de $\sigma_x^{-1}$) et $y$ (haché en $\sigma_y$), le serveur calcule :
     $$\tilde{\sigma}_{x,y}(z) = \sigma_x^{-1}(z) \cdot \sigma_y(z) \pmod{z^{t+1}}$$
   • Il utilise ensuite l'Algorithme d'Euclide Étendu (EEA) sur les polynômes $\tilde{\sigma}_{x,y}$ et $z^{t+1}$.
   • L'algorithme s'arrête lorsqu'un reste $r_k$ satisfait $\deg(r_k) < t_+$ et $\deg(r_{k-1}) \ge t_+$.
   • Si le degré du polynôme associé $u_k$ satisfait $\deg(u_k) \le t_- - \delta$ (où $\delta$ est un paramètre de sécurité), alors le prédicat retourne 1 (images similaires).

C. Sécurité et Robustesse

• Robustesse (RPPH) : Le schéma est robuste contre les erreurs d'un seul côté (le cas où le prédicat est 1 mais l'évaluation donne 0). Cela empêche les attaques par évasion.
• Résistance aux collisions : Bien que des collisions soient théoriquement possibles dans l'espace des polynômes, trouver une image réelle $y$ qui correspond à un polynôme collision est computationnellement coûteux (complexité exponentielle en fonction de la taille de l'image).
• Compression : La taille du hachage est $O(t \log n)$, ce qui offre une compression significative par rapport à la taille brute de l'image ($n \log q$) lorsque le seuil $t$ est petit.

---

3. Contributions Clés

1. Première construction PPH pour la distance $\ell_1$ : C'est la première fois qu'un PPH est construit pour une prédicat de distance $\ell_1$ (et non seulement pour la distance de Hamming).
2. Protection contre les attaques adverses : En liant la similarité à une distance $\ell_1$ avec une garantie de correction négligeable, l'attaquant est forcé d'ajouter un bruit important pour contourner la détection, ce qui dégrade considérablement la qualité visuelle de l'image (mesurée par LPIPS).
3. Bornes théoriques de compression : Les auteurs établissent des bornes inférieures sur la taille du hachage nécessaire pour préserver la distance $\ell_1$, montrant que leur schéma atteint des taux de compression proches de l'optimal pour de petits seuils $t$.
4. Implémentation et analyse d'efficacité : Une implémentation complète en Python (bibliothèque galois) démontrant la viabilité pratique du système.

---

4. Résultats Expérimentaux

Les auteurs ont évalué leur système sur le jeu de données Imagenette (images RGB 224x224) et des images MNIST (28x28).

• Performance Temporelle :

  • Pour des images 28x28 (grayscale), l'évaluation du prédicat prend 0,0784 seconde (pour une perturbation de 1%).
  • Pour des images 224x224 (RGB), en divisant l'image en 1000 blocs (pour parallélisation), le temps par bloc est de 0,0128 seconde (1% de changement) jusqu'à 0,2641 seconde (14% de changement).
  • Le système est hautement parallélisable, permettant une accélération significative sur les GPU.

• Résistance aux Attaques (FGSM et PGD) :

  • Les auteurs ont simulé des attaques par évasion (FGSM et PGD).
  • Pour que l'attaque réussisse (c'est-à-dire que le hachage ne détecte pas la similarité), l'attaquant doit augmenter le paramètre de bruit $\epsilon$ jusqu'à ce que la NAD (Normalized Asymmetric Distance) dépasse le seuil $t$.
  • À ce niveau de bruit, la qualité de l'image chute drastiquement (LPIPS > 0,5), rendant l'image inutilisable ou très visible comme altérée.
  • Par exemple, pour une attaque FGSM, un $\epsilon$ de 0,1 (NAD $\approx$ 1,13) dégrade l'image au point d'être perceptiblement différente, alors que le hachage perceptuel classique échouerait à détecter la similarité avec des perturbations bien plus faibles.

• Transformations d'images :

  • Le système résiste également aux transformations simples (luminosité, contraste) tant que la distance $\ell_1$ asymétrique reste sous le seuil $t$.

---

5. Signification et Impact

Ce travail est significatif pour plusieurs raisons :

1. Sécurité Renforcée : Il comble une lacune majeure dans les systèmes de vérification d'images sensibles, offrant une garantie mathématique (probabilité d'erreur négligeable) là où les méthodes existantes (hachage perceptuel) ne fournissent que des garanties probabilistes faibles.
2. Dissuasion des Attaques : En forçant l'attaquant à introduire un bruit important pour réussir une évasion, le schéma protège non seulement la détection, mais préserve aussi l'intégrité visuelle des images validées.
3. Efficacité Pratique : Malgré la complexité mathématique (polynômes, EEA), l'approche est suffisamment rapide pour être utilisée en temps réel, surtout grâce à la stratégie de découpage en blocs et au parallélisme.
4. Ouverture de nouvelles pistes : L'article ouvre la voie à des recherches sur les PPH pour d'autres métriques (comme la distance Euclidienne $\ell_2$) et sur l'amélioration de la robustesse contre les erreurs des deux côtés (0 et 1).

En conclusion, cette proposition transforme le problème de la détection d'images similaires d'un problème heuristique en un problème cryptographique rigoureux, offrant une défense robuste contre les manipulations adverses tout en préservant la confidentialité des données.