International Journal of Computer Network and Information Security(IJCNIS)

ISSN: 2074-9090 (Print), ISSN: 2074-9104 (Online)

Published By: MECS Press

IJCNIS Vol.9, No.5, May. 2017

Toward Constructing Cancellable Templates using K-Nearest Neighbour Method

Full Text (PDF, 511KB), PP.1-10

Views:98   Downloads:2


Qinghai Gao

Index Terms

Fingerprint;minutiae;pseudo random number generator;synthetic template;k-nearest neighbours;cancellable template


The privacy of biometric data needs to be protected. Cancellable biometrics is proposed as an effective mechanism of protecting biometric data. In this paper a novel scheme of constructing cancellable fingerprint minutiae template is proposed. Specifically, each real minutia point from an original template is mapped to a neighbouring fake minutia in a user-specific randomly generated synthetic template using the k-nearest neighbour method. The recognition template is constructed by collecting the neighbouring fake minutiae of the real minutiae. This scheme has two advantages: (1) An attacker needs to capture both the original template and the synthetic template in order to construct the recognition template; (2) A compromised recognition template can be cancelled easily by replacing the synthetic template. Single-neighboured experiments of self-matching, nonself-matching, and imposter matching are carried out on three databases: DB1B from FVC00, DB1B from FVC02, and DB1 from FVC04. Double-neighboured tests are also conducted for DB1B from FVC02. The results show that the constructed recognition templates can perform more accurately than the original templates and it is feasible to construct cancellable fingerprint templates with the proposed approach.

Cite This Paper

Qinghai Gao,"Toward Constructing Cancellable Templates using K-Nearest Neighbour Method", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.5, pp.1-10, 2017.DOI: 10.5815/ijcnis.2017.05.01


[1]D. Maltoni, D. Maio, A.K. Jain, and S. Prabhakar, Handbook of Fingerprint Recognition, 2nd ed., Springer, London, 2009.

[2]N. Ratha, J. Connell, and R. Bolle, "Enhancing security and privacy in biometrics-based authentication systems," IBM Systems Journal, vol. 40, no. 2, pp. 614-634, 2001. 

[3]N. Ratha, J. Connell, R. Bolle, and S. Chikkerur, "Cancellable biometrics: a case study in fingerprints," 18th International Conference on Pattern Recognition, 2006, pp. 370-373.

[4]N. Ratha, S. Chikkerur, J. Connell, and R. Bolle, "Generating cancellable fingerprint templates," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no.4, pp. 561-572, 2007.

[5]H. Yang, X. Jiang, and A. Kot, "Generating secure cancellable fingerprint templates using local and global features," IEEE 2nd International Conference on Computer Science and Information Technology, 2009, pp. 645-649.

[6]C. Lee and J. Kim, "Cancellable fingerprint templates using minutiae-based bit-strings," Journal of Network and Computer Applications, vol. 33, no. 3, pp. 236-246, 2010.

[7]T. Ahmad, J. Hu, and S. Wang, "Pair-polar coordinate-based cancellable fingerprint templates," Pattern Recognition, vol. 44, no. 10, pp. 2555-2564, 2011.

[8]S. Wang and J. Hu, "Alignment-free cancellable fingerprint template design: a densely infinite-to-one mapping (DITOM) approach," Pattern Recognition, vol. 45, no. 12, pp. 4129-4137, 2012

[9]S. Wang and J. Hu, "Design of alignment-free cancellable fingerprint templates via curtailed circular convolution," Pattern Recognition, vol. 47, no. 3, pp. 1321-1329, 2014.

[10]S. Wang and J. Hu, "A blind system identification approach to cancellable fingerprint templates," Pattern Recognition, vol. 54, pp. 14-22, 2016.

[11]G. Bebis, T. Deaconu, and M. Georgiopoulos, "Fingerprint identification using Delaunay triangulation," International Conference on Information Intelligence and Systems, 1999, pp. 452-459.

[12]G. Parziale and A. Niel, "A fingerprint matching using minutiae triangulation," Biometric Authentication, 2004, pp. 241-248.

[13]N. Liu, Y. Yin, and H. Zhang, "A fingerprint matching algorithm based on Delaunay triangulation net," 5th International Conference on Computer and Information Technology, 2005, pp. 591-595.

[14]H. Deng and Q. Huo, "Minutiae matching based fingerprint verification using Delaunay triangulation and aligned-edge-guided triangle matching," International Conference on Audio-and Video-Based Biometric Person Authentication, 2005, pp. 270-278.

[15]Y. Yin, H. Zhang, and N. Liu, "Fingerprint matching based on Delaunay triangulation," Journal of Computer Research and Development, vol. 42, no. 9, pp. 1622-1627, 2005.

[16]C. Wang and M. Gavrilova, "Delaunay triangulation algorithm for fingerprint matching," 3rd International Symposium on Voronoi Diagrams in Science and Engineering, 2006, pp. 208-216.

[17]X. Liang, A. Bishnu, and T. Asano, "A robust fingerprint indexing scheme using minutia neighbourhood structure and low-order Delaunay triangles," IEEE Transactions on Information Forensics and Security, vol. 2, no. 4, pp. 721-733, 2007.

[18]T. Uz, G. Bebis, A. Erol, and S. Prabhakar, "Minutiae-based template synthesis and matching using hierarchical Delaunay triangulations," IEEE 1st International Conference on Biometrics: Theory, Applications, and Systems, 2007, pp. 1-8.

[19]M. Vatsa, R. Singh, A. Noore, and S. Singh, "Quality induced fingerprint identification using extended feature set," IEEE 2nd International Conference on Biometrics: Theory, Applications and Systems, 2008, pp. 1-6.

[20]P. Júnior, A. de Nazare-Junior, and D. Menotti, "A complete system for fingerprint authentication using Delaunay triangulation," Pattern Recognition, Department of Computing, Federal University of Ouro Preto, 2010, pp. 1-7.

[21]A. C. Chau and C. Soto, "Hybrid algorithm for fingerprint matching using Delaunay triangulation and local binary patterns," 16th Iberoamerican Congress Conference on Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, 2011, pp. 692-700.

[22]S. Tulyakov, F. Farooq, P. Mansukhani, and V. Govindaraju, "Symmetric hash functions for secure fingerprint biometric systems," Pattern Recognition Letters, vol. 28, no. 16, pp. 2427-2436, 2007

[23]X. Li, "Interoperable protected fingerprint minutiae templates," Master Thesis (2012), Norwegian University of Science and Technology.

[24]M. Sandhya and M. Prasad, "A bio-cryptosystem for fingerprints using Delaunay neighbour structures (DNS) and fuzzy commitment scheme," Advances in Signal Processing and Intelligent Recognition Systems, 2016, pp. 159-171.

[25]M. Sandhya, M. Prasad, and R. Chillarige, "Generating cancellable fingerprint templates based on Delaunay triangle feature set construction," IET Biometrics, vol. 5, no. 2, pp. 131-139, 2016.

[26]C. Abirami and M. Begum, "Biometric cryptosystem based on Delaunay quadrangle structure for fingerprint template protection and person identification," Middle-East Journal of Scientific Research, vol. 24, no.S2, pp. 53-57, 2016.

[27]W. Yang, J. Hu, and S. Wang, "A Delaunay quadrangle-based fingerprint authentication system with template protection using topology code for local registration and security enhancement," IEEE transactions on Information Forensics and Security, vol. 9, no. 7, pp. 1179-1192, 2014.

[28]M. Sagayee, "A Delaunay pentangle-based fingerprint authentication system for preserving privacy using topology code," Advanced Technology for Leaning, vol. 2, no. 6, pp. 142-149, 2015.

[29]V. Krivokuca, W. Abdulla, and A. Swain, "A non-invertible cancellable fingerprint construct based on compact minutiae patterns," International Journal of Biometrics, vol. 6, no. 2, pp. 125-142, 2014.

[30]S. Kumari and A. Moghe, "Delaunay hexangle based fingerprint matching scheme for authentication," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 6, no. 5, pp. 489-494, 2016.

[31]H. Li, J. Zhang, and Z. Zhang, "Generating cancellable palmprint templates via coupled nonlinear dynamic filters and multiple orientation palmcodes," Information Sciences, vol. 180, pp. 3876–3893, 2010.

[32]H. Li and L. Wang, "Chaos-based cancellable palmprint authentication system," Procedia Engineering, vol. 29, pp. 1239-1245, 2012.

[33]E. Du, K. Yang, and Z. Zhou, "Key incorporation scheme for cancellable biometrics," Journal of Information Security, vol. 2, pp. 185-194, 2011.

[34]C. Rathgeb, F. Breitinger, and C. Busch, "Alignment-free cancellable iris biometric templates based on adaptive bloom filters," IAPR International Conference on Biometrics, 2013, pp. 1-8.

[35]C. Rathgeb and C. Busch, "Cancellable multi-biometrics: mixing iris-codes based on adaptive bloom filters," Computers & Security, vol. 42, pp. 1-12, 2014.

[36]C. Rathgeb, M. Gomez-Barrero, C. Busch, J. Galbally, and J. Fierrez, "Towards cancellable multi-biometrics based on bloom filters: a case study on feature level fusion of face and iris," International Workshop on Biometrics and Forensics, 2015, pp. 1-6. 

[37]J. Hämmerle-Uhl, E. Pschernig, and A. Uhl, "Cancellable iris biometrics using block re-mapping and image warping," International Conference on Information Security, 2009, pp. 135-142. 

[38]J. Pillai, V. Patel, R. Chellappa, and N. Ratha, "Sectored random projections for cancellable iris biometrics," International Conference on Acoustics, Speech and Signal Processing, 2010, pp. 1838-1841.

[39]O. Osama, N. Tsumura, and T. Nakaguchi, "Bioencoding: a reliable tokenless cancellable biometrics scheme for protecting iriscodes," IEICE Transactions on Information and Systems, vol. 93, no. 7, pp. 1878-1888, 2010.

[40]S. Kanade, D. Petrovska-Delacretaz, and B. Dorizzi, "Cancellable biometrics for better security and privacy in biometric systems," 1st International Conference on Advances in Computing and Communications, 2011, pp. 20-34.

[41]M. Savvides, B. Kumar, and P. Khosla, "Cancellable biometric filters for face recognition," International Conference on Pattern Recognition, vol. 3, pp. 922-925, 2004.

[42]S. Hirata and K. Takahashi, "Cancellable biometrics with perfect secrecy for correlation-based matching," Advances in Biometrics, Lecture Notes in Computer Science, M. Tistarelli and M. Nixon, Eds., vol. 5558, pp. 868–878, 2009.

[43]K. Takahashi and S. Hirata, "Cancellable biometrics with provable security and its application to fingerprint verification," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 94-A, no. 1, pp. 233-244, 2011.

[44]E. Maiorana, P. Campisi, J. Fierrez, J. Ortega-Garcia, and A. Neri, "Cancellable templates for sequence-based biometrics with application to on-line signature recognition," IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 40, no. 3, pp. 525-538, 2010.

[45]W. Xu, Q. He, Y. Li, and T. Li, "Cancellable voiceprint templates based on knowledge signatures," International Symposium on Electronic Commerce and Security, 2008, pp. 412-415.

[46]T. Connie, A. Teoh, M. Goh, and D. Ngo, "Palmhashing: a novel approach for cancellable biometrics," Information Processing Letters, vol. 93, no. 1, pp. 1-5, 2005.

[47]J. Zuo, N. Ratha, and J. Connell, "Cancellable iris biometric," International Conference on Pattern Recognition, 2008, pp. 1-4.

[48]G. Bajwa and R. Dantu, "Neurokey: towards a new paradigm of cancellable biometrics-based key generation using electroencephalograms," Computers & Security, vol. 62, pp. 95-113, 2016.

[49]A. Jain, K. Nandakumar, and A. Ross, "50 years of biometric research: accomplishments, challenges, and opportunities," Pattern Recognition Letters, vol. 79, pp. 80-105, 2016.

[50]A. Rukhin et al., "A statistical test suite for the validation of random number generators and pseudo random number generators for cryptographic applications," NIST special publication: 800-22. 

[51]C. Ellison, "Cryptographic random numbers," Accessed online on 07/29/2016:

[52]Q. Gao, "A preliminary study of fake fingerprints," International Journal of Computer Network and Information Security, vol. 6, no. 12, pp. 1-8, 2014.

[53]FVC2000, available at:

[54]FVC2002, available at:

[55]FVC2004, available at:

[56]NIST fingerprint software, Accessed online on 06/27/2016: