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

Questo lavoro propone il primo schema di hashing che preserva le proprietà per predicati di distanza $\ell_1$, offrendo una soluzione efficiente e robusta per rilevare immagini simili anche in presenza di attacchi avversariali che tentano di eludere i sistemi di hashing percettivo tradizionali.

L'essenziale

🕵️‍♂️ Il Problema: Il Finto Gemello Perfetto

Immagina di avere un database di foto segnaletiche (ad esempio, per il controllo alle frontiere o per bloccare immagini illegali online). Il tuo sistema usa un "codice segreto" (un hash) per riconoscere se una foto che arriva è uguale a una di quelle nel database.

Il problema è che gli hacker hanno scoperto un trucco: possono modificare leggermente una foto, in modo che ai nostri occhi umani sembri identica all'originale, ma il codice segreto cambi completamente. È come se un ladro si mettesse una parrucca e un naso finto: per l'occhio umano è lo stesso ladro, ma per il sistema di riconoscimento è una persona diversa. Questo si chiama "attacco avversario".

🛡️ La Soluzione: La "Cassaforte che Capisce la Somiglianza"

Gli autori di questo articolo hanno creato qualcosa di nuovo: una Cassaforte che Preserva le Proprietà (Property-Preserving Hashing o PPH).

Per capire come funziona, immagina due scenari:

1. Il vecchio sistema (Hashing Perceptuale): È come se dessi a un guardiano due foto e gli chiedessi: "Sono uguali?". Il guardiano guarda e dice "Sì" o "No". Ma a volte sbaglia, o peggio, l'hacker può ingannarlo cambiando un solo pixel che il guardiano non nota, ma che cambia il risultato finale.
2. Il nuovo sistema (PPH): Invece di dare le foto al guardiano, le trasformi in due ricette matematiche (polinomi). Il guardiano non vede le foto, ma confronta le ricette. La magia è che questa ricetta è costruita in modo che, se le due foto sono "vicine" (cioè simili), le ricette devono dire che lo sono, con una certezza matematica quasi assoluta.

📏 La Regola del "Distanziometro"

Il cuore della loro invenzione è una nuova regola per misurare la distanza tra due immagini. Non usano la solita regola matematica, ma una chiamata distanza $\ell_1$ asimmetrica.

Facciamo un'analogia con i mattoncini LEGO:

• Immagina due torri di LEGO.
• La distanza normale misura quanti mattoncini devi togliere da entrambe per farle combaciare.
• La loro nuova regola è più intelligente: misura quanto devi aggiungere alla torre A per arrivare alla torre B, e quanto devi aggiungere alla torre B per arrivare alla torre A.

Se la somma di questi "aggiunte" è piccola, allora le torri sono simili. Se un hacker prova a cambiare la torre A per ingannare il sistema, deve aggiungere così tanti mattoncini che la torre diventa orribile e irriconoscibile. Non può fare piccoli aggiustamenti invisibili.

🧙‍♂️ La Magia Matematica (Senza la Formula)

Come fanno a trasformare un'immagine in una ricetta matematica?

1. Prendono ogni pixel dell'immagine (ogni piccolo quadratino di colore).
2. Lo trasformano in un numero speciale.
3. Moltiplicano questi numeri tra loro in un modo molto specifico per creare un polinomio (una lunga equazione matematica).
4. Questo polinomio è la "firma" dell'immagine.

Il bello è che per confrontare due immagini, non serve guardare i pixel. Basta fare un calcolo matematico veloce tra le due "firme". Se il calcolo dice "Sì, sono simili", allora lo sono davvero. Se dice "No", allora sono diverse.

⚡ Perché è Veloce e Utile?

• Velocità: Anche se sembra complicato, il sistema è velocissimo. Per un'immagine grande, dividono il lavoro in piccoli pezzi (come dividere un puzzle in sezioni) e li calcolano tutti insieme. Su un computer moderno, ci vogliono meno di un secondo.
• Privacy: Il server che controlla le immagini non vede mai la foto vera! Vede solo la "ricetta matematica". Quindi, anche se un hacker ruba il database delle ricette, non può ricostruire le foto originali.
• Sicurezza: Gli autori hanno provato a ingannare il sistema con attacchi intelligenti (aggiungendo rumore alle immagini). Risultato? Per ingannare il sistema, l'hacker deve rovinare così tanto l'immagine che diventa inutile (diventa una macchia di colori). Quindi, l'attacco fallisce.

🎯 In Sintesi

Gli autori hanno inventato un nuovo modo di "fingerprintare" le immagini che è:

1. Imbattibile contro i trucchi degli hacker (non puoi ingannarlo con piccoli cambiamenti).
2. Privato (nessuno vede la foto, solo il codice).
3. Veloce (funziona in tempo reale).

È come avere un guardiano che non si fa ingannare dalle parrucche e dai trucco, ma che guarda direttamente l'osso del cranio per riconoscere chi sei, e lo fa senza mai toccare il tuo viso.

Sommario tecnico

1. Il Problema

Il paper affronta la vulnerabilità degli attuali sistemi di hashing percettivo (Perceptual Hashing) utilizzati per rilevare immagini simili (es. per il controllo dei contenuti illegali o il riconoscimento facciale) di fronte ad attacchi avversariali.

• Contesto: L'hashing percettivo genera hash simili per immagini visivamente simili. Tuttavia, la sua correttezza è probabilistica, non garantita.
• Minaccia: Gli attaccanti possono applicare piccole perturbazioni impercettibili a un'immagine (attacchi di evasione) per alterare il suo hash percettivo in modo tale che non corrisponda più all'originale, pur mantenendo l'immagine visivamente simile.
• Limitazione attuale: Le funzioni di hashing esistenti non offrono garanzie di correttezza "trascurabili" (negligible). Esistono limiti teorici che impediscono di rendere l'errore di correttezza sufficientemente piccolo per prevenire questi attacchi senza compromettere l'utilità del sistema.
• Obiettivo: Sviluppare un meccanismo che preservi una proprietà specifica (la distanza tra le immagini) nello spazio degli hash con una garanzia di correttezza quasi assoluta, rendendo inefficaci gli attacchi di evasione che tentano di mantenere la similarità percettiva ma alterare l'hash.

2. Metodologia Proposta

Gli autori propongono la prima costruzione di Property-Preserving Hashing (PPH) per un predicato basato sulla distanza asimmetrica $\ell_1$.

• Definizione del Predicato: Il sistema verifica se due immagini $x$ e $y$ sono simili controllando se le loro distanze $\ell_1$ "unilaterali" sono entro una soglia $t$.

  • Si definisce $x \dot{-} y$ come il vettore con elementi $\max\{x_i - y_i, 0\}$.
  • Il predicato restituisce 1 se $\|y \dot{-} x\|_1 < t_+$ e $\|x \dot{-} y\|_1 \le t_-$.
  • Poiché la distanza $\ell_1$ è strettamente correlata alla distanza $\ell_2$ (Euclidea) usata spesso negli attacchi avversariali, controllare il limite $\ell_1$ permette di controllare anche la similarità percettiva.

• Costruzione Crittografica:

  • Codici Correttori di Errore: La costruzione si basa su codici correttori di errore per la distanza $\ell_1$ (di Tallini e Rose).
  • Polinomi $\sigma$: Ogni immagine $x$ (rappresentata come vettore di pixel) viene mappata in un polinomio $\sigma_x(z)$ su un campo finito $\mathbb{Z}_p$. Il polinomio è definito come $\prod_{i=1}^n (1 - a_i z)^{x_i}$, dove $a_i$ sono coefficienti casuali unici.
  • Hashing: L'hash dell'immagine è la riduzione del polinomio $\sigma_x(z)$ modulo $z^{t+1}$. Questo riduce il polinomio a un vettore di dimensione $t+1$, garantendo compressione.
  • Valutazione (Eval): Per verificare la similarità tra due hash, il server utilizza l'Algoritmo di Euclide Esteso (EEA) per risolvere un'equazione chiave modulo $z^{t+1}$. Se i gradi dei polinomi risultanti soddisfano certi vincoli (legati a $t_+$ e $t_-$), il predicato restituisce 1.

• Gestione della Privacy e Robustezza:

  • Il sistema è progettato per essere robusto contro errori unilaterali (evitare falsi negativi: immagini simili che appaiono diverse).
  • L'errore di falsi positivi (immagini diverse che appaiono simili) è reso trascurabile in pratica scegliendo opportuni parametri.
  • Il server non necessita di conoscere i coefficienti $a$ per eseguire la verifica, riducendo la superficie di attacco.

3. Contributi Chiave

1. Prima Costruzione PPH per $\ell_1$: Introduzione del primo schema di hashing che preserva la proprietà della distanza $\ell_1$ asimmetrica, superando i limiti precedenti che si concentravano solo sulla distanza di Hamming.
2. Garanzia di Correttezza Robusta: Dimostrazione che lo schema è robusto contro gli errori unilaterali, rendendo estremamente difficile per un attaccante generare un'immagine avversaria che sia visivamente simile all'originale ma che fallisca il test di similarità nell'hash.
3. Analisi dei Limiti di Compressione:
   • Sono stati derivati limiti inferiori teorici sulla lunghezza dell'hash (digest) necessaria per preservare la distanza $\ell_1$.
   • Lo schema proposto raggiunge una compressione vicina a questi limiti teorici per valori piccoli di $t$ (tipici nelle applicazioni di immagini), con una dimensione dell'hash di circa $t \log_2 n$.
4. Analisi della Sicurezza:
   • Inversione: È stato dimostrato che invertire l'hash per recuperare l'immagine originale è computazionalmente costoso (complessità esponenziale $O(q^n)$).
   • Collisioni: Trovare collisioni nello spazio delle immagini (due immagini diverse con lo stesso hash) è difficile, sebbene sia possibile nello spazio dei polinomi.
   • Decodifica: È stato dimostrato che la decodifica a lista (syndrome decoding) non è efficiente per la distanza $\ell_1$ a causa dell'enorme dimensione della "palla" $\ell_1$, rendendo l'attacco basato sulla decodifica impraticabile.

4. Risultati Sperimentali

Gli autori hanno implementato lo schema in Python (libreria galois) e testato su dataset come Imagenette (immagini RGB 224x224) e immagini in scala di grigi (28x28).

• Efficienza Computazionale:

  • Per immagini 28x28 (grigi), la valutazione del predicato richiede 0.0784 secondi per una perturbazione dell'1%.
  • Per immagini 224x224 (RGB), dividendo l'immagine in blocchi (es. 1000 blocchi), il tempo di valutazione è di 0.0128 secondi per blocco. L'elaborazione dell'intera immagine è altamente parallelizzabile.
  • La complessità temporale è $O(t^2)$ per la valutazione, molto efficiente per valori di $t$ piccoli.

• Resistenza agli Attacchi Avversariali:

  • Gli autori hanno simulato attacchi FGSM (Fast Gradient Sign Method) e PGD (Projected Gradient Descent).
  • Risultato: Per evadere il rilevamento (ovvero, per far sì che l'hash non corrisponda all'originale pur mantenendo la similarità percettiva), un attaccante è costretto ad aggiungere un rumore significativo.
  • Ad esempio, per superare la soglia di rilevamento con un attacco FGSM, il rumore necessario degrada la qualità dell'immagine (misurata con LPIPS) a livelli inaccettabili per l'occhio umano (LPIPS > 0.5), rendendo l'attacco inutile per scopi pratici.
  • Anche trasformazioni semplici (luminosità, contrasto) richiedono modifiche sostanziali per eludere il sistema, degradando notevolmente l'immagine.

5. Significato e Impatto

• Sicurezza delle Immagini: Questo lavoro fornisce un fondamento teorico e pratico per proteggere i sistemi di rilevamento di immagini (come quelli usati da Microsoft, Meta, Apple per la CSAM o il riconoscimento facciale) dagli attacchi di evasione.
• Privacy: Permette di verificare la similarità tra un'immagine inviata da un utente e un database di riferimento senza rivelare né l'immagine dell'utente né il contenuto del database al server di verifica (Privacy-Preserving).
• Nuova Direzioni: Apre la strada all'uso di PPH per metriche di distanza continue (come $\ell_1$ e $\ell_2$) in contesti crittografici, superando i limiti delle funzioni di hash tradizionali basate sulla distanza di Hamming.
• Scalabilità: La natura parallela dell'algoritmo lo rende adatto per l'implementazione su GPU e per sistemi su larga scala.

In sintesi, il paper dimostra che è possibile costruire schemi di hashing che non solo comprimono i dati e proteggono la privacy, ma offrono anche garanzie matematiche contro la manipolazione avversariale, costringendo gli attaccanti a scegliere tra eludere il rilevamento o distruggere la qualità visiva dell'immagine.