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

Dit paper introduceert de eerste constructie voor property-preserving hashing (PPH) voor $\ell_1$-afstandspredicaten, een efficiënt cryptografisch hulpmiddel dat perceptuele hashing robuust maakt tegen adversariële aanvallen door de invoer te dwingen tot waarneembare ruis om detectie te ontlopen.

De kern

De "Magische Vergelijkingsmachine" voor Beelden: Hoe we Hackers tegenhouden zonder Beelden te Lezen

Stel je voor dat je een enorme bibliotheek hebt vol met miljoenen foto's. Je wilt weten of een nieuwe foto die iemand aanlevert, al in die bibliotheek staat. Maar er is een groot probleem: je mag de foto's niet zelf zien. Misschien zijn het privéfoto's van reizigers op een vliegveld, of gevoelige beelden in de cloud. Je wilt alleen weten: "Is deze foto een kopie van een van de foto's in mijn lijst?" zonder ooit de foto's zelf te openen.

Vroeger gebruikten we daar een soort "digitale vingerafdruk" voor, genaamd perceptuele hashing. Dit werkt als een snelle samenvatting van een foto. Als twee foto's er hetzelfde uitzien, zouden hun vingerafdrukken ook hetzelfde moeten zijn.

Het Probleem: De Sluwe Hacker
Het probleem is dat hackers deze vingerafdrukken kunnen bedriegen. Ze kunnen een foto zo klein veranderen (bijvoorbeeld een paar pixels hier en daar aanpassen) dat het voor een mens er nog steeds hetzelfde uitziet, maar de computer denkt: "Nee, dit is een heel andere foto!" Dit noemen we een evasion attack (ontwijkingsaanval). De hacker "ontsnapt" aan de detectie.

De Oplossing: Een Nieuw Type "Magische Machine"
De auteurs van dit paper hebben een nieuwe, sterkere oplossing bedacht. Ze noemen het Property-Preserving Hashing (PPH). Laten we dit uitleggen met een analogie.

Stel je voor dat je twee zakken met gekleurde balletjes hebt (de foto's).

• De oude manier: Je telt de balletjes en maakt een lijstje. Als de lijsten verschillen, zijn de zakken verschillend. Maar een hacker kan één balletje veranderen, waardoor de lijst anders wordt, terwijl de zak er voor een mens nog steeds hetzelfde uitziet.
• De nieuwe manier (PPH): Je gebruikt een magische machine die niet kijkt naar de balletjes zelf, maar naar een specifiek eigenschap: "Zijn de zakken binnen een bepaalde afstand van elkaar?"

Deze machine werkt als volgt:

1. Je stopt de foto in de machine.
2. De machine maakt een geheime code (een hash) die de foto niet onthult, maar wel de "afstand" tussen foto's vasthoudt.
3. Je kunt twee codes vergelijken zonder de foto's te zien. Als de codes zeggen dat de foto's "binnen de veilige afstand" liggen, dan zijn ze hetzelfde.

Waarom is dit zo slim? (De "Vuilnisbak"-Analogie)
De kracht van deze nieuwe methode zit in de wiskunde achter de "afstand". De auteurs gebruiken een maatstaf die ze $\ell_1$-afstand noemen.

Stel je voor dat je een hacker bent die probeert een foto te veranderen om te ontsnappen.

• Met de oude methoden kon je een foto een beetje "vies" maken (een beetje ruis toevoegen) en de vingerafdruk veranderde volledig.
• Met deze nieuwe methode is het alsof de machine zegt: "Oké, je mag de foto een beetje vies maken, maar als je meer dan een bepaalde hoeveelheid vuil toevoegt, dan slaat de alarmbel."

Het mooie is: om de alarmbel te ontlopen, moet de hacker de foto zo erg vervormen dat hij voor een mens niet meer herkenbaar is. Het is alsof je probeert een portret te tekenen dat er anders uitziet voor de politie, maar als je te veel verandert, ziet het eruit als een abstract schilderij en niet meer als een mens. De hacker heeft dus een keuze: of hij wordt gedetecteerd, of hij maakt de foto zo lelijk dat het doel (de foto herkennen) mislukt.

Hoe werkt het technisch? (De "Receptuur"-Analogie)
De auteurs gebruiken een slimme wiskundige truc met polynomen (soort recepten met getallen).

• Elke foto wordt omgezet in een heel complex "recept" (een polynoom).
• Als twee foto's bijna hetzelfde zijn, zijn hun recepten bijna identiek.
• De machine gebruikt een slimme rekenmethode (de Extended Euclidean Algorithm) om te checken of twee recepten binnen de toegestane "rekenfout" liggen.
• Dit is zo snel dat het zelfs op grote foto's werkt, en het kan worden opgedeeld in stukjes (zoals blokken) om nog sneller te zijn.

De Resultaten in het Dagelijkse Leven
De auteurs hebben dit getest met echte foto's:

• Voor kleine foto's (zoals die van gezichten) duurt het slechts een fractie van een seconde.
• Voor grote foto's (zoals die van sociale media) kunnen ze de foto in duizenden blokjes verdelen en tegelijkertijd controleren.
• Ze hebben getest of hackers het konden omzeilen. Het resultaat? Om de machine te bedriegen, moesten ze de foto's zo erg veranderen dat ze eruit zagen als vage, onherkenbare vlekken. De kwaliteit van de foto ging zo hard achteruit dat de aanval zinloos werd.

Conclusie
Dit paper introduceert een nieuwe manier om te kijken of beelden op elkaar lijken, zonder de beelden zelf te hoeven zien. Het is als een slimme poortwachter die niet kijkt naar het gezicht van de bezoeker, maar alleen checkt of de bezoeker "ver genoeg weg" staat van een lijst met gezochte criminelen. Als de bezoeker probeert een masker op te zetten om niet herkend te worden, moet hij het masker zo dik opzetten dat hij eruitziet als een monster, waardoor hij toch wordt geweigerd.

Het is een veilige, snelle en slimme manier om privacy te beschermen terwijl we toch veilig kunnen zoeken naar verdachte beelden.

Technische samenvatting

Probleemstelling

Perceptuele hashing wordt veel gebruikt om te detecteren of een invoerbeeld vergelijkbaar is met een referentiebeeld, met toepassingen in beveiliging (zoals gezichtsherkenning en het detecteren van illegale inhoud). Echter, recente studies hebben aangetoond dat perceptuele hashing kwetsbaar is voor adversariële invoeraanvallen. Bij deze aanvallen worden kleine, voor het menselijk oog onmerkbare wijzigingen aangebracht in een afbeelding om de hash-waarde zodanig te veranderen dat de oorspronkelijke gelijkenis niet meer wordt gedetecteerd, terwijl de afbeelding visueel nog steeds hetzelfde blijft.

De kern van het probleem is dat perceptuele hashing (en algemene Locality Sensitive Hashing - LSH) geen verwaarloosbare correctiefout garandeert. De kans dat twee visueel vergelijkbare afbeeldingen verschillende hashes produceren is niet verwaarloosbaar klein, wat ruimte biedt voor aanvallers om de hash te manipuleren.

Methodologie

De auteurs stellen een oplossing voor op basis van Property-Preserving Hashing (PPH). In tegenstelling tot traditionele hashing, behoudt PPH een specifieke eigenschap (predikaat) van de invoer in het hash-domein.

1. Predikaat: Het artikel introduceert het eerste PPH-construkt voor een asymmetrisch $\ell_1$-afstandspredikaat. Dit predikaat controleert of de twee eenzijdige $\ell_1$-afstanden tussen twee afbeeldingen $x$ en $y$ binnen een drempelwaarde $t$ liggen.

   • De afstand wordt gedefinieerd via een eenzijdige aftrekking: $x \dot{-} y = \max\{x_i - y_i, 0\}$.
   • Het predikaat geeft '1' terug als zowel $\|x \dot{-} y\|_1 < t_+$ als $\|y \dot{-} x\|_1 \leq t_-$ (waarbij $t = t_+ + t_-$).

2. Cryptografische Constructie:

   • De methode is gebaseerd op $\ell_1$-foutcorrigerende codes van Tallini en Rose.
   • Elke afbeelding (vector) wordt omgezet in een $\sigma$-polynoom over een eindig veld $\mathbb{Z}_p$.
   • De hash van een afbeelding $x$ is de polynoom $\sigma_x(z) = \prod_{i=1}^n (1 - a_i z)^{x_i} \pmod{z^{t+1}}$, waarbij $a_i$ unieke, willekeurige coëfficiënten zijn.
   • Om de predikaat te evalueren, gebruikt de server de Extended Euclidean Algorithm (EEA) om te bepalen of de graden van de polynomen die de verschilvectoren voorstellen binnen de drempel $t$ vallen.

3. Veiligheidseigenschappen:

   • Correctheid: De methode garandeert dat als het predikaat waar is in de originele ruimte, het ook waar is in de hash-ruimte (met verwaarloosbare foutkans).
   • Robuustheid: Het systeem is robuust tegen "one-sided errors" (waar het predikaat waar is maar de hash-evaluatie fout). Dit voorkomt dat aanvallers via kleine wijzigingen de detectie omzeilen.
   • Privacy: De hash digest is een compressie van de afbeelding, en het is computatief moeilijk om de originele afbeelding te reconstrueren uit de hash (inversie-aanval) of om botsingen te vinden.

Belangrijkste Bijdragen

• Eerste PPH voor $\ell_1$-afstand: Het is de eerste constructie van een Property-Preserving Hash voor een asymmetrisch $\ell_1$-afstandspredikaat voor vectoren met elementen uit $\{0, 1, \dots, q-1\}$.
• Wiskundige Onderbouwing: De auteurs bewijzen ondergrenzen voor de compressie (de lengte van de hash digest) die nodig is om $\ell_1$-afstanden te behouden. Ze tonen aan dat hun schema dicht in de buurt komt van deze theoretische ondergrenzen voor kleine drempelwaarden.
• Analyse van Adversariële Aanvallen: Ze tonen aan dat omdat veel adversariële aanvallen (zoals FGSM en PGD) gebruikmaken van $\ell_2$-afstand (gerelateerd aan $\ell_1$) als objectief, het instellen van een juiste drempelwaarde $t$ de aanvaller dwingt om aanzienlijke ruis toe te voegen om de detectie te omzeilen. Dit resulteert in een merkbare verslechtering van de beeldkwaliteit.
• Efficiëntie: Het schema is zeer efficiënt en draait in tijd $O(t^2)$ voor de evaluatie.

Resultaten en Experimenten

De auteurs hebben hun schema geïmplementeerd in Python (met de bibliotheek galois) en getest op het Imagenette-dataset (RGB-afbeeldingen van 224x224) en MNIST-achtige grijstinten (28x28).

• Prestaties:
  • Voor grijstinten van 28x28 wordt het predikaat geëvalueerd in 0,0784 seconden bij een pixelverandering van 1%.
  • Voor RGB-afbeeldingen van 224x224, verdeeld in 1.000 blokken, is de evaluatietijd 0,0128 seconden per blok (voor 1% verandering).
  • Het schema is hoogst paralleliseerbaar, wat de totale verwerkingstijd voor grote afbeeldingen aanzienlijk kan verkorten.
• Effectiviteit tegen Aanvallen:
  • Bij toepassing van FGSM en PGD-aanvallen bleek dat om de detectie te omzeilen (d.w.z. de hash te laten falen), de aanvaller een Normalized Asymmetric Distance (NAD) moet bereiken die leidt tot een significante daling van de beeldkwaliteit (gemeten via LPIPS).
  • Bijvoorbeeld, bij een NAD van 1,12 (wat overeenkomt met een drempel $t$ die de aanvallen zou moeten detecteren), daalt de LPIPS (een maat voor perceptuele gelijkenis) naar 0,57, wat betekent dat het beeld visueel sterk vervormd is.
• Compressie: De hash-digests zijn aanzienlijk kleiner dan de originele afbeeldingen, vooral bij kleine drempelwaarden $t$.

Betekenis en Conclusie

Dit werk biedt een fundamentele doorbraak in de beveiliging van perceptuele hashing-systemen. Door over te stappen van probabilistische perceptuele hashing naar Property-Preserving Hashing met een wiskundig bewezen correctheidsgarantie, wordt het mogelijk om adversariële aanvallen effectief te detecteren zonder dat de beveiliging afhankelijk is van de "geluk" van een hash-kolliisie.

De methologie maakt het mogelijk om in privacy-bewuste omgevingen (waar de originele afbeeldingen en databases niet onthuld mogen worden) te controleren of een afbeelding binnen een bepaalde veiligheidsdrempel valt. De belangrijkste implicatie is dat een aanvaller nu gedwongen wordt om een ruil te maken tussen het omzeilen van de detectie en het behoud van de beeldkwaliteit: om de hash te manipuleren, moet de afbeelding zo sterk worden vervormd dat deze niet meer bruikbaar is voor zijn beoogde doel. Dit maakt het systeem zeer geschikt voor toepassingen zoals grenscontrole, cloud-opslag van gevoelige afbeeldingen en detectie van schadelijke inhoud.