🤖 machine learning

ScoreShield: Differentially Private Release of Similarity Scores

The paper introduces ScoreShield, a differentially private mechanism that perturbs and projects similarity scores onto a valid feasibility set to significantly reduce utility loss and improve privacy-utility trade-offs compared to naive noise addition, while providing theoretical guarantees and demonstrating effectiveness across diverse applications like RAG and biometrics.

Original authors: Behrooz Razeghi, Parsa Rahimi

Published 2026-07-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Behrooz Razeghi, Parsa Rahimi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are at a massive, high-tech library where every book, photo, and song has been converted into a secret "fingerprint" made of numbers. These fingerprints are so precise that a computer can instantly tell if two items are twins, cousins, or strangers just by comparing them. This is how modern technology works, from unlocking your phone with your face to finding the perfect song in a playlist or even helping AI chatbots find the right facts to answer your questions. But here's the catch: these fingerprints are like a master key. If someone steals the list of how similar everything is to everything else, they can figure out exactly who is in the library, even if they never saw the original photos or heard the songs. It's like knowing the exact distance between every house in a neighborhood; you can map out who lives next to whom and potentially guess who lives in a specific house you're curious about.

To stop this, scientists use a clever trick called "differential privacy." Think of it like adding a little bit of static noise to a radio signal. You want the music (the useful information) to come through clearly, but you add just enough static so that if someone tries to listen in, they can't tell exactly which song is playing or who is singing. The problem is, if you add too much static, the music becomes unrecognizable garbage. If you add too little, the eavesdropper can still hear the lyrics. For a long time, the standard way to add this noise was a bit clumsy: it treated the data like a simple list of numbers, ignoring the fact that these "similarity scores" have strict rules (like, two things can't be more than 100% similar, or a thing must be 100% similar to itself). This clumsy method often ruined the music, making the data too distorted to be useful for ranking search results or verifying identities.

This is where the new paper, ScoreShield, steps in with a smarter solution. The researchers, Behrooz Razeghi and Parsa Rahimi, realized that instead of just dumping noise onto the data and hoping for the best, they should add the noise and then immediately "fix" the result to make sure it follows the rules of similarity. Imagine you are trying to throw a ball into a specific basket, but you have to throw it through a foggy window (the noise). A naive approach would just throw the ball blindly and hope it lands in the basket. ScoreShield is like throwing the ball through the fog, and then, the moment it lands, gently nudging it back into the basket if it rolled slightly outside the lines. This "nudge" is a mathematical projection that ensures the final numbers are still valid similarity scores (between -1 and 1, and mathematically consistent) without undoing the privacy protection.

The paper finds that this "add-noise-then-fix" method is a game-changer. When they tested it on real-world tasks like recognizing faces in photos or helping AI chatbots find the right information, ScoreShield kept the data much more useful than the old, clumsy methods. For example, when releasing a full list of how similar thousands of photos are to each other, the old method made the data so messy that the error grew huge as the number of photos increased. ScoreShield, however, kept the error much smaller and more manageable, even with thousands of items. They proved mathematically that this works for both single checks (like "is this face a match?") and massive lists (like "how do all these faces relate to each other?").

The researchers also showed that this method doesn't just work in theory; it works in practice. They tested it on famous face-recognition datasets and found that even with strong privacy protection, the system could still correctly identify faces and rank search results almost as well as the non-private version. They even built a fast computer algorithm to do the "nudging" quickly, so it doesn't slow things down. In short, ScoreShield proves that you don't have to choose between total privacy and useful data; by respecting the shape of the data, you can have both. It's a way to protect people's secrets without breaking the tools we rely on every day.

Technical Summary: ScoreShield

Problem Statement

A growing number of applications, including biometric verification and retrieval-augmented generation (RAG), rely on cosine similarity scores computed between vector embeddings. These systems often release similarity scores (either as vectors for query-to-collection matching or as Gram matrices for pairwise analytics) via APIs. However, such releases can leak information about individual records, enabling membership inference attacks and score-guided hill-climbing attacks.

While differential privacy (DP) offers a principled framework for mitigating these risks, the naïve application of standard DP mechanisms—specifically adding independent and identically distributed (i.i.d.) Gaussian noise to vector entries or matrix elements—proves inadequate. This approach treats cosine-score vectors and Gram matrices as unconstrained Euclidean arrays. Consequently, the perturbed outputs often violate the geometric constraints inherent to cosine similarities:

Vectors: Scores must lie within $[-1, 1]$ .
Gram Matrices: The matrix must be symmetric, positive semi-definite (PSD), have unit diagonal entries (since embeddings are unit-norm), and off-diagonal entries bounded by $[-1, 1]$ .

Naïve Gaussian perturbation fails to preserve these constraints, leading to excessive distortion (low utility) at a given privacy budget. Furthermore, the error scaling of naïve mechanisms is poor; for full pairwise Gram release under record-level replacement, the expected squared Frobenius error scales as $\Theta(n^3)$ , which degrades rapidly as the gallery size $n$ increases.

Methodology: ScoreShield

The authors propose ScoreShield, a "perturb-then-project" mechanism designed to release similarity scores under central-model $(\varepsilon, \delta)$ -differential privacy while strictly enforcing geometric feasibility. The framework operates in two regimes:

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

In this regime, a curator releases a privatized score vector $s = Eq$ representing the similarity between a public query embedding $q$ and a gallery of $n$ stored embeddings.

Mechanism: The curator computes the clean score vector, adds Gaussian noise calibrated to the global $\ell_2$ -sensitivity ( $\Delta_{query} = 2$ ), and then projects the noisy vector onto the feasibility set $C_{query} = [-1, 1]^n$ .
Projection: The projection is a simple coordinate-wise clipping operation: $\text{proj}_{C_{query}}(s')_i = \max(-1, \min(1, s'_i))$ .
Privacy: Since projection is a deterministic post-processing step independent of the private data, the $(\varepsilon, \delta)$ -DP guarantee of the Gaussian mechanism is preserved.

2. Full Pairwise Gram Matrix Release (Regime ii)

In this regime, the curator releases a privatized pairwise cosine Gram matrix $S = EE^\top$ for non-interactive analytics (e.g., clustering, bias auditing).

Mechanism: The curator adds Gaussian noise to the Gram matrix, calibrated to the global Frobenius sensitivity. Under record-level adjacency, this sensitivity is $\Delta_{full} = 2\sqrt{2(n-1)} = \Theta(\sqrt{n})$ .
Projection: The noisy matrix is projected onto the cosine-Gram feasibility set $C_{coll}$ , defined as the set of symmetric, PSD matrices with unit diagonal and off-diagonal entries in $[-1, 1]$ .
Algorithm: Since exact projection onto this set (the elliptope) is computationally expensive (requiring a Semidefinite Program), the authors employ a Fast Averaged Alternating Projection (AAP) algorithm. This iterates between projecting onto the PSD cone (via eigenvalue clipping) and projecting onto the unit-diagonal box (via entry-wise clipping). The authors prove R-linear convergence to feasibility under bounded linear regularity.

Key Contributions

Quantitative Improvement over Naïve Gaussian DP:
- For Gram matrix release under record-level adjacency, the naïve Gaussian mechanism yields an expected squared Frobenius error of $\Theta(n^3)$ . ScoreShield, utilizing the geometry of the feasibility set, improves this bound to $O(n^2)$ for fixed privacy parameters.
- Under output-space (Gram-matrix) adjacency, the improvement is from $\Theta(n^2)$ to $O(n^{3/2})$ .
- For vector release, ScoreShield preserves the $\Theta(n)$ worst-case scaling of the naïve mechanism but offers constant-factor gains by reducing error on saturated coordinates via projection.
Utility Guarantees for Decision-Level Metrics (Regime i):
- The paper provides theoretical guarantees for verification tasks, characterizing the probability of decision flips (accept/reject) due to noise.
- It proves the existence and uniqueness of a threshold re-calibration that restores any attainable operating point (False Positive Rate, True Positive Rate) achievable by the privatized scores.
- It establishes uniform stability for ROC/AUC, showing that under Lipschitz score CDFs, the deviation is at most $O(\sigma)$ , which is first-order tight.
Scalable Projection with Convergence Guarantees:
- The authors introduce a scalable AAP solver for enforcing cosine constraints on large Gram matrices.
- They provide theoretical proofs for the R-linear convergence of this solver to the feasibility set, ensuring practical applicability for large-scale releases where exact SDP projection is intractable.
Comprehensive Evaluation:
- Regime (i): Evaluated on Face Recognition (using LFW, IJB-B/C, and other benchmarks) and DP-RAG (using the FRAMES benchmark). Results demonstrate that ScoreShield maintains decision-level utility (verification accuracy, TAR) significantly better than naïve Gaussian noise, particularly at strict operating points.
- Regime (ii): Evaluated on image similarity (CIFAR-10/100, Oxford-IIIT Pets), semantic textual similarity (STS-B), and recommendation systems (MovieLens-100K). The projected Gram matrices consistently outperform unprojected noisy matrices in downstream tasks like clustering (NMI), retrieval (Recall@1), and collaborative filtering (RMSE).

Significance and Claims

The paper claims to provide the first systematic central-model $(\varepsilon, \delta)$ -DP analysis of match-score releases in deep face recognition systems that connects threshold recalibration to decision-level guarantees. It addresses a critical gap in the literature where prior work either focused on local DP (perturbing inputs) or cryptographic methods, leaving central-model guarantees for released similarity scores largely unexplored.

The authors position ScoreShield as a general, modality-agnostic post-processing wrapper. By enforcing the structural constraints of cosine similarity (PSD, unit diagonal, bounded entries) through projection, the mechanism achieves a superior privacy-utility tradeoff compared to unconstrained noise addition. The results suggest that constraint-aware privatization is a necessary primitive for similarity-based systems to remain functional while providing rigorous privacy protections against membership inference and score-guided attacks.

The work is modest in its scope, focusing on one-shot, non-interactive releases under record-level replacement adjacency. It explicitly notes that it does not address repeated adaptive queries (which require composition accounting) or the derivation of instance-optimal noise distributions, leaving those as directions for future work.