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

Diese Arbeit stellt den ersten property-preserving Hashing-Ansatz für $\ell_1$-Distanzprädikate vor, der es ermöglicht, Bilder auch unter adversariellen Angriffen zuverlässig zu erkennen und dabei gleichzeitig die Bildqualität durch die Erzwungung signifikanter Rauschzugaben bei Angriffen zu erhalten.

Das Wesentliche

Das große Problem: Der "unsichtbare Tarnkappen-Angriff"

Stellen Sie sich vor, Sie haben eine riesige Bibliothek mit Millionen von Fotos (z. B. Gesichter von Passagieren oder verbotene Bilder). Sie wollen prüfen, ob ein neues Foto, das jemand hochlädt, in dieser Bibliothek existiert.

Das Problem ist: Sie wollen keine privaten Daten austauschen. Der Server soll das Foto nicht sehen, und der Nutzer soll die Datenbank nicht kennen. Die Lösung war bisher "Perzeptuelles Hashing" (eine Art digitaler Fingerabdruck für Bilder).

Aber hier kommt der Trick: Hacker haben herausgefunden, wie man ein Bild so manipuliert, dass es für das menschliche Auge genau gleich aussieht, aber für den Computer einen völlig anderen Fingerabdruck hat.

• Die Analogie: Stellen Sie sich vor, Sie tragen eine Maske, die so perfekt ist, dass Sie wie Ihr Bruder aussehen. Der Wachmann (der Computer) sieht Sie und denkt: "Das ist nicht mein Bruder, das ist ein Fremder!" und lässt Sie durch. Der Wachmann hat den "Fingerabdruck" nicht erkannt, obwohl Sie eigentlich derselbe Mensch sind. Das nennt man einen Evasion-Angriff (Ausweichangriff).

Die neue Lösung: Der "Wahrheitsbewahrer" (Property-Preserving Hashing)

Die Autoren dieses Papiers haben eine neue Art von "Fingerabdruck" entwickelt, die wir PPH nennen.

Wie funktioniert das?
Statt nur zu fragen: "Sind diese beiden Bilder identisch?", fragt das neue System: "Sind diese beiden Bilder nahe genug beieinander?"

• Der Vergleich: Stellen Sie sich vor, Sie haben zwei Kugeln.
  • Altes System: Es fragt: "Sind die Kugeln exakt am selben Ort?" (Wenn ja, OK. Wenn nein, auch wenn sie nur 1 Millimeter daneben sind, wird es als "falsch" markiert). Hacker nutzen diese kleine Lücke aus.
  • Neues System (PPH): Es fragt: "Liegen die Kugeln innerhalb eines bestimmten Radius?" (z. B. innerhalb von 10 Zentimetern). Wenn ja, sagt das System: "Ja, das ist ein Treffer!"

Das Geniale daran: Das System ist mathematisch so gebaut, dass es unmöglich ist, die Kugel so zu verschieben, dass sie immer noch innerhalb des Radius liegt, aber das System sagt "Nein". Der Hacker kann die Kugel nicht bewegen, ohne dass das System es merkt.

Wie machen sie das? (Die Magie der Polynome)

Um das zu erreichen, nutzen die Forscher eine clevere mathematische Methode, die auf Polynomen (komplizierte mathematische Formeln) basiert.

1. Das Bild als Formel: Jedes Bild wird in eine riesige mathematische Formel (ein Polynom) umgewandelt.
2. Der "Abstand"-Check: Anstatt die Bilder direkt zu vergleichen, vergleicht das System diese Formeln. Es nutzt einen Algorithmus (den erweiterten euklidischen Algorithmus), der wie ein hochpräzises Lineal funktioniert.
3. Die Regel: Wenn die Formeln des neuen Bildes und des gespeicherten Bildes "nahe genug" sind (innerhalb einer bestimmten Toleranzgrenze $t$), dann sagt das System: "Das ist dasselbe Bild!"

Warum ist das sicher?
Die Forscher haben gezeigt, dass ein Hacker, der versucht, das Bild zu manipulieren, um den "Fingerabdruck" zu täuschen, gezwungen ist, das Bild so stark zu verändern, dass es für das menschliche Auge unwiedererkennbar wird.

• Die Metapher: Wenn Sie versuchen, den Fingerabdruck zu täuschen, müssen Sie so viel "Rauschen" (Störung) hinzufügen, dass das Bild wie ein abstraktes Gemälde aussieht. Der Hacker kann nicht gewinnen: Entweder er wird erkannt, oder er zerstört das Bild.

Die Ergebnisse in der Praxis

Die Autoren haben das System getestet:

• Geschwindigkeit: Es ist sehr schnell. Ein Bild kann in Bruchteilen einer Sekunde geprüft werden.
• Größe: Die "Fingerabdrücke" sind klein und sparen Speicherplatz.
• Sicherheit: Selbst wenn Hacker versuchen, das Bild mit bekannten Angriffsmethoden (wie FGSM oder PGD) zu verändern, scheitern sie. Um den Schutz zu umgehen, müssten sie das Bild so stark verzerren, dass es unbrauchbar wäre.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie wollen in ein geheimes Club-Event.

• Früher: Sie zeigten Ihren Ausweis. Ein Hacker konnte einen Ausweis fälschen, der fast genauso aussah, aber einen winzigen Fehler hatte, den der Scanner übersehen hat.
• Heute (mit dieser neuen Technik): Der Scanner prüft nicht nur den Ausweis, sondern misst, wie "ähnlich" Sie dem echten Inhaber sind. Wenn Sie versuchen, sich zu verstellen, um den Scanner zu täuschen, müssen Sie sich so sehr verstellen (z. B. eine Maske aufsetzen, die Ihnen das Gesicht verdeckt), dass Sie sofort als "falsch" erkannt werden.

Dieses neue System ist wie ein mathematischer Sicherheitsgürtel, der sicherstellt, dass man Bilder nicht manipulieren kann, ohne dass es sofort auffällt – und das, ohne dass die privaten Daten jemals den Server verlassen müssen.

Technische Zusammenfassung

1. Problemstellung und Motivation

Hintergrund:
Perzeptuelles Hashing (Perceptual Hashing) wird häufig verwendet, um zu prüfen, ob ein Bild einem Referenzbild in einer Datenbank ähnlich ist, ohne die Bilder selbst offenzulegen (z. B. für Gesichtserkennung oder das Filtern von illegalen Inhalten). Im Gegensatz zu kryptografischen Hash-Funktionen erzeugen perzeptuelle Hashes ähnliche Ausgaben für visuell ähnliche Bilder.

Das Problem:
Perzeptuelle Hashing-Verfahren sind anfällig für adversarielle Angriffe (Evasion Attacks). Angreifer können kleine, für das menschliche Auge kaum wahrnehmbare Störungen (Perturbationen) in ein Bild einfügen, die den Hash-Wert drastisch verändern, sodass das Bild nicht mehr als ähnlich erkannt wird, obwohl es visuell fast identisch ist. Der Grund liegt darin, dass herkömmliche perzeptuelle Hashes keine strenge Korrektheitsgarantie haben; die Wahrscheinlichkeit, dass zwei ähnliche Bilder denselben Hash erzeugen, ist zwar hoch, aber nicht vernachlässigbar (negligible). Dies lässt Raum für Angriffe.

Ziel:
Die Autoren zielen darauf ab, ein Property-Preserving Hashing (PPH)-System zu entwickeln. Ein PPH bewahrt eine bestimmte Eigenschaft (Prädikat) der Eingabedaten im Hash-Bereich bei. Das Ziel ist es, ein Prädikat zu definieren, das prüft, ob der Abstand zwischen zwei Bildern einen Schwellenwert $t$ unterschreitet, mit einer vernachlässigbaren Fehlerwahrscheinlichkeit. Dies soll verhindern, dass Angreifer Bilder manipulieren können, ohne dass dies im Hash-Bereich erkannt wird, ohne dabei die Bildqualität stark zu beeinträchtigen.

2. Methodik und Konstruktion

Die Autoren schlagen den ersten PPH-Entwurf für ein asymmetrisches $\ell_1$-Distanz-Prädikat vor.

Das Prädikat:
Gegeben zwei Vektoren $x$ und $y$ (Bilder), wird das Prädikat $P(x, y)$ auf 1 gesetzt, wenn beide einseitigen $\ell_1$-Distanzen unter einem Schwellenwert liegen:
$$\|y \dot{-} x\|_1 < t_+ \quad \text{und} \quad \|x \dot{-} y\|_1 \le t_-$$
Dabei ist $y \dot{-} x$ der Vektor mit den Elementen $\max(y_i - x_i, 0)$. Dies ist eng mit der $\ell_2$-Distanz (Euklidische Distanz) verknüpft, die häufig als Zielfunktion für adversarielle Angriffe dient. Da $\ell_1$ und $\ell_2$ durch Ungleichungen verbunden sind ($\|v\|_2 \le \|v\|_1 \le \sqrt{n}\|v\|_2$), kann ein Schwellenwert für $\ell_1$ so gewählt werden, dass ein Angreifer gezwungen ist, erhebliches Rauschen hinzuzufügen, um die Erkennung zu umgehen, was die Bildqualität stark verschlechtert.

Kryptografische Konstruktion:
Die Lösung basiert auf $\ell_1$-Fehlerkorrigierenden Codes von Tallini und Rose.

1. Polynom-Darstellung: Jedes Bild $x$ wird in ein Polynom $\sigma_x(z)$ über einem endlichen Körper $\mathbb{Z}_p$ (wobei $p > n$ eine Primzahl ist) umgewandelt:
   $$\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i}$$
   Hierbei sind $a_i$ zufällige, eindeutige Koeffizienten und $x_i$ die Pixelwerte.
2. Hashing: Der Hash-Wert $h(x)$ ist das Polynom $\sigma_x(z)$ modulo $z^{t+1}$. Dies reduziert den Grad des Polynoms auf $t$.
3. Auswertung (Evaluation): Um zu prüfen, ob zwei Bilder ähnlich sind, nutzt der Server den inversen Hash des Referenzbildes ($\sigma_x^{-1}$) und den Hash des Eingabebildes ($\sigma_y$).
   • Es wird berechnet: $\tilde{\sigma}_{x,y}(z) = \sigma_x^{-1}(z) \cdot \sigma_y(z) \pmod{z^{t+1}}$.
   • Mithilfe des Erweiterten Euklidischen Algorithmus (EEA) wird versucht, die Gleichung $\alpha(z) \equiv \beta(z) \cdot \tilde{\sigma}_{x,y}(z) \pmod{z^{t+1}}$ zu lösen, wobei die Grade von $\alpha$ und $\beta$ die Schwellenwerte $t_+$ und $t_-$ nicht überschreiten dürfen.
   • Wenn eine solche Lösung existiert, ist das Prädikat erfüllt (Ausgabe 1).

Sicherheitseigenschaften:

• Robustheit gegen Evasion: Das System ist robust gegen einseitige Fehler (wenn das Prädikat 1 ist, aber der Hash 0 ausgibt). Dies verhindert, dass Angreifer Bilder manipulieren, die eigentlich als ähnlich gelten sollten.
• Kollisionsresistenz: Die Wahrscheinlichkeit, dass zwei völlig verschiedene Bilder denselben Hash erzeugen (Kollision), ist in der Praxis extrem gering, da dies das Lösen eines komplexen algebraischen Problems erfordert.
• Kompression: Die Hash-Länge beträgt ca. $t \log_2 n$, was bei kleinen Schwellenwerten $t$ eine signifikante Kompression gegenüber der Originalbildgröße ($n \log_2 q$) ermöglicht.

3. Wichtige Beiträge

1. Erster PPH für $\ell_1$-Distanz: Die Autoren stellen den ersten Property-Preserving Hash für das asymmetrische $\ell_1$-Distanz-Prädikat vor. Bisherige Arbeiten konzentrierten sich fast ausschließlich auf Hamming-Distanzen.
2. Theoretische Grenzen: Sie leiten untere Schranken für die Kompression (Hash-Länge) ab und zeigen, dass ihre Konstruktion für kleine $t$ nahe an diesen theoretischen Grenzen liegt.
3. Analyse der List-Decoding-Fähigkeit: Sie beweisen, dass eine effiziente List-Decoding (wie bei Hamming-Distanzen) für $\ell_1$-Distanzen aufgrund der enormen Größe des $\ell_1$-Balls nicht praktikabel ist, und entwickeln daher einen direkten Evaluationsansatz.
4. Implementierung und Performance: Sie implementieren das Schema in Python (Bibliothek galois) und zeigen, dass es effizient ist. Die Auswertung läuft in $O(t^2)$ Zeit.
5. Anwendung auf Adversarielle Angriffe: Sie demonstrieren, wie das Schema FGSM- und PGD-Angriffe sowie einfache Bildtransformationen (Helligkeit, Kontrast) erkennt, indem sie die erforderliche Rauschmenge für eine Umgehung quantifizieren.

4. Ergebnisse und Experimente

Die Autoren testeten ihr System am Imagenette-Datensatz (9.459 RGB-Bilder, 224x224 Pixel).

• Schwellenwert-Optimierung: Ein Schwellenwert $t \approx 0.008qn$ führt zu 0% False Positives auf dem Datensatz.
• Widerstandsfähigkeit gegen Angriffe:
  • Bei FGSM-Angriffen führt ein $t$, das eine Erkennung garantiert, dazu, dass die Bildqualität (gemessen via LPIPS) stark sinkt (z. B. LPIPS > 0.5 bei einem Pixeländerungsanteil von ~1%).
  • Ähnliche Ergebnisse wurden für PGD und Helligkeits-/Kontrastanpassungen erzielt. Um die Erkennung zu umgehen, müsste der Angreifer das Bild so stark verzerren, dass es für Menschen nicht mehr als das Original erkennbar ist.
• Laufzeit:
  • Für kleine Graustufenbilder (28x28): Hash-Erstellung in ~0.26s, Auswertung in ~0.08s.
  • Für große RGB-Bilder (224x224): Durch Aufteilung in 1.000 Blöcke kann die Auswertung pro Block in ~0.013s erfolgen (insgesamt ~13s pro Bild, aber stark parallelisierbar).
• Hash-Größe: Die Hash-Digests sind deutlich kleiner als die Originalbilder, bieten aber dennoch die notwendige Sicherheit.

5. Bedeutung und Fazit

Signifikanz:
Dieses Paper adressiert eine kritische Schwachstelle in der Sicherheit von Bilderkennungssystemen: die Anfälligkeit von Perzeptuellen Hashes gegenüber adversariellen Angriffen. Durch die Einführung von Property-Preserving Hashing mit strengen mathematischen Garantien (vernachlässigbare Fehlerwahrscheinlichkeit) wird es Angreifern praktisch unmöglich gemacht, Bilder zu manipulieren, ohne dass dies erkannt wird oder die Bildqualität unakzeptabel leidet.

Zukünftige Arbeiten:
Die Autoren sehen Potenzial für weitere Forschung in folgenden Bereichen:

• Entwicklung robuster PPH für exakte $\ell_1$-Distanzen (aktuell nur für asymmetrische).
• Erweiterung auf euklidische ($\ell_2$) Distanz-Prädikate.
• Nachweis der vollständigen „Hiding"-Eigenschaft (Schutz vor Inversion des Hashes).
• Weitere Beschleunigung der Implementierung durch GPU-Nutzung und Parallelisierung.

Zusammenfassend bietet die vorgeschlagene Methode einen vielversprechenden Weg, um die Integrität und Privatsphäre von Bildvergleichen in unsicheren Umgebungen (wie Cloud-Diensten) zu gewährleisten, indem sie die Lücke zwischen theoretischer Kryptographie und praktischer Bildverarbeitung schließt.