General Framework to Evaluate Unlinkability in Biometric Template Protection Systems

In plain words

Biometric systems store a digital version of a fingerprint, iris, face or signature. If the same person is enrolled in two services, and both stored versions can be matched to each other, someone can tell that the two records belong to the same person. That is a privacy problem even when the stored data cannot be turned back into the original biometric. The standard that covers biometric template protection asks that stored templates should not be linkable across applications, but it gives no way to measure this.

This paper proposes a measuring method. For any way of comparing two protected records, you collect comparison scores for pairs that really come from the same person and for pairs that do not. From these two score distributions, the method works out, for each score, how much more likely "same person" is than "different people". It turns that into a number between 0 and 1 for each score, and a single overall number for the whole system. A value of 0 means the protected records cannot be linked for any score. A value of 1 means they can be linked with near certainty.

The authors apply the method to four protection schemes built on iris, signature, face and fingervein data. The point is that one fixed measure can compare very different systems, and can be re-run against stronger attacks that use other ways of comparing records.

TL;DR

• The paper defines a score-wise linkability measure D(s) and a system-wide measure D_sys in [0, 1], both from mated and non-mated score distributions of templates protected with different keys §4.
• A prior ratio omega appears in the formula; the paper uses omega = 1 as the worst case when priors are unknown §4.1 §5.
• Author-reported results: D_sys = 0 for iris XOR and signature with homomorphic encryption under the system's own comparison score; 0.07 for face Bloom filters; 0.92 for fingervein block re-mapping §6.2 §6.5.
• The code is a Python script from the authors' lab, under a custom license that does not permit open reuse; only cite it §5 evaluateUnlinkability.py.

Problem

Biometric template protection schemes are meant to make stored templates irreversible and unlinkable, as required by ISO/IEC 24745 §1. Earlier unlinkability analyses are either binary (accuracy curves such as ROC or DET that are compared between same-key and different-key settings), or they assume uniform data, or they cover only one scheme type §2 tab. 1. No quantitative and general metric was in use §1. The framework assumes an attacker who has two protected templates and a linkage function that yields continuous, normalisable scores, and who knows the score distributions of the system §3 §5.

Method

The scenario has two applications. The same biometric sample M is enrolled in both, and a Pseudonymous Identifier Encoder (PIE) uses a different secret key for each, producing templates T1 and T2. A linkage function LS gives a score s for the pair §3 fig. 1.

Step 1. Score distributions §3

• Mated samples: templates from the same instance, enrolled with different keys. The distribution is written p(s | H_m) eq. 1.
• Non-mated samples: templates from different instances, enrolled with different keys. The distribution is written p(s | H_nm) eq. 2.
• The paper merges a third case of earlier work (the same sample under two keys) into the mated distribution §3.

Step 2. Likelihood ratio and odds §4.1

• Define LR(s) = p(s | H_m) / p(s | H_nm) eq. 4.
• Bayes' rule gives p(H_m | s) / p(H_nm | s) = LR(s) · omega, where omega = p(H_m) / p(H_nm) eq. 6 §4.1.
• Since only two hypotheses exist, p(H_m | s) = LR(s) · omega / (1 + LR(s) · omega) eq. 10.

Step 3. Local measure D(s) §4.1

• Start from the difference D = p(H_m | s) − p(H_nm | s) = 2 p(H_m | s) − 1 eq. 3 eq. 11.
• Where LR(s) · omega ≤ 1, the paper sets D(s) = 0 so that all unlinkable scores share one value §4.1.
• The final definition is piecewise: 0 when LR(s) · omega ≤ 1, and 2 · x / (1 + x) − 1 with x = LR(s) · omega otherwise eq. 13. The function is continuous at x = 1 app. A.1.
• D(s) lies in [0, 1], is non-decreasing, and is defined for every score app. A.1.

Step 4. Prior ratio omega §4.1 §5

• If the priors are known, use them. Otherwise set omega = 1, which the paper calls the worst case for unlinkability §4.1.
• With N enrolled subjects in the second database, p(H_m) = 1/N and p(H_nm) = (N − 1)/N [eqs. 14, 15]. Taking the ratio gives omega = 1/(N − 1). This is derived here from the two stated probabilities; the paper states only that omega ≤ 1 and equals 1 for N = 2 §4.1.

Step 5. Global measure D_sys §4.2

• Integrating the mated-weighted difference gives D_sys = ∫ p(s | H_m) · D(s) ds eq. 18, normalised by p(H_m) [eqs. 16, 17].
• D_sys is in [0, 1] app. A.2. It is 1 when the mated and non-mated distributions do not overlap, and 0 when they fully overlap §4.2.
• If some score range favours non-mated pairs, the distributions must favour mated pairs somewhere else, so D_sys is non-zero in that case §4.3.

Step 6. Evaluation protocol §5

1. Create K databases of protected templates, each with a different key. The paper recommends K > 5 §5.
2. Compute the mated score distribution across the K databases §5.
3. Compute the non-mated score distribution across the K databases §5.
4. Set omega from the priors, or omega = 1 if they are unknown §5.
5. Compute D(s) eq. 13 and D_sys eq. 18.
6. Report the D(s) plot with both distributions and the value D_sys. Also report the database, the scoring protocol, how the linkage function works, and the adversary model §5.

Repeat for each linkage function. Several functions run in parallel are evaluated separately, and the system's value is the maximum over them §5.

# Local and global linkability from score samples  [§4] [§5]
# Input:  mated_scores, nonmated_scores (1-D arrays), omega (float)
# Output: local D per score, global D_sys in [0, 1]

def linkability(mated_scores, nonmated_scores, omega):
    # Estimate p(s | H_m) and p(s | H_nm) on a common score grid [§5 steps 2-3]
    density_mated = estimate_density(mated_scores, score_grid)     # (bins,)
    density_nonmated = estimate_density(nonmated_scores, score_grid)  # (bins,)

    # Likelihood ratio LR(s) = p(s | H_m) / p(s | H_nm)  [eq. 4]
    likelihood_ratio = density_mated / density_nonmated

    # Odds of mated versus non-mated, scaled by the prior ratio  [eq. 6]
    odds = likelihood_ratio * omega

    # Local measure: 0 up to odds = 1, then 2x/(1+x) - 1  [eq. 13]
    local = where(odds > 1, 2 * odds / (1 + odds) - 1, 0.0)

    # Limit as LR goes to infinity, used where p(s | H_nm) = 0  [eq. 13] [§6.3]
    local[density_nonmated == 0] = 1.0

    # Global measure: integral of D(s) weighted by p(s | H_m)  [eq. 18]
    global_value = integrate(local * density_mated, score_grid)
    return local, global_value

Hyperparameters

The paper has no training hyperparameters. The table lists the evaluation settings it reports, plus the code's defaults.

Results

Author-reported. Setup: BioSecure sub-corpora for iris, signature and face with 210 subjects, UTFVP for fingervein with 60 subjects, K = 10 keys, omega = 1 §6.1. Baselines are the paper's own alternatives: DET-based and RTMR-based analyses §6.5.

Note on the fingervein row: the DET and RTMR analyses cited by the paper call the system unlinkable, while the paper's measure gives 0.92 §6.5.

Paper vs code

The official repository is github.com/dasec/unlinkability-metric, owned by the da/sec group of the authors §5 evaluateUnlinkability.py. It has no LICENSE file. It ships hda-license.pdf, a Hochschule Darmstadt licence agreement that is not open source: one licence per institution, signed by an authorised signatory, with citation and indemnity terms hda-license.pdf. Only cite the code; do not copy snippets. The pseudocode above is written from the paper and the code's structure.

• Likelihood ratio estimator. The paper computes LR point-wise §6.1. The code builds normalised histograms on a shared grid of bins and divides them bin by bin evaluateUnlinkability.py. The number of bins defaults to min(N/10, 100), which gives 100 for any input of 1,000 or more scores evaluateUnlinkability.py evaluateUnlinkability.py.
• Plotted densities. The plotted mated and non-mated curves are kernel density estimates. The D curve is computed from the histograms, so the drawn curves and the values used for D come from two different estimators evaluateUnlinkability.py evaluateUnlinkability.py.
• Local measure. The code applies the paper's piecewise formula eq. 13 with the same boundary, and sets D = 1 where the non-mated histogram is empty evaluateUnlinkability.py.
• Global measure. The paper's integral eq. 18 is computed as a trapezoidal sum over bin centres evaluateUnlinkability.py.
• omega. Default 1, as in the paper evaluateUnlinkability.py §5 step 4. The code does not compute omega from N.
• Sample data. The files are named .hdf5, but the code reads them with numpy.fromfile, which reads raw bytes and does not parse HDF5 evaluateUnlinkability.py. The mated file holds 226,800 float64 values and the non-mated file 900,000 [raw/code: matedScores.hdf5, nonMatedScores.hdf5, sizes 1,814,400 and 7,200,000 bytes]. The paper's non-mated count is 987,525 §6.1. The README does not say which system these files belong to.
• Library calls. The code uses numpy.trapz and seaborn's shade argument. These may be deprecated in current versions. I did not run the script, so this is unverified.
• Other. The paper and README both ask for the paper to be cited in any work that uses the code README.md evaluateUnlinkability.py.

Pitfalls

• omega changes the answer. For a fixed score, a larger omega gives a larger D(s) §6.4. Using omega = 1 is the worst case, not a neutral choice. With N enrolled subjects and known priors, omega = 1/(N − 1) follows from the stated probabilities §4.1 [eqs. 14, 15], but the paper does not say so explicitly.
• Empty tails. Where the non-mated density is zero, D is set to 1 eq. 13 §6.3. With finite samples, empty bins can come from sampling alone. The paper's face-attack claims that some scores link "with almost all certainty" rest on this rule §6.3.
• Low-probability scores. For the face Bloom-filter PIC score, some scores below 0.94 favour mated pairs, yet D_sys is 0.07. The paper says these scores have p(s | H_m) < 0.005, so they carry little weight in the global value §6.2.
• Overall values depend on the linkage function. A system is only as unlinkable as its weakest function. The paper reports the maximum over functions §5 §6.3. A single D_sys = 0 says nothing about attacks not tried.
• Continuous scores. The method needs continuous, normalisable scores. Discrete scores must be mapped to a distance first §5. The paper does not say how to do this.
• Sampling choices change the distributions. Mated pairs must use different keys. The paper's non-mated pairing (one sample against the first sample of other subjects) is a choice that must be reported §5 §6.1.
• Histogram bins. The paper gives no bin count or bandwidth. The code's 100-bin histogram estimator is one choice, and the plots use a different one evaluateUnlinkability.py evaluateUnlinkability.py.
• Results come from the authors. The comparison with DET-based and RTMR-based analyses is the authors' own reading of those papers §6.5. The numbers here are not independently checked: the sample score files were not run through the script.

Lineage

• Builds on: Buhan et al., a classification-function view of unlinkability as a continuous property, for a fuzzy scheme §2. Also the mated and non-mated analysis of Ferrara et al., reduced here from three distributions to two §3.
• Compared against: DET- and ROC-based unlinkability analyses (Kelkboom et al.; Piciucco et al.) and the other entries in tab. 1 §2 §6.5.
• Superseded by: not known from the content in this wiki.