Abstract
Biometrics plays an important role in authentication applications since they are strongly linked to holders. With an increasing growth of e-commerce and e-government, one can expect that biometric-based authentication systems are possibly deployed over the open networks in the near future. However, due to its openness, the Internet poses a great challenge to the security and privacy of biometric authentication. Biometric data cannot be revoked, so it is of paramount importance that biometric data should be handled in a secure way. In this paper we present a scheme achieving privacy-preserving fingerprint authentication between two parties, in which fingerprint minutiae matching algorithm is completed in the encrypted domain. To improve the efficiency, we exploit homomorphic encryption as well as garbled circuits to design the protocol. Our goal is to provide protection for the security of template in storage and data privacy of two parties in transaction. The experimental results show that the proposed authentication protocol runs efficiently. Therefore, the protocol can run over open networks and help to alleviate the concerns on security and privacy of biometric applications over the open networks.
1. Introduction
Biometric characteristic, such as fingerprint, face, and iris, has been used to a higher level of security in order to cope with an increasing demand for reliable and highly usable information security systems. Currently, most practical biometric systems handle biometric data locally, or in secure local network. When they are migrated directly to an open network which is in partly secure or insecure environments, the inherent risks of privacy and security of traditional biometric technologies will be blown up. Jain et al. [1] analyze the vulnerabilities about biometrics to intrinsic failures and potential attacks by adversaries. One of the most serious risks is compromising the template database, which will exert a disastrous impact on the whole authentication system. Besides, a new challenge of privacy and security arises since a remote server and a user may not trust each other before the authentication. Their respective data should not be directly delivered to each other as in a usual biometric system. These data, as the private data, must not be leaked to each other during the authentication. Therefore, the template and the privacy protection are the key challenges for any biometric system deployed over the open network and must be properly addressed.
Among many solutions to privacy-preserving biometrics, some schemes focus on constructing a transformed template with noninvertible transformation, including fuzzy commitment [2], fuzzy vaults [3], biohashing [4], fuzzy sketch/fuzzy extractor [5], cancelable template [6], and random local region descriptor (RLRD) [7]. In these schemes, the researchers try to prevent biometric information being revealed from the transformed template by one-way transformation. However, some of them, for example, fuzzy vault, biohashing, and cancelable template, are proven to be vulnerable to attacks [8–10]. Though fuzzy sketch scheme is theoretically complete and secure, it complies with stronger requirements than what suffices in practice, which leads to degradation of accuracy.
Some researchers employ cryptographic technique to achieve privacy protection, which has a solid theoretical foundation. They have designed privacy-preserving protocols by resorting to secure two-party computation, where two nontrusted parties cooperate to carry out a computation without revealing their own inputs. Bringer and Chabanne [11] proposed a biometric authentication protocol which can protect the sensitive relationship between the biometric template and the relevant pseudorandom username, which is based on the homomorphic properties of Goldwasser-Micali and Paillier cryptosystems. Tang et al. [12] developed two concepts of biometric privacy called identity privacy and transaction anonymity, respectively, and presented an authentication protocol employing Private Information Retrieval protocols which was based on the ElGamal cryptosystems. In both works, however, the type of biometrics is limited to those which can be represented as binary strings because their protocols only computed the Hamming distance between biometric templates in the encryption domain. Erkin et al. [13] designed a privacy-preserving face recognition protocol based on additive homomorphic encryption, in which Euclidean distances between feature vectors or finding a minimum are computed by using the homomorphic property of the cipher texts. The protocol of Erkin requires large network traffic and a large memory, which makes those systems less practical. Sadeghi et al. [14] improved the performance by combining homomorphic encryption with garbled circuits. Barni et al. [15] employed fingercode [16] as a feature along with the technique similar to Sadeghi et al. [14] to realize privacy-preserving system for fingerprint-based identification. Huang et al. [17] provided further improvement for the privacy-preserving identification protocol by elaborate optimizations such as packing method, carefully integrating the subtraction and comparison computations, and backtracking technique. Upmanyu et al. [18] designed “blind” authentication protocol in which some classifiers such as linear, support vector machines, and neural networks were realized by using multiplicative homomorphic encryption. However, the experience of biometric recognition proved that, in most cases, direct matching shows a better performance than classifiers because, in practical applications, it is difficult to gather enough biometric samples of one person to train the classifier.
In this paper, we propose a solution to fingerprint authentication with providing protection for both template and privacy. In particular, we focus on the realization of fingerprint authentication in a secure framework by implementing minutiae matching instead of fixed-length features as in the existed schemes [16–18]. We address the problem of minutiae matching in the encrypted domain by combining homomorphic encryption with gabled circuit. In the proposed scheme, the template of a user, stored on the server, is encrypted by the user’s private key, even the server learning nothing about the genuine information of the user. Therefore, our scheme shows a better performance in privacy protection than the existed schemes [16, 17].
2. Preliminaries
The primary cryptographic tools we use are homomorphic encryption, oblivious transfer, and garbled circuits. We briefly summarize each of these standard techniques here.
2.1. Additively Homomorphic Encryption
Let denote encryption of with a public key. Our constructions use a semantically secure public-key encryption scheme that preserves the group homomorphism of addition and allows multiplication by a constant. This property, which is obtained by the additively homomorphic encryption schemes, supports the following operations that can be performed without knowledge of the private key: Given the encryptions and , we can efficiently compute . Given that a constant belongs to the same group, we can compute .
There are many public-key cryptosystems satisfying the above properties. In our implementation, we use Paillier’s cryptosystem [19] which has plaintext space and cipher text space , where is a -bit RSA modulus and is the bits length of RSA.
2.2. Oblivious Transfer
1-out-of-2 oblivious transfer () allows a sender, holding strings , , to transfer to a receiver, holding a selection bit , exactly one of the inputs . The receiver learns nothing about , and the sender has no idea of . Parallel of -bit strings is denoted as . For , the sender inputs a pair of -bit strings , and the receiver inputs choice bits . At the end of the protocol, the receiver learns about the chosen string , but nothing about whereas the sender learns nothing about the choice . Oblivious transfer has been studied extensively. In this scheme, we use oblivious transfer extension scheme of Ishai et al. [20] which serves to efficiently reduce the number of computationally expensive public-key operations of to be independent of .
2.3. Garbled Circuits
Garbled circuit [21, 22] allows two parties holding inputs and , respectively, to evaluate an arbitrary function without leaking any information about their inputs. The basic idea is that a server creates an “encrypted” version of the circuit to compute , and then a client obliviously computes the output of the circuit. In more detail, for each wire of , the server randomly chooses two secrets, and , where is called garbled value of ’s value. Further, for each gate of , the server creates a garbled table which records a collection of the garbled values corresponding to the output wires of with those corresponding to the input wires. All s are transferred to a client as well as the garbled values of the server’ input. The client gets the garbled values corresponding to his input by protocol from the server. Then, the client can evaluate the garbled circuit to obtain the garbled output simply gate by gate, using the garbled tables s.
Some optimizations can be applied to the standard garbled circuit protocol. A powerful technique is “free XOR” scheme [23, 24] which eliminates the need to garble XOR gates, so XOR gates become “free,” incurring no communication or cryptographic operations. Another efficient approach [25] can reduce the size of a garbled table from four to three cipher texts for a 2-input-and-1-output gate, thus saving 25% of network bandwidth.
3. Overview
In the existing schemes [13–15, 17], the authors only considered protecting the privacy of biometric data of a user and a server, without taking the template protection into consideration. Although biometrics is assumed as public data, it should not be easy to obtain the biometric data by compromising a central server. Fingerprint is one of the biometric characteristics with the highest level of reliability. Barni et al. [15] and Huang et al. [17] both take fingercode as the feature, whose length is fixed. This helps to reduce the computational and communicational complexity. In fact, the minutiae set is the most popular feature used in practical systems because minutiae-based matching is more robust to distortions frequently encountered in practical applications, so these systems usually achieve a good accuracy. Minutiae are the endpoints and bifurcations of fingerprint ridges. Each minutia can be represented as triplet, where is the location of the minutia and angle of the associated ridge . A template of minutiae is represented as a set of points in the three-dimensional. Fingerprint matching can be reduced to finding the paired points problem. Let and denote the template and query, respectively. A minutiae-based fingerprint matching algorithm usually returns the number of matched minutiae on both and to generate similarity scores. In this paper, the matching score is calculated as follows: where is the number of paired minutiae. If is greater than or equal to a predefined threshold ; then the query and the template can be considered coming from the same finger.
A minutia in and a minutia in are considered matching if the following conditions are satisfied: where is a distance function and and are the given thresholds. In this paper, we consider two distance metrics: (i) square of Euclidean distance (for simplicity, we still call Euclidean distance) and (ii) city block distance . However, for a given minutia belonging to , the above approach might find at least one matching result belonging to , but, in fact, at most one is correct. In this paper, for a minutia and those minutiae belonging to satisfying (2) and (3), we choose the closest to as the matched minutia.
We design the privacy-preserving protocol based on the aforementioned matching algorithm, which works in the two-party setting in the semihonest attacker model. In this model, the participants do not deviate from their protocol but may use any information they obtain to their own advantage. Suppose that Bob (the server) holds a database containing the template of the users. To protect the user’s privacy, however, the template is not the original feature but its encrypted version. Thus, even Bob does not learn the user’s biometric information. Alice (the user) can update her template by choosing a new private key. When Bob receives Alice’s request for authentication, he first retrieves the encrypted template from his database. During the interactive authentication protocol, Alice provides the fresh minutiae as the inputs. She trusts Bob to correctly perform the matching algorithm but is unwilling to expose her information of fingerprint to Bob. The protocol consists of two phases: the first one is related to the blind distance computation, which is carried out by homomorphic encryption (Section 4); the second one is related to minutiae matching, which is implemented by garbled circuit (Section 5). At the end of protocol, Alice obtains the number of the matched minutiae and returns it to Bob. However, the number is represented as the garbled value, so Alice knows nothing about the genuine value. Bob decrypts it and computes the matching score. For the sake of simplicity, we just describe the content concerning distance computation and minutiae matching.
4. Blind Distance Computation
In this section, we present two protocols which compute the two kinds of blind distances of Euclidean and city block, respectively, which is the first phase in our authentication process.
4.1. Euclidean-Distance Protocol
Basic. Alice computes the distance between each minutia in and that in with the help of Bob. As mentioned in (2) and (3), there are two distances needing to be calculated: the spatial distance and the directional difference. The spatial distance discussed in this section is Euclidean distance. is the encrypted version with Alice’s private key while is in the clear. Here we denote the encrypted template as . is held by Bob. Since Alice holds the private key, to keep his privacy, Bob can blind in advance and Alice can only compute the blind distance. To do so, he blinds with the uniformly random numbers , , , from the plaintext space to get the following cipher texts by using the homomorphic property: , , , . Then he sends these cipher texts to Alice. Alice decrypts them to get , , ,and . She calculates
To further compute the blind distance, Alice needs which can be easily gotten by interacting with Bob: Alice transfers and to Bob. The latter computes and returns , where . It is easy to observe that . Alice decrypts and calculates the blind distance .
Bob further blinds with a random number by computing , where is a random number and then transfers it to Alice.
Improvement. In order to improve the efficiency of the above approach, we choose the shorter random masks and pack multiple values into a single cipher text. Assume that , , , , and are -, -, 2-, 2-, and -bit positive integers, respectively, and the random masks , , , , , and are -, -, -, -, -, and -bit positive integers, respectively. The resulting blind values , , , , and can be packed into a single cipher text. The cross item such as can also be packed. The storage size of the encrypted minutiae template can also be reduced by using the packing technique. That is, when generating the encrypted template , we firstly pad some zeros before , , , , and to increase their lengths to , , , , , respectively, and concatenate them together. As described later, we have , , , , ( is a security parameter which will be explained later). Then a unit chunk representing a minutia is written down as: The purpose of padding zeroes before each component is to prevent the possible overflow when the component is added to the corresponding mask. Therefore, one cipher text can contain minutiae. The number of cipher texts of is only . Compared with the basic approach, the method saves (% storage space. We rewrite as: , . These methods reduce the communicational and computational complexity because each cipher text carries multiple blind minutiae.
Enrollment. When Alice registers herself to Bob, she creates an encrypted template by employing the aforementioned method. She sends to Bob who stores in a safe database.
Protocol. In the authentication phase, Alice and Bob carry out the protocol EUCLIDEAN-DISTANCE to compute the blind distances of the minutiae (Algorithm 1). The detail is given as follows. For simplicity, we assume that two parties have learned the number of minutiae in the template and the query, that is, and , and exchanged the public key.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Packing Size. We have supposed that , , , , and are , , 2, 2, and bits, respectively, and random masks , , , , are , , , , and bits, respectively. To keep statistical security, we need , , , , and . In fact, our random masks are longer than the corresponding blind values by bits; that is, , , , , and . Besides, we need to handle the possible overflow of the intermediate values in computation. Therefore, the length of these values will be determined as follows: , , , , and (step 1) are -, -, -, -, and -bit values. The main task of the protocol is computing the cross item (step 4 (i)). We need bits to represent , and to represent the random mask . Accordingly, it is clear that bits are sufficient (step 2 (ii)). We pad zeros before and to form -bit and because this ensures that no overflow happens when computing (step 2 (ii)). The blind squared-distance and the blind orientation difference are -bit and -bit, respectively.
Correctness. Here, we prove that the equality in EUCLIDEAN-DISTANCE, is established. In step 2 of the protocol, since is -bit, , -bit, and , -bit binary string, respectively; in step 3, and so forth.
Similarly, and so forth. So,
and so forth.
One can further verify that
Thus,
Obviously, , which is the blind difference between and .
Security. The security of the protocol depends on whether the short masks can adequately blind the values that Bob is unwilling to reveal to Alice. Since the addition in the homomorphic encryption is computed over the integers rather than modulo addition, we only obtain statistical hiding rather than perfect hiding. If is -bit integer and is uniform -bit integer, then gives statistical security roughly for , where can stand for , , , , and . This probability can be lowered arbitrarily by choosing properly. However, a longer will increase computational and communicational complexity. Since , , and are -, -, and -bit integers, respectively, and the probability of guessing right , , and is , , and , respectively, it is sufficient that , are not less than and is not less than . Assume that is equal to ; thus, is satisfied.
Complexity. Since the computational complexity of EUCLIDEAN-DISTANCE is dominated by operations related to Paillier encryption, such as exponentiation with an exponent of length (Exp), encryption (Enc), and decryption (Dec), we only take their costs into consideration. The overall complexity of EUCLIDEAN-DISTANCE is given in Table 1. The computational complexity of the protocol can be further reduced. The operations in step 1 of the protocol can be precomputed, and, thus, Bob saves Encryption.
4.2. City-Block-Distance Protocol
In this section, we present a protocol based on city block distance (Algorithm 2). As there are no quadric components in the computation of city block distance, the size of the encrypted template can also be reduced. Let us describe how to generate the encrypted template firstly. For a minutia , we pad zeroes before each component and concatenate them to , where . The encrypted template can be created as: , where and . Compared with the template in Section 4.1, the size of this template is further reduced.
| ||||||||||||||||||||||||||||||
In the authentication phase, Alice and Bob firstly carry out the protocol CITY-BLOCK-DISTANCE to calculate a blind list for further computation of city block by using garbled circuits. We detail the protocol as follows.
Compared with EUCLIDEAN-DISTANCE, this protocol is rather simple. It is easy to verify the correctness of the protocol by employing the homomorphic property. The secure analysis is similar to that of EUCLIDEAN-DISTANCE. Table 2 shows its complexity. The computational complexity can be further reduced by precomputing step 1 of the protocol.
5. Circuits for Minutiae Matching
Garbled circuit is employed to complete minutiae matching with respect to Section 3. Section 5.1 describes the circuits related to Euclidean distance and Section 5.2 presents the circuits related to city block distance.
5.1. Circuits for Euclidean Distance
After the protocol EUCLIDEAN-DISTANCE is carried out, Alice learns the blind Euclidean distance and the blind directional difference . The remaining tasks of authentication are implemented by using garbled circuits. The circuits firstly take off the random masks covered on and to get the Euclidean distances and the directional differences. Then, for each minutia (, , ) belonging to , the closest matching minutia which belongs to is found according to (2) and (3). To do so, the circuits choose the minutiae belonging to as the candidates, whose directional differences are smaller than the threshold (see (3)). The candidates’ Euclidean distances are then fed into the minimum circuit to find the minimum. And then the minimum is checked whether it is smaller than the threshold (see (2)). Finally, the number of minutiae belonging to meeting the above two conditions is counted. We adopt the efficient building blocks from [23, 24] to design our circuit: addition ADD, subtraction SUB, comparison CMP, and multiplexer MUX circuits.
Figure 1 shows the circuit ORIDIFF to take off the mask of and compute the result according to (3). Alice’s input is and Bob’s, and . If is smaller than , ORIDIFF outputs “1”; otherwise “0”. Since is the result of , is likely to be negative, and it must be represented as a signed integer. We represent it as a -bit integer in two’s complement representation to cater to the requirement of circuit SUB [24], and so does . In ORIDIFF, the first SUB(in Figure 1, from left to right) outputs the result of . However, we want to get its absolute value according to (3). Since the result is represented in two’s complement, if it is negative, the second SUB computes its magnitude by subtracting it from . The most significant bit (MSB) of the output of the first SUB, which is the signed bit, controls the selection of the first MUX in ORIDIFF. If the MSB is “0,” the MUX chooses the output of the first SUB, otherwise the output of the second SUB. Thus, the first MUX outputs which is smaller than 360°. However, the output of the MUX is bits. Since the bits length of the orientation is bits, low bits of the output can be only preserved for the next computation. As is significantly bigger than , this method substantially reduces the number of gates. The third SUB in ORIDIFF computes the result of . And the second MUX in ORIDIFF outputs . If there exists the forged input, the high bits of the output of the first MUX may not be zeros. When this happens, we need to set the output of ORIDIFF “0.” Besides, the bit lengths of and are and , respectively, and is smaller than . So if the high order bits are not zeros, must be greater than , and there is no need to compare the other bits. Considering the above two cases, in ORIDIFF, we compute the logical OR of high order bits of the output of the first MUX and high order bits of the second MUX. If the result is 1, the third MUX chooses as its output, otherwise, the low bits of the second MUX. The OR operation can be implemented by two-inputs-OR gates one by one. At last, the output of the third MUX is compared against , if it is greater than , ; the output of ORIDIFF is set to 1, otherwise, 0, which will be further utilized to control the computation related to spatial distance. Bob generates ORIDIFF for Alice to evaluate (3) where and .
Figure 2 reveals the circuit of MATCH which serves to uncover the masks, find the matched minutiae, and count their number. The functions of the modules SPADIS, MINM, and COUNTER will be detailed later. Alice’s inputs are blind squared-distances , , and the corresponding , ; Bob’s inputs are random masks , where and ,. Note that is larger than and they are both -bit positive integers. However, the result of is the squared distance which can be represented as 2ρ-bit integer (). Let denote the distances between a minutia in and each minutia in , respectively, (). Among these distances, only the smallest one that simultaneously meets the requirement specified in (3) is picked out to compare with the threshold . Let denote its bits length (note that ). To reduce the complexity of overall circuits, instead of directly comparing with , we generate which is only a bits value as follows and compare it with later, which can avoid unnecessary bit operations:
The module SPADIS shown in Figure 3(a) uncovers the masks and compute . The logical OR of the high bits of is computed. If the result is 1, must be greater than . Hence, there is no need to compare the other bits. The -bit OR operation can be implemented by two-inputs-OR gates one by one. Besides, if the bit is 1, it indicates that the orientation difference between and is too large to meet the requirement, so OR of with the result of the above OR operation is further computed. For simplicity, we draw only one OR block standing for these operations in Figure 3(a). The result of the OR block controls the MUX to select or the low bits of . Since is significantly smaller than , the method saves a mass of gates in MIN and CMP circuits.
(a)
(b)
(c)
The module of MINM is presented in Figure 3(b), which takes as the inputs where and picks out the minimum. The circuit MIN2 shown in Figure 3(c) is the functional unit of MINM, which compares two inputs against and selects the smaller one.
In Figure 2, if the output of th CMP is 1 , it indicates that there exists a minutia belonging to that matches the th minutia belonging to . The module of COUNTER further counts the number of these “1”s. Obviously, the number is at most , so bits are needed to represent it. To reduce the complexity, we do not use -bit adders one by one to construct COUNTER. Instead, we use a hierarchical structure, which includes levels. The first level is composed of 1-bit ADDs with the number of . The second level is composed of 2-bit ADD with the number of , and so forth. The th level is composed of only one -bit ADD. Figure 4 shows an example for constructing COUNTER with being thirteen.
We can estimate the cost of circuits used in this section. The blocks here adopt the technique of “free” XOR [23, 24], which do not contribute significantly to the cost of garbled circuits since they need no communicational or cryptographic operations, so we just consider the number of non- XOR gates in the circuits. Table 3 gives the number of non-XOR gates in each of the circuits and the total number.
To implement the authentication, Bob prepares a garbled version of the circuits described above and transfers them to Alice, as well as the garbled values of his inputs—the random masks and the thresholds, and . Alice carries out the OT protocol along with Bob to obtain the garbled values corresponding to her inputs— and for , . She first evaluates ORIDIFF and then MATCH. The final result is the garbled version of the number of the matched minutiae. She sends it to Bob who gets the actual value and computes the matching score according to (1). If the score is greater than the threshold , Bob will accept Alice’s identity, otherwise, reject her.
5.2. Matching Circuit for City Block Distance
After the protocol CITY-BLOCK-DISTANCE is performed, Alice only get the intermediate data—the blind list . In this section, we present the circuit to complete the computation of city block distance as well as the other subtasks. Firstly, Alice computes the circuits containing ORIDIFF to take off the random masks of and compute the directional differences, select the minutiae belonging to , whose directional differences are smaller than as the candidates. Secondly, she uses the circuits shown in Figure 2 to calculate the distances, find the minima among the candidates, and check whether they are smaller than . However, the module SPADIS of Figure 2 should be replaced with Figure 5 designed for city block distance. Finally, she counts the number of the matched minutiae by using COUNTER described in Section 5.1.
SPADIS in Figure 5 takes as the inputs , , , , and . It firstly takes off the random masks on and . Note that and may be negative since there exists subtraction operation in step 2) of CITY-BLOCK-DISTANCE, so , , ,and all need an additive bit as the signed bits. Therefore, their bits lengths are set to be when they enter SPADIS. In Figure 5, the left two SUBs and a MUX serve to compute and the right correspondences serve to compute . The output of ADD is exactly the city block distance . To reduce the complexity of whole circuit, we take the same method which has been used in SPADIS for Euclidean distance—the module does not output city block distance directly. Instead, it computes :
The bits length of is which is that of the threshold . It is half of since the latter is the bits length of squared threshold. The gates of the subsequent circuit also employ this length, so the complexity of the circuit is remarkably reduced. Table 4 gives the complexity for city block distance.
6. Experimental Results and Discussion
As described in the above sections, the shorter bits length for representing a minutia can significantly lead to lower communicational and computational overloads. However, the shorter bits length consequentially may decrease the accuracy of matching. Hence, in this section, we try to evaluate the performance of the matching system and the effect of the bits length on the accuracy through the experiments. To achieve the goals, we implemented the whole system and tested on FVC2002-DB1 fingerprint database [26]. The database contains 8 images of 100 fingers, thus 800 images in total. The size of each image is pixels. Consequently, in order to represent each entry of a minutia completely, nine bits are required. The minutiae of each fingerprint were extracted and prealigned by using the algorithm of [27]. We considered the following three scenarios of the bits length: eight bits, seven bits, and six bits. That is, each entry of a minutia, , , and , was linearly mapped and rounded to 8-bit, 7-bit, and 6-bit integers, respectively. The genuine accept rate (GAR) and false accept rate (FAR) are tested in accordance with the requirements of FVC2002. For a genuine match, each impression of each finger was compared with other impressions of the same finger. There were totally 28 combinations per finger and a total of tests that were done for GAR. The cross tests were also done among 100 fingers to evaluate FAR. The first impression of each finger was compared with the first impression of other fingers. Totally, tests were done.
There are several implementation tools of a generic secure two-party computation that have been developed in the past few years which serve to build privacy-preserving protocols, for example, Fairplay [28], TASTY [29], and FSCUGC [30]. The approach of FSCUGC allows the users to write their programs with a combination of high-level and circuit-level Java code and provides more efficiency and scalability than others with the pipeline technique. So, we employed Java and the library provided by FSCUGC implemented the protocols. In our experimental setting, the server (Bob) and the client (Alice) were set up on different PCs connected by a LAN. Both PCs were configured with AMD 1055T 2.8 G CPU and 8 GB DDR3 memory. We used Paillier encryption scheme with a 1024-bit modulus and 80 bits for symmetric and statistical security. The other parameters of the protocols used in our experiments are listed in Table 5.
Table 6 gives the average running time of our protocols on FVC2002-DB1, in which “” refers to the time related to Paillier encryption; “” refers to that of Oblivious Transfer; and “Circuit” refers to that of garbled circuit. “Prep,” the preparation phase, only needs to be performed once. Since garbled circuits consume a large amount of memory with the increment of , and the average number of the minutiae of a fingerprint approximates to 43 in FVC2002DB1, in order to reduce an excessive exhaustion of the memory, the upper bounds of and were both set to be 90. Accordingly, the excessive minutiae will be discarded. Step of EUCLIDEAN-DISTANCE or CITY-BLOCK-DISTANCE was computed in the preparation of “Enc.” In the preparation phase of “Circuit,” the gabled circuits for and were generated, except for the wire labels and garbled tables which would be regenerated for each execution. The preparation phase of OT protocol depends only on the security parameters we choose. The “Exec” in Table 6 refers to execution phase which must be operated for each fingerprint. For the gabled circuits, since he had generated circuits, in this phase, the server reset the corresponding wire labels according to actual and and transferred them to the client. As expected, the average execution time of Enc in the case of city block distance is much smaller than that of Euclidean distance. However, the running time is dominated by the computation related to garbled circuits, so the average total time of city block distance is greater than that of Euclidean distance since the circuits of the former are more complex than those of the latter.
Table 7 shows the obtained accuracy measured by Equal Error Rate (EER), while Figure 6 shows the curves of receiver operating characteristic (ROC) of the matcher systems, in which Figure 6(a) is that of Euclidean distance and Figure 6(b) is that of city block distance. As expected, the quantization has effect on the accuracy of the matching algorithm. In both cases, the longer the bits length is, the higher the accuracy is. This can be explained by the fact that that quantization compresses the feature space. The two distinct minutiae with the distance less than a quantization step may be mapped to the same point. And the shorter the bits length is, the higher the probability is. This quantization effect increases FAR, so it lowers the accuracy of the matcher system. Surprisingly, the contrast between Figures 6(a) and 6(b) shows that the matcher based on city block distance has a better accuracy. The result can be explained as follows. We judge whether two minutiae are matched just according to the distance between them. The decision region formed by Euclidean distance is a circle whereas the one by city block distance is a diamond (square). For the same threshold , the radius of the circle is , while the side length of the diamond is . Thus, the area of the diamond is only of that of the circle. As mentioned above, the quantization may lead to the merging of distinct minutiae. The bigger decision area, though it increases the GAR, meanwhile, increases FAR more. Hence, it reduces the overall accuracy of the matcher based on Euclidean distance. On the contrary, the smaller area lowers the probability of false matching, thus resulting in the improvement of the accuracy. Compared with the implementation of fingercode version of fingerprint [15], our schemes based on minutiae show a better accuracy performance when , . And, compared with the results of [15], even six bits length also achieved a rather competitive accuracy (ERR = 0.051 for Euclidean distance and ERR = 0.045 for city block distance, resp.) when , .
(a)
(b)
7. Conclusion
Biometry serves as an excellent mechanism for the authentication of individuals while biometric data are extremely sensitive and must be well protected. Furthermore, once leaked, the data cannot be revoked or replaced. The use of privacy-preserving protocol is a very desirable solution to improving security in biometric applications. In this paper we have addressed the construction of privacy-preserving protocols of fingerprint minutiae based on the combination of garbled circuit and homomorphic encryption. The proposed scheme provides protection for both template and transaction privacy. The template stored on the server is encrypted by the user’s private key. Therefore, the template can be updated or revoked by reencryption. Two hybrid protocols with the combination of homomorphic encryption and garbled circuit are presented to fulfill the minutiae matching, in one of which, Euclidean distance is utilized as distance measures and in the other, city block distance is adopted. We have designed the efficient circuits to implement the corresponding tasks. The experimental results on FVC2002-DB2 show that the proposed scheme has acceptable verification accuracy. Future work could be oriented to the application of the results we obtained and to the development of privacy-preserving systems with a higher accuracy and efficiency.
Conflict of Interests
We do not have a direct financial relation that might lead to a conflict of interests for any of the authors.
Acknowledgment
This work is supported by the National Natural Science Foundation of China (61062012).