Technische Samenvatting: ScoreShield

Probleemstelling

Een groeiend aantal toepassingen, waaronder biometrische verificatie en retrieval-augmented generation (RAG), vertrouwt op cosine similarity-scores die worden berekend tussen vector-embeddings. Deze systemen geven dergelijke similarity-scores vrij (als vectoren voor matching tussen query en collectie of als Gram-matrices voor pairwise analytics) via API's. Het vrijgeven van dergelijke scores kan echter informatie lekken over individuele records, wat membership inference attacks en score-guided hill-climbing attacks mogelijk maakt.

Hoewel differential privacy (DP) een principieel kader biedt voor het verzachten van deze risico's, blijkt de naïeve toepassing van standaard DP-mechanismen—specifiek het toevoegen van onafhankelijke en identiek verdeelde (i.i.d.) Gaussische ruis aan vector-elementen of matrix-elementen—ontoereikend. Deze benadering behandelt cosine-score vectoren en Gram-matrices als onbeperkte Euclidische arrays. Bijgevolg schenden de geperturbeerde outputs vaak de geometrische beperkingen die inherent zijn aan cosine similarities:

1. Vectoren: Scores moeten binnen $[-1, 1]$ liggen.
2. Gram-matrices: De matrix moet symmetrisch, positief semi-definiet (PSD) zijn, eenheid-diagonale elementen hebben (aangezien embeddings een unit-norm hebben) en off-diagonal elementen hebben die begrensd zijn door $[-1, 1]$.

Naïeve Gaussische perturbatie faalt in het behoud van deze beperkingen, wat leidt tot excessieve distortie (lage utility) bij een gegeven privacy-budget. Bovendien is de foutschaling van naïeve mechanismen slecht; voor de volledige release van een pairwise Gram-matrix onder record-level vervanging, schaalt de verwachte gekwadrateerde Frobenius-fout met $\Theta(n^3)$, wat snel degradeert naarmate de galerijgrootte $n$ toeneemt.

Methodologie: ScoreShield

De auteurs stellen ScoreShield voor, een "perturb-then-project" mechanisme ontworpen om similarity scores vrij te geven onder centrale-model $(\varepsilon, \delta)$-differential privacy, terwijl de geometrische haalbaarheid strikt wordt afgedwongen. Het framework opereert in twee regimes:

1. Query-to-Collection Vector Release (Regime i)

In dit regime geeft een curator een geprivatiseerde score-vector $s = Eq$ vrij, die de similarity vertegenwoordigt tussen een publieke query-embedding $q$ en een galerij van $n$ opgeslagen embeddings.

• Mechanisme: De curator berekent de schone score-vector, voegt Gaussische ruis toe gekalibreerd aan de globale $\ell_2$-sensitiviteit ($\Delta_{query} = 2$), en projecteert vervolgens de ruisgevoelige vector op de haalbaarheidsset $C_{query} = [-1, 1]^n$.
• Projectie: De projectie is een eenvoudige coördinaat-gewijze clipping-operatie: $\text{proj}_{C_{query}}(s')_i = \max(-1, \min(1, s'_i))$.
• Privacy: Omdat projectie een deterministische post-processing stap is die onafhankelijk is van de private data, blijft de $(\varepsilon, \delta)$-DP garantie van het Gaussische mechanisme behouden.

2. Full Pairwise Gram Matrix Release (Regime ii)

In dit regime geeft een curator een geprivatiseerde pairwise cosine Gram-matrix $S = EE^\top$ vrij voor niet-interactieve analytics (bijv. clustering, bias auditing).

• Mechanisme: De curator voegt Gaussische ruis toe aan de Gram-matrix, gekalibreerd aan de globale Frobenius-sensitiviteit. Onder record-level adjacency is deze sensitiviteit $\Delta_{full} = 2\sqrt{2(n-1)} = \Theta(\sqrt{n})$.
• Projectie: De ruisgevoelige matrix wordt geprojecteerd op de cosine-Gram haalbaarheidsset $C_{coll}$, gedefinieerd als de verzameling symmetrische, PSD matrices met een eenheid-diagonaal en off-diagonal elementen in $[-1, 1]$.
• Algoritme: Omdat exacte projectie op deze set (de elliptope) computationeel duur is (vereist een Semidefinite Program), gebruiken de auteurs een Fast Averaged Alternating Projection (AAP) algoritme. Dit iterereert tussen het projecteren op de PSD-kegel (via eigenvalue clipping) en het projecteren op de unit-diagonal box (via entry-wise clipping). De auteurs bewijzen R-lineaire convergentie naar haalbaarheid onder gebonden lineaire regulariteit.

Belangrijkste Bijdragen

1. Kwantitatieve verbetering ten opzichte van Naïve Gaussian DP:

   • Voor Gram-matrix release onder record-level adjacency, levert het naïeve Gaussische mechanisme een verwachte gekwadrateerde Frobenius-fout van $\Theta(n^3)$. ScoreShield, gebruikmakend van de geometrie van de haalbaarheidsset, verbetert deze grens naar $O(n^2)$ voor vaste privacy-parameters.
   • Onder output-space (Gram-matrix) adjacency, is de verbetering van $\Theta(n^2)$ naar $O(n^{3/2})$.
   • Voor vector release, behoudt ScoreShield de $\Theta(n)$ worst-case schaling van het naïeve mechanisme, maar biedt het constante-factor winsten door de fout op verzadigde coördinaten te verminderen via projectie.

2. Utility garanties voor Decision-Level Metrics (Regime i):

   • Het paper biedt theoretische garanties voor verificatietaken, waarbij de waarschijnlijkheid van decision flips (accept/reject) door ruis wordt gekarakteriseerd.
   • Het bewijst het bestaan en de uniciteit van een threshold re-calibratie die elk bereikbaar operatiepunt (False Positive Rate, True Positive Rate) herstelt dat haalbaar is door de geprivatiseerde scores.
   • Het stelt uniforme stabiliteit voor ROC/AUC vast, waarbij wordt aangetoond dat de afwijking onder Lipschitz score CDF's maximaal $O(\sigma)$ is, wat first-order tight is.

3. Schaalbare Projectie met Convergentie Garanties:

   • De auteurs introduceren een schaalbare AAP-solver voor het afdwingen van cosine constraints op grote Gram-matrices.
   • Ze leveren theoretische bewijzen voor de R-lineaire convergentie van deze solver naar de haalbaarheidsset, wat praktische toepasbaarheid garandeert voor grootschalige releases waar exacte SDP-projectie onuitvoerbaar is.

4. Uitgebreide Evaluatie:

   • Regime (i): Geëvalueerd op Face Recognition (met behulp van LFW, IJB-B/C, en andere benchmarks) en DP-RAG (met behulp van de FRAMES benchmark). Resultaten laten zien dat ScoreShield de decision-level utility (verificatie nauwkeurigheid, TAR) aanzienlijk beter behoudt dan naïeve Gaussische ruis, vooral bij strikte operatiepunten.
   • Regime (ii): Geëvalueerd op beeld-gelijkenis (CIFAR-10/100, Oxford-IIIT Pets), semantische tekstuele gelijkenis (STS-B), en aanbevelingssystemen (MovieLens-100K). De geprojecteerde Gram-matrices presteren consequent beter dan ongeprojecteerde ruisgevoelige matrices in downstream taken zoals clustering (NMI), retrieval (Recall@1), en collaborative filtering (RMSE).

Betekenis en Claims

Het paper claimt de eerste systematische centrale-model $(\varepsilon, \delta)$-DP analyse van match-score releases in deep face recognition systemen te bieden die de connectie legt tussen threshold recalibration en decision-level garanties. Het adresseert een kritiek gat in de literatuur waar eerder werk zich ofwel richtte op lokale DP (het perturberen van inputs) of cryptografische methoden, waardoor de centrale-model garanties voor vrijgegeven similarity scores grotendeendeels onverkend bleven.

De auteurs positioneren ScoreShield als een algemene, modaliteit-agnostische post-processing wrapper. Door de structurele beperkingen van cosine similarity (PSD, unit-diagonaal, bounded entries) af te dwingen via projectie, bereikt het mechanisme een superieure privacy-utility tradeoff vergeleken met onbeperkte ruis-toevoeging. De resultaten suggereren dat constraint-aware privatisatie een noodzakelijke primitief is voor similarity-gebaseerde systemen om functioneel te blijven terwijl ze rigoureuze privacybescherming bieden tegen membership inference en score-guided attacks.

Het werk is bescheiden in zijn reikwijdte, met de focus op one-shot, niet-interactieve releases onder record-level replacement adjacency. Er wordt expliciet vermeld dat het geen herhaalde adaptieve queries behandelt (die require composition accounting) of de afleiding van instance-optimale ruisdistributies, en laat deze als richtingen voor toekomstig werk open.