PaperlayerView exact revision on arXiv

Source-linked AI summary

How Much Feedback Is Needed to Break Template Protection? The Geometric Vulnerability of Biometric Authentication

Eliron Rahimi, Margarita Osadchy, Orr Dunkelman

arXiv:2610.25118v1cs.CR

TL;DR

Biometric authentication interfaces may leak information about protected templates, but it is unclear whether binary accept/reject feedback alone is sufficient for reconstruction. This paper develops geometric and distribution-aware reconstruction attacks for binary-feedback and score-releasing systems. The attacks achieve low reconstruction error with fewer queries, and the findings identify authentication itself as a source of template information leakage.

  • Problem

    It is unclear whether binary accept/reject feedback, which reveals less information than similarity scores, still provides enough information to reconstruct protected biometric templates.

    Source: §I · p. 1

  • Method

    The paper uses geometric constraints from binary decisions and distribution-aware query selection, including generative priors, to reconstruct templates under limited feedback.

    Source: §I · p. 1, §VII · p. 12

  • Results

    Across evaluated benchmarks, the attacks achieve the lowest reconstruction error while requiring fewer queries, and geometric information can enable perfect reconstruction up to numerical precision.

    Source: §I · p. 2, §VII · p. 12

  • Takeaways & Limitations

    Authentication feedback can expose geometric information that enables template reconstruction independently of the underlying protection mechanism.

    Source: §I · p. 2, §VI · p. 11

    The attacks assume black-box system access and, in some cases, a dataset generated by the same feature extractor; robustness under stricter constraints, mismatched distributions, and active query detection remains to be evaluated.

    Source: §VI · p. 12

Abstract

from arXiv · show

Biometric authentication systems increasingly use privacy-preserving mechanisms to protect sensitive templates. However, the authentication interface itself may still leak information that enables reconstruction attacks. Prior attacks exploit released similarity scores, whereas more advanced systems reveal only the binary accept/reject decision. This binary feedback provides substantially less information, making template reconstruction far more challenging. In this work, we introduce query-efficient reconstruction attacks under extremely limited feedback, addressing two key limitations of prior attacks. First, we introduce the first attack that reconstructs protected biometric templates using only authentication success/failure feedback by exploiting the geometric constraints of biometric authentication. Second, we introduce distribution-aware query-efficient reconstruction methods for score-releasing systems, achieving a more realistic threat model by reducing the number of required queries by a factor of $5\times$ compared to recent prior score-based attacks. Finally, we combine these two insights by incorporating a pretrained facial diffusion prior into our geometric binary attack, reducing the number of required queries by a factor of $5\times$. Our findings reveal a fundamental security limitation of biometric authentication: independently of the template protection mechanism, the authentication process itself exposes geometric information that can enable perfect template reconstruction up to numerical precision. Moreover, the distribution of biometric templates can be leveraged to make significantly more effective reconstruction attacks.

I. INTRODUCTION

Biometric templates contain sensitive information, and even systems that return only binary authentication outcomes may expose enough information for reconstruction. This work develops geometric and distribution-aware attacks, finding that authentication feedback can undermine template protection and that biometric-template distributions can improve attack efficiency.

I. INTRODUCTION

  • Deep face-recognition embeddings encode sensitive biometric information, and this work addresses irreversibility: protected representations should not allow recovery of the original template.Template protection schemes also target unlinkability and renewability.Source: §I · p. 1, A. Biometric Template Protection · p. 2
  • Binary authentication appears safer than score release because each query reveals only one bit, motivating the question of whether accept/reject feedback still enables reconstruction.Prior score-based attacks exploit similarity scores through hill-climbing or systems of equations.Source: §I · p. 1
  • Binary accept/reject feedback suffices for template reconstruction because decision boundaries impose geometric constraints: spheres for squared Euclidean distance and cones for cosine similarity.Locating boundary points lets an attacker construct equations that reveal the protected template.Source: §I · pp. 1–2
  • Across evaluated benchmarks, the attacks achieve the lowest reconstruction error while requiring fewer queries, and geometric information can enable perfect reconstruction up to numerical precision.The findings apply independently of the underlying template protection mechanism, including homomorphic encryption.Source: §I · p. 2
  • Distribution-aware score-based attacks reduce required queries by up to 5×, while a diffusion-prior binary attack reduces them by over 80% in experiments.The binary method combines a geometric reconstruction approach with a pretrained facial diffusion-based prior.Source: §I · p. 2

A. Biometric Template Protection

  • Template protection includes feature transformations and biometric cryptosystems, including homomorphic encryption and secure multiparty computation, but balancing accuracy, security, and efficiency remains challenging.The paper states its results apply to mechanisms that preserve recognition accuracy.Source: A. Biometric Template Protection · p. 2

B. Reconstruction Attacks from Similarity Scores

The section reviews score-based reconstruction and places the paper’s attacks in a black-box threat model. Its algebraic method uses similarity scores to construct equations for recovering the target template.

B. Reconstruction Attacks from Similarity Scores

  • Earlier score-based attacks use hill-climbing or solve equations from exposed scores; recent deep-feature methods may require many queries without optimizing query selection.The paper’s method uses a unified algebraic framework for squared Euclidean distance and cosine similarity.Source: B. Reconstruction Attacks from… · p. 2, §III · p. 3

A. Threat Model

  • The attacker has black-box access to the matching module, can submit arbitrary feature vectors, and receives either similarity scores or binary outcomes while the protected template remains inaccessible.The model assumes a semi-honest service provider that follows the protocol but may be curious about inputs and outputs.Source: A. Threat Model · p. 3

B. Algebraic Reconstruction from Similarity Scores

  • Squared Euclidean-distance scores yield d+1 equations that can be differenced to eliminate a common nonlinear term and produce a linear system for the template.The approach follows a triangulation principle.Source: B. Algebraic Reconstruction from… · p. 3
  • For cosine similarity, each authentication trial gives a linear equation, so d independent trials form a system with d variables for recovering the template.The construction uses normalized deep feature vectors.Source: B. Algebraic Reconstruction from… · p. 3

C. Reconstruction from Binary Authentication Feedback

The section introduces reconstruction from binary authentication feedback, first giving a baseline and then using the geometry of the acceptance region to recover the target template in squared-Euclidean-distance systems.

C. Reconstruction from Binary Authentication Feedback

  • The attack recovers a target from binary feedback by reducing reconstruction to geometric constraints: a sphere center for squared-Euclidean-distance systems and a cone axis for cosine systems.The section also introduces a simple baseline for comparison.Source: C. Reconstruction from Binary… · p. 3

1) Baseline Approach:

  • The baseline averages breaking-set templates that are falsely accepted, which lie inside the system’s acceptance region.That region is a sphere for squared-Euclidean-distance systems or a cone/spherical cap for cosine systems.Source: 1) Baseline Approach · p. 4

2) Squared Euclidean Distance Systems:

  • The squared-Euclidean-distance attack finds one accepted point, then uses binary search along d + 1 directions to locate sphere-boundary points and solve for the center.The accepted point search requires an average of 1/FMR attempts; increasing binary-search iterations brings each point closer to the sphere surface.Source: 2) Squared Euclidean Distance Systems · p. 4

3) Cosine Similarity Systems:

For cosine-similarity systems, the accepted region is a spherical cap, equivalently a cone around the target template. The attack uses binary feedback to recover the cone axis.

3) Cosine Similarity Systems:

  • Cosine-similarity reconstruction recovers the target template as the axis of the acceptance cone using only yes/no authentication outcomes.Because feature vectors are normalized, the accepted region is a spherical cap on the unit hypersphere.Source: 3) Cosine Similarity Systems · p. 5
  • The attack moves from an accepted point outside the cone, then binary-searches the boundary while renormalizing each midpoint.Repeating this process d times yields a linear system that can be solved for the target template.Source: 3) Cosine Similarity Systems · p. 5
  • The attack requires an average of 1/FMR + Pd authentication attempts and has the same asymptotic complexity as score-based cosine reconstruction.It requires only binary authentication feedback.Source: 3) Cosine Similarity Systems · p. 6

IV. QUERY-EFFICIENT TEMPLATE RECONSTRUCTION ATTACK METHODOLOGY

The query-constrained formulation makes reconstruction accuracy depend on how the attacker spends a limited query budget. The proposed score-based methods use biometric-template distribution information to select informative queries and constrain recovery.

A. Query-Constrained Threat Model

B. Query-Efficient Reconstruction from Similarity Scores

  • The proposed score-based objective constrains recovered templates to the biometric-template distribution, narrowing the feasible set when the system is underdetermined.The text states that only a small subset of vectors satisfying observed constraints falls within that distribution.Source: B. Query-Efficient Reconstruction from… · p. 6
  • Selecting facial templates from the same feature extractor’s real-image distribution yields more informative queries than random vectors, because those samples better span the target’s expected region.The passage describes this as providing a built-in prior through consistent geometric relationships in feature space.Source: B. Query-Efficient Reconstruction from… · p. 6
  • PCA selects diverse query directions from normalized templates, using principal components to construct a spanning set.Cosine similarity is equivalent to the dot product for normalized vectors, making PCA a natural tool for spanning-set construction.Source: B. Query-Efficient Reconstruction from… · p. 6
  • With a query budget B, the method uses the first B principal components; when B < d, this gives a low-rank approximation minimizing squared-Euclidean reconstruction error.The passage says this error coincides with cosine-based reconstruction error due to normalization; components below variance threshold τ are replaced with randomly sampled templates.Source: B. Query-Efficient Reconstruction from… · p. 6
  • The constructed constraints are solved with a least-squares linear solver to efficiently approximate the reconstruction objective.The passage describes this solver as operating after the breaking-set is constructed.Source: B. Query-Efficient Reconstruction from… · p. 6

C. Query-Efficient Reconstruction from Binary Authentication Feedback

The binary attack uses geometric constraints from authentication feedback, while query-efficient reconstruction uses priors to recover accurate templates from fewer equations. A pretrained facial diffusion model guides generation using constraints in biometric feature space.

C. Query-Efficient Reconstruction from Binary Authentication Feedback

  • The query budget is set by the system threshold, binary-search precision P, and the number of equations required by the algebraic solver.Reducing the required equations saves P authentication queries per removed boundary-search procedure.Source: C. Query-Efficient Reconstruction from… · pp. 6–7
  • Binary feedback does not allow boundary points to be chosen to align with informative feature-space directions, so score-based input selection cannot be applied in the same way.The binary equations arise through a random boundary-search process.Source: C. Query-Efficient Reconstruction from… · p. 7
  • A prior-based objective combines constraint fit with the likelihood of a template under the target distribution.The likelihood P(x) is estimated from facial templates extracted with the same feature extractor; the approach seeks accurate templates from fewer equations.Source: C. Query-Efficient Reconstruction from… · p. 7
  • A pretrained facial-image diffusion model is guided through a differentiable feature extractor to satisfy constraints in the target biometric feature space.The image-space prior restricts recovered templates to the feature-space distribution and leads to more accurate reconstruction.Source: C. Query-Efficient Reconstruction from… · p. 7

V. EXPERIMENTAL EVALUATION

The evaluation asks whether binary feedback enables template reconstruction and whether query-efficient methods improve score-based reconstruction. It also examines prior-based reconstruction without input selection and the query reduction of the binary attack.

V. EXPERIMENTAL EVALUATION

  • RQ1 asks whether protected biometric templates can be reconstructed from binary authentication feedback alone.The evaluation also examines the query reduction of the proposed binary-feedback attack.Source: §V · pp. 7–8
  • RQ2 asks whether the query-efficient score-based attack has lower reconstruction error than prior attacks at every query budget.RQ3 asks whether a prior-based solver improves reconstruction when the attacker cannot choose the breaking set.Source: §V · pp. 7–8
  • RQ4 asks how much the query-efficient binary-feedback attack reduces authentication queries; Figure 3 studies how binary-search precision P affects reconstruction loss.The figure caption identifies each point as a target template and the solid line as mean reconstruction loss.Source: §V · p. 8, Figure 3 · p. 8

A. Experimental Setup

The experiments use standard face-recognition feature extractors and benchmarks, evaluate two false-match-rate thresholds, and measure both reconstruction accuracy and query efficiency.

A. Experimental Setup

  • The evaluation uses ArcFace and FaceNet and sets system thresholds for false match rates of 1.0% and 0.1%.These feature extractors are also used in prior protected-recognition systems.Source: A. Experimental Setup · p. 8
  • The study uses LFW and celebA, randomly selecting 300 identities from each benchmark as target users.Both benchmarks contain more than 10,000 facial images and 1,000 identities.Source: A. Experimental Setup · p. 8
  • Reconstruction accuracy is measured by distance from the target template under the corresponding matching metric, while query efficiency tracks loss against authentication-query count.The evaluation also reports the share of targets below 1% of the authentication threshold and the queries needed to reach that criterion.Source: A. Experimental Setup · p. 8

B. Binary Reconstruction Evaluation

Across the evaluated settings, binary feedback enables highly accurate reconstruction, while distribution-aware score-query selection and prior-based solving improve query efficiency. Without input selection, the diffusion-based solver performs close to the ideal target-distribution setting.

B. Binary Reconstruction Evaluation

  • 97.6%–100% of the proposed method’s reconstructions fall below 1% of the system threshold, versus 0% in most settings and at most 4.0% for the baseline.This pattern holds across datasets, feature extractors, decision rules, and false-match-rate operating points.Source: Table II · p. 9, B. Binary Reconstruction Evaluation · p. 9
  • At P = 20, almost all targets fall below the 1% threshold; baseline reconstruction remains limited because false-match points follow feature-space structure rather than uniform sphere coverage.The baseline does not reach perfect reconstruction even with many false-match points.Source: B. Binary Reconstruction Evaluation · p. 9, Figure 4 · p. 9

C. Evaluation of Query-Efficient Reconstruction from Similarity Scores

  • PCA-based input selection achieves the lowest reconstruction loss at every evaluated query budget and reaches numerical precision after roughly 50 queries.It improves loss by 26%–72% over random selection from the target feature-space distribution and requires approximately 5× fewer queries than prior baselines that do not exploit that distribution.Source: Figure 5 · p. 10, C. Evaluation of Query-Efficient… · pp. 10–11

D. Evaluation of Query-Efficient Reconstruction from Similarity Scores Without Input Selection

  • Without input selection, the diffusion-based solver outperforms classical algebraic and Gaussian-prior methods, approaching the ideal setting with target-distribution equations.The result indicates that the prior-based solver approximates the distribution-constrained objective.Source: Figure 6 · p. 10, D. Evaluation of Query-Efficient… · p. 11

E. Query-Efficient Binary Reconstruction Evaluation

The diffusion-based solver reaches perfect binary-feedback reconstruction with about five times fewer queries than the algebraic solver. The discussion and conclusion emphasize that repeated authentication interactions can leak reconstructive information despite template protection.

E. Query-Efficient Binary Reconstruction Evaluation

  • Binary-search boundary constraints cost P authentication queries each, so needing fewer constraints directly reduces total query cost.The diffusion solver exploits a facial-image prior, while the algebraic solver requires enough independent constraints to determine the template directly.Source: E. Query-Efficient Binary… · p. 11
  • Approximately 5× fewer queries let the diffusion-based solver reach perfect reconstruction than the algebraic solver, which needs about 10,000 queries.The algebraic solver uses enough independent boundary constraints to determine the template directly; the diffusion solver uses a facial-image prior to recover it from fewer constraints.Source: E. Query-Efficient Binary… · p. 11

VI. SECURITY IMPLICATIONS AND DISCUSSION

  • Repeated system interactions can leak template information despite cryptographic protection at rest and during computation.The authentication interface acts as a side channel through which carefully designed queries can gradually recover the protected template.Source: §VI · p. 11
  • In SED systems, binary decisions define a sphere; cosine systems yield a cone on the unit hypersphere, and both boundaries can support reconstruction.The discussion also notes that distribution-aware priors improve reconstruction.Source: §VI · p. 11
  • Attacks assume black-box access and sometimes access to data from the same feature extractor; robustness under stricter constraints, mismatched distributions, or active query detection remains to be evaluated.Source: §VI · p. 12

VII. CONCLUSION AND FUTURE WORK

  • The conclusion presents attacks on both score and binary feedback, including distribution-aware input selection and generative-prior binary reconstruction, as recovering templates with low error and fewer queries.Future work includes other biometric modalities and relaxing the assumption of access to the exact feature extractor.Source: §VII · p. 12

APPENDIX A

The appendix reports additional benchmark results consistent with the main-text findings and describes implementation details for the diffusion solver and Lagrange baseline. It also presents additional score-based and binary-feedback comparisons.

A. Additional Results

1) Query-Efficient Reconstruction from Similarity Scores:

2) Query-Efficient Reconstruction from Similarity Scores Without Input Selection:

3) Query-Efficient Binary Reconstruction:

1) Our Diffusion-Based Solver:

  • The diffusion solver guides pretrained facial diffusion sampling toward images whose extracted biometric features satisfy the feedback-derived linear constraints.It uses IDiff-Face as a generative prior without additional training or identity conditioning; SVD row whitening is applied to the diffusion solver's constraint system, not the algebraic solver's.Source: 1) Our Diffusion-Based Solver · p. 14

2) Lagrange-Based Reconstruction Method:

  • The Lagrange baseline converts released scores into a linear system and recovers the template by solving that system.Its implementation uses random normalized Gaussian probes, least squares, and unit normalization, with a fallback to unconstrained least squares if rootfinding fails.Source: 2) Lagrange-Based Reconstruction Method · p. 14

3) GMM-Based Prior:

The appendix describes a distributional prior for score-derived reconstruction, a score-guided hill-climbing baseline, and PCA-based selection of informative queries. Additional figures report results consistent with the main text.

3) GMM-Based Prior:

  • The GMM prior formulates score-derived reconstruction as maximum a posteriori estimation using a full-covariance Gaussian estimate of the target feature distribution.The estimate uses one mixture component and is trained on training-validation embeddings.Source: 3) GMM-Based Prior · p. 14
  • Additional results for score reconstruction with input selection across CelebA and LFW under cosine and SED are consistent with the main-text findings.Source: Figure 8 · p. 15

4) Hill Climbing:

  • Hill climbing keeps a candidate only when its released matching score improves over the current reconstruction.For SED, improvement means lower distance; for normalized templates, minimizing SED is equivalent to maximizing cosine similarity.Source: 4) Hill Climbing · p. 15

5) PCA-Based Input Selection:

  • PCA-based input selection retains the first 40 principal components to form informative, non-redundant constraints, then selects later queries randomly from the breaking-set.The breaking-set contains 10,000 non-target images; released scores are converted into linear constraints for least-squares reconstruction.Source: 5) PCA-Based Input Selection · p. 15
  • Additional results for score reconstruction without input selection across CelebA and LFW under cosine and SED support the same conclusions as the main text.Source: Figure 9 · p. 16
  • Additional binary-reconstruction benchmark and decision-boundary results across CelebA and LFW under cosine and SED are consistent with the main-text results.Source: Figure 10 · p. 16

Related papers

Loading 2610.25118v1…