Fingerprint matching

The present invention relates to secure computation of a measure of similarity between two sets of data, when these sets have different size. More specifically, the invention relates to matching of biometric templates, and in particular to minutiae based fingerprint matching.

When using biometric information, such as a fingerprint, to authenticate the identity of a person, typically a fingerprint template acquired by a sensor is compared to reference data stored in a secure database. The reference data can be obtained through an enrollment process, linking the identity of the person to a template of his/her fingerprint.

In order to preserve privacy, and increase security, of such a matching process, various ways have been proposed to preserve the privacy of the user, and to increase the security of the system. In such approaches, encryption, e.g. homomorphic threshold encryption, is used to perform the matching process without disclosing or sharing sensitive information. A drawback with these solutions is that they in general require that the data sets to match are of equal length. In reality, this is often not the case, and for example in the case of minutiae based fingerprint matching, the number of minutiae in each acquired template is not constant, and strongly depends on the presented fingerprint.

It is an object of the present invention to overcome this problem, and to enable matching of data sets of unequal length and thereby provide secure authentication.

According to the invention, this and other objects are achieved by a method for authenticating a claimed identity, comprising acquiring a first set of data, generating a first set of filters, associated with said first set of data, receiving a second set of filters, associated with a previously stored set of data associated with said claimed identity, for each filter in said first filter set, determining with which filter in said second set it has the greatest correlation, determining a first subset of said first set of data, including data corresponding to filters in said first set of filters that have a greatest correlation exceeding a given threshold

(Tl), determining a measure of similarity between the first subset and a second subset of the second set of data, the second subset including data corresponding to filters in said second set of filters that have a greatest correlation exceeding said given threshold (Tl), the first and second subsets having equal length, in order to authenticate the claimed identity. According to this approach, correlation between the two filter sets is used to establish which data elements correspond to each other. The data sets are then reduced to form subsets containing only these corresponding elements, and therefore being equal in size. These subsets can then be used to determine a measure of similarity, for example using existing conventional measures such as Euclidian distance or ridge distance. The claimed identity is typically the identity of a person, but the invention is not limited to personal identification. On the contrary, the claimed identity may relate to a request for access of data or physical access of premises, requiring some type of access code (the first data set), e.g. provided from a physical object like e.g. a physical unclonable function (PUF). The filters associated with the data sets are selected such that a high correlation between filters will indicate similar data elements. In the case of fingerprint minutiae, the filters are advantageously based on a surrounding of the minutiae point, i.e. an area of the fingerprint much smaller than the entire fingerprint. An example of useful filters are rotation invariant filters, which can be based on Fourier, Mellin, Gabor, or wavelet transforms of such surroundings.

Preferably, the method comprises verifying that the resulting first subset includes at least a predetermined number of elements. If not, the authentication is denied, as no reliable matching can be performed.

According to a preferred embodiment, the first set of filters is generated by a first party, the second set of filters is received in encrypted form from a second party, and the step of determining correlation is performed under the encryption. In such a case, each maximum correlation can be compared with the given threshold using a secure two party protocol. According to such a protocol, homomorphic threshold encryption can be used to determine if the product (correlation) between the first filter and the encrypted second filter exceeds the given threshold without sharing information about the actual filters. Details of such a two party protocol is described in European patent application EP030784375 (PCT application IB2004/052259) [attorney docket NL031322].

The step of determining a measure of similarity is preferably also performed under the encryption using a secure two party protocol, thus avoiding sharing information

about the actual data sets. Such a two party protocol is described in US patent application 60/668905 [attorney docket NL041335].

According to one embodiment, the step of determining the measure of similarity includes calculating a matrix of pairwise differences for each of the subsets, and determining if a distance between said matrices is less than a third given threshold.

The second set of filters can include at least one random filter, adapted to result in no correlation with any filter in said first set of filters. By including such random filters in the second set of filters, the security of the authentication process is further enhanced. An intruder attempting to respond to the filter set received from the second party (the verifier), will not know which of the filters that are random, and thus should result in no correlation. If the random filters do not result in negligible correlation, the second party (the verifier) can refuse the authentication.

The step of determining correlation, and/or the step of determining a measure of similarity at least in part are outsourced to at least one secure server. This can be viewed as an alternative, or a complement, to using secure two party protocols as mentioned above.

The object according to the invention is further achieved by a device for authenticating a claimed identity, comprising means being arranged to implement the method according to the invention, and by a computer program product comprising computer executable instructions being arranged to, when loaded and executed, implement the method according to the invention.

This and other aspects of the present invention will now be described in more detail, with reference to the appended drawings showing a currently preferred embodiment of the invention.

Fig. 1 shows a schematic block diagram of a system for identification and authentication suitable for implementing the present invention.

Fig. 2 shows a flow chart of a method according to an embodiment of the invention.

The process of biometric authentication has two parts, the enrollment and the authentication. During the enrollment authentication data, such as a fingerprint template is stored in a database in association with a specific identity or authorization. During the

authentication, a template is acquired together with a request to a service, such as access to information or physical access to a location.

Figure 1 shows a system for identification and authentication of an individual based on biometric data associated with the individual, in which system the present invention advantageously may be employed. The system 100 includes an enrollment device 110 for performing the enrollment procedure, and an authentication device 120 for performing the authentication procedure.

The enrollment device 110 comprises a measuring device such as a fingerprint sensor 112 for acquiring raw biometric data, e.g. fingerprints, iris or retinal, facial or hand geometry, voice features etc. In the present example, the data is a fingerprint 101.

The enrollment device 110 further includes a processor 114 for generating the auxiliary data that has to be used during the authentication phase. The processor may be any suitable processor, such as a general purpose processor under the control of a control program, which may be stored in a non- volatile memory. In order to enhance security, the enrollment device may be placed in a secure environment, and parts of the processing steps may be executed in a secure module, such as a cryptographic module. The authentication data is stored in a database 130, accessible from the authentication device 120. The database 130 may be incorporated into the enrollment device 120.

In order to clarify the difference between enrollment and authentication, the authentication device 120 is illustrated in fig 1 as a separate device, but it will be realized by the skilled person that the authentication device and the enrollment device may be the same structure.

The authentication device 120 includes a measuring device such as a fingerprint sensor 122. It is preferable that the sensors 112 and 122 are of similar device in order to minimize any differences occurring during scanning of e.g. the fingerprint 105.

The authentication device 120 further includes a processor 124 for comparing the properties acquired by the sensor 122 with the authentication data stored in the database 130 and communicated to the authentication device 120. The processor may be of similar kind as used in the enrollment device 110. During enrollment, the user provides a certification authority (CA) with his fingerprint template, by using the sensor 112 of the enrollment device 110 to scan a fingerprint image. Using some standard algorithm, the processor 114 determines a set of minutiae: (xi; V ₁ ; θi)i _{= 1; : : : ; n} , where Xi, yi are the x- and y-coordinates of the i'th minutiae, and θi is the direction of the ridge field. For each minutiae i, the processor 114 also generates a

(correlation) filter Fi using some part of the fingerprint image around (xi; yi). The processor 114 also computes a matrix of pair-wise distances, D = (dki)k;i ₌ i;:::;n, where dki = (Xk - xi) ² + (yk - V ₁ ) ² + w * (θk - B ₁ ) ² or dki = r^ + w * (θk - B ₁ ) ² , r^ is the ridge distance between the minutiae's k and 1, which is defined as a number of ridge lines crossed by a straight line connecting points (xk; yk) and (X ₁ ; V ₁ ), and w is a weight factor.

The user and CA both choose secret keys ku and kcA, respectively. A common public key k _Pl3l is constructed from ku and kcA (e.g. using a known procedure such as the one described in B. Schoenmakers, P. Tuyls, Practical Two-Party Computation based on the Conditional Gate, In proceedings of Asiacrypt 2004, volume 3329 of Lecture Notes in Computer Science, pages 119-136, Berlin, 2004. Springer- Verlag). Using the key k _Pl3l , the matrix D = (dki) and the filters Fi, i _{= 1; : : : ; n} are encrypted using a homomorphic encryption algorithm E and stored in the database 130 as E(D) and E(Fi).

During authentication, a fingerprint image is scanned by the sensor 122, and the processor 124 performs an authentication procedure based on this acquired fingerprint template and the encrypted information stored in the database 130. According to the invention, this procedure involves running a secure two party computation protocol between a "sensor", here the authentication device 120 and a remote party (referred to as a "verifier"). For simplicity, it is here assumed that this remote party is the enrollment device 110, but in principle this party could be separate from the enrollment device, as long as it has access to the authentication data and the secret key kcA-

First, in step Sl, the sensor (e.g. the processor 124 in the authentication device 120) repeats the steps performed by the CA. Namely, a set of minutiae (χ _{j 5} y ₃ β _j ) is extracted, and the corresponding filters G _j are created, j = 1 ; : : : ;m. The distance matrix

D = (d _kl ) , k;l=l ; : : : ;m is also computed according to the equation above. Note that the number of extracted minutiae m is not necessarily equal to the number of minutiae extracted during the enrollment, e.g. due to a noisy measurement, nor does the first minutiae in the acquired set necessarily correspond to the first minutiae in the authentication data.

Next, in steps S2 - S9, the sensor and the verifier establish the correspondence between their respective sets of minutiae, in order to select a number of corresponding minutiae to base the similarity measure upon.

For each minutiae point in its set, the verifier transmits the encrypted filter

E(Fi), to the sensor (step S2). For each j = 1; : : : ;m, the sensor then computes a an encrypted

correlation between the filters F ₁ and G ₃ , by computing the encrypted convolution between the filters, Q _1J =E(Cy)=E(F^G _j )= E(∑ F ₁ (t)G _D (t)) (step S3). As the encryption is t homomorphic, this corresponds to computing , which is convenient, as the sensor has access to the encrypted filter E(F ₁ ) and the plain text filter G _j . An index j* is selected such that c _lj* =max(c _lj ) (step S4).

In step S5 - S6 the sensor and the verifier run a secure two-party protocol in order to determine if the correlation C _1J* exceeds a predetermined threshold, Tl. A protocol to allow such a determination, without revealing cij, has been described in European patent application EP030784375 (PCT application IB2004/052259) [attorney docket NL031322], which is hereby incorporated by reference.

IfC _1J* is indeed larger than Tl, both the sensor and the verifier include these indices i and j* in lists Is and Iy so as to create index lists Is and Iy for defining subsets of matched minutiae, (X ₁ ; V ₁ ; θ,), e Iv and (x _{j 5} y _D β _D ) _} e h (steps S7 - S8). Steps S2 - S8 are then repeated for all filters F ₁ (step S9, SlO). At the end of this processing, both the sensor and the verifier will have constructed sets of equal length. To facilitate reliable fingerprint matching, these lists must be sufficiently large. Hence, if the number of points in these sets are fewer than a second threshold T2, authentication is refused (step Sl 1). Note that step 11 of course may be performed in the verifier. At this point, a sufficient number of corresponding minutiae have been selected. However, this is not enough for a match. Next, it must be determined that these minutiae are part of the same fingerprint, and this can be accomplished by using the matrices of pair-wise distances.

During the matching step, the verifier forms a reduced matrix of encrypted distances, My = (m,i, $), \\, i ₂ e Iy (step S12). The sensor creates a matrix Ds = (d _jld 2),

J ₁ J ₂ G Is- and encrypts it with the public key k _Pl3l , forming a matrix Ms= E(Ds) (step Sl 3). Finally, using the encrypted matrices My and Ms, and by running a secure two party protocol the verifier and the sensor check whether |d _ll>l2 - d _jld 2| < T3 for all pairs of matching minutiae, and where T3 is another threshold (steps S14 - S15). A protocol to allow such a determination, without revealing the distances d, has been described in US patent application 60/668905 [attorney docket NL041335], which is hereby incorporated by reference.

If the outcome of this check is affirmative, the authentication is successful.

According to one embodiment, the set of filters Fi includes at least one random filter, causing only negligible correlation with any one of the filters Gi. The verifier will hence expect to receive no correlation for these filters. An intruder attempting to deduce information from the verifier will not know which filters that are expected to return negligible correlation. If such an intruder indicates high correlation for any one of these random filters, the authentication can be refused by the verifier. By including one or several such random filters, the security of the system may thus be further enhanced.

The person skilled in the art realizes that the present invention by no means is limited to the preferred embodiments described above. On the contrary, many modifications and variations are possible within the scope of the appended claims. For example, instead of, or in combination with, using secure two-party protocols as mentioned above, the step of determining correlation, and/or the step of determining a measure of similarity can be at least in part outsourced to a secure server, or a network of secure servers. As mentioned above, the present invention may also advantageously be used also to other kinds of biometrics, and authentication of physical objects.