PaperlayerView exact revision on arXiv

Source-linked AI summary

Ranking Based Locality Sensitive Hashing Enabled Cancelable Biometrics: Index-of-Max Hashing

Zhe Jin, Yen-Lung Lai, Jung-Yeon Hwang, Soohyung Kim, Andrew Beng Jin Teoh

arXiv:1703.05455v2cs.CV

TL;DR

The paper addresses biometric template protection with a ranking-based, LSH-inspired cancelable representation. IoM hashing transforms real-valued features into discrete max-ranked indices using two realizations, and experiments and analyses report preserved accuracy alongside protection properties.

  • Problem

    Cancelable biometric templates must protect irrevocable biometric traits while supporting non-invertibility, revocability, unlinkability, and performance preservation.

  • Method

    IoM hashing uses externally generated random parameters to transform real-valued biometric features into discrete index codes through GRP-based and URP-based realizations.

  • Results

    The experiments report favorable fingerprint accuracy on FVC2002 and FVC2004, while analyses report resilience to major attacks and satisfaction of revocability and unlinkability criteria.

  • Takeaways & Limitations

    IoM hashed codes largely preserve before-transformation accuracy and provide non-linkability and revocability under properly tuned parameters.

Abstract

from arXiv · show

In this paper, we propose a ranking based locality sensitive hashing inspired two-factor cancelable biometrics, dubbed "Index-of-Max" (IoM) hashing for biometric template protection. With externally generated random parameters, IoM hashing transforms a real-valued biometric feature vector into discrete index (max ranked) hashed code. We demonstrate two realizations from IoM hashing notion, namely Gaussian Random Projection based and Uniformly Random Permutation based hashing schemes. The discrete indices representation nature of IoM hashed codes enjoy serveral merits. Firstly, IoM hashing empowers strong concealment to the biometric information. This contributes to the solid ground of non-invertibility guarantee. Secondly, IoM hashing is insensitive to the features magnitude, hence is more robust against biometric features variation. Thirdly, the magnitude-independence trait of IoM hashing makes the hash codes being scale-invariant, which is critical for matching and feature alignment. The experimental results demonstrate favorable accuracy performance on benchmark FVC2002 and FVC2004 fingerprint databases. The analyses justify its resilience to the existing and newly introduced security and privacy attacks as well as satisfy the revocability and unlinkability criteria of cancelable biometrics.

I. INTRODUCTION

Biometric template protection is motivated by security and privacy risks, especially because biometric traits are irrevocable. Cancelable biometrics address these risks through irreversible, regenerable transformations while aiming to preserve matching performance.

  • Biometric templates create security and privacy concerns because they are strongly bound to individuals and biometric traits are irrevocable.
  • Cancelable biometrics irreversibly transform biometric templates and permit new templates to be regenerated when compromised.
  • A general cancelable system adds a parameterized transformation after feature extraction and performs matching in the transformed domain.
  • Fingerprint minutiae are stable features for verification, but storing original minutiae is insecure because fingerprint reconstruction has been demonstrated.
  • Protected templates should satisfy non-invertibility, revocability, unlinkability, and performance preservation criteria.
  • The literature includes fingerprint-specific and generic cancelable biometric schemes, with generic methods applicable to modalities such as face and iris.

A. Minutiae-based Fingerprint Cancelable Template

Prior cancelable biometric methods use minutiae descriptors, projections, salting, and Bloom filters, but reported weaknesses include disclosure attacks, high computation, limited attack analyses, and unresolved security or privacy.

  • A. Minutiae-based Fingerprint Cancelable Template: Disclosing random offsets and orientation vectors can reveal minutiae coordinates and orientations in a minutia-vicinity scheme.
  • A. Minutiae-based Fingerprint Cancelable Template: Dynamic random projection was proposed to alleviate that disclosure problem, but it incurs substantially higher computation cost than random offsets.
  • A. Minutiae-based Fingerprint Cancelable Template: P-MCC applies Binary-KL projection to centered MCC features using the mean vector and largest eigenvectors, but its cancellability is not addressed.
  • A. Minutiae-based Fingerprint Cancelable Template: MLC constructs descriptors from neighboring-minutiae spatial distributions and uses binarization methods for protection.
  • A. Minutiae-based Fingerprint Cancelable Template: Blind system identification preserves accuracy and theoretically and experimentally justifies irreversibility, but protection against attacks such as ARM remains unknown.
  • B. Generic Cancelable Biometric Techniques: Biohashing uses a user-specific random projection and can regenerate a template by issuing new random vectors from the user token.
  • B. Generic Cancelable Biometric Techniques: Random projections have also been applied separately to iris sectors, with concatenated transformed vectors forming a cancelable template.
  • B. Generic Cancelable Biometric Techniques: Bloom filters support multiple modalities through binary vectors and parameterized many-to-one mappings, but their security and privacy remain unresolved.

III. MOTIVATIONS AND CONTRIBUTIONS

Existing cancelable biometric schemes face inversion, attack resilience, modality coverage, performance, and token-scenario problems. The paper proposes IoM hashing to address these challenges with ranking-based LSH and discrete hashed indices.

  • Some reported non-invertible transforms remain susceptible to partial or full inversion.
  • Existing methods may be weak against attacks including ARM and false-accept or dictionary attacks.
  • Fingerprint minutiae protection schemes such as P-MCC and 2P-MCC limit coverage to point-set data.
  • Strict non-invertibility and accuracy preservation create a trade-off because preserving discriminative information is needed for matching.
  • Some user-specific salting methods show an accuracy discrepancy between genuine-token and stolen-token scenarios.
  • IoM hashing uses externally generated random parameters and nonlinear discrete max-ranked indices to conceal real-valued biometric features.
  • The paper develops GRP-based and URP-based IoM realizations and analyzes their accuracy, security, privacy, revocability, and unlinkability.

A. Locality Sensitive Hashing

LSH hashes similar objects into common buckets with higher probability than dissimilar objects. The paper draws on ordinal and max-based hashing ideas while applying IoM hashing to fixed-length fingerprint vectors.

  • LSH reduces dimensionality by mapping similar items to the same buckets with high probability.
  • The LSH collision probability is tied to a similarity function over object pairs.
  • WTA hashing forms a nonlinear ordinal embedding based on partial order rather than absolute input values.
  • WTA repeatedly permutes the input, selects k items, records the largest item's index, and produces a compact hash code.
  • RMF uses iid standard Gaussian vectors and takes a maximum inner product over q vectors for each of m mappings.
  • IoM hashing takes a fixed-length fingerprint vector as input and has GRP and URP realizations.

A. Globally ordered fixed-length fingerprint vector

The paper constructs fixed-length real-valued fingerprint vectors from MCC minutia descriptors using kernel learning and KPCA, then applies IoM hashing to conceal feature information while retaining magnitude-independent ranking.

  • Fingerprint-vector construction: Fingerprint vectors begin with Minutia Cylinder-Code descriptor extraction from fingerprint minutiae.The procedure then omits binarization because IoM hashing accepts real-valued vectors.
  • Fingerprint-vector construction: A kernel matrix is computed from MCC training samples using an exponential kernel based on MCC dissimilarity and spread factor σ.The kernel entries are defined from pairwise MCC similarities.
  • Fingerprint-vector construction: KPCA eigenvectors form a projection matrix P∈ℝ^N_t×d, where d is the desired output dimension.The projection matrix is inferred from the kernel matrix.
  • Fingerprint-vector construction: A query MCC descriptor is matched against all training samples to form a vector of matching scores.Each score is defined as v_i←sim(Ω_q,Ω_t(i)).
  • Fingerprint-vector construction: The transformed matching-score vector is projected with P to produce the d-dimensional fingerprint vector x.The construction applies the kernel transform before the final projection.
  • IoM transformation: IoM hashing nonlinearly embeds fingerprint features into a rank space, preserving biometric accuracy while representing outputs as discrete indices.The GRP realization uses random projections and records maximum indices; its hashed code contains m entries in [1,q].

D. Uniformly Random Permutation (URP)-based IoM hashing

URP-based IoM hashing combines random permutations, p-order Hadamard products, and k-window maximum-index selection to produce concatenated discrete hash codes. The window size controls how strongly top-ranked entries are emphasized, while the Hadamard product is important to security and privacy.

  • URP construction: URP-based IoM hashing uses uniform random permutations inherited from WTA hashing and strengthens them with a Hadamard product.Each hash function is built from a p-order Hadamard product.
  • URP construction: Each URP hash permutes the input vector using p independent uniform permutation seeds.The resulting permuted vectors are combined in subsequent steps.
  • URP construction: The method multiplies p permuted vectors element-wise, selects the first k entries, and records the maximum entry’s index as t∈[1,k].Repeating this process with different permutation sets concatenates the outputs into the URP hashed code.
  • Illustration: The illustrated URP construction uses d=5, p=2, and k=3.These values are provided as an illustration of the transformation.
  • URP design choice: The window size k changes index distributions and tunes the relative weight assigned to the top entry versus other entries.This choice affects pairwise agreements among indices in the first k permuted positions.
  • Security consideration: The p-order Hadamard product is described as crucial for security and privacy because revealing codes and permutation seeds can reduce attack complexity.The relevant attacks include brute-force, dictionary, and ARM attacks.

E. Matching of IoM Hashed Codes

IoM matching relies on collision probabilities in rank space: similar fingerprint vectors should collide more often, while URP uses rank correlation and GRP uses Gaussian-projection collision analysis.

  • LSH matching principle: IoM hashing aims for higher hash-collision probability between highly similar fingerprint vectors and lower probability between dissimilar vectors.This is the locality-sensitive hashing principle underlying matching.
  • GRP matching: GRP matching is derived from the probability that corresponding Gaussian-projection hash entries have identical maximum indices.The analysis models Gaussian random vectors and approximates the collision kernel as m becomes large.
  • GRP matching: Operationally, GRP matching counts hash collisions as the number of zero entries after element-wise subtraction of enrolled and query codes.The score counts collisions across the m hashed-code entries.
  • URP matching: URP matching uses a rank-correlation similarity function based on pairwise-order agreement.Pairwise-order is introduced as the simplest similarity measure for rank correlation.
  • URP matching: For URP codes, the pairwise-order formulation counts shared ways for an index to be maximal within a k-sized permuted window.This quantity also represents the collision probability of a pair of URP hashed codes.

F. Cancelable Template Generation

IoM templates use externally generated, user-specific random parameters that can be replaced after compromise. The paper reports experimental verification of revocability and identifies stolen-token accuracy as a separate concern.

  • Template renewal: A compromised IoM hashed code can be replaced with a new tokenized permutation seed for URP or Gaussian random matrices for GRP.The random parameters are user-specific in the described real-world scenario.
  • Evaluation scope: The effectiveness of revocability is experimentally verified, while stolen-token accuracy is evaluated separately.The passage points to section VII(D) for revocability and section VI(B) for stolen-token performance.

G. Generic Template Protection

IoM hashing is presented as a generic cancelable-biometrics framework evaluated on six fingerprint datasets, with parameter studies for URP- and GRP-based realizations. Results show accuracy depends on window size, Hadamard order, and hashing-function count, while GRP performance is relatively insensitive to q when m is adequate.

  • G. Generic Template Protection: IoM hashing applies to binary and fixed-length biometric features, including iris, palmprint, face, and the real-valued fingerprint features evaluated here.The paper also identifies Index First One hashing as a special case of URP-based IoM hashing.
  • VI. EXPERIMENTS AND DISCUSSIONS: The evaluation uses 299-dimensional fingerprint vectors from six FVC2002 and FVC2004 datasets, each containing 100 users with eight samples.The six datasets are FVC2002 DB1–DB3 and FVC2004 DB1–DB3.
  • VI. EXPERIMENTS AND DISCUSSIONS: EERs are averaged over five repetitions because random permutations or projections are applied during hashing.
  • VI. EXPERIMENTS AND DISCUSSIONS: The matching protocol uses samples 1–3 for fingerprint-vector training and samples 4–8 for testing, producing 1000 genuine and 4950 imposter scores per dataset.
  • A. Parameters of IoM hashing: URP-based IoM EER decreases as window size k increases, then levels off when k becomes large.Smaller k provides fewer comparisons and less information about maximum-ranked features.
  • A. Parameters of IoM hashing: URP-based IoM has lower EER with smaller Hadamard order p, while increasing the number of independent hashing functions m improves EER until it levels off.The larger-p degradation reflects a performance-security trade-off, and m=200 with k=250 gives reasonably good accuracy.
  • A. Parameters of IoM hashing: GRP-based IoM is relatively insensitive to q when m is adequate, while increasing m substantially improves EER and can reduce it from 27.82% to 0.24%.On FVC2002 DB1 with q=250, this change occurs as m increases from 2 to 300; q=2 and q=250 yield EERs of 0.26% and 0.24% when m=300.

B. Accuracy Performance Evaluation

The evaluation compares IoM hashing with original fingerprint-vector, MCC, and existing cancelable-template systems under genuine- and stolen-token conditions. GRP-based IoM preserves accuracy across token conditions, while URP-based IoM remains comparable to prior methods despite dataset-dependent deterioration; code generation is slower than matching.

  • B. Accuracy Performance Evaluation: GRP-based IoM preserves accuracy relative to original fingerprint vectors and MCC, with insignificant differences between genuine-token and stolen-token cases.The result suggests the external token need not remain secret for comparable accuracy.
  • B. Accuracy Performance Evaluation: URP-based IoM deteriorates by approximately 3%–5% on the remaining testing sets but remains comparable to state-of-the-art cancelable templates.Its genuine-token accuracy is comparable to the original vector and MCC counterparts, while some datasets show gradual decreases.
  • B. Accuracy Performance Evaluation: Hashed-code generation takes longer than matching because many independent hash functions must be generated, and the MATLAB implementation was not optimized.

VII. SECURITY AND PRIVACY ANALYSIS

The paper evaluates IoM hashing against privacy and security attacks, including non-invertibility, ARM, brute-force, false-accept, and birthday attacks. Results indicate strong resistance under suitable parameter choices, while attack difficulty depends on the realization and selected parameters.

  • Privacy analysis: IoM non-invertibility requires approximately 2^12 attempts per feature component and about 2^588 attempts for all 299 components in the stated FVC2002 DB1 example.The analysis uses 4-decimal precision and 4636 possible values per component.
  • Privacy analysis: ARM privacy attacks remain computationally hard because IoM templates are transformed into rank space that is uncorrelated with the fingerprint feature space.The paper states that ARM complexity is identical to the non-invertibility attack complexity.
  • Security attacks: 24200 brute-force attempts are required for a URP code with m=600 and k=128, based on guessing each index among 128 possibilities.The configuration is identified as the best observed accuracy setting for the URP realization.
  • Security attacks: For URP-based IoM, false-accept attack complexity decreases to 2462 for FVC2002 DB1 but remains sufficiently high to resist false acceptance.The paper reports that the same complexity reduction appears across the remaining test datasets.
  • Security attacks: GRP security is more sensitive to parameter selection; increasing m or reducing q can raise attack complexity, with larger m requiring more storage.The paper reports computational infeasibility for m=1200 on FVC2004 DB1–DB3.
  • Security attacks: Birthday attacks reduce complexity approximately by a square-root factor relative to conventional false-accept attacks, and their difficulty remains closely tied to the selected parameters.For example, the reported FVC2004 DB3 complexity is 2^35, which the paper considers not ideally secure; increasing m or reducing τ can raise it.

C. Non-linkability

Non-linkability is evaluated by comparing pseudo-genuine and pseudo-imposter matching-score distributions generated with different random parameters. Overlapping distributions indicate that hashed codes from the same user and from different users are difficult to distinguish.

  • Non-linkability: Pseudo-genuine scores compare hashed codes from different templates of the same individual using different permutation seeds or projection matrices.The protocol generates 1000 pseudo-genuine matching scores.
  • Non-linkability: Pseudo-imposter scores compare hashed codes generated from each template using different permutation seeds or projection matrices.The two distributions are used to assess whether protected codes can be differentiated by user identity.
  • Non-linkability: Overlapping pseudo-genuine and pseudo-imposter distributions imply that hashed codes from the same user and from others are sufficiently indistinctive.Separated distributions would make it easier for an adversary to identify whether codes came from the same individual.

D. Revocability

Revocability is evaluated by regenerating hashed codes with different random parameters and comparing genuine, imposter, and pseudo-imposter score distributions. The reported overlap supports revocability for both IoM realizations.

  • Revocability: The revocability experiment produces 50000 pseudo-imposter scores from regenerated hashed codes.FVC2002 is used for URP-based IoM and FVC2004 for GRP-based IoM.
  • Revocability: Large overlap between imposter and pseudo-imposter distributions indicates that newly generated hashed codes are significantly distinct from the original codes.This distributional relationship is the paper’s empirical basis for evaluating renewability.
  • Revocability: The reported intersections between genuine and pseudo-imposter distributions verify that both IoM realizations satisfy the revocability requirement.The paper also states that stolen permutation seeds or random matrices do not significantly compromise accuracy performance.
  • Conclusion: IoM hashing is presented as a generic ranking-based LSH-inspired two-factor cancelable biometric scheme with URP-based and GRP-based realizations.The conclusion links the proposed construction to accuracy preservation, non-linkability, and revocability.
Loading 1703.05455v2…