Privacy-preserving similarity evaluation and application to remote biometrics authentication

Abstract

In this paper, a new method for secure remote biometric authentication preventing the vulnerability of compromised biometrics is presented. The idea is based on a public-key cryptographical protocol, referred as zero-knowledge proof, which allows a user to prove that she has surely a valid biometric data without revealing the data. Hence, the scheme is free from the risk of disclosure of biometric data. Even if a malicious administrator has a privilege access to the private database, it is infeasible for him to learn the private template. This paper studies two well-known definitions, the cosine correlation and the Euclidean distance as similarities of given two feature vectors. Both similarities are defined with some multiplications and additions, which can be performed in privacy-preserving way because of the useful property of public-key commitment scheme, additive homomorphism. The estimation based on the experimental implementation shows that the private Euclidean distance scheme archives better accuracy in terms of false acceptance and rejection than the private cosine coloration scheme, but it requires about $5/2 n \ell$ overhead to evaluate $n$-dimension feature vectors consisting of $\ell$-bit integers.

1 Introduction

Biometrics identifiers are now commonly used to identify individuals in more secure and more efficient ways than the conventional password-based methods. Typically, the biometric identifiers including fingerprint, vein, iris, facial images are scanned and processed in appropriate algorithm to extract a feature vector, which is stored as a template in registration (Maltoni et al. 2003). In authentication, a feature vector extracted from a newly scanned image will be compared to the template to verify that the owner of the biometric data is legitimate or not.

The biometric recognition, however, is mostly made in local environment, e.g., a matching with the template data stored in secure smartcard (in ATM cards), or a user authentication at personal laptop PCs. The reason of limitation in local is the known vulnerabilities of remote biometric authentication that once a biometric template is stolen, it is stolen forever and can not be recovered. If we store our biometric data to some service provider, we immediately face risks that the server may be compromised, or a malicious administrator of the server may learn our highly private data and can disclose it.

Many researchers pointed out the issue in remote biometrics authentication and several attempts addressing it have been made. Ratha et al. (2001) proposed a “cancelable biometrics”, using a morphing technique to transform biometric data into a randomized form, which depends on given morphing function. Jeong et al. (2006) proposed a changeable biometrics for face recognition using the principal component analysis (PCA) and the independent component analysis (ICA). Given two vectors chosen from PCA and ICA coefficients, they extract from an input face image the transformed vector according to a scrambling rule. When the transformed template is compromised, the scrambling rule is replaced by a new one. Juels and Sudan’s “fuzzy vault scheme” (Juels and Sudan 2002) is an improvement upon the previous work by Juels and Wattenberg (1999). In Juels and Sudan (2002), they use the polynomial reconstruction problem based on an error-collection code such as the Reed-Solomon. Clancy et al. (Clancy and Kiyavash 2003) proposed a “fingerprint vault system” based on the fuzzy vault. Using multiple minutiae location sets, they use canonical positions of minutiae, as the elements of a set. Uludag and Jain (2004) proposed a fuzzy vault system for fingerprint using the Lagrange interpolation and the cyclic redundancy check (CRC) for testing polynomial reconstruction instead of the error-collection step.

Many cryptographical primitives are introduced to construct secure protocols. Bringer et al. proposed a scheme using a group signature in Julien et al. (2008). In Julien et al. (2007), an extended private information retrieval is used and then improved in Julien and Hervé (2008), too. Socek et al. used a set intersection as the degree of similarity in Daniel and Vladimir (2008). Barbosa et al. proposed a hybrid approach based on the support vector machine classifier and the Paillier public key encryption in Manuel et al. (2008).

Studies on security model of remote biometric authentications are made in Qiang et al. (2008). In Qiang et al. (2008), Tang et al. proposed a new formal security model for biometric-based remote authentication schemes so that several privacy concerns can be covered in it. Une et al. proposes a measure for evaluating schemes, called “wolf attack probability” in Masashi et al. (2007).

In this paper, we present a new method for secure remote biometric authentication preventing the vulnerability of compromised biometrics. Our idea is based on a public-key cryptographical protocol, referred as zero-knowledge proof, which allows a user to prove that she has surely a valid biometric data without revealing the data. Hence, the scheme is free from the risk of disclosure of biometric data. Even if the administrator with privilege access to the private database is malicious, it is infeasible to learn the private template. Without learning the template stored at the server, he performs an evaluation of similarities between the template and the new input in privacy-preserving way.

The zero-knowledge proof is generally “expensive” in terms of communication and computation costs. The performance of schemes depends on what similarity measure is used for the secret evaluation. In this paper, we study two well-known definitions, the cosine correlation and the Euclidean distance as similarities of given two feature vectors. Both similarities are defined with some multiplications and some additions, which can be performed in privacy-preserving way because of the useful property of public-key commitment scheme, additive homomorphic. The estimation based on the experimental implementation shows that the private Euclidean distance scheme achieves better accuracy in terms of false acceptance and rejection than the private cosine correlation scheme, but it requires about $5/2 n \ell$ overhead to evaluate $n$-dimension feature vectors consisting of $\ell$-bit integers.

The remainder of this paper is organized as follows. After giving the definitions for some fundamental building blocks, e.g., similarities and commitment functions, in Sect. 2, we construct two protocols for secure private similarity evaluation in Sect. 3. In Sect. 4, we evaluate our two proposed protocols from several viewpoints, including accuracy, performance and security. Section 5 concludes our study on secure remote biometric authentication.

2 Preliminaries

2.1 Similarities

Let $\user2{a}=(a_1,\ldots, a_n)$ and $\user2{b}=(b_1,\ldots, b_n)$ be $n$-dimensional vectors of $R^n.$ We consider the following two well-known similarities between $\user2{a}$ and $\user2{b},$ which will be evaluated in privacy-preserving way in a later section.

Definition 1

A cosine correlation is a similarity between $\user2{a}$ and $\user2{b}$ defined as

$$ {\rm cos}(\user2{a},\user2{b}) = {\frac{\user2{a} \cdot \user2{b}}{|| \user2{a}||\cdot||\user2{b}||}}={\frac{a_1 b_1+\cdots+a_n b_n}{\sqrt{a_1^2+\cdots+a_n^2} \sqrt{b_1^2+\cdots+b_n^2}}} $$

where $||\user2{a}||$ is a norm of $\user2{a}.$

Definition 2

An Euclidean distance, $d(\user2{a}, \user2{b}),$ is defined as

$$ d(\user2{a}, \user2{b})=||\user2{a}-\user2{b}||=\sqrt{\sum_i^n (a_i - b_i)^2}. $$

For simplification, taking the normalization of $\user2{a}$ and $\user2{b},$ we can reduce the computational cost of cosine correlation as $cos(\user2{a}/||\user2{a}||, \user2{b}/||\user2{b}||) = \user2{a} \cdot \user2{b}.$ Taking squared as $d(\user2{a}, \user2{b})^2,$ we can omit the computation of square root for Euclidean similarity.

2.2 Secure commitment

A commitment is a cryptographical primitive to commit to a value while keeping it hidden and then reveal the committed value later.

A function $E(m,r)$ is considered as secure commitment to message $m,$ where $r$ is a random number, if it satisfies

• 1. No information reveals from $E(m, r),$ and

• 2. No one finds $m' \ne m, r$ and $r'$ such that $E(m, r) = E(m', r').$

Fujisaki and Okamoto proposed (Fujisaki and Okamoto 1997) a probabilistic commitment scheme based on the integer factorization problem as follows.

Definition 3

Let $n$ be a composite number that no one knows the factors, and $g$ and $h$ be elements of $Z_{N}$ such that $\log_{g} h$ is not known by anybody. A commitment to $m$ is

$$ E(m,r) = g^{m}h^{r} \bmod N, $$

where $r$ is a random number.

The Fujisaki–Okamoto commitment has an additive homomorphism, a useful property for privacy-preserving computation, satisfying

$$ E(m,r) \times E(m',r') = E(m+m',r+r')\hbox{ and }\ E(m,r)^{x} = E(mx, rx), $$

where the addition $m + m'$ is an ordinary arithmetic (not modular arithmetic) since we do not know the order of $g$ and $h.$

We often write $E(m)$ to mean $E(m,r)$ when we do not necessary specify the random value.

2.3 Zero-knowledge proof of commitment

We introduce a cryptographical protocol for proving that a committed value $m$ lies in a specific interval $[a,b]$ without revealing $m,$ often known as Boudot’s Range Proof (Boudot 2000).

Definition 4

Let $F$ be a commitment $E(m,r)$ to message $m.$ A range proof of knowledge of commitment is a cryptographical protocol allowing a prover to show that committed $m$ is in $[a,b]$ without revealing $m$ to a verifier, denoted by

$$ PK \left\{ m,r \;\big\arrowvert\; F=E(m,r) \wedge m \in [a,b] \right\} $$

where $r$ is uniformly chosen over $[-2^s N +1, 2^s N -1]$ and $s$ is a security parameter [e.g., $s = 160$ (bit)].

The range proof takes about five times of overhead of a standard zero-knowledge proof of the committed value $PK \{m \;\big|\; F = E(m,r)\}.$ Namely, it is expensive in terms of both computation and communication.

3 Private similarity evaluations

3.1 Overview and assumption

In our model, Alice is a user who tries to prove her identity to a server. Bob is the server who authenticates Alice based on the data that Alice has already registered. Assume that Alice does not fully trust Bob, that is, in so-called “honest-but-curious” model, where all players follow the protocol honestly, but are curious in that they try to find out as much as possible about the other input. In other words, no party can intentionally forget knowledge that it learns during the protocol. Therefore, instead of her private biometric data $\user2{x}= (x_1,\ldots, x_n),$ Alice registers the commitment to $\user2{x}, E(\user2{x}),$ from which Bob cannot learn $\user2{x}.$ To authenticate her to Bob, Alice scans her fresh biometric data $\user2{y} = (y_1,\ldots, y_n)$ and proves $\user2{x} \approx \user2{y}$ to Bob without revealing $\user2{y}$ (nor $\user2{x}$) in the zero-knowledge proof of similarities between $\user2{x}$ and $\user2{y}.$

There are many efficient protocols for proving several kinds of equalities in zero-knowledge way, and we need to prove privately that $\user2{y}$ is “close” to $\user2{x}.$ It is not so hard to implement the fuzzy matching if Alice is allowed to access her tamper-proof device to recover $\user2{x}$ to be compared with new one $\user2{y}.$ In the next section, we will show that the state-of-the-art cryptographical protocols allow us to evaluate similarities between any given committed vectors and to show the difference is within a range, without disclosing private biometric data to anyone. Hence, the protocol is free from the risk of private information disclosure.

3.2 Private cosine correlation evaluation

We show a protocol for secure evaluation of a cosine correlation given $\user2{x}$ and $\user2{y}$ in Fig. 1.

Fig. 1

Protocol for cosine correlation evaluation

First of all, Alice needs to compute the commitment to her true private input $\user2{x}$ using random values $r_1,\ldots, r_n$ chosen uniformly over $Z_N,$ as $E_i = E(x_i/c, r_i)$ for $i = 1, \ldots, n.$ For reducing computational cost, we use the norm $c = ||\user2{x}||$ to normalize the committed input $x_i.$ The random values are used for making the commitment indistinguishable against Bob in a sense that he can not distinguish two messages with non-negligible probability.

The key idea of the protocol is to evaluate the cosine correlation between template data $\user2{x}$ and an input data $\user2{y}$ without revealing private $\user2{x}$ and $\user2{y}.$ The additive homomorphic property of the commitment scheme allows Bob to compute the commitment of the cosine correlation between hidden $\user2{x}$ and $\user2{y}$ at the third step as follows:

$$ \begin{aligned} D_C &=\prod_{i=1}^n G_{i=1}^n = \prod_{i=1}^n E(x_i/c, r_i)^{y_i/c'} = \prod_{i=1}^n E(x_i y_i/c c', r_i y_i/c' )\\ &=E\left({\frac{1}{||\user2{x}|| ||\user2{y}||}} \sum_{i=1}^n x_i y_i, \sum_{i=1}^n r_i y_i/c'\right) = E({\rm cos}(\user2{x},\user2{y}), R_C) \end{aligned} $$

where $R_C$ is a random element computed as $\sum_{i=1}^n r_i y_i/c'.$ Since Alice is allowed to access the tamper-proof device to obtain random values used to commit $\user2{x},$ she is able to learn $R_C,$ and thereby get $d_C.$ She also needs to prove to Bob that the commitment $G_i$ has been correctly computed as defined formula without revealing $y_i$ in $PK_1.$

At the end of the protocol, using the Boudot’s range proof (Boudot 2000) and the conjunctive proof of knowledge (Cramer et al. 1994) ($PK_2$), she can finally convince Bob that she has valid input $\user2{y}$ such that the similarities $d_C = cos(\user2{x}, \user2{y})$ is greater than pre-determined threshold $\tau_1,$ which means that Alice is surely a legitimate user.

3.3 Private Euclidean distance evaluation

Figure 2 shows the protocol private-Euclid for proving Alice’s private identity $\user2{y}$ is within the distance $\tau_2$ from registered $\user2{x}.$ In addition to the protocol private-cosine , it requires Alice to commit to not only $\user2{x}$ but also to squared $\user2{x}$ as $\tilde{E}_i$ at the registration step. Implicitly, we use notation $X$ for the commitment to $x,$ and $\tilde{X}$ for the commitment to $x^2$ in the figure.

Fig. 2

Protocol for Euclidean distance evaluation

The additive homomorphic property allows us to privately evaluate the Euclidean distance between $\user2{x}$ and $\user2{y}$ at side of Bob, at Step 3, as follows:

$$ \begin{aligned} D_E&=\prod_{i=1}^n \tilde{E}_i \tilde{F}_i/ G_i^2 = \prod_{i=1}^n E(x_i^2, r_i x_i) E(y_i^2, \tilde{r}'_i) / E(2 x_i y_i, 2 r_i y_i) \\ &=\prod_{i=1}^n E(x_i^2 + y_i^2 - 2 x_i y_i, r_i x_i + \tilde{r}'_i - 2 r_i y_i)\\ &=E\left(\sum_{i=1}^n x_i^2 - 2 x_i y_i + y_i^2, R_E\right) = E(||\user2{x} - \user2{y}||^2, R_E),\\ \end{aligned} $$

letting $R_E$ be a constant defined as $\sum_{i=1}^n r_i x_i-2r_i y_i+\tilde{r}'_i.$ For constructing zero-knowledge protocols $PK_3, PK_4$ and $PK_5,$ we add a protocol proving that a committed number is a squared number, presented in Boudot (2000). If all proofs are valid, Bob is convinced that Alice is a legitimate user who has registered $\user2{x}$ and hence is able to show the correctly computed commitment of $||\user2{x} - \user2{y} ||^2$ less than threshold $\tau_2.$

4 Evaluation

Most zero-knowledge protocols are designed to be secure in the cost of communicational and computational overhead, which are not often considered as significant. There is a trade-off between performance and security, e.g., reducing a probability being impersonated by half requires double amount of bits to be computed. In addition, we claim that there is one more trade-off between accuracy and performance in secure biometric authentication. The accuracy (and the performance) depends on a function for similarity to be evaluated in zero-knowledge protocol. Hence, it is not trivial to identify the optimal function of similarity for the multiple objective requirements involved each other.

4.1 Feature vector

To compare two similarities, we performed some experiments using actual fingerprint images under the environment listed in Table 1. More than 500 live fingerprints are scanned and performed some sorts of image processing and extraction algorithms, which yield the feature vectors, called ridge-valley orientation.

The feature vector consists of a $18\times18$ matrix of orientations of ridges and valleys of the surface of finger, taking average for each local $16\times16$-pixel image. The ridge-valley orientation is quite stable against a transformation of images, thus good for the evaluation of similarities of high-dimension vectors. While, it needs to deal with empty portions of image caused by miss-scanning. To avoid some elements of feature from being zero, we take $n = L^2$ elements from the core of the $18 \times 18$ matrix. The accuracy of authentication depends on dimension $n$ of the feature, and hence the optimal dimension is a significant issue. Figure 3 shows the variance of similarities (Euclidean distance) of two fingerprint images with respect to dimensions $n = 2 \times 2, 4 \times 4, \ldots, 18\times 18.$ From the observation of the result, we see that $n > 10 \times 10$ provides a good enough similarities to distinguish two images.

Table 1 Experiment environment

Figure 4 shows two distributions of cosine correlations; one between genuine and imposter images (labeled as “Imposter”), and the other one between two distinct images chosen from genuine images (as “Genuine”). The dimension of feature vector is $n = 8^2.$ The genuine images are distributed within a narrow area of range, while the distribution of imposter images is broad. These distributions look almost disjoint, that is, the classification hardly ever fails.

Fig. 3

Variance of similarity $d_E$

Fig. 4

Histogram of Cosine correlations ${\rm cos}(\user2{a}, \user2{b})$

The Euclidean distances of two feature vectors are distributed as well, shown in Fig. 5. In comparison of two similarities, the distribution of genuine images is quite separate from that of imposter images in the Euclidean distance, while these are distributed closely in cosine correlations. Therefore, the accuracy of Euclidean distance is likely to be better than that of the cosine correlation.

Fig. 5

Histogram of Euclidean distances $d(\user2{a}, \user2{b})$

4.2 Accuracy

We show the accuracy of authentication schemes based on the similarities in Fig. 6, where overall accuracy is given as equal error rate (ERR) of thresholds $\tau_1$ and $\tau_2$ with respects to $n,$ the dimensions of feature vectors. An ERR is the rate at which both accept and reject errors are equal. Obviously, the experiment means that the Euclidean distance is superior in accuracy to the cosine correlation for all dimensions $n.$ The result is compatible with the analysis of distributions studied in the above section.

Fig. 6

Equal error rates (ERRs) with respect to dimension $n$

Figure 7 shows the relative operating characteristic plot (ROC) for particular dimension $n = 18^2,$ illustrating the change of false rejection rate (FRR) with respects to False Acceptance Rate (FAR). We observe that the tradeoff between these rates by varying thresholds, and the cosine correlation has higher error rate than the Euclidean distance. After all, the Euclidean distance is better similarity measure than the cosine correlation in terms of accuracy.

Fig. 7

Relative operating characteristic plot (ROC) for $n=18^2$-dimension future vector

4.3 Performance

There are two factors for performance of protocols; the computational cost and the communication cost. The former is estimated as a number of modular exponentiations, which is the dominant factor of processing time, for each step in zero-knowledge proof. The latter is the function taking dimension $n$ and size of modulus $\ell = |N|,$ typically $\ell = 1024$ bit. We summarize the estimation of both costs in Table 2. The estimation shows that the Euclidean distance requires about double, $5/2 n\ell$ overhead of the cosine correlation to evaluate $n$ -dimension vectors consisting of $\ell$ -bit integers, in theory.

Table 2 Estimation of costs for each step in two protocols

In addition to the estimation from equations, we measure the processing time based on sample implementation of the protocols. Figure 8 shows the experimental results, where the size of modulus is $\ell=|N|=1024,$ security parameter in zero-knowledge protocol is $t=160$ bit, and dimension of feature vector ranges from $2\times2$ to $18\times18.$ We confirm that the estimation is compatible with the experimental result. Note that there is a constant amount of time at $n = 0,$ which means the overhead caused at $PK_2$ and $PK_5.$ In typical setting, say $n = 8^2,$ protocol private-cosine and private-Euclid take $3,218$ and $8,078$ (ms), respectively.

Fig. 8

Processing times for evaluating protocols with respect to dimension $n$

4.4 Security

The security of the proposed protocols are based on the security of the strong RSA assumption, the difficulty of the decision Diffie–Hellman problem in the random oracle model. The probability to forge the commitments in PKs can be negligible as the security parameter increases. On the other hand, the common biometric features have less entropy than the commitment scheme. The probability of malicious party to impersonate someone without his biometric feature is fixed at a level determined by the entropy of the feature. Hence, the zero-knowledge protocol is secure enough to apply the biometric authentication.

Definition 5

Let $n$ be a secure RSA modulus. We say that RSA is a $(t, \epsilon)$-secure one-way function if for any adversary $A$ with running time less than $t,$ we have ${\rm Pr}[ A(N, e, x^e) = x ] < \epsilon ,$ where $e \in Z_{\varphi(N)}^*, x \in Z_n^*.$

Theorem 1

(Security) Assume that RSA is a $(t, \epsilon_{RSA})$-secure one-way function. The Cosine correlation evaluation protocol is $(t', q, \epsilon')$-secure against existential forgeries making at most $q$ chosen-message queries and running in time at most $t$ in the random oracle model.

The security of the Euclidean distance evaluation protocol can be shown in the same way. The confidentiality of the committed value has been proved in Fujisaki and Okamoto (1997).

Theorem 2

(Fujisaki and Okamoto 1997) If the probability that any polynomial-time adversary can factor $n$ is negligible, there exists no probabilistic polynomial-time algorithm which given $E(x/c,r)$ can output $(x'/c', r')$ such that $(x/c,r) \ne (x'/c',r')$ and $E(x/c,r) = E(x'/c',r').$

Our model makes an assumption of tamper-freeness of secure device that stores the template feature vector with the random values used for commitment. We consider the assumption is reasonable in practical perspective since many secure devices are widely used in our daily life, e.g., the RFID and the smart cards. The requirement of secure device, however, is not useful from the usability point of view.

5 Conclusions

We have studied the protocols for secure similarity evaluation of vectors, private-cosine and private-Euclid , based on the zero-knowledge proof of range. The Private-Cosine allows a user to convince a server that the user has a secret similar to the data stored at server in a sense of the cosine correlation, while protocol Private-Euclid uses the Euclidean distance to evaluate similarity. The latter archives better accuracy in terms of false acceptance and rejection than the former in the cost of computational overhead. Our schemes are designed for secure remote biometric authentication that no malicious party including even server administrator can reveal private biometric data.