💻 computer science

A Deeper Dive into the Irreversibility of PolyProtect: Making Protected Face Templates Harder to Invert

This paper enhances the irreversibility of the PolyProtect face template protection method by introducing a key selection algorithm that optimizes polynomial parameters to resist inversion attacks and balances the trade-off between security and recognition accuracy, while also addressing performance issues through embedding normalization.

Original authors: Vedrana Krivokuća Hahn, Jérémy Maceiras, Sébastien Marcel

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vedrana Krivokuća Hahn, Jérémy Maceiras, Sébastien Marcel

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 your face is a unique, irreplaceable key that unlocks your digital life. In the past, we've stored copies of this key (called "face embeddings") in databases to let you unlock your phone or access your bank account. But if a hacker steals that database, they don't just get a password; they get a blueprint of your face that can be used to create fake videos (deepfakes) or trick systems into thinking they are you.

This paper is about building a super-strong vault for those face keys. Specifically, it improves a method called PolyProtect, which scrambles your face data so that even if the vault is stolen, the thief cannot unscramble it to get your original face back.

Here is a breakdown of the paper's journey, using simple analogies:

1. The Problem: The "Math Puzzle" Was Too Easy

The PolyProtect method works like a complex math puzzle. It takes your face data and mixes it using a special formula (a polynomial) with secret ingredients (numbers called coefficients and exponents).

The Old Way: The researchers found that the original way of mixing these numbers was a bit like leaving the back door unlocked. They realized that a specific type of math tool (a "solver" based on cosine distance) could solve the puzzle much faster than the tool they originally tested (based on Euclidean distance).
The Analogy: Imagine you lock a safe with a combination. The original authors thought the lock was unbreakable because they only tested it with a standard screwdriver. This paper found that a power drill (the cosine solver) could break it open much more easily.

2. The First Fix: Flattening the Hills

Before fixing the lock, the researchers noticed a problem with the "terrain" of the data.

The Issue: Some face data models (like iResNet100) produced numbers that were very spread out (ranging from -4 to +4), while others were tight and small (ranging from -0.7 to +0.7). When they applied the scrambling formula to the "spread out" data, the numbers exploded into massive values (like -20,000 to +20,000). This made the system very confused, leading to poor recognition (it couldn't tell if two photos were the same person).
The Fix: They simply normalized the data. Think of this as flattening a mountain range into a gentle hill before scrambling it. By squeezing all the data into the same small range first, the scrambling process works smoothly, and the system recognizes faces accurately again, regardless of which model created the data.

3. The Big Breakthrough: Choosing Better "Secret Ingredients"

This is the main contribution of the paper.

The Old Method: Previously, the "secret ingredients" (the coefficients and exponents) for the math puzzle were chosen completely at random. It was like rolling dice to pick the combination for your safe. Sometimes you got a strong lock; sometimes you got a flimsy one.
The New Method: The authors created a "Key Selection Algorithm." Instead of rolling dice, this algorithm acts like a quality control inspector.
1. It picks a random set of ingredients.
2. It tries to break the lock using the "power drill" (the cosine solver).
3. If the lock breaks: It throws those ingredients away and tries a new set.
4. If the lock holds: It keeps those ingredients.
The Result: This process ensures that every single face template gets a "super-lock" that is incredibly hard to break.

4. Solving the Trade-Off: Getting the Best of Both Worlds

There was a known rule in this field: The more you overlap the data pieces during scrambling, the easier it is to recognize the face, but the easier it is to hack.

Low Overlap: Very secure (hard to hack), but the system makes many mistakes (low accuracy).
High Overlap: Very accurate, but easier to hack.

The researchers found that their new "Quality Control Inspector" (the Key Selection Algorithm) changed the game. Because the algorithm is so good at finding the strongest locks, it equalized the security.

The Analogy: Imagine you have different types of doors. Usually, a glass door is easy to see through (accurate) but easy to break. A steel door is hard to break but hard to see through. The new algorithm found a way to make the glass door as unbreakable as the steel door.
The Outcome: You can now choose the "High Overlap" setting to get the best face recognition accuracy, without worrying that you've made the system easier to hack. The security remains high regardless of the setting.

Summary of Findings

Better Attackers: They proved that hackers using "cosine distance" tools are more dangerous than previously thought, so we must defend against them.
Normalization: You must "flatten" the face data before scrambling it to ensure the system works well.
Smart Keys: Instead of random locks, use an algorithm that tests and rejects weak locks. This makes the system nearly impossible to reverse-engineer.
No More Compromise: This method allows for high accuracy and high security simultaneously, removing the usual trade-off where you have to sacrifice one for the other.

The Bottom Line: The paper provides a recipe to make face recognition systems that are both highly accurate and extremely secure, ensuring that even if a database is stolen, the original faces remain safe and unrecoverable.

Technical Summary: A Deeper Dive into the Irreversibility of PolyProtect

Problem Statement
Biometric Template Protection (BTP) is essential for securing face recognition systems, ensuring that stored templates cannot be reversed to recover original face images or sensitive attributes. While the PolyProtect method was previously established as a handcrafted BTP technique using multivariate polynomials to transform face embeddings, its "irreversibility" property required deeper analysis. Specifically, the authors identified two critical gaps:

Solver Vulnerability: Previous evaluations of PolyProtect's irreversibility relied on numerical solvers minimizing Euclidean distance. However, face recognition systems typically operate using cosine distance. It was unclear if a solver minimizing cosine distance would be more effective at inverting PolyProtected templates.
Parameter Selection: The original PolyProtect implementation selected polynomial coefficients and exponents (keys) purely at random. The authors questioned whether a smarter selection strategy could enhance irreversibility without sacrificing recognition accuracy.
Model Sensitivity: Preliminary observations suggested that PolyProtect's accuracy varied significantly depending on the range of values in the underlying face embeddings (e.g., iResNet100 vs. EdgeFace), potentially causing high intra-class variance in the protected domain.

Methodology
The study utilized a 512-dimensional face embedding framework and evaluated three datasets (Multi-PIE, SOTERIA, iCarB-Face) across two face recognition models (iResNet100 and EdgeFace). The methodology proceeded in three phases:

Accuracy Evaluation and Normalization:
The authors applied PolyProtect to embeddings from both models using varying "overlap" parameters (0 to 4). They observed that iResNet100 embeddings, which naturally occupy a larger numerical range (approx. [-4, 4]) compared to EdgeFace (approx. [-0.7, 0.7]), suffered significant accuracy degradation after transformation due to exaggerated intra-class variance. To address this, they proposed normalizing embeddings to a standard range prior to applying the PolyProtect transform.
Irreversibility Analysis (Solver Comparison):
The authors challenged the definition of the "worst-case attacker" by comparing two numerical solvers:
- Euclidean Solver: The original method (Levenberg-Marquardt algorithm) minimizing Euclidean distance.
- Cosine Solver: A new method (BFGS algorithm) minimizing cosine distance.
  Both solvers attempted to recover the original embedding $V$ from a protected template $P$ . Success was measured by the cosine distance between the recovered $V^*$ and the true $V$ .
Key Selection Algorithm:
To counter the more effective cosine-based solver, the authors proposed a "key selection algorithm." Instead of random generation, this algorithm iteratively generates coefficients ( $C$ ) and exponents ( $E$ ) for the polynomial. It tests each candidate set by attempting an inversion attack using the cosine solver. If the attack succeeds (i.e., the recovered template is too close to the original), the keys are discarded, and new ones are generated. This process repeats until a set of keys is found that renders the template "irreversible" (failing the inversion attack) even under the worst-case scenario.

Key Contributions

Normalization for Robustness: The paper demonstrates that normalizing face embeddings before applying PolyProtect is a simple yet effective fix for accuracy degradation in models with large value ranges (like iResNet100), making the method applicable across different embedding types.
Revised Threat Model: The authors establish that a cosine-distance-based numerical solver is a more potent inversion tool than the Euclidean-based solver previously used. Consequently, the definition of irreversibility for PolyProtect must be updated to account for this stronger attacker.
Key Selection Algorithm: The primary contribution is an algorithm that selects polynomial parameters to maximize irreversibility. This method significantly reduces the Inversion Success Rate (ISR) compared to random key generation.
Trade-off Mitigation: The study shows that the key selection algorithm not only improves irreversibility but also approximately equalizes it across different overlap parameters. This allows system designers to tune the overlap parameter primarily for recognition accuracy without worrying about drastic drops in irreversibility.

Results

Accuracy: Without normalization, iResNet100 embeddings showed poor accuracy in the protected domain (e.g., FNMR > 50% at 0.1% FMR for overlap 0). With normalization, accuracy improved drastically, matching or exceeding the performance of EdgeFace and approaching the unprotected baseline.
Inversion Vulnerability: The cosine-based solver was found to be more effective than the Euclidean solver, yielding lower inversion scores (higher similarity to the original) and thus confirming a higher risk of inversion.
Irreversibility Improvement: The key selection algorithm drastically reduced the Inversion Success Rate (ISR). For random keys, ISR was often >90% at 0.1% FMR. With the key selection algorithm, ISR dropped to <1% (often ~0%) across all datasets and overlaps.
Accuracy vs. Irreversibility: While the key selection algorithm caused a slight degradation in recognition accuracy compared to random keys (e.g., an increase in FNMR of 1–14% depending on the dataset), this loss was deemed negligible compared to the massive gain in irreversibility (improvement of 68–98% in ISR).

Significance and Claims
The paper claims that PolyProtect can be made significantly more secure against practical inversion attacks by adopting a cosine-based threat model and utilizing a targeted key selection strategy. The authors emphasize that while the method incurs a minor accuracy cost, the resulting templates are "practically irreversible" even under worst-case assumptions. Furthermore, the ability to equalize irreversibility across different overlap settings provides greater flexibility in balancing the trade-off between security and recognition performance. The work concludes that random key generation is insufficient for high-security applications and that the proposed key selection algorithm should be the standard for deploying PolyProtect. The authors also note that the code is open-source to ensure reproducibility.