A Fuzzy Vault Scheme

We describe a simple and novel cryptographic construction that we refer to as a fuzzy vault. A player Alice may place a secret value κ in a fuzzy vault and “lock” it using a set A of elements from some public universe U. If Bob tries to “unlock” the vault using a set B of similar length, he obtains κ only if B is close to A, i.e., only if A and B overlap substantially. In constrast to previous constructions of this flavor, ours possesses the useful feature of order invariance, meaning that the ordering of A and B is immaterial to the functioning of the vault. As we show, our scheme enjoys provable security against a computationally unbounded attacker. Fuzzy vaults have potential application to the problem of protecting data in a number of real-world, error-prone environments. These include systems in which personal information serves to authenticate users for, e.g., the purposes of password recovery, and also to biometric authentication systems, in which readings are inherently noisy as a result of the refractory nature of image capture and processing.