# Minutiae Matching with Privacy Protection Based on the Combination of Garbled Circuit and Homomorphic Encryption

Authors: Mengxing Li; Quan Feng; Jian Zhao; Mei Yang; Lijun Kang; Lili Wu
Journal: The Scientific World Journal
 (2014)

---

## 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.


---

## Body

## 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[x] denote encryption of x 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: (1) Given the encryptions [a] and [b], we can efficiently compute [a+b]=[a][b]. (2) Given that a constant c belongs to the same group, we can compute [c·a]=[a]c.There are many public-key cryptosystems satisfying the above properties. In our implementation, we use Paillier’s cryptosystem [19] which has plaintext space ZN and cipher text space ZN2*, where N is a T-bit RSA modulus and T is the bits length of RSA.


### 2.2. Oblivious Transfer

1-out-of-2 oblivious transfer (OT12) allows a sender, holding strings s0, s1, to transfer to a receiver, holding a selection bit b, exactly one of the inputs sb. The receiver learns nothing about s1-b, and the sender has no idea of b. Parallel OT12 of m  l-bit strings is denoted as OTlm. For i=1,…,m, the sender inputs a pair of l-bit strings si0, si1∈{0,1}l and the receiver inputs m choice bits bi∈{0,1}. At the end of the protocol, the receiver learns about the chosen string sibi, but nothing about si1-bi whereas the sender learns nothing about the choice bi. 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 OTlm to be independent of m.


### 2.3. Garbled Circuits

Garbled circuit [21, 22] allows two parties holding inputs x and y, respectively, to evaluate an arbitrary function f(x,y) without leaking any information about their inputs. The basic idea is that a server creates an “encrypted” version of the circuit C to compute f, and then a client obliviously computes the output of the circuit. In more detail, for each wire wi of C, the server randomly chooses two secrets, w~i0 and w~i1, where w~ij is called garbled value of wi’s valuej. Further, for each gate Gi of C, the server creates a garbled table T~i which records a collection of the garbled values corresponding to the output wires of Gi with those corresponding to the input wires. All T~is 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 OT 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 T~is.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.


## 2.1. Additively Homomorphic Encryption

Let[x] denote encryption of x 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: (1) Given the encryptions [a] and [b], we can efficiently compute [a+b]=[a][b]. (2) Given that a constant c belongs to the same group, we can compute [c·a]=[a]c.There are many public-key cryptosystems satisfying the above properties. In our implementation, we use Paillier’s cryptosystem [19] which has plaintext space ZN and cipher text space ZN2*, where N is a T-bit RSA modulus and T is the bits length of RSA.


## 2.2. Oblivious Transfer

1-out-of-2 oblivious transfer (OT12) allows a sender, holding strings s0, s1, to transfer to a receiver, holding a selection bit b, exactly one of the inputs sb. The receiver learns nothing about s1-b, and the sender has no idea of b. Parallel OT12 of m  l-bit strings is denoted as OTlm. For i=1,…,m, the sender inputs a pair of l-bit strings si0, si1∈{0,1}l and the receiver inputs m choice bits bi∈{0,1}. At the end of the protocol, the receiver learns about the chosen string sibi, but nothing about si1-bi whereas the sender learns nothing about the choice bi. 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 OTlm to be independent of m.


## 2.3. Garbled Circuits

Garbled circuit [21, 22] allows two parties holding inputs x and y, respectively, to evaluate an arbitrary function f(x,y) without leaking any information about their inputs. The basic idea is that a server creates an “encrypted” version of the circuit C to compute f, and then a client obliviously computes the output of the circuit. In more detail, for each wire wi of C, the server randomly chooses two secrets, w~i0 and w~i1, where w~ij is called garbled value of wi’s valuej. Further, for each gate Gi of C, the server creates a garbled table T~i which records a collection of the garbled values corresponding to the output wires of Gi with those corresponding to the input wires. All T~is 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 OT 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 T~is.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 (x,y,θ) triplet, where (x,y) is the location of the minutia and θ angle of the associated ridge (0≤θ<360°). 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 MT={(xi,yi,θi)∣1≤i≤NT} and MQ={(xj′,yj′,θj′)1≤i≤NQ} denote the template and query, respectively. A minutiae-based fingerprint matching algorithm usually returns the number of matched minutiae on both MT and MQ to generate similarity scores. In this paper, the matching score SM is calculated as follows:
(1)SM=100×NMmax⁡(NT,NQ),
where NM is the number of paired minutiae. If SM is greater than or equal to a predefined threshold TM; then the query and the template can be considered coming from the same finger.A minutiaMi=(xi,yi,θi) in MT and a minutia Mj′=(xj′,yj′,θj′) in MQ are considered matching if the following conditions are satisfied:
(2)d((xi,yi),(xj′,yj′))<TD,(3)min⁡⁡(|θi-θj′|,360-|θi-θj′|)<Tθ,
where d() is a distance function and TD and Tθ are the given thresholds. In this paper, we consider two distance metrics: (i) square of Euclidean distance dE((xi,yi),(xj′,yj′))=(xi-xj′)2+(yi-yj′)2 (for simplicity, we still call Euclidean distance) and (ii) city block distance dB((xi,yi),(xj′,yj′))=|xi-xj′|+|yi-yj′|. However, for a given minutia belonging to MQ, the above approach might find at least one matching result belonging to MT, but, in fact, at most one is correct. In this paper, for a minutia Mj′∈MQ and those minutiae belonging to MT satisfying (2) and (3), we choose the closest to Mj′ 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 minutiaeMQ 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 MQ and that in MT 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. MT is the encrypted version with Alice’s private key while MQ is in the clear. Here we denote the encrypted template as EMT={EMi=([xi],[xi2],[yi],[yi2],[θi])∣1≤i≤NT}. EMT is held by Bob. Since Alice holds the private key, to keep his privacy, Bob can blind MT in advance and Alice can only compute the blind distance. To do so, he blinds EM with the uniformly random numbers r1, r2, r3, r4 from the plaintext space to get the following cipher texts by using the homomorphic property: [a]=[x][r1]=[x+r1], [b]=[y][r2]=[y+r2], [c]=[x2][r3]=[x2+r3], [d]=[y2][r4]=[y2+r4]. Then he sends these cipher texts to Alice. Alice decrypts them to get a, b, c,and d. She calculates
(4)ed=c+d-2x′a-2y′b+x′2+y′2=x2-2xx′+x′2+y2-2yy′+y′2+r3+r4-2r1x′-2r2y′.To further compute the blind distance, Alice needs2r1x′+2r2y′ which can be easily gotten by interacting with Bob: Alice transfers [2x′] and [2y′] to Bob. The latter computes and returns [t]=[2x′]r1[2y′]r2[r5], where r5∈RZN. It is easy to observe that [t]=[2x′r1+2y′r2+r5]. Alice decrypts [t] and calculates the blind distance bd=ed+t=dE+r3+r4+r5=dE+r.Bob further blinds[θ] with a random number by computing e=[r6][θ]=[r6+θ], where r6 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 x(x′), y(y′), x2, y2, and θ are ρ-, ρ-, 2ρ-, 2ρ-, and μ-bit positive integers, respectively, and the random masks r1, r2, r3, r4, r5, and r6 are ηr1-, ηr2-, ηr3-, ηr4-, ηr5-, and ηr6-bit positive integers, respectively. The resulting blind values x+r1, y+r2, x2+r3, y2+r4, and θ+r6 can be packed into a single cipher text. The cross item such as t=2x′r1+2y′r2+r5 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 EMT, we firstly pad some zeros before x, y, x2, y2, and θ to increase their lengths to ηr1+1, ηr2+1, ηr3+1, ηr4+1, ηr6+1, respectively, and concatenate them together. As described later, we have ηr1=ρ+δ, ηr2=ρ+δ, ηr3=2ρ+δ, ηr4=2ρ+δ, ηr6=η+δ (δ is a security parameter which will be explained later). Then a unit chunk representing a minutia Mi=(xi,yi,θi) is written down as: mpi=0δ+1∥xi∥0δ+1∥yi∥0δ+1∥xi2∥0δ+1∥yi2∥0δ+1∥θi. The purpose of padding δ+1 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 NP=⌈T/(6ρ+μ+5δ+5)⌉ minutiae. The number of cipher texts of EMT is only NM=⌊NT/NP⌋. Compared with the basic approach, the method saves (1-NM/5NT)% storage space. We rewrite EMTas: EMT={cp1=[mp1∥⋯∥mpNP],…, cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}. 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 EMT by employing the aforementioned method. She sends EMT to Bob who stores EMT 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, NT and NQ, and exchanged the public key.Algorithm 1:Euclidean-distance (EMT, MQ).
Input: the encrypted template EMT={cp1=[mp1∥⋯∥mpNP],…,cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}
from Bob, and query minutiae from AliceMQ
Output: Alice gets the blind squared-distance bd (i,j) and blind direction bo (i,j) between Mi=(xi,yi,θi)
andMj′=(xj′,yj′,θj′).
(1)  Bob choosesr1i,r2i∈R{0,1}ρ+δ, r3i,r4i∈R{0,1}2ρ+δ, r6i∈R{0,1}μ+δ, 1≤i≤NT, concatenates them as strings:
R1=rt1∥⋯∥rtNP, …, RNM=rt(NM-1)NP+1∥⋯∥rtNT,
whererti=0∥r1i∥0∥r2i∥0∥r3i∥0∥r4i∥0∥r6i∥.
Fork=1, …, NM, he computes [Ak]=cpk[Rk],
where[A1]=[a11∥b21∥c31∥d41∥e51∥⋯∥a1NP∥b2NP∥c3NP∥d4NP∥e5NP], and so forth
andai=r1i+xi, bi=r2i+yi, ci=r3i+xi2, di=r4i+yi2, ei=r6i+θi. He sends these cipher texts to Alice.
(2)  Alice decrypts[A1],…, [ANM] and obtains ai=r1i+xi,bi=r2i+xi,ci=r3i+xi2,di=r4i+yi2,
andei=r6i+θi(1≤i≤NT) by parsing A1,…,ANM into ρ+δ+1-, ρ+δ+1-, 2ρ+δ+1-,
2ρ+δ+1- and μ+δ+1-bit chunks respectively. And:
(i)   Fori=1, …, NT  and  j=1, …, NQ, she calculates edij=ci+di-2xj′ai-2yj′bi+xj′2+yj′2.
(ii)   She padsλ-ρ-1 zeros before each 2xj′ and 2yj′,
constructs theλ-bit strings: uj1=0(λ-ρ-1)∥2xj′ and uj2=0(λ-ρ-1)∥2yj′, where λ=2ρ+δ+3.
She then concatenates these strings together respectively:B1=u11∥⋯∥uNX1, …,
BNB=u(NB-1)NX+11∥⋯∥uNQ1, C1=u12∥⋯∥uNX2, …, CNB=u(NB-1)NX+12∥⋯∥uNQ2,
where2xj′ and 2yj′ are both ρ+1-bit values, ui1 and ui2 are both λ-bit values, NX=⌈T/λ⌉
andNB=⌊NQ/NX⌋.
(iii)    Fork=1, …, NB, she computes [Bk] and [Ck], transfers them to Bob.
(3)  Bob receives the cipher texts. Then:
(i)   Fori=1,…, NT  and k=1, …, NB, he computes [ti,k1]=[Bk]ri1[Ck]ri2=[ri1Bk+ri2Ck].
(ii)   He choosesri,j5∈R{0,1}λ-1, 1≤i≤NQ, 1≤j≤NQ, pads a zero before each number,
concatenates eachNX numbers as strings with respect to j:
ti,12=0∥ri,15∥⋯∥0∥ri,NX5, …, ti,NB2=0∥ri,(NB-1)NX+15∥⋯∥0∥ri,NQ5, and computes
[ti,12], …, [ti,NB2].
(iii)   Fori=1,…, NT and k=1,…, NB, he computes [ti,k3]=[ti,k1][ti,k2]=[ti,k1+ti,k2]
and sends them to Alice.
(4)  Alice receives and decrypts[ti,k3], 1≤i≤NT, 1≤k≤NB. Then:
(i)     Fori=1, …, NT, she unpacks each ti,k3 by parsing it into λ-bit chunks to obtain
ti,14, …, ti,NX4, …, ti,(NB-1)NX+14, …, ti,NQ4, where ti,j4=2ri1xj′+2ri2yj′+ri,j5.
(ii)   Fori=1, …, NT and j=1, …, NQ, she computes the blind squared-distance
bd(i,j)=edij+ti,j4 and the blind orientation difference bo(i,j)=ei-θj′
betweenMj′∈MQ and each Mi∈MT.Packing Size. We have supposed that x, y, x2, y2, and θ are ρ, ρ, 2ρ, 2ρ, and μ bits, respectively, and random masks r1, r2, r3, r4, r6 are ηr1, ηr2, ηr3, ηr4, and ηr6 bits, respectively. To keep statistical security, we need ηr1>ρ, ηr2>ρ, ηr3>2ρ, ηr4>2ρ, and ηr6>μ. In fact, our random masks are longer than the corresponding blind values by δ bits; that is, ηr1=ρ+δ, ηr2=ρ+δ, ηr3=2ρ+δ, ηr4=2ρ+δ, and ηr6=μ+δ. 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: a, b, c, d, and e (step 1) are ρ+δ+1-, ρ+δ+1-, 2ρ+δ+1-, 2ρ+δ+1-, and μ+δ+1-bit values. The main task of the protocol is computing the cross item ti,j4=2ri1xj′+2ri2yj′+ri,j5 (step 4 (i)). We need (ηr1+ρ+1)+1=2ρ+δ+2 bits to represent 2ri1xj′+2ri2yj′, and ηr5=2ρ+δ+2 to represent the random mask ri,j5. Accordingly, it is clear that λ=ηr5+1=2ρ+δ+3 bits are sufficient (step 2 (ii)). We pad λ-ρ-1 zeros before 2xj′ and 2yj′ to form λ-bit ui1 and ui2 because this ensures that no overflow happens when computing 2ri1xj′+2ri2yj′ (step 2 (ii)). The blind squared-distance bd(i,j) and the blind orientation difference bo(i,j) are λ-bit and μ+δ+1-bit, respectively.Correctness. Here, we prove that the equality in Euclidean-Distance, bd(i,j)=edij+ti,j4=dE(i,j)+rij is established. In step 2 of the protocol, since ui1 is λ=2ρ+δ+3-bit, ri1, ρ+δ-bit, and 2x′, ρ+1-bit binary string, respectively; in step 3,
(5)[B1]ri1=[u11∥⋯∥uNX1]ri1=[∑j=1NXuj1·2(NX-j)λ]ri1=[∑j=1NXuj1·ri1·2(NX-j)λ]=[∑j=1NX2xj′·ri1·2(NX-j)λ]=[2x1′ri1∥2x2′ri1∥⋯2xNX′ri1],[B2]ri1=[2xNX+1′ri1∥⋯],
and so forth.Similarly,(6)[C1]ri1=[u12∥⋯∥uNX2]ri1=[2y1′ri2∥2y2′ri2∥⋯2yNX′ri2],[C2]ri1=[2yNX+1′ri2∥⋯],
and so forth. So,
(7)[ti,11]=[B1]ri1[C1]ri2=[ri1B1+ri2C1]=[2x1′ri1+2y1′ri2∥⋯∥2xNX′ri1+2xNX′ri2],[ti,21]=[2xNX+1′ri1+2yNX+1′ri2∥⋯],and so forth.One can further verify that(8)[ti,13]=[ti,11+ti,12]=[2ri1x1′+2ri2y1′+ri,15∥⋯∥2ri1xNX′+2ri2yNX′+ri,NX52ri1x1′+2ri2y1′+ri,15∥⋯∥2ri1xNX′+2ri2yNX′],…,[ti,NB3]=[ti,NB1+ti,NB2]=[2ri1x(NB-1)NX+1′+2ri2y(NB-1)NX+1′dd+ri,(NB-1)NX+15∥⋯∥2ri1xNQ′+2ri2yNQ′+ri,NQ5].Thus,(9)ti,j4=2ri1xj′+2ri2yj′+ri,j5(step4),bd(i,j)=edij+ti,j4=(xi-xj′)2+(yi-yj′)2+ri3+ri4+ri,j5=dE(i,j)+ri3+ri4+ri,j5=dE(i,j)+rij.Obviously,bo(i,j)=ei-θj′=θi-θj′+ri6, which is the blind difference between θi and θj′.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 w is ρ-bit integer and r is uniform η-bit integer, then v=w+r gives statistical security roughly 2ρ-η for w, where w can stand for x, y, x2, y2, and θ. This probability can be lowered arbitrarily by choosing η properly. However, a longer η will increase computational and communicational complexity. Since x, y, and θ are ρ-, ρ-, and μ-bit integers, respectively, and the probability of guessing right x, y, and θ is 2-ρ, 2-ρ, and 2-μ, respectively, it is sufficient that ηr1-ρ, ηr2-ρ are not less than ρ and ηr6-μ 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 T (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 NM Encryption.Table 1
Complexity of the protocol Euclidean-distance.
Round complexity
Communication complexity (bits)
Asymptotic computation complexity
3
Bob
→
Alice: (NM+NT×NB)×2T
Bob:(NM+NT×NB)Enc+(2×NT×NB)Exp
Alice
→
Bob: 2NB×2T
Alice:2NBEnc+(NM+2×NT×NB)Dec


### 4.2. City-Block-Distance Protocol

In this section, we present a protocol based on city block distance (Algorithm2). 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 Mi=(xi,yi,θi), we pad δ+1 zeroes before each component and concatenate them to mpi, where mpi=0δ+1∥xi∥0δ+1∥yi∥0δ+1∥θi. The encrypted template can be created as: EMT={cp1=[mp1∥⋯∥mpNP],…,cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}, where NP=⌊T/(2ρ+μ+3δ+3)⌋ and NM=⌈NT/NP⌉. Compared with the template in Section 4.1, the size of this template is further reduced.Algorithm 2:City-block-distance (EMT, MQ).
Input: the encrypted template
E
M
T
=
{
c
p
1
=
[
m
p
1
∥
⋯
∥
m
p
N
P
]
,
…
,
c
p
N
M
=
[
m
p
(
N
M
-
1
)
N
P
+
1
∥
⋯
∥
m
p
N
T
]
}
from Bob, and query minutiae from AliceMQ
Output:Alice gets a blind list {bx(i,j),by(i,j),bo(i,j)∣1≤i≤NT,1≤j≤NQ}
betweenMi=(xi,yi,θi) and Mj′=(xj′,yj′,θj′).
(1)   Bob choosesr1i,r2i∈R{0,1}ρ+δ,r3i∈R{0,1}μ+δ, 1≤i≤NT, concatenates them as strings:
R1=rt1∥⋯∥rtNP,⋯,RNM=rt(NM-1)NP+1∥⋯∥rtNT,
whererti=0∥r1i∥0∥r2i∥0∥r3i. For k=1, …, NM,
he computes[Ak]=cpk[Rk], where [A1]=[a11∥b21∥e51∥⋯∥a1NP∥b2NP∥e5NP],
and so forth andai=r1i+xi, bi=r2i+yi, ei=r6i+θi. He sends these cipher texts to Alice.
(2)   Alice decrypts[A1], …, [ANM] and obtains ai=r1i+xi,bi=r2i+xi and ei=r6i+θi(1≤i≤NT)
by parsingA1,⋯,ANM into ρ+δ+1-, ρ+δ+1- and μ+δ+1-bit chunks respectively.
Fori=1, …, NT and j=1, …, NQ, she computes bx(i,j)=ai-xj′=ri1+xi-xj′,
by(i,j)=bi-yj′=ri2+yi-yj′
andbo(i,j)=ei-θj′=ri6+θi-θj′.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.Table 2
Complexity of protocol City block distance.
Round complexity
Communication complexity (bits)
Asymptotic computation complexity
1
Bob
→
Alice
:
N
M
×
2
T
Bob:NM (Enc)
Alice:NM (Dec)


## 4.1. Euclidean-Distance Protocol

Basic. Alice computes the distance between each minutia in MQ and that in MT 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. MT is the encrypted version with Alice’s private key while MQ is in the clear. Here we denote the encrypted template as EMT={EMi=([xi],[xi2],[yi],[yi2],[θi])∣1≤i≤NT}. EMT is held by Bob. Since Alice holds the private key, to keep his privacy, Bob can blind MT in advance and Alice can only compute the blind distance. To do so, he blinds EM with the uniformly random numbers r1, r2, r3, r4 from the plaintext space to get the following cipher texts by using the homomorphic property: [a]=[x][r1]=[x+r1], [b]=[y][r2]=[y+r2], [c]=[x2][r3]=[x2+r3], [d]=[y2][r4]=[y2+r4]. Then he sends these cipher texts to Alice. Alice decrypts them to get a, b, c,and d. She calculates
(4)ed=c+d-2x′a-2y′b+x′2+y′2=x2-2xx′+x′2+y2-2yy′+y′2+r3+r4-2r1x′-2r2y′.To further compute the blind distance, Alice needs2r1x′+2r2y′ which can be easily gotten by interacting with Bob: Alice transfers [2x′] and [2y′] to Bob. The latter computes and returns [t]=[2x′]r1[2y′]r2[r5], where r5∈RZN. It is easy to observe that [t]=[2x′r1+2y′r2+r5]. Alice decrypts [t] and calculates the blind distance bd=ed+t=dE+r3+r4+r5=dE+r.Bob further blinds[θ] with a random number by computing e=[r6][θ]=[r6+θ], where r6 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 x(x′), y(y′), x2, y2, and θ are ρ-, ρ-, 2ρ-, 2ρ-, and μ-bit positive integers, respectively, and the random masks r1, r2, r3, r4, r5, and r6 are ηr1-, ηr2-, ηr3-, ηr4-, ηr5-, and ηr6-bit positive integers, respectively. The resulting blind values x+r1, y+r2, x2+r3, y2+r4, and θ+r6 can be packed into a single cipher text. The cross item such as t=2x′r1+2y′r2+r5 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 EMT, we firstly pad some zeros before x, y, x2, y2, and θ to increase their lengths to ηr1+1, ηr2+1, ηr3+1, ηr4+1, ηr6+1, respectively, and concatenate them together. As described later, we have ηr1=ρ+δ, ηr2=ρ+δ, ηr3=2ρ+δ, ηr4=2ρ+δ, ηr6=η+δ (δ is a security parameter which will be explained later). Then a unit chunk representing a minutia Mi=(xi,yi,θi) is written down as: mpi=0δ+1∥xi∥0δ+1∥yi∥0δ+1∥xi2∥0δ+1∥yi2∥0δ+1∥θi. The purpose of padding δ+1 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 NP=⌈T/(6ρ+μ+5δ+5)⌉ minutiae. The number of cipher texts of EMT is only NM=⌊NT/NP⌋. Compared with the basic approach, the method saves (1-NM/5NT)% storage space. We rewrite EMTas: EMT={cp1=[mp1∥⋯∥mpNP],…, cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}. 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 EMT by employing the aforementioned method. She sends EMT to Bob who stores EMT 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, NT and NQ, and exchanged the public key.Algorithm 1:Euclidean-distance (EMT, MQ).
Input: the encrypted template EMT={cp1=[mp1∥⋯∥mpNP],…,cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}
from Bob, and query minutiae from AliceMQ
Output: Alice gets the blind squared-distance bd (i,j) and blind direction bo (i,j) between Mi=(xi,yi,θi)
andMj′=(xj′,yj′,θj′).
(1)  Bob choosesr1i,r2i∈R{0,1}ρ+δ, r3i,r4i∈R{0,1}2ρ+δ, r6i∈R{0,1}μ+δ, 1≤i≤NT, concatenates them as strings:
R1=rt1∥⋯∥rtNP, …, RNM=rt(NM-1)NP+1∥⋯∥rtNT,
whererti=0∥r1i∥0∥r2i∥0∥r3i∥0∥r4i∥0∥r6i∥.
Fork=1, …, NM, he computes [Ak]=cpk[Rk],
where[A1]=[a11∥b21∥c31∥d41∥e51∥⋯∥a1NP∥b2NP∥c3NP∥d4NP∥e5NP], and so forth
andai=r1i+xi, bi=r2i+yi, ci=r3i+xi2, di=r4i+yi2, ei=r6i+θi. He sends these cipher texts to Alice.
(2)  Alice decrypts[A1],…, [ANM] and obtains ai=r1i+xi,bi=r2i+xi,ci=r3i+xi2,di=r4i+yi2,
andei=r6i+θi(1≤i≤NT) by parsing A1,…,ANM into ρ+δ+1-, ρ+δ+1-, 2ρ+δ+1-,
2ρ+δ+1- and μ+δ+1-bit chunks respectively. And:
(i)   Fori=1, …, NT  and  j=1, …, NQ, she calculates edij=ci+di-2xj′ai-2yj′bi+xj′2+yj′2.
(ii)   She padsλ-ρ-1 zeros before each 2xj′ and 2yj′,
constructs theλ-bit strings: uj1=0(λ-ρ-1)∥2xj′ and uj2=0(λ-ρ-1)∥2yj′, where λ=2ρ+δ+3.
She then concatenates these strings together respectively:B1=u11∥⋯∥uNX1, …,
BNB=u(NB-1)NX+11∥⋯∥uNQ1, C1=u12∥⋯∥uNX2, …, CNB=u(NB-1)NX+12∥⋯∥uNQ2,
where2xj′ and 2yj′ are both ρ+1-bit values, ui1 and ui2 are both λ-bit values, NX=⌈T/λ⌉
andNB=⌊NQ/NX⌋.
(iii)    Fork=1, …, NB, she computes [Bk] and [Ck], transfers them to Bob.
(3)  Bob receives the cipher texts. Then:
(i)   Fori=1,…, NT  and k=1, …, NB, he computes [ti,k1]=[Bk]ri1[Ck]ri2=[ri1Bk+ri2Ck].
(ii)   He choosesri,j5∈R{0,1}λ-1, 1≤i≤NQ, 1≤j≤NQ, pads a zero before each number,
concatenates eachNX numbers as strings with respect to j:
ti,12=0∥ri,15∥⋯∥0∥ri,NX5, …, ti,NB2=0∥ri,(NB-1)NX+15∥⋯∥0∥ri,NQ5, and computes
[ti,12], …, [ti,NB2].
(iii)   Fori=1,…, NT and k=1,…, NB, he computes [ti,k3]=[ti,k1][ti,k2]=[ti,k1+ti,k2]
and sends them to Alice.
(4)  Alice receives and decrypts[ti,k3], 1≤i≤NT, 1≤k≤NB. Then:
(i)     Fori=1, …, NT, she unpacks each ti,k3 by parsing it into λ-bit chunks to obtain
ti,14, …, ti,NX4, …, ti,(NB-1)NX+14, …, ti,NQ4, where ti,j4=2ri1xj′+2ri2yj′+ri,j5.
(ii)   Fori=1, …, NT and j=1, …, NQ, she computes the blind squared-distance
bd(i,j)=edij+ti,j4 and the blind orientation difference bo(i,j)=ei-θj′
betweenMj′∈MQ and each Mi∈MT.Packing Size. We have supposed that x, y, x2, y2, and θ are ρ, ρ, 2ρ, 2ρ, and μ bits, respectively, and random masks r1, r2, r3, r4, r6 are ηr1, ηr2, ηr3, ηr4, and ηr6 bits, respectively. To keep statistical security, we need ηr1>ρ, ηr2>ρ, ηr3>2ρ, ηr4>2ρ, and ηr6>μ. In fact, our random masks are longer than the corresponding blind values by δ bits; that is, ηr1=ρ+δ, ηr2=ρ+δ, ηr3=2ρ+δ, ηr4=2ρ+δ, and ηr6=μ+δ. 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: a, b, c, d, and e (step 1) are ρ+δ+1-, ρ+δ+1-, 2ρ+δ+1-, 2ρ+δ+1-, and μ+δ+1-bit values. The main task of the protocol is computing the cross item ti,j4=2ri1xj′+2ri2yj′+ri,j5 (step 4 (i)). We need (ηr1+ρ+1)+1=2ρ+δ+2 bits to represent 2ri1xj′+2ri2yj′, and ηr5=2ρ+δ+2 to represent the random mask ri,j5. Accordingly, it is clear that λ=ηr5+1=2ρ+δ+3 bits are sufficient (step 2 (ii)). We pad λ-ρ-1 zeros before 2xj′ and 2yj′ to form λ-bit ui1 and ui2 because this ensures that no overflow happens when computing 2ri1xj′+2ri2yj′ (step 2 (ii)). The blind squared-distance bd(i,j) and the blind orientation difference bo(i,j) are λ-bit and μ+δ+1-bit, respectively.Correctness. Here, we prove that the equality in Euclidean-Distance, bd(i,j)=edij+ti,j4=dE(i,j)+rij is established. In step 2 of the protocol, since ui1 is λ=2ρ+δ+3-bit, ri1, ρ+δ-bit, and 2x′, ρ+1-bit binary string, respectively; in step 3,
(5)[B1]ri1=[u11∥⋯∥uNX1]ri1=[∑j=1NXuj1·2(NX-j)λ]ri1=[∑j=1NXuj1·ri1·2(NX-j)λ]=[∑j=1NX2xj′·ri1·2(NX-j)λ]=[2x1′ri1∥2x2′ri1∥⋯2xNX′ri1],[B2]ri1=[2xNX+1′ri1∥⋯],
and so forth.Similarly,(6)[C1]ri1=[u12∥⋯∥uNX2]ri1=[2y1′ri2∥2y2′ri2∥⋯2yNX′ri2],[C2]ri1=[2yNX+1′ri2∥⋯],
and so forth. So,
(7)[ti,11]=[B1]ri1[C1]ri2=[ri1B1+ri2C1]=[2x1′ri1+2y1′ri2∥⋯∥2xNX′ri1+2xNX′ri2],[ti,21]=[2xNX+1′ri1+2yNX+1′ri2∥⋯],and so forth.One can further verify that(8)[ti,13]=[ti,11+ti,12]=[2ri1x1′+2ri2y1′+ri,15∥⋯∥2ri1xNX′+2ri2yNX′+ri,NX52ri1x1′+2ri2y1′+ri,15∥⋯∥2ri1xNX′+2ri2yNX′],…,[ti,NB3]=[ti,NB1+ti,NB2]=[2ri1x(NB-1)NX+1′+2ri2y(NB-1)NX+1′dd+ri,(NB-1)NX+15∥⋯∥2ri1xNQ′+2ri2yNQ′+ri,NQ5].Thus,(9)ti,j4=2ri1xj′+2ri2yj′+ri,j5(step4),bd(i,j)=edij+ti,j4=(xi-xj′)2+(yi-yj′)2+ri3+ri4+ri,j5=dE(i,j)+ri3+ri4+ri,j5=dE(i,j)+rij.Obviously,bo(i,j)=ei-θj′=θi-θj′+ri6, which is the blind difference between θi and θj′.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 w is ρ-bit integer and r is uniform η-bit integer, then v=w+r gives statistical security roughly 2ρ-η for w, where w can stand for x, y, x2, y2, and θ. This probability can be lowered arbitrarily by choosing η properly. However, a longer η will increase computational and communicational complexity. Since x, y, and θ are ρ-, ρ-, and μ-bit integers, respectively, and the probability of guessing right x, y, and θ is 2-ρ, 2-ρ, and 2-μ, respectively, it is sufficient that ηr1-ρ, ηr2-ρ are not less than ρ and ηr6-μ 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 T (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 NM Encryption.Table 1
Complexity of the protocol Euclidean-distance.
Round complexity
Communication complexity (bits)
Asymptotic computation complexity
3
Bob
→
Alice: (NM+NT×NB)×2T
Bob:(NM+NT×NB)Enc+(2×NT×NB)Exp
Alice
→
Bob: 2NB×2T
Alice:2NBEnc+(NM+2×NT×NB)Dec


## 4.2. City-Block-Distance Protocol

In this section, we present a protocol based on city block distance (Algorithm2). 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 Mi=(xi,yi,θi), we pad δ+1 zeroes before each component and concatenate them to mpi, where mpi=0δ+1∥xi∥0δ+1∥yi∥0δ+1∥θi. The encrypted template can be created as: EMT={cp1=[mp1∥⋯∥mpNP],…,cpNM=[mp(NM-1)NP+1∥⋯∥mpNT]}, where NP=⌊T/(2ρ+μ+3δ+3)⌋ and NM=⌈NT/NP⌉. Compared with the template in Section 4.1, the size of this template is further reduced.Algorithm 2:City-block-distance (EMT, MQ).
Input: the encrypted template
E
M
T
=
{
c
p
1
=
[
m
p
1
∥
⋯
∥
m
p
N
P
]
,
…
,
c
p
N
M
=
[
m
p
(
N
M
-
1
)
N
P
+
1
∥
⋯
∥
m
p
N
T
]
}
from Bob, and query minutiae from AliceMQ
Output:Alice gets a blind list {bx(i,j),by(i,j),bo(i,j)∣1≤i≤NT,1≤j≤NQ}
betweenMi=(xi,yi,θi) and Mj′=(xj′,yj′,θj′).
(1)   Bob choosesr1i,r2i∈R{0,1}ρ+δ,r3i∈R{0,1}μ+δ, 1≤i≤NT, concatenates them as strings:
R1=rt1∥⋯∥rtNP,⋯,RNM=rt(NM-1)NP+1∥⋯∥rtNT,
whererti=0∥r1i∥0∥r2i∥0∥r3i. For k=1, …, NM,
he computes[Ak]=cpk[Rk], where [A1]=[a11∥b21∥e51∥⋯∥a1NP∥b2NP∥e5NP],
and so forth andai=r1i+xi, bi=r2i+yi, ei=r6i+θi. He sends these cipher texts to Alice.
(2)   Alice decrypts[A1], …, [ANM] and obtains ai=r1i+xi,bi=r2i+xi and ei=r6i+θi(1≤i≤NT)
by parsingA1,⋯,ANM into ρ+δ+1-, ρ+δ+1- and μ+δ+1-bit chunks respectively.
Fori=1, …, NT and j=1, …, NQ, she computes bx(i,j)=ai-xj′=ri1+xi-xj′,
by(i,j)=bi-yj′=ri2+yi-yj′
andbo(i,j)=ei-θj′=ri6+θi-θj′.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.Table 2
Complexity of protocol City block distance.
Round complexity
Communication complexity (bits)
Asymptotic computation complexity
1
Bob
→
Alice
:
N
M
×
2
T
Bob:NM (Enc)
Alice:NM (Dec)


## 5. Circuits for Minutiae Matching

Garbled circuit is employed to complete minutiae matching with respect to Section3. 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 bd(i,j)=dE(i,j)+rij and the blind directional difference bo(i,j)=θi-θj′+ri6. The remaining tasks of authentication are implemented by using garbled circuits. The circuits firstly take off the random masks covered on bd(i,j) and bo(i,j) to get the Euclidean distances and the directional differences. Then, for each minutia (xi, yi, θi) belonging to MT(1≤i≤NT), the closest matching minutia which belongs to MQ is found according to (2) and (3). To do so, the circuits choose the minutiae belonging to MQ as the candidates, whose directional differences are smaller than the threshold Tθ (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 TD (see (2)). Finally, the number of minutiae belonging to MQ 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.Figure1 shows the circuit ORIDIFF to take off the mask of bo(i,j) and compute the result according to (3). Alice’s input is bo(i,j) and Bob’s, ri6 and Tθ. If θi-θj′ is smaller than Tθ, ORIDIFF outputs oaij= “1”; otherwise oaij= “0”. Since bo(i,j) is the result of ei-θj′, bo(i,j) is likely to be negative, and it must be represented as a signed integer. We represent it as a μ+δ+2-bit integer in two’s complement representation to cater to the requirement of circuit SUB [24], and so does ri6. In ORIDIFF, the first SUB(in Figure 1, from left to right) outputs the result of θi-θj′. 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 2μ+δ+2. 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 |θi-θj′| which is smaller than 360°. However, the output of the MUX is μ+δ+1 bits. Since the bits length of the orientation is μ bits, μ low bits of the output can be only preserved for the next computation. As μ+δ+1 is significantly bigger than μ, this method substantially reduces the number of gates. The third SUB in ORIDIFF computes the result of 360-|θi-θj′|. And the second MUX in ORIDIFF outputs od=min⁡⁡(|θi-θj′|,360-|θi-θj′|). If there exists the forged input, the δ+1 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 od and Tθ are μ and σ, respectively, and σis smaller than μ. So if the high order μ-σ bits are not zeros, od must be greater than Tθ, 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 δ+2 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 2σ-1 as its output, otherwise, the low σ bits of the second MUX. The OR operation can be implemented by λ-τ-1 two-inputs-OR gates one by one. At last, the output of the third MUX is compared against Tθ, if it is greater than Tθ, oij; 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 NT×NQ ORIDIFF for Alice to evaluate (3) where i=1,…,NT and j=1,…,NQ.Figure 1
ORIDIFF circuit for computing (3).Figure2 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 bd(1,1),…,bd(1,NQ),…,bd(i,1),…,bd(i,NQ),…, bd(NT,1),…,d(NT,NQ), and the corresponding o11,…,o1,NQ,…,oi,1,…, oi,NQ,oNQ,1,…,oNT,NQ; Bob’s inputs are random masks r11,…,r1,NQ,…,ri1,…,ri,NQ,…,rNT,NQ, where rij=ri3+ri4+ri,j5 and 1≤i≤NT,1≤j≤NQ. Note that bd(i,j) is larger than rij and they are both λ-bit positive integers. However, the result of bd(i,j)-rij is the squared distance dE(i,j) which can be represented as 2ρ-bit integer (λ>2ρ). Let dE(i,1),…,dE(i,NQ)denote the distances between a minutia Mi in MT and each minutia in MQ, respectively, (1≤i≤NT). Among these distances, only the smallest one that simultaneously meets the requirement specified in (3) is picked out to compare with the threshold TD. Let τ denote its bits length (note that τ<2ρ). To reduce the complexity of overall circuits, instead of directly comparing dE(i,j) with TD, we generate d*(i,j) which is only a τ bits value as follows and compare it with TD later, which can avoid unnecessary bit operations:
(10)d*(i,j)={2τ-1,ifbd(i,j)-rij≥2τoroij=1τlow-orderbitsifbd(i,j)-rij<2τ,oij=0,ofbd(i,j)-rij.Figure 2
Finding matched minutiae and counting their number.The module SPADIS shown in Figure3(a) uncovers the masks and compute d*(i,j). The logical OR of the high λ-τ bits of bd(i,j)-rij is computed. If the result is 1, bd(i,j)-rij must be greater than TD. Hence, there is no need to compare the other bits. The λ-τ-bit OR operation can be implemented by λ-τ-1 two-inputs-OR gates one by one. Besides, if the bit oij is 1, it indicates that the orientation difference between Mi and Mj is too large to meet the requirement, so OR of oij 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 2τ-1 or the low τ bits of bd(i,j)-rij. Since τ is significantly smaller than λ, the method saves a mass of gates in MIN and CMP circuits.Structure of module SPADIS for Euclidean distance, MINM, and MIN2. (a) SPADIS, (b). MINM, and (c). MIN2.
(a)
(b)
(c)The module of MINM is presented in Figure3(b), which takes as the inputs d*(i,1),…,d*(i,NQ) where 1≤i≤NT and picks out the minimum. The circuit MIN2 shown in Figure 3(c) is the functional unit of MINM, which compares two inputs w against v and selects the smaller one.In Figure2, if the output of ith CMP is 1 (1≤i≤NT), it indicates that there exists a minutia belonging to MQ that matches the ith minutia Mi belonging to MT. The module of COUNTER further counts the number of these “1”s. Obviously, the number is at most NT, so n=⌊log⁡NT⌋ bits are needed to represent it. To reduce the complexity, we do not use NT  n-bit adders one by one to construct COUNTER. Instead, we use a hierarchical structure, which includes n levels. The first level is composed of 1-bit ADDs with the number of ⌈NT/2⌉. The second level is composed of 2-bit ADD with the number of ⌈⌊NT/2⌋/2⌉, and so forth. The nth level is composed of only one n-bit ADD. Figure 4 shows an example for constructing COUNTER with NT being thirteen.Figure 4
An example of COUNTER withNT=13.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.Table 3
Number of non-XOR gates in circuit for Euclidean distance.
ORIDIFF
SPADIS
MIN2
MINM
COUNTER
MATCH
Total
7
7
μ
+
4
δ
+
σ
+
5
4
ρ
+
2
δ
+
12
2
τ
2
τ
N
Q
m
*
(
4
ρ
+
2
δ
+
6
+
2
τ
)
N
T
N
Q +τNT+m
(
7
μ
+
4
ρ
+
6
δ
+
σ
+
17
+
2
τ
)
N
T
N
Q +τNT+m
Note: *m=⌈NT/2⌉+2⌈⌊NT/2⌋/2⌉+⋯+⌊log⁡NT⌋.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,Tθ and TD. Alice carries out the OT protocol along with Bob to obtain the garbled values corresponding to her inputs—bd(i,j) and bo(i,j) for 1≤i≤NT, 1≤k≤NB. 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 TM, 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 {bx(i,j),by(i,j),bo(i,j)∣1≤i≤NT,1≤j≤NQ}. 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 NT×NQ ORIDIFF to take off the random masks of bo(i,j) and compute the directional differences, select the minutiae belonging to MQ, whose directional differences are smaller than Tθ 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 TD. 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.Figure 5
Structure of SPADIS for city block distance.SPADIS in Figure5 takes as the inputs bx(i,j), r1i, by(i,j), r2i, and oi,j. It firstly takes off the random masks (r1i,r2i) on bx(i,j) and by(i,j). Note that bx(i,j) and (by(i,j) may be negative since there exists subtraction operation in step 2) of City-Block-Distance, so bx(i,j), r1i, by(i,j),and r2i all need an additive bit as the signed bits. Therefore, their bits lengths are set to be ρ+δ+2 when they enter SPADIS. In Figure 5, the left two SUBs and a MUX serve to compute |xi-xj′| and the right correspondences serve to compute |yi-yj′|. The output of ADD is exactly the city block distance |xi-xj′|+|yi-yj′|. 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 d*(i,j):
(11)d*(i,j)={2τ′-1,if|xi-xj′|+|yi-yj′|≥2τ′oroij=1τ′low-orderbitsofif|xi-xj′|+|yi-yj′|<2τ′,|xi-xj′|+|yi-yj′|,oij=0.The bits length ofd*(i,j) is τ′ which is that of the threshold TD. 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.Table 4
Number of non-XOR gates in circuit for city block distance.
ORIDIFF
SPADIS
MIN2
MINM
COUNTER
MATCH
Total
7
7
μ
+
4
δ
+
σ
+
5
8
ρ
+
8
δ
+
10
2
τ
′
2
τ
′
N
Q
m
*
(
8
ρ
+
8
δ
+
10
+
2
τ
′
) ×  NTNQ+τ′NT+m
(
7
μ
+
8
ρ
+
12
δ
+
σ
+
15
+
2
τ
′
) NTNQ+τ′NT+m
Note: *m=⌈NT/2⌉+2⌈⌊NT/2⌋/2⌉+…+⌊log⁡NT⌋.


## 5.1. Circuits for Euclidean Distance

After the protocol Euclidean-Distance is carried out, Alice learns the blind Euclidean distance bd(i,j)=dE(i,j)+rij and the blind directional difference bo(i,j)=θi-θj′+ri6. The remaining tasks of authentication are implemented by using garbled circuits. The circuits firstly take off the random masks covered on bd(i,j) and bo(i,j) to get the Euclidean distances and the directional differences. Then, for each minutia (xi, yi, θi) belonging to MT(1≤i≤NT), the closest matching minutia which belongs to MQ is found according to (2) and (3). To do so, the circuits choose the minutiae belonging to MQ as the candidates, whose directional differences are smaller than the threshold Tθ (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 TD (see (2)). Finally, the number of minutiae belonging to MQ 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.Figure1 shows the circuit ORIDIFF to take off the mask of bo(i,j) and compute the result according to (3). Alice’s input is bo(i,j) and Bob’s, ri6 and Tθ. If θi-θj′ is smaller than Tθ, ORIDIFF outputs oaij= “1”; otherwise oaij= “0”. Since bo(i,j) is the result of ei-θj′, bo(i,j) is likely to be negative, and it must be represented as a signed integer. We represent it as a μ+δ+2-bit integer in two’s complement representation to cater to the requirement of circuit SUB [24], and so does ri6. In ORIDIFF, the first SUB(in Figure 1, from left to right) outputs the result of θi-θj′. 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 2μ+δ+2. 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 |θi-θj′| which is smaller than 360°. However, the output of the MUX is μ+δ+1 bits. Since the bits length of the orientation is μ bits, μ low bits of the output can be only preserved for the next computation. As μ+δ+1 is significantly bigger than μ, this method substantially reduces the number of gates. The third SUB in ORIDIFF computes the result of 360-|θi-θj′|. And the second MUX in ORIDIFF outputs od=min⁡⁡(|θi-θj′|,360-|θi-θj′|). If there exists the forged input, the δ+1 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 od and Tθ are μ and σ, respectively, and σis smaller than μ. So if the high order μ-σ bits are not zeros, od must be greater than Tθ, 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 δ+2 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 2σ-1 as its output, otherwise, the low σ bits of the second MUX. The OR operation can be implemented by λ-τ-1 two-inputs-OR gates one by one. At last, the output of the third MUX is compared against Tθ, if it is greater than Tθ, oij; 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 NT×NQ ORIDIFF for Alice to evaluate (3) where i=1,…,NT and j=1,…,NQ.Figure 1
ORIDIFF circuit for computing (3).Figure2 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 bd(1,1),…,bd(1,NQ),…,bd(i,1),…,bd(i,NQ),…, bd(NT,1),…,d(NT,NQ), and the corresponding o11,…,o1,NQ,…,oi,1,…, oi,NQ,oNQ,1,…,oNT,NQ; Bob’s inputs are random masks r11,…,r1,NQ,…,ri1,…,ri,NQ,…,rNT,NQ, where rij=ri3+ri4+ri,j5 and 1≤i≤NT,1≤j≤NQ. Note that bd(i,j) is larger than rij and they are both λ-bit positive integers. However, the result of bd(i,j)-rij is the squared distance dE(i,j) which can be represented as 2ρ-bit integer (λ>2ρ). Let dE(i,1),…,dE(i,NQ)denote the distances between a minutia Mi in MT and each minutia in MQ, respectively, (1≤i≤NT). Among these distances, only the smallest one that simultaneously meets the requirement specified in (3) is picked out to compare with the threshold TD. Let τ denote its bits length (note that τ<2ρ). To reduce the complexity of overall circuits, instead of directly comparing dE(i,j) with TD, we generate d*(i,j) which is only a τ bits value as follows and compare it with TD later, which can avoid unnecessary bit operations:
(10)d*(i,j)={2τ-1,ifbd(i,j)-rij≥2τoroij=1τlow-orderbitsifbd(i,j)-rij<2τ,oij=0,ofbd(i,j)-rij.Figure 2
Finding matched minutiae and counting their number.The module SPADIS shown in Figure3(a) uncovers the masks and compute d*(i,j). The logical OR of the high λ-τ bits of bd(i,j)-rij is computed. If the result is 1, bd(i,j)-rij must be greater than TD. Hence, there is no need to compare the other bits. The λ-τ-bit OR operation can be implemented by λ-τ-1 two-inputs-OR gates one by one. Besides, if the bit oij is 1, it indicates that the orientation difference between Mi and Mj is too large to meet the requirement, so OR of oij 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 2τ-1 or the low τ bits of bd(i,j)-rij. Since τ is significantly smaller than λ, the method saves a mass of gates in MIN and CMP circuits.Structure of module SPADIS for Euclidean distance, MINM, and MIN2. (a) SPADIS, (b). MINM, and (c). MIN2.
(a)
(b)
(c)The module of MINM is presented in Figure3(b), which takes as the inputs d*(i,1),…,d*(i,NQ) where 1≤i≤NT and picks out the minimum. The circuit MIN2 shown in Figure 3(c) is the functional unit of MINM, which compares two inputs w against v and selects the smaller one.In Figure2, if the output of ith CMP is 1 (1≤i≤NT), it indicates that there exists a minutia belonging to MQ that matches the ith minutia Mi belonging to MT. The module of COUNTER further counts the number of these “1”s. Obviously, the number is at most NT, so n=⌊log⁡NT⌋ bits are needed to represent it. To reduce the complexity, we do not use NT  n-bit adders one by one to construct COUNTER. Instead, we use a hierarchical structure, which includes n levels. The first level is composed of 1-bit ADDs with the number of ⌈NT/2⌉. The second level is composed of 2-bit ADD with the number of ⌈⌊NT/2⌋/2⌉, and so forth. The nth level is composed of only one n-bit ADD. Figure 4 shows an example for constructing COUNTER with NT being thirteen.Figure 4
An example of COUNTER withNT=13.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.Table 3
Number of non-XOR gates in circuit for Euclidean distance.
ORIDIFF
SPADIS
MIN2
MINM
COUNTER
MATCH
Total
7
7
μ
+
4
δ
+
σ
+
5
4
ρ
+
2
δ
+
12
2
τ
2
τ
N
Q
m
*
(
4
ρ
+
2
δ
+
6
+
2
τ
)
N
T
N
Q +τNT+m
(
7
μ
+
4
ρ
+
6
δ
+
σ
+
17
+
2
τ
)
N
T
N
Q +τNT+m
Note: *m=⌈NT/2⌉+2⌈⌊NT/2⌋/2⌉+⋯+⌊log⁡NT⌋.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,Tθ and TD. Alice carries out the OT protocol along with Bob to obtain the garbled values corresponding to her inputs—bd(i,j) and bo(i,j) for 1≤i≤NT, 1≤k≤NB. 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 TM, 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 {bx(i,j),by(i,j),bo(i,j)∣1≤i≤NT,1≤j≤NQ}. 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 NT×NQ ORIDIFF to take off the random masks of bo(i,j) and compute the directional differences, select the minutiae belonging to MQ, whose directional differences are smaller than Tθ 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 TD. 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.Figure 5
Structure of SPADIS for city block distance.SPADIS in Figure5 takes as the inputs bx(i,j), r1i, by(i,j), r2i, and oi,j. It firstly takes off the random masks (r1i,r2i) on bx(i,j) and by(i,j). Note that bx(i,j) and (by(i,j) may be negative since there exists subtraction operation in step 2) of City-Block-Distance, so bx(i,j), r1i, by(i,j),and r2i all need an additive bit as the signed bits. Therefore, their bits lengths are set to be ρ+δ+2 when they enter SPADIS. In Figure 5, the left two SUBs and a MUX serve to compute |xi-xj′| and the right correspondences serve to compute |yi-yj′|. The output of ADD is exactly the city block distance |xi-xj′|+|yi-yj′|. 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 d*(i,j):
(11)d*(i,j)={2τ′-1,if|xi-xj′|+|yi-yj′|≥2τ′oroij=1τ′low-orderbitsofif|xi-xj′|+|yi-yj′|<2τ′,|xi-xj′|+|yi-yj′|,oij=0.The bits length ofd*(i,j) is τ′ which is that of the threshold TD. 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.Table 4
Number of non-XOR gates in circuit for city block distance.
ORIDIFF
SPADIS
MIN2
MINM
COUNTER
MATCH
Total
7
7
μ
+
4
δ
+
σ
+
5
8
ρ
+
8
δ
+
10
2
τ
′
2
τ
′
N
Q
m
*
(
8
ρ
+
8
δ
+
10
+
2
τ
′
) ×  NTNQ+τ′NT+m
(
7
μ
+
8
ρ
+
12
δ
+
σ
+
15
+
2
τ
′
) NTNQ+τ′NT+m
Note: *m=⌈NT/2⌉+2⌈⌊NT/2⌋/2⌉+…+⌊log⁡NT⌋.


## 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 388×374 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, x, y, 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 28×100=2800 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, 99×100/2=4950 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 5
Bits length of parameters in our experiments.
ρ
μ
δ
σ
τ
/
τ
′
τ
/
τ
′
η
r
1
η
r
2
η
r
3
η
r
4
η
r
5
η
r
6
λ
Scenario 1
8
8
8
4
8/4
14
14
22
22
24
14
25
Scenario 2
7
7
7
3
6/3
13
13
20
20
22
14
23
Scenario 3
6
6
6
2
4/2
12
12
18
18
20
14
21Table6 gives the average running time of our protocols on FVC2002-DB1, in which “Enc” refers to the time related to Paillier encryption; “OT” 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 NT×NQ, 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 NT and NQ were both set to be 90. Accordingly, the excessive minutiae will be discarded. Step (1) of Euclidean-Distance or City-Block-Distance was computed in the preparation of “Enc.” In the preparation phase of “Circuit,” the gabled circuits for NT=90 and NQ=90 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 90×90 circuits, in this phase, the server reset the corresponding wire labels according to actual NT and NQ 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 6
Running time of the proposed methods.
Euclidean distance
City block distance
Average times
Scenario 1
Scenario 2
Scenario 3
Scenario 1
Scenario 2
Scenario 3
s
s
s
s
s
s
E
n
c
0.158
0.158
0.158
0.048
0.033
0.031
Prep
O
T
0.703
0.703
0.696
0.703
0.703
0.698
C
i
r
c
u
i
t
20. 818
16.392
14.010
28.974
25.869
22.893
E
n
c
3.301
3.089
2.991
0.048
0.030
0.028
Exec
O
T
3.980
3.465
2.904
5.291
4.308
3.497
C
i
r
c
u
i
t
9.732
8.870
8.684
15.475
13.238
11.772
Average total times
17.013
15.424
14.579
20.814
17.576
15.297Table7 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 TD, the radius of the circle is TD, while the side length of the diamond is 2TD. Thus, the area of the diamond is only (2TD)2/π(TD)2≈63.7% 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 TD=15, Tθ=20. 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 TD=15, Tθ=20.Table 7
Accuracy performance of the proposed methods.
ERR
Euclidean distance
City block distance
Scenario 1
Scenario 2
Scenario 3
Scenario 1
Scenario 2
Scenario 3
T
D
T
D
=
15
,
T
θ
=
20
0.039
0.05
0.051
0.025
0.036
0.045
T
D
=
20
,
T
θ
=
30
0.087
0.092
0.095
0.06
0.075
0.082ROC curves for authentication. (a) Euclidean distance, (b) city block distance.
(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.



---

*Source: 525387-2014-02-24.xml*