EXTERNALIZED FINGERPRINT MATCHING Claude Barral, Jean-Sébastien Coron, David Naccache

Gemplus Card International Since the 9/11 tragedy fingerprints have rallied significant support as the biometric technology that will probably be most widely used in the future.

The fingerprint’s strength is its acceptance, convenience and reliability.

It takes little time and effort for somebody using a fingerprint identification device to have his or her fingerprint scanned.

Studies have also found that using fingerprints as an identification means is the least intrusive of all biometric techniques. Verification of fingerprints is also fast and reliable. Users experience fewer errors in matching when they use fingerprints versus many other biometric methods.

Biometric System: General Outline

Generally, a fingerprint biometric system comprises four modules:

• A capture unit, which acquires the raw biometric fingerprint data D of an individual (typically a bitmap).

• A feature extractor f in which the acquired biometric data is processed to extract a feature-set f(D) that models D. Typically f(D) is the position of ridge bifurcations / endings in D (points called minutiae).

• A matcher μ in which an extracted feature-set f(A) can be compared to a reference f(B). This outputs a score 0 ≤ score = μ(f(A), f(B)) ≤ 1.

• A decision-maker in which the user’s claimed identity is either accepted or rejected based on the matching score: if score > α return accept else reject. α is a security parameter.

Figure 1. Different Minutia Types Figure 2. Minutiae in a Fingerprint Figure 3. Processing a Fingerprint Bitmap

5

Figure 4. Fingerprint Matching

6

FAR and FRR

The performance of a biometric system is described by the probability distributions of genuine and impostor matching scores. A genuine matching score is obtained when two feature sets corresponding to the same individual are compared, and an impostor matching score is obtained when feature sets belonging to two ≠ individuals are compared. When a matching score > α, the two feature sets are declared as belonging to the same individual; otherwise, they are assumed to belong to two ≠ individuals.

Thus, there are two types of errors associated with a biometric system:

• A false accept, which occurs when an impostor matching score happens to exceed α.

• A false reject, which occurs when a genuine matching score doesn’t exceed α.

The Matching Problem

Let f(D) and f(D′) be the representation of the template and input fingerprint, respectively. Here the representation f is a feature vector (of variable length) whose elements are the fingerprint minutiae. Each minutia may be described by a number of attributes, including its location in the fingerprint image, orientation and type (e.g. termination / bifurcation). Most common minutiae matching algorithms consider each minutia m as a triplet {x, y, θ} that indicates the x, y minutia location coordinates and the minutia angle θ:

\begin{aligned}f(D) & = & \{m_{1}, m_{2}, ⋯, m_{n} & \} & , & m_{i} = \{x_{i}, y_{i}, θ_{i}\} \\ f(D′) & = & \{m′_{1}, m′_{2}, ⋯, m′_{n′} & \} & , & m′_{i} = \{x′_{i}, y′_{i}, θ′_{i}\} \end{aligned}

The Matching Problem

A minutia m′_{j} ∈ f(D′) and a minutia m_{i} ∈ f(D) are considered matching, if the spatial distance (sd) between them is smaller than a given tolerance r_{0} and the direction difference (dd) between them is smaller than an angular tolerance θ_{0}:

sd(m′_{j}, m_{i}) = \sqrt{(x′_{j} − x_{i})^{2} + (y′_{j} − y_{i})^{2}}  ≤ r_{0}  (1)

and

dd(m′_{j}, m_{i}) = min(|θ′_{j} − θ_{i}|, 360^{∘} − |θ′_{j} − θ_{i}|) ≤ θ_{0}  (2)

FAR and FRR

Equation (2) takes the minimum of |θ′_{j} − θ_{i}| and 360^{∘} − |θ′_{j} − θ_{i}| because of the circularity of angles (the difference between angles of 2^{∘} and 358^{∘} is only 4^{∘}). The tolerance boxes (or hyper-spheres) defined by r_{0} and θ_{0} are necessary to compensate for the unavoidable errors made by feature extraction algorithms and to account for the small plastic distortions that cause the minutiae positions to change.

Aligning the two fingerprints is a mandatory step in order to maximize the number of matching minutiae. Correctly aligning two fingerprints requires displacement (in x and y) and rotation (θ) to be recovered.

The Matching Problem

Let map(.) be the function that maps a minutia m′_{j} ∈ f(D′) into m′′_{j} according to a given geometrical transformation; for example, by considering a displacement of [Δx, Δy] and a counterclockwise rotation θ around the origin (whatever origin means...):

map_{Δx,Δy,θ}(m′_{j}) = m′′_{j} = {x′′_{j}, y′′_{j}, θ′_{j} + θ}

where

[ \begin{matrix}x′′_{j} \\ y′′_{j} \end{matrix} ] = ( \begin{matrix}cos θ & − sin θ \\ sin θ & cos θ \end{matrix} ) [ \begin{matrix}x′_{j} \\ y′_{j} \end{matrix} ] + [ \begin{matrix}Δx \\ Δy \end{matrix} ]

The Matching Problem

Let ζ(.) be an indicator function that returns 1 when the minutiae m′′_{j} and m_{i} match according to Equations (1) and (2):

ζ(m′′_{j}, m_{i}) = \{ \begin{matrix}1 & if sd(m′′_{j}, m_{i}) ≤ r_{0} and dd(m′′_{j}, m_{i}) ≤ θ_{0} \\ 0 & otherwise \end{matrix}

The the matching problem can be formulated as:

maximize ∑_{i=1}^{n} ζ(map_{Δx,Δy,θ}(m′_{P (i)}), m_{i}) (3)
Δx,Δy,θ,P

where P (i) is an unknown function that determines the pairing between f(D) and f(D′) minutiae.

In Detail...

In particular, each minutia has either exactly one mate in the other fingerprint or has no mate at all:

1. P (i) = j indicates that the mate of the m_{i} ∈ f(D) is m′_{j} ∈ f(D′)

2. P (i) =⊥ indicates that m_{i} ∈ f(D) has no mate in f(D′)

3. an m′_{j} ∈ f(D′) such that ∀i = 1, ⋯, n P (i) ≠ j has no mate in f(D)

4. ∀i = 1, ⋯, n ∀k = 1, ⋯, n′ ⇒ P (i) ≠ P (k) or P (i) = P (k) =⊥ (this requires that each minutia in f(D′) is associated with at most one minutia in f(D)).

When (Δx, Δy, θ) Is Known

Expression (3) requires that the number of minutiae mates be maximized, independently of how strict these mates are; in other words, if two minutiae comply with Equations (1) and (2), then their contribution to expression (3) is made independently of their spatial distance and of their direction difference.

Solving the minutiae matching problem (expression (3)) is trivial when the correct alignment (Δx, Δy, θ) is known; in fact, the pairing (i.e. the function P) can be determined by setting for each i = 1, ⋯, n:

• P (i) = j if m′′_{j} = map_{Δx,Δy,θ}(m′_{j}) is closest to m_{i} among the minutiae.

{m′′_{k} = map_{Δx,Δy,θ}(m′_{k}) | k = 1, ⋯, n, ζ(m′′_{k}, m_{i}) = 1}

• P (i) =⊥ if ∀k = 1, ⋯, n, ζ(map_{Δx,Δy,θ}(m′_{k}), m_{i}) = 0

The Closest Is Not Necessarily The Best!

To comply with constraint 4 above, each minutia m′′_{j} already mated has to be marked, to avoid mating it twice or more. Figure 5 shows an example of minutiae pairing given a fingerprint alignment.

To achieve the optimum pairing (according to Equation (3)), a slightly more complicated scheme should be adopted: in fact, in the case when a minutia of f(D′) falls within the tolerance hyper-sphere of more than one minutia of f(D), the optimum assignment is that which maximizes the number of mates (refer to Figure 6 for a simple example).

How To Maximize?

The maximization in (3) can be easily solved if the function P (minutiae correspondence) is known; in this case, the unknown alignment (Δx, Δy, θ) can be determined in the least square sense. Unfortunately, in practice, neither the alignment parameters nor the correspondence function P are known and therefore, solving the matching problem is very hard. A brute force approach, that is, evaluating all the possible solutions (correspondences and alignments) is prohibitive as the number of possible solutions is exponential in the number of minutiae (the function P is more than a permutation due to the possible ⊥ values). Hence heuristics are used.

Two Examples

In figure 5 minutiae of f(D′) mapped into f(D) coordinates for a given alignment. Minutiae of f(D) are denoted by ⊙s, whereas f(D′) minutiae are denoted by ×s. Note that f(D′) minutiae are referred to as m′′, because what is shown in the figure is their mapping into f(D) coordinates. Pairing is performed according to the minimum distance. The dashed circles indicate the maximum spatial distance. The gray circles denote successfully mated minutiae; minutia m_{1} of f(D) and minutia m′′_{3} of f(D′) have no mates, minutiae m_{3} and m′′_{6} cannot be mated due to their large direction difference.

Figure 5. Mating

18

In figure 6, if m_{1} were mated with m′′_{2} (the closest minutia), m_{2} would remain unmated; however, pairing m_{1} with m′′_{1}, allows m_{2} to be mated with m′′_{2}, thus maximizing Equation (3).

Figure 6. Mating with a Second-Closest

Fingerprint Match On Card

Why match on card? Typically, an accept will ’open’ the card and permit access to some of its EEPROM files, enable the generation of a digital signature or debit a purse.

It is customary to require that these steps take place in less than a second (convenience). When coded in a card a matching algorithm would use at least 2,000 bytes of RAM. Code would usually occupy 2,000 to 12,000 ROM bytes.

Code complexity (matching involves many floating-point trigonometric operations) and RAM consumption are two decisive cost factors in the design of such solutions.

Finally... This Paper’s Contribution

A novel solution to this problem. The solution, called Externalized Fingerprint Matching, allowing to implement μ in simple (microprocessor-less) memory cards. This is particularly important for addressing cost-effectively very large markets (e.g. China, 1.3 billion inhabitants) and for deploying disposable biometric IDs such as visas, hotel room keys or visitor/subcontractor badges.

Externalizing the Fingerprint Matching

The new idea: add false minutiae to f(D) and have the card challenge the reader to find out, based on the incoming scanner acquisition, which minutiae are genuine. The enrolment protocol is the following:

1. The issuer extracts f(D), picks a set of random minutiae r and merges it into f(D). We denote the result of this operation by t = f(D) ∪ r. The issuer encodes t as a binary string u where bit u_{i} = 1 if the i-th minutia in t belongs to f(D) and u_{i} = 0 if the i-th minutia in t belongs to r.

2. The issuer signs, using a public-key signature scheme the data {t, u, d} where d is a security parameter which choice is discussed below. Let σ be the signature of {t, u, d}.

3. The issuer delivers an identity card containing {t, u, d, σ}. The card allows the free reading of t and d.

↭

Figure 8. Fingerprint Scrambling with False Minutiae

⋃  =

Figure 9. Fingerprint Scrambling with False Minutiae

Identification

1. The terminal receives from the scanner a candidate D′.

2. The terminal reads t from the card and partitions t (based upon D′) into two sets t = t_{true} ∪ t_{false}. The terminal encodes this partition as a binary string u′ where bit u′_{i} = 1 iff the i-th minutia in t belongs to t_{true}. The terminal sends u′ to the card.

3. The card computes w = u ⊕ u′. If the Hamming weight of w (denoted H(w)) is smaller than d the card outputs σ and u. At this step the card considers that the presented finger is legitimate.

4. The terminal verifies σ with respect to the issuer’s public-key and if σ is correct and H(u ⊕ u′) ≤ d then the terminal considers that the scanned finger and the card match each other and are approved by the issuer.

Computing The FAR

A somewhat intricate formula given in the paper.

The correct fingerprint is characterized by the reference vector u whose length is n + m and whose Hamming weight is n. Letting FAR = 10^{−e} typical {n, m} values for e = 5 and d = 0 would be: {6, 17}, {7, 14}, {8, 12}, {9, 11}, {10, 10}, {11, 9}.

Variations in d

Variations in d affect the FAR as shown in the graphics below:

Figure 10. FAR for d = 4.

Variations in d

Figure 11. FAR for m = n and different d values.

Assumptions Underlying The FAR Evaluation

Assumption 1. Spatial Uniformity Assumption: The probability to find a minutia at any given {x, y} coordinate in f(D) is constant.

In other words, the simplified FAR estimate assumes that there are no denser or scarcer areas in f(D) and that minutiae are independent of each other i.e., knowing that a minutia m exists at a given {x, y} location does not provide any information about the would-be existence (or type) of minutiae at m’s neighborhood.

Assumption 2. Biometric Scrambling Assumption: There exists an probabilistic algorithm A taking as input f(D) and outputting a t = f(D) ∪ r such that partitioning t into the original subsets f(D) and r, even approximately, is intractable.

Physical ID Applications

In a typical national ID application, an agent using a portable secret-less biometric reader must ascertain that a physically present individual is associated to a data Q. Usually Q encodes the surname, given names, dates of issue and expiry, color of eyes, residence etc. In the sequel we assume that σ also signs Q

Given that the portable reader is under the agent’s total control the display of Q on the reader’s screen provides the officer with a binding between the physically present individual and Q.

Note (as is the case with all other match-on-card protocols) that biometry alone cannot provide a binding between the ID (physical support) and the individual but only between Q (the information) and the individual. To provide also a binding between the ID and the individual the ID must be enriched with active digital signature or zero-knowledge capabilities.

Internet Login and On-Line Access Applications

As is the case with passwords and other biometric protocols, one cannot require resistance against parties who witnessed a successful biometric identification session (or participated in it). However, we do require that a party who never witnessed a successful session will be unable to mimic the legitimate user and his card, even under the (very adversarial) assumption that the attacker managed to steal the user’s ID card.

Given that the card will only reveal w when the interrogator proves to it that he knows already an extremely close approximation of w, the thief will not be able to retrieve f(D) from the ID card and mimic the user’s presence on the other side of the communication line.

Note That:

As is the case with passwords and other biometric protocols, a remote user can always voluntarily ’delegate’ (lend) his D and σ to friends or colleagues. To prevent this and ascertain that the ID card is physically present at the other side of the line, the ID card must be enriched with active public-key capabilities. Note that even such a capability will never ascertain that the user did not voluntarily give the physical ID plus D to the friend or the colleague.

Access to Card Inner Data Applications

In many settings, one wishes to bind the enabling of an on-card function to the user’s presence. A typical example is an electronic purse where a debit function is activated only after successfully recognizing the user’s D. This provides an excellent protection against card theft and subsequent illegal debit.

Note that unless the capture unit is embedded in the card (such capture units are marketed by several suppliers today), a user can, again, voluntarily lend his D to a friend (although in most cases debit operations are done in front of merchants). Other applications of access control to inner card data consist in accessing private files on a memory stick or medical data in a health cards.

Conclusion

The above shows that although extremely economic (from an on-board resource consumption perspective), the protocol presented in this paper provides equivalent functionalities to other match-on-card techniques in all typical use-cases.