A fast algorithm for polynomial reconstruction of fuzzy fingerprint vault

Abstract

In recent years, a cryptographic construct, called fuzzy vault, has been proposed, which aims to secure critical data ( e. g., secret encryption key) with the fingerprint data in a way that only the authorized user can access the secret by providing the valid fingerprint, and some implementation results have been reported. However, all the previous results adopted the brute-force search to reconstruct the polynomial or skipped the procedure for the polynomial reconstruction. In this paper, we propose a fast polynomial reconstruction algorithm for the fuzzy fingerprint vault which can improve the execution time of the brute-force search by a factor of 300 similar to 1,500.