Tue, 04/19/2011 - 23:49 — jad12

Fuzzy Vault is an encryption scheme proposed by Juels and Sudan [1] which leverages some of the concepts of error-correcting codes, to encode information in such a way as to be difficult to obtain without the "key" used to encode it, even if the methods used for encoding are publicly known. Although this approach can work with any code, the Fuzzy Vault scheme is often used with Reed-Solomon codes, so we will focus on them for this exposition. A secret is encoded using a set of values (the "key"), and can then be unlocked with another set of values only if it has substantial overlap with the set used to lock it. This approach offers order invariance, meaning that the sets used to lock and unlock the secret are unordered. Because of this property, the Fuzzy Vault scheme has been seen application in biometric encryption [2,3], namely fingerprint authentication.

**Table of Contents**

- Overview
- Problem Statement
- LOCK Algorithm
- UNLOCK Algorithm
- Proof of -Completeness
- Proof of Soundness
- Fuzzy Vault in Biometrics
- See Also
- References

**Overview**

Reed-Solomon codes work by encoding the values in a message as the coefficients of a polynomial and then evaluating that polynomial at a set of points to obtain the codeword for that message. By using a number of evaluation points greater than the degree of the polynomial, it will be possible to obtain the polynomial (and therefore the message) by interpolation even in the presence of missing or erroneous values. However, if there are too many errors, there will not be a unique interpolating polynomial of the proper degree. These properties are leveraged in the Fuzzy Vault scheme.

Suppose that an entity Alice wishes to lock a secret such that it will be secure even if an adversary has access to the locked secret. Alice has a set with which to encode the secret, whose values are not know to the adversary. Alice can encode in a polynomial , and evaluate at the values in the set . Thus, the values in the projected set lie on the polynomial. Alice then combines points of random noise, or chaff points, which do not lie on , with the set of points in into an unordered set . The set represents the points of which lie on , and provided the cardinality of is large enough, (and therefore ) can be determined from by interpolation.

Now suppose that another entity Bob has a set of values, and wishes to unlock . If is large, then will contain many values whose corresponding points in lie on . Even if does not agree with everywhere, if they are sufficiently close, Bob can leverage the error correcting properties of Reed-Solomon codes to correctly recover . On the other hand, if and have few values in common, then the points in identified by will mostly be chaff points, and he will not be able to recover through interpolation because many polynomials of the proper degree will be equally likely.

In the context of fingerprint authentication, fingerprint features, or minutiae, are detected and their locations and orientations are quantized. The set of all possible tuples of quantized location and orientation forms the alphabet of which a particular user's minutiae are a subset. However, the many variables involved in collecting fingerprint features (finger orientation, pressure on the sensor, etc.) make retrieving the exact same readings difficult, even from the same user. This is part of the motivation for using the Fuzzy Vault approach; if a significant portion of the minutiae can be retrieved from the user's fingerprint at each use, the error-correcting properties of Reed-Solomon codes and the order invariance property will enable the user to be correctly recognized even if their fingerprint is measured slightly differently each time.

This intuition for the Fuzzy Vault scheme motivates the following formalized problem statement.

**Problem Statement**

We have a secret , a -length vector of values from the finite field of size , , and a set such that contains distinct values from . We desire a function ** LOCK**: where . Thus

`LOCK`

`UNLOCK`

We want our ** LOCK** and

`UNLOCK`

`UNLOCK`

`LOCK`

For any adversary with limited knowledge of , with high probability there will be exponentially many valid possibilities for based on the adversary's . This represents that if the set does not overlap with the correct enough, the adversary will not be able to retrieve the secret .

**LOCK Algorithm**

The idea is to encode the secret in polynomial , add points from key set to as tuples with their projection onto the polynomial, then fill the remaining points in with points that are not on .

`LOCK`

- Initialize and to be
- Encode in coefficients of polynomial
- for

- for

Pick randomly from

Pick randomly from

- Output after randomly permuting it

**UNLOCK Algorithm**

The idea is to take a locked secret, represented as a set of points (the output of ** LOCK**), and a set of evaluation points. For each , retrieve the corresponding point from (where ); decode this set of points using the Reed-Solomon Code. If there are fewer than errors, the secret can be correctly decoded; if not, then the Reed-Solomon decoding algorithm outputs NULL.

`UNLOCK`

- Initialize to be
- for

Find the such that ; set

- Output Decode Q with Reed-Solomon Decoding Algorithm

**Proof that the Fuzzy Vault Scheme is -complete**

We will show that the Fuzzy Vault Scheme is tolerant of up to errors.

*Proof:* Given such that , then . Also, assume ** LOCK**.

If , then matches some and .

For at least of , we know .

Since we have less than errors, the Reed-Solomon decoding algorithm will correctly output (and therefore ).

**See Also**

Reed-Solomon Error Correction

Fingerprint Recognition

Biometrics

Fuzzy Extractor

**References**

[1] A Fuzzy Vault Scheme - A. Juels and M. Sudan

[2] Fuzzy Vault for Fingerprints - U. Uludag et al.

[3] Fingerprint-based fuzzy vault: Implementation and performance - K. Nandakumar et al.

- Login to post comments