Biometric Template Protection

Biometric Template Protection

Hamdan Alzahrani

University of Colorado at Colorado Springs

Abstract

We show how using Local Structure Representations of fingerprint minutia allows for use of biometric key management systems effectively. Several systems are reviewed to demonstrate this.

Introduction

Why biometrics?

There is currently a strong demand for identity assurance systems. Current authentication systems determine an identity based on the possession of a token, generally a password or smartcard. However, token-based identity transactions are relatively easy to repudiate since other people may possess the token. A system that can guarantee the presence of a user during authentication would greatly enhance the non-reputability of these transactions. Biometrics can provide this strong link between a user and their identity.

Difficulties with biometrics

Despite the clear promise of biometrics, they are difficult to implement.

Biometrics is subject to noise, which generates intra-user variation. The approximate matching or error correction codes used to manage intra-user variation may accept biometrics from others, which is the problem of inter-user variation. Increasing matching tolerances or error correction accepts more intra-user variation. Reducing matching tolerances or error correction rejects more inter-user variation. The relationship between accepting intra-user variation and rejecting inter-user variation is generally inverse, but sensitive to the biometric representation and details of system implementation.

Biometric features are not practically changeable. With the exception of serious injury, features change very slowly with time. This stability brings both advantages and disadvantages. This prevents criminals from changing their features to avoid detection, but it also means that features cannot be changed when compromised.

Why templates?

Authentication systems operate based on matching. A user presents a token to the system. This token is compared against a stored target. If the token matches, the user is authenticated. Biometrics operates similarly, with the biometric feature acting as a token. Within biometrics, the matching target is called a template.[1]

Protection of the token is necessary for the operation of authentication systems. A compromised token no longer uniquely identifies a user. While similar to physical tokens, biometric features cannot be revoked in case of copying. Classical cryptographic solutions interact poorly with intra-user variation since nearby inputs do not generate nearby outputs.

Existing Literature

An additional difficulty within the field of biometrics is with consistent terminology and metrics. As noted by Breebaart et al [2], there was no consistent use of terminology within the literature. This was improved somewhat by ISO 24745 [3] which introduced standardized terminology and goals for protected biometric templates. Unfortunately, the terminology introduced was not well defined. Simoens et al [4] published improved terminology with an emphasis on measurability. While the definitions introduced were now more exact, there is still no consistent set of metrics.

Jain et al have published several surveys over the last decade. The most recent version groups systems into three categories: Biometric Cryptosystems, Transformations, and Hybrid [5]. Unfortunately, no clear, exact definition of these categories is provided. As used, the categories are not very distinct, making it very difficult to sort systems not categorized by the authors.

Fingerprint Biometric Systems

Protected biometric systems have advanced significantly over the last decade. One promising approach is to recover a key from a biometric input [5]. This simplifies matching operations, since a key can be exactly matched. This also allows biometric systems to integrate with standard authentication systems, which are often based on cryptography. Finally, such systems simplify key management since users no longer need to keep passwords.

An important modality of biometrics is fingerprints. Fingerprints are easy and convenient to use. This makes them attractive for use as authentication systems. Unfortunately, standard fingerprint representations lack the stability needed for biometric key management systems.

An approach to fingerprint representation that does have the required stability is local minutia structures [5]. These involve constructing translation and rotation invariant structures from the underlying input. We focus on two approaches, minutia pair and minutia triangles.

These representations are sufficiently stable for use in biometric key management systems. We examine two such systems to show this.

Biometric Key Management

Introduction

Significant work has been done on combining key management with biometrics [6], [7], [8]. These systems provide a way to bind or generate a key from a biometric input. Ideally, this key should be usable for either cryptographic operations or authentication.

Systems

Fuzzy Commitment

Fuzzy commitment binds a key to a biometric by treating an input biometric as a corrupted code word [6]. An input biometric is shifted by some stored helper data. An error correction decode function is applied to the shifted biometric. If the input biometric is sufficiently close to the enrolled biometric, the decoder will reproduce the bound key. Two difficulties of Fuzzy Commitment are its use of an ordered, fixed length input [7] and that the error correction code is centered on the key, not the biometric.

Fuzzy Vault

Fuzzy Vault was developed to fix a flaw in the application of fuzzy commitment [7]. Instead of standard error correction, Fuzzy vault utilizes polynomial interpolation to correct errors in the input. Polynomials are invariant to a change in order of the generating points.

A polynomial is constructed from a key. The biometric is used to evaluate the polynomial. The evaluation locations and values are stored as a point. Fake “chaff” points are added to the set to disguise the real points in the vault. A user can identify the real points by comparing the location values in the vault to those generated by the biometric. Polynomial interpolation allows correction of some false identifications. The reconstructed polynomial produces the key.

Most of the flaws in fuzzy vault are due to the use of stenography for protection [9]. A matching set can only be used with one secret securely, since the points in the vault are not protected. Insiders can insert their own matching set into the chaff points, creating a vault that accepts more than one user. Knowledge of the key allows the identification of the matching set. Despite these severe security flaws, the concept of fuzzy vault has been used to make effective biometric authentication systems [10].

Fuzzy Extractor

Fuzzy Extractor is another system based on fuzzy commitment [8]. Fuzzy extractor focuses the error correction code on the biometric. However, the error correction code now outputs a corrected biometric instead of a key. Fuzzy Extractor hashes the biometric to produce a key.

A biometric is encoded with error correction bits. The error correction bits are stored as helper data. During use, a user submits a new biometric sample. The sample is mixed with the error correction bits. The resulting codeword is decoded to produce the original input. The biometric is hashed to produce a key.

Fuzzy Extractor is defined broadly, allowing the error correction to operate over any metric space. However, it needs a stable representation for the error correction to work properly. Using fuzzy extractor with standard minutia representations results in poor accuracy [11].

Review

The primary failure of these systems is the biometric representation. Fuzzy Commitment and Fuzzy Extractor systems perform operations on bit strings while fuzzy vault performs operations on points. These are not natural representations for biometrics. Better representations are needed.

Local Structure Representations

Introduction

Fingerprints have a lot of structure. Fingerprint minutia are points where ridges end or bifurcate [5]. Minutia extracts much of the relevant information from a fingerprint. However, minutia are vulnerable to translation and rotations of the biometric. Local structures can be formed from these points which are translation and rotation invariant. Minutia pair and minutia triangle representations are two examples of local structures.

Minutia Pair representation

Minutia pair representations are among the simplest forms of translation and rotation invariant representations. It consists of distances between two points. However, these elements lack distinctiveness. Many pairs will have the same distance between them.

Graphs are an easy way to extract more distinctive information from the pair data. Pairs are linked to form larger graphs. The simplest graphs require only the distance data. More sophisticated graphs include minutia orientation data to provide additional distinctiveness to pairs.

Minutia triangle representation

Minutia triangle representations are transformations of minutia data into triangles. These triangles are rotation and translation invariant. The larger structures provide more data, and therefore distinctness, than minutia pair representations. Common information extracted from the triangles is the pairwise distance between points and the angles between the sides of the triangles. Some systems also use the orientation of minutia. They can be practically matched without the construction of larger structures such as graphs.

Systems

Minutia pair representations

Minimum distance graphs

A minimum distance graph is perhaps the simplest graph that can be constructed from minutia pair data. This implementation [12] builds the graph starting from the core point. The nearest neighboring point is added to the graph. This process is iterated until a sufficiently large graph is formed or the minutia points are spent.

The minimum distance graph does not need alignment due to its use of the minutia pair representation. It requires identification of the core point. The enrolled template consists of only one possible graph that the user may generate.

The system does not handle intra-user variation well. Some minutia insertions or deletions will significantly change the minimum distance graph.

Security is provided by the local transformation and by a template specific PIN. Recovery of the biometric from the minutia pair data is non-trivial. However, the minimum distance graph excludes minutia from some regions, possibly simplifying reconstruction. The storage of the core point also simplifies reconstruction. The overall effect of this information is not well analyzed by the paper. The template specific PIN scrambles the location of points before construction of the graph. This allows the construction of multiple independent templates, giving the system renewability.

Revocable Biotoken

Revocable biotokens use a more sophisticated matcher based on the Bozorth matcher [13]. Minutia pair distances and minutia orientations are used to build graphs. It links edges based on orientation, and a node may have multiple connecting edges.

Very similar graphs are likely to be from the same user, while very different graphs are likely to be from different users. The balance between the two is managed empirically. The reduction of different threshold values (e.g. distance and angle thresholds) to a single match score simplifies the decision process.

Security is the biggest improvement presented by revocable biotokens. The minutia pair distance is quantized. The integer portion is cryptographically secured and the residual is stored unprotected for increased accuracy. Additionally, the minutia pair transformation removes location data from the template.

Minutia triangle representations

Fuzzy Feature representation

The fuzzy feature representation system is based on minutia triangles [14]. The invariants of the triangles are extracted to vectors which can be compared for a match. The vector comparison is performed approximately. A vector from the probe and gallery are paired, and a match score is generated between them. The total matcher score is a weighted sum of the individual triangle vector match scores.

Intra-user variation is managed by a minutia triangle similarity. The triangle sets from a user are assumed to be similar while triangle sets from others are assumed to be different. These assumptions are validated by experiments on standardized fingerprint databases.

This system demonstrates the practicality of minutia triangle representation in matching. The authors make no attempts to improve system security beyond the passive protection afforded by the transformation.

Combined Systems

Introduction

Biometric key management and local transformations complement each other. Biometric key management allows the use of normal matching operations, simplifying the authentication process. Local structure representations provide stability over a large class of intra-user variation.

Systems

Bipartite Biotoken

Bipartite biotokens demonstrate the utility of minutia pair representations and key binding [10]. The low individual distinguishability of pair distance is overcome by combining many pairs into larger graph structures. The security flaws of Fuzzy Vault are overcome, allowing the binding of keys to a biometric.

Key binding within bipartite biotokens is based on Fuzzy Vault like polynomial interpolation. Unlike fuzzy vault, bipartite biotokens do not store the evaluation location or use chaff points. Bipartite biotokens store the polynomial evaluation value with the minutia pair representation. It relies on the stability of revocable biotokens to reproduce evaluation locations, and pairs the locations with their associated values. Polynomial interpolation on the location-value pairs reproduces the key.

Security for bipartite biotokens is provided primarily through cryptographic operations and by the local transform. Bipartite biotokens are based on revocable biotokens and share many of their security characteristics, including cryptographically protected templates. Bipartite biotokens demonstrate the ability to bind keys of up to 1024 bits.

Fingerprints with error correction codes

Fingerprints with error correction codes demonstrate the utility of minutia triangle representations and key generation [15]. The authors show how to construct a sufficiently stable bit string from the minutia triangles. This stable input allows for Fuzzy Extractor-like use of error correction codes and hash functions.

The minutia triangles are represented as vectors. The space of these vectors is divided, and the distribution of vectors with respect to this division produces a bit string. Linear Discriminant Analysis (LDA) is used to reduce the correlations in the bit string and to reduce it to a fixed size. An error correction code can then be applied to the bit string to correct for intra user variation. The bit string is hashed to produce a key.

This system utilizes statistical analysis (e.g. LDA) to increase inter-user distance for a given bit string length. This represents one of the few attempts to actively correct for inter user variation in biometric fingerprint matchers currently in the literature.

Bit string reduction and local transformation prevent recovery of the biometric. The authors do not present an analysis of how much protection this provides.

The security of the generated key depends on the error encoding used. The author recommended system provides 48 bits of security against attempts to find a feature vector that can reproduce the key.

Discussion