Model Inversion meets Cryptographic Fuzzy Extractors

Technical Summary: Model Inversion meets Cryptographic Fuzzy Extractors

Problem Statement
Machine learning (ML) systems, particularly in face authentication, rely on storing embedding vectors derived from user inputs (e.g., face images). These vectors are often stored persistently in databases or on devices, making them susceptible to "smash-and-grab" attacks where an adversary gains access to all stored data. If these embedding vectors are stored unprotected, they are highly vulnerable to model inversion attacks, where an adversary can reconstruct the original input image (e.g., a user's face) from the leaked vector. While cryptographic Fuzzy Extractors (FEs) have been proposed as a post-processing defense to tolerate noise (essential for biometric authentication) while protecting the secret, existing FEs designed for $\ell_2$-norm noise (required by modern ML models) lack systematic cryptanalysis. Prior work has not rigorously evaluated whether these schemes can withstand model inversion attacks under a full-leakage threat model.

Methodology and Analysis
The authors conduct a comprehensive security analysis of existing $\ell_2$-based Fuzzy Extractor schemes, specifically Facial-FE (based on E8 and Leech lattices) and Randomized FE (based on Learning With Errors, LWE).

1. Cryptanalysis of Existing Schemes:

   • The authors identify a fundamental flaw in code-offset constructions used by these schemes. In these constructions, the public helper string $p$ contains an "offset" value (the difference between the input embedding and the nearest lattice codeword).
   • For natural face distributions, this offset is not uniformly random; it correlates with the user's identity and the specific geometry of the embedding relative to the lattice Voronoi cells.
   • This leakage allows an attacker to significantly reduce the residual entropy of the protected secret. The authors demonstrate that for Facial-FE, the conditional min-entropy drops drastically (e.g., from ~3.6 bits to ~0.02 bits for E8-based schemes), rendering the scheme insecure.
   • For Randomized FE, while the lattice is randomized per user, the public helper still leaks a linear signal about the input. The authors show that by averaging multiple leaked helper values for the same user, an attacker can cancel out the random noise and recover a high-fidelity estimate of the original embedding.

2. The PIPE Attack:

   • To empirically validate these theoretical weaknesses, the authors introduce PIPE (a new model inversion attack).
   • PIPE utilizes conditional diffusion models. It trains an inversion model on a public dataset to map "surrogate vectors" (derived from the leaked helper data $p$ and protected output $r$) back to realistic face images.
   • Unlike prior attacks that struggle against randomized schemes, PIPE effectively exploits the partial information leakage in the helper strings of existing $\ell_2$-FE schemes.

3. Proposed Solution: Snapper-FE:

   • The authors propose Snapper-FE, a new candidate scheme designed to be secure against model inversion.
   • Mechanism: Unlike code-offset schemes that release the offset, Snapper-FE first decodes the input embedding into a lattice codeword and then hashes this codeword. The secret is the hash output, and the public helper consists only of the hash keys.
   • Trade-off: This "decode-first" paradigm sacrifices some correctness (utility) because nearby inputs might decode to different codewords, but it eliminates the information leakage that enables inversion attacks.
   • Verification: The system uses a block-wise authentication with a soft-decision threshold (majority vote of matching hash blocks) to restore usability.

Key Results

• Breaking Prior Schemes: The PIPE attack achieves high success rates against existing $\ell_2$-FE schemes. Against Facial-FE (E8), PIPE achieves an Attack Success Rate (ASR) of 99.8% (based on $\ell_2$ distance) and 99.6% (based on authentication). Against Facial-FE (Leech), the ASR is approximately 65–73%. This demonstrates that prior schemes fail to provide cryptographic security against inversion.
• Ineffectiveness of Prior Attacks on Randomized FE: Previous inversion attacks (Bob, GMI, KED-MI) failed against the randomized Facial-FE variant (ASR < 6%), but PIPE successfully attacked it with an ASR of 66.5%, proving that randomization alone is insufficient.
• Security of Snapper-FE: Against Snapper-FE, PIPE and all other evaluated attacks achieve an ASR of roughly 0.4% to 4%, which is comparable to or only marginally better than random guessing. The reconstructed images are visually dissimilar to the original faces and fail authentication.
• Usability: Snapper-FE maintains practical utility. While the True Positive Rate (TPR) drops slightly compared to unprotected embeddings (e.g., from 91% to ~83.5% on Celeb-A), the False Positive Rate (FPR) remains low (4%). The authors note that majority voting over multiple enrollment samples can boost TPR back to over 90% while keeping FPR below 2%.
• Runtime: Snapper-FE offers comparable runtime performance to existing schemes, with authentication taking approximately 0.9 ms per sample on 504-dimensional embeddings.

Significance and Claims
The paper claims to be the first work to empirically connect model inversion attacks with the cryptanalysis of $\ell_2$-based fuzzy extractors. Its primary contributions are:

1. Demonstrating Insecurity: It establishes that existing $\ell_2$-FE schemes (Facial-FE and Randomized FE) do not offer the strong cryptographic properties required for face authentication, as they leak exploitable information about the input distribution.
2. Introducing PIPE: It presents a powerful, generalizable attack that defeats prior defenses, highlighting the gap between theoretical security assumptions and practical performance on real-world data distributions.
3. Proposing Snapper-FE: It offers the first practically usable and provably secure candidate for $\ell_2$-based fuzzy extractors. Snapper-FE provides "attack-agnostic" security, meaning its security relies on hardness assumptions about the input distribution rather than specific attack strategies, and it remains secure even under a full-leakage threat model where all persistent data is compromised.

The authors emphasize that their definitions and attacks are generic, applicable to any system using high-dimensional embedding vectors with $\ell_2$ distance comparisons, extending beyond face authentication to modalities like audio and text.