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
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
of size
. We also want a function
UNLOCK
: .
We want our LOCK
and UNLOCK
algorithms to have the following properties:
-completeness
Def: Let such that
. Then
UNLOCK
LOCK
. This represents the number of errors that the scheme can tolerate; we prove later that the Fuzzy Vault scheme is
-complete.
Soundness
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
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
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.