In privacy-preserving systems—ranging from biometric authentication to genetic sequence matching—a common goal is to compare two sensitive data points without ever revealing their raw contents. To achieve this, researchers often use "similarity-preserving" transformations. These methods, such as Locality-Sensitive Hashing (LSH) or cancellable biometrics, map sensitive data into a new space where the distance between points remains roughly the same as in the original space.
However, a growing body of research reveals a fundamental "similarity paradox": the very property that makes these systems functional also makes them vulnerable. If a system reveals the exact distance (or similarity score) between a query and a protected template, an adversary can use that score as a compass to navigate the search space and reconstruct the original sensitive information.
The Similarity Score as a Feedback Signal
The most intuitive way to understand this vulnerability is to view the similarity score as a fitness function in an optimization problem. In a "black-box" scenario, an attacker does not need to know the internal math of the protection scheme; they only need the numerical output.
Dong et al. demonstrated this using a Genetic Algorithm-enabled Similarity-Based Attack (GASAF). By starting with a population of random guesses and iteratively refining them based on the similarity scores returned by the system, the authors were able to "evolve" a synthetic biometric template that matches the original. Similarly, Tian et al. showed that Automatic Speaker Verification systems could be breached by using similarity scores to fine-tune voice conversion models, creating synthetic speech that deceives the system's "ears."
This feedback loop turns the security mechanism against itself. As Wang et al. argue, increasing the complexity of the security code can counter-intuitively make the system more vulnerable, as more complex codes may provide a more granular gradient for the attacker’s optimization process.
Triangulation and Geometric Exploitation
Beyond iterative refinement, similarity scores leak geometric information that allows for direct reconstruction through triangulation. If an attacker knows the distance between an unknown target and several known reference points, they can mathematically narrow down the target's exact position in the feature space.
Portelo et al. and Riazi et al. both highlight how similarity-preserving embeddings inadvertently facilitate these triangulation attacks. By comparing hashes to a set of known reference profiles, an adversary can reconstruct private attributes. This is particularly dangerous in systems using Euclidean or Cosine metrics; Jiang et al. note that these continuous metrics allow attackers to leverage linear programming to reverse-engineer original features if they obtain the protected template and the transformation key.
The Failure of Partial Encryption
A common misconception is that encrypting the underlying data—using tools like Homomorphic Encryption (HE)—is sufficient for privacy. However, if the final decision phase leaks a plaintext similarity score to save on computational costs, the encryption is effectively bypassed.
Bassit et al. demonstrated that even when facial templates are encrypted, leaking a simple similarity score allows an attacker to reconstruct the entire facial identity using AI-generated synthetic faces. This highlights that the "leakage" isn't in the storage, but in the interface. As Kim et al. show, even a single batch of queries can be enough to exploit the geometric structure of an AI model's internal embeddings if granular scores are provided.
Moving Beyond Exact Distances
To mitigate these risks, researchers are moving away from revealing exact distances. Several strategies have emerged to break the feedback loop:
- Restricted Outputs: Instead of returning a floating-point similarity score, systems can return a simple binary "match/no-match" decision. Beck and Beck compare the challenge of reconstruction to a "Mastermind-style" game, where reducing the information provided per query significantly increases the difficulty for the attacker.
- Quantization and Non-Linearity: By using many-to-one mappings or modulo-based transformations, systems can ensure that hashes appear random for distant samples while only preserving similarity within a specific threshold. Jiang et al. propose such a modulo-based mapping to thwart iterative optimization.
- Randomized Domains: Wang et al. suggest using statistical inference within randomized "Montgomery domains" to perform identification without ever calculating or revealing the exact distance between a query and a record.
The research across these 14 papers suggests a shift in how we define "privacy-preserving." It is no longer enough to hide the raw data; we must also hide the mathematical relationships—the distances and similarities—that define that data's identity in the digital world.
Key Foundational Work
Approximate Two-Party Privacy-Preserving String Matching with Linear Complexity (2012) — contributed 1 concept elements to this direction.
Secure binary embeddings of front-end factor analysis for privacy preserving speaker verification (2013) — contributed 1 concept elements to this direction.