Cancelable biometrics

• Dr. Andrew Teoh Beng Jin, School of Electrical and Electronic Engineering, Yonsei University, Korea

• Mr. Lim Meng Hui, Yonsei University

Cancelable biometrics refers to the intentional and systematically repeatable distortion of biometric features in order to protect sensitive user-specific data. If a cancelable feature is compromised, the distortion characteristics are changed, and the same biometrics is mapped to a new template, which is used subsequently. Cancelable biometrics is one of the major categories for biometric template protection purpose besides biometric cryptosystem.

Introduction

Although biometrics is a powerful tool against repudiation and has been widely deployed in various security systems, biometric characteristics are largely immutable, resulting in permanent biometric compromise when a template is stolen. The concept of cancelable biometrics was introduced to make a biometric template can be cancelled and be revoked like a password, as well as being unique to every application. Cancelable biometrics requires storage of the distorted version of the biometric template which provide high privacy level by allowing multiple templates to be associated with the same biometric data. This helps to promote non-linkability of user’s biometric data stored across various databases.

Objectives

Four objectives of designing a cancelable biometric scheme are as followed:

• Diversity: No same cancelable features can be used across various applications, therefore a large number of protected templates from same biometric feature is required.
• Reusability/Revocability  : Straightforward revocation and reissue in the event of compromise.
• Non-invertibility: Non-invertibility of template computation to prevent recovery of original biometric data.
• Performance: The formulation should not deteriorate the recognition performance.

Methods

The first attempt towards this direction was recorded by Soutar et al. (1998) but the concrete idea of cancelable biometrics was furnished by Bolle et al. (2002). This area is growing rapidly and numerous new techniques have been proposed since then. The methods generally fall into two categories: (1) Biometric Salting and (2) Non-invertible Transforms.

A distinct advantage of cancelable biometric compare to other biometric template techniques such as biometric cryptosystem is that the transformed biometrics can remain in the same feature space of the original ones, so that the same matcher can be used for authentication.

Biometric Salting

Figure 1: Block diagram of Biometric Salting.

Biometric salting resembles to password salting in cryptography, which consists of random bits r used as the input factor to be concatenated with a secret key, \(k\ .\) The output is often stored as hash \(H(r+k)\) in the database. Biometric salting follows the same principle such that a user-specific and independent input factor (auxiliary data such as a password or user-specific random numbers) is blended with biometric data to derive a distorted version of the biometric template. Since the auxiliary data is externally derived and interact directly with biometric data, it can be changed and revoked easily but must be kept secretly for maximum security protection. However, since the external confidential keys or passwords are easily to be lost, stolen or compromised, the accuracy and vulnerabilities of existing schemes should be justified (Kong et al., 2008).

An instance of biometric salting, namely biohashing, which is based on user-specific random projection was proposed by Teoh et al. (2004, 2006). A user-specific random matrix R with size \(r\) x \(c\) is generated from the auxiliary data, and the Gram-Schmidt orthonormalization is carried out such that \(c\) columns of R are orthonormal. The extracted feature vector x is then projected with y = R^Tx, and y is thresholded by b_i = 0, if y_i < τ, and b_i = 1, otherwise for \(i\) = 1, 2, …,\(c\ ,\) where τ is a prefix threshold which is usually set to 0. The binary vector b is stored as the template. The formulation with its optimal setting has been examined with several biometric modalities such as fingerprint, iris, palm print, speech and face with nearly zero error rates. However, Biohash performance degrades substantially in the stolen-token scenario when a genuine user token is “stolen” and utilized by an imposter for the verification purpose. Besides that, the non-invertibility of biohashing could be jeopardized if both y and R are known and if ratio of r/c is near to 1. This is because biohashing is essentially a quantized under-determined linear equation system, which could be solved partially via pseudo-inverse operation.

A variant of BioHashing, known as Multistage Random Projection (MRP) (Teoh and Chong, 2007) was proposed to address the stolen-token performance issue. Both theoretical and experimental analysis showed that the performance regresses to the original system under stolen-token scenario. Besides, Lumini et al. (2007) improved the performance of BioHashing under stolen-token scenario by utilizing different threshold values and fuse the scores. The invertibility issue, was addressed with BioPhasoring (Teoh et al., 2006, 2007), a quantized underdetermined non-linear equation system as well as resampled and concatenation of long BioHash with random subspace technique (Nanni and Lumini, 2008). Other proposals that stem from the idea of user-specific random projection include random correlator (Chong et al., 2006), multiple high dimension random projection (Kim and Toh, 2007), shifted Random Orthonormal Transformation (Wang and Plataniotis, 2007), one-time face template (Lee et al., 2007), 2^N Discretization (Teoh et al., 2008), Preserving Transform with distinguishing points (Feng et al., 2008b), Sorted Index Numbers (Wang, YJ and Hatzinakos, D., 2009), augmented random projection (Sohn et al. 2009) and a combination of BioHashing and BioPhasor (Nanni and Lumini, 2010).

Savvides et al. (2004) proposed another instance of biometric salting method which encrypts the training images by synthesizing a correlation filter for face recognition. They showed that different templates can be obtained from the same biometrics by varying the random convolution kernels thus enabling cancelable templates. Note that the random kernels were generated from different random matrices created using a user-specific PIN. Their results demonstrated that convolving the training images with any random convolution kernel prior to building the biometrics filter does not change the resulting correlation output peak-to-side-lobe ratios thus preserving existing performance. However, the security could be jeopardized via a deterministic deconvolution with a known random kernel. An enhancement of cancelable correlation filter encryption was reported by Hirata and Takahashi (2009). It was shown that the security is heighten by applying Number Theoretic Transform, a Fourier-like transform over a finite field, into biometric data before random kernel convolution.

Jeong et al. (2006) proposed a biometric salting scheme for appearance-based face template. Two feature vectors were extracted with PCA (Principal Component Analysis) and ICA (Independent Component Analysis) from a face image, and these vectors Italic text were normalized. The resulting vectors were then permuted using a token-derived permutation matrix and fused in the feature level via SUM rule. If this was compromised, a new feature vector can be generated by changing the permutation matrix.

For fingerprint minutiae, Lee et al. (2007) introduced the translation and rotation invariant values, which were extracted using orientation information around each minutia. These values were then used as the inputs for two user-specific transformation functions which were responsible in generating translational and rotational parameters. The cancelable templates were then constructed by changing each minutia in accordance to the said parameters. When a cancelable template was compromised, new template can be regenerated by replacing the transformation functions.

Farooq et al. (2007) presented a method by converting the fingerprint minutiae into a cancelable bitstring, without registration or pre-alignment. The idea is based on the fact that fingerprints can be represented by a set of triangles derived from sets of three minutiae that can be used directly in template-based matching. The proposed method is proven to be computational irreversible and satisfies the criteria of reusability and diversity. Note that the reusability is achieved by assigning a unique key to each user in the database to randomize the user template, and in the event of being compromised, the biometric template can be revoked by simply assigning a different key.

Non-invertible Transforms

In Non-invertible transformation, a many-to-one function, \(f\) is designed to modify a raw biometric image intentionally into a new form within the context of feature or signal space. The function \(f\) serves as an agent in the context of template security allowing for template non-invertibility, reusability and diversity. Since \(f\) does not have direct interaction with raw biometrics, the main advantage of this approach is that \(f\) does not need to be kept secret.

A realization of non-invertible transform was reported by Ratha et al. in (2007) wherein fingerprint data is transformed by a sequence of three non-invertible transformation functions. As shown in figure 2, the three transformation functions are based on Cartesian, polar and surface folding transformation of the minutiae positions.

Figure 2: Cancelable Templates from Different Transforms (adopted from Ratha et al. PAMI, 2007).

In the Cartesian transformation, the fingerprint minutiae space is tessellated into a rectangular grid with reference to positions of singular points. Note that each cell, which possibly contains some minutiae, is shifted to a new position by a non-invertible transform, but retain within their relative position to maintain the status-quo of intra-class variability. The polar transformation is similar to the Cartesian transformation with the only difference being that the image is now tessellated into polar sectors. Since the size of sectors can be different according to their location, the translation vector generated from the random key are used to control the radial distance of the transformed sectors so that there are not very different each others.

In surface folding transformation, a mixture of 2D Gaussians and 2D electric potential field random charge distributions are used to translate the minutiae points. Since the transformations used in the mixture are locally smooth, this will only have a minimal effect on the error rates and will not reduce the discriminability of minutiae to any large extent when compared to the previous two transforms. Nevertheless, as a small change in minutiae position of the original fingerprint can lead to a large change post transformation especially if the point crosses a sharp boundary, proper pre-alignment with reference to the position of the core point is required to ensure that the biometric feature is transformed consistently across multiple instances of minutiae.

In general, all the three transformation functions allow more than one minutia to be mapped to the same point (many-to-one mapping) in the transform domain. For example, in the Cartesian transformation, two or more cells can be mapped onto a single cell so that even if an adversary knows the key and hence the transformation between cells, he cannot determine the original cell to which a minutia belongs because each minutia can independently belong to one of the possible cells. Hence, the method provides a certain extent of non-invertibility to the resulting template.

However, Feng, et al. (2008a) reasoned that the above transforms and the parameters chosen could degenerate the many-to-one mapping property, in which the non-invertible functions rely to, and resulted in recovering of original biometric features. Shin, et al. (2009) showed that the surface folding transform could be inverted if two transformed templates originating from the same fingerprint are compromised.

Tulyakov et al. (2005) presented a method of hashing fingerprint minutiae information and performing fingerprint matching in a new domain. It is computationally hard to reconstruct original features with resulting hash values due to one-way transformation characteristic of hashing function. In case hash values are compromised, user will be re-enrolled with new hash function, hence both non-invertibility and reusability requirements are satisfied. Diversity can also be attained since different hash functions are used for old compromised hash values and new hash values.

Along the same line, Ang et al. (2005) proposed a geometric transformation to generate a key-dependent non-invertible cancelable template for fingerprint minutiae. In the proposal, a core point of a fingerprint image is first located, and then a line through the core point is specified. Since the angle of the line depends on the key transformation function, where the value can be set in the range of 0 ≤ key ≤ π, thus different transformed fingerprint templates can be obtained by simply changing the key value. However, since the minutiae above the line are reflected symmetrically below the line, the transformed template still retains some information of the original template. In addition, both techniques could not preserve the performance due to query alignment issue.

Maiorana et al. (2009) proposed a non-invertible transformation scheme targets to sequence based biometrics such as dynamic handwritten signature. The basic idea is to segment (from at least one sample) online signature feature into several chunks whereby the length of chunks is determine by a set of random integers. The segmented chunks are then convoluted to form a new transformed feature which satisfies the reusability, diversity, non-invertibility and performance requirements. Nanni et al. (2010) showed that different matchers trained using cancelable templates could be combined for improving the performance of a secure on-line signature verification.

Remarks

Cancellable biometrics offers a solution for preserving user privacy since the user’s true biometric is never reveal in the authentication process. It ensures that template protection is achieved at the feature level with the assistance of the auxiliary data/non-invertible transforms. On the other hand, cancellable biometrics has certain limitations that need to be taken into account. For instance in biometric salting design, the template may not longer secure when the auxiliary data is compromised. For non-invertible transforms, non-invertibility enhances the security of the template space by employing a transformation process to reset the order or position of the feature set. However, this weakens the discriminatory power (performance) of the transformed features due to the enlargement of intra-class variation in the biometrics. In this context, if performance is the main concern in the design of a biometric system, then the system is expected to be lacking in randomness as required for the design of a secure and unpredictable template space. Hence, it is very challenging to design a non-invertible function that satisfies both performance and non-invertibility requirements.

References

• Ang, R.; Rei, S.N. and McAven, L. (2005). Cancelable Key-Based Fingerprint Templates. Information Security and Privacy: 10th Australasian Conference (ACISP 2005) : 242-252.

• Bolle, R.M.; Connel, J.H. and Ratha, N.K. (2002). Biometrics Perils and Patches. Elsevier - Pattern Recognition 35: 2727-2738.

• Chong, S.C.; Teoh, A.B.J. and Ngo, D.C.L. (2006). High security Iris verification system based on random secret integration. Computer Vision and Image Understanding 102(2): 169-177.

• Feng, Q.; Su, F.; Cai, A. and Zhao, F.F. (2008a). Cracking Cancelable Fingerprint Template of Ratha. International Symposium on Computer Science and Computational Technology (ISCSCT'08), vol.2: 572-575.

• Feng, Y.C.; Yuen, P.C. and Jain, A.K. (2008b). A Hybrid Approach for Face Template Protection. SPIE Defense and Security Symposium 102(2): 169-177.

• Hirata(2009). Cancelable Biometrics with Perfect Secrecy for Correlation-Based Matching. Lecture Notes in Computer Science 5558: 868-878.

• Jeong, M.Y. et al. (2006). Changeable Biometrics for Appearance Based Face Recognition. Biometric Consortium Conference, 2006 Biometrics Symposium : 1-5.

• Kim, Y.S. et al. (2007). A Method to Enhance Face Biometric Security. IEEE Conference on Biometrics: Theory, Applications and Systems,2007 (BTAS) : 1-5.

• Kong, B. et al. (2006). An analysis of Biohashing and its variants. Elsevier - Pattern Recognition 39(7): 1359-1368.

• Lee, C. H.; Choi, C.Y. and Toh, K.A. (2007b). Alignment-Free Cancelable Fingerprint Templates Based on Local Minutia Information. IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 37, no. 4: 980-992.

• Lee, Y.J. et al. (2007). One-Time Templates for Face Authentication. International Conference on Convergence Information Technology (ICCIT 2007) : 1818-1823.

• Lumini(2007). An Improved BioHashing for Human Authentication. Elsevier - Pattern Recognition 40(3): 1057-1065.

• Maiorana, E.; Campisi, P.; Fierrez, J. and Ortega-Garcia, J. (2009). Cancelable Templates for Sequence Based Biometrics with Application to On-line Signature Recognition. IEEE System Man and Cybernetics-Part A, Special Issue on Biometrics : (in press, 2009).

• Nanni(2008). Random Subspace for an improved BioHashing for Face authentication. Elsevier - Pattern Recognition Letters 29(3): 295-300.

• Nanni(2010). Cancellable Biometrics: Problems and Solutions for Improving Accuracy. NovaPublisher - Biometrics: Methods, Applications and Analyses : (in press, 2010).

• Nanni, L.; Maiorana, E.; Lumini, A. and Campisi, P. (2010). On-Line Signature Verification: Comparison and Fusion of Feature Based and Function Based Classifiers . NovaPublisher - Biometrics: Methods, Applications and Analyses : (in press, 2010).

• Ratha, N.K.; Chikkerur, S.; Connell, J.H. and Bolle, R.M. (2007). Generating Cancelable Fingerprint Templates. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(4): 561-572.

• Shin, S.W.; Lee, M.-K.; Moon, D.S. and Moon, K.Y. (2009). Dictionary Attack on Functional Transform-Based Cancelable Fingerprint Templates. ETRI Journal, 31(5): 628-630.

• Savvides, M.; Vijaya Kumar, B.V.K. and Khosla, P.K. (2004). Cancelable Biometrics Filters for Face Recognition. Int. Conf. of Pattern Recognition, vol.3: 922-925.

• Sohn, H.; Ro, Y.M. and Plataniotis, K.N. (2009). Biometric Authentication using Augmented Face and Random Projection. IEEE International Conference on Biometrics (ICB 2009) : .

• Soutar, C.; Roberge, A. and Vijaya Kumar, B.V.K. (1998). Biometric Encryption using Image Processing. SPIE : 178-188.

• Teoh, Andrew B.J.; Goh, A. and Ngo, D.C.L. (2006a). Random Multispace Quantisation as an Analytic Mechanism for BioHashing of Biometric and Random Identity Inputs. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(12): 1892-1901.

• Teoh(2006b). Biophasor:Token Supplemented Cancellable Biometrics. 9th International Conference on Control, Automation, Robotics and Vision (ICARCV 2006) : 1-5.

• Teoh(2007a). Cancellable Biometrics Realization with Multispace Random Projections. IEEE Transaction SMC Part B - Special Issue on Recent Advances in Biometrics Systems, vol.37, no.5: 1096-1106.

• Teoh, A.B.J.; Toh, K.A. and Yip, W.K. (2007b). 2^N Discretisation of BioPhasor in Cancellable Biometrics. Lecture Notes in Computer Science 4642: 435-444.

• Teoh, A.B.J.; Yip, W.K. and Lee, S.Y. (2008). Cancellable Biometrics and Annotations on BioHash. Elsevier - Pattern Recognition 41(6): 2034-2044.

• Tulyakov, S.; Farooq, F. and Govindaraju, V. (2005). Symmetric Hash Functions for Fingerprint Minutiae. International Workshop on Pattern Recognition for Crime Prevention, Security and Surveillance (ICAPR 2005), vol.3687: 30-38.

• Wang, Y.; Hatzinakos, D. and Jain, A.K. (2009). Sorted Index Numbers for Privacy Preserving Face Recognition. EURASIP Journal on Advances in Signal Processing : .

• Wang(2007). Face based biometric authentication with changeable and privacy preserving templates. Biometrics Symposium (BSYM 2007) : .

Further reading

• Jain, A.K.; Nandakumar, K. and Nagar, A. (2008). Biometric template security. EURASIP J. Adv. Signal Process 2008 : .

Sponsored by: Jian-Gang Wang, Institute for Infocomm Research, Singapore

Reviewed by: Anonymous

Reviewed by: Dr. Nanni Loris, DEIS, University of Bologna

Accepted on: 2010-01-04 07:01:11 GMT