A collusion attack on the fuzzy vault scheme




The Fuzzy Vault scheme is an encryption scheme, which can tolerate errors in the keys. This leads to the possibility of enhancing the security in environments where these errors can be common, such as biometrics storage systems. Although several researchers have provided implementations, we find that the scheme is vulnerable to attacks when not properly used. This paper describes an attack on the Fuzzy Vault scheme where the attacker is assumed to have access to multiple vaults locked by the same key and where a non-maximal vault size is used. The attack effectively reduces the vault size by identifying and removing cha_ points. As the vault size decreases, the rate at which cha_ points are identified increases exponentially. Several possible defenses against the attack are also discussed.


[1] Ari Juels and Martin Wattenberg. A Fuzzy Commitment Scheme. In Proceedings of the 6th ACM Conference on Computer and Communications Security (CCS'99), pages 28-36, Kent Ridge Digital Labs, Singapore, 1999. ACM Press.

[2] Ari Juels and Madhu Sudan. A Fuzzy Vault Scheme. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), page 408, 2002.

[3] T. Charles Clancy, Negar Kiyavash, and Dennis J. Lin. Secure Smartcard-Based Fingerprint Authentication. In Proceedings of the ACM SIGMM Workshop on Biometrics Methods and Applications (WBMA'03), pages 45-52, Berkley, California, 2003. ACM.

[4] Umut Uludag, Sharath Pankanti, and Anil K. Jain. Fuzzy Vault for Fingerprints. In Proceedings of the Audio- and Video-based Biometric Person Authentication (AVBPA'05), pages 310-319, Hilton Rye Town, NY, USA, 2005.

[5] S. Yang and I. Verbauwhede. Automatic Secure Fingerprint Veri_cation System Based on Fuzzy Vault Scheme. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'05), pages 609-612, Philadelphia, PA, USA, 2005.

[6] Ee-Chien Chang, Ren Shen, and Francis Weijian Teo. Finding the Original Point Set Hidden among Chaff. In Proceedings of the ACM Symposium on Information, Computer and Communications Security (ASIACCS'06), pages 182-188, Taipei, Taiwan, 2006. ACM.

[7] Ee-Chien Chang and Qiming Li. Hiding Secret Points Amidst Chaff. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Advances in Cryptology- EUROCRYPT'06), volume 4004 of Lecture Notes in Computer Science (LNCS), pages 59-72, Petersburg, Russia, 2006. Springer.

[8] Preda Mihailescu. The Fuzzy Vault for Fingerprints is Vulnerable to Brute Force Attack. http://arxiv.org/abs/0708.2974v1.

[9] W.L.W. AlTarawneh and W.L Woo. Biometric Key Capsulation Technique Based on Fingerprint Vault: Anatomy and Attack. In Proceedings of the International Conference on Information and Communication Technologies: From Theory to Applications (ICTTA'08), pages 1-5, Damascus, Syria, 2008.

[10] Karthik Nandakumar, Abhishek Nagar, and Anil K. Jain. Hardening Fingerprint Fuzzy Vault Using Password. In Proceedings of the International Conference on Biometrics (ICB'07), volume 4642 of Lecture Notes in Computer Science (LNCS), pages 927-937, Seoul, Korea, 2007. Springer.

[11] S. Reed and G. Solomon. Polynomial Codes Over Certain Finite Fields. International Journal of Applied Mathematics, 8(2):300-304, 1960.

[12] N. Ratha, J. Connell, and R. Bolle. Enhancing Security and Privacy in Biometrics-Based Authentication Systems. IBM System Journal, 40(3):614-634, 2001.