30-09-2016, 10:02 AM
1456929622-NandakumarJainPankantiFpFuzzyVaultTIFS07.pdf (Size: 1.78 MB / Downloads: 3)
Abstract—Reliable information security mechanisms are required
to combat the rising magnitude of identity theft in our
society. While cryptography is a powerful tool to achieve information
security, one of the main challenges in cryptosystems is to
maintain the secrecy of the cryptographic keys. Though biometric
authentication can be used to ensure that only the legitimate user
has access to the secret keys, a biometric system itself is vulnerable
to a number of threats. A critical issue in biometric systems is
to protect the template of a user which is typically stored in a
database or a smart card. The fuzzy vault construct is a biometric
cryptosystem that secures both the secret key and the biometric
template by binding them within a cryptographic framework.
We present a fully automatic implementation of the fuzzy vault
scheme based on fingerprint minutiae. Since the fuzzy vault stores
only a transformed version of the template, aligning the query
fingerprint with the template is a challenging task. We extract
high curvature points derived from the fingerprint orientation
field and use them as helper data to align the template and query
minutiae. The helper data itself do not leak any information about
the minutiae template, yet contain sufficient information to align
the template and query fingerprints accurately. Further, we apply
a minutiae matcher during decoding to account for nonlinear
distortion and this leads to significant improvement in the genuine
accept rate. We demonstrate the performance of the vault implementation
on two different fingerprint databases. We also show
that performance improvement can be achieved by using multiple
fingerprint impressions during enrollment and verification.
INTRODUCTION
CRYPTOGRAPHIC techniques are being widely used for
ensuring the secrecy and authenticity of information [1].
Although several cryptosystems have proven security guarantees
(e.g., AES and RSA), the security relies on the assumption
that the cryptographic keys are known only to the legitimate
user. Maintaining the secrecy of keys is one of the main challenges
in practical cryptosystems. The keys are usually stored in a secure location (e.g., tamper-resistant hardware) and password-based
authentication is commonly used for controlling
access to cryptographic keys [2]. However, passwords can be
easily lost, stolen, forgotten, or guessed using social engineering
[3] and dictionary attacks. Limitations of password-based authentication
can be alleviated by using stronger authentication
schemes, such as biometrics. Biometric systems [4] establish
the identity of a person based on his or her anatomical or behavioral
traits, such as face, fingerprint, iris, voice, etc. Biometric
authentication is more reliable than password-based authentication
because biometric traits cannot be lost or forgotten and it is
difficult to share or forge these traits. Hence, biometric systems
offer a natural and reliable solution to the problem of user authentication
in cryptosystems.
Biometric cryptosystems can operate in one of the following
three modes: 1) key release; 2) key binding; and 3) key generation.
In the key-release mode, biometric authentication is completely
decoupled from the key release mechanism. The biometric
template and the key are stored as separate entities and
the key is released only if the biometric matching is successful.
In the key binding mode, the key and the template are monolithically
bound within a cryptographic framework (see Fig. 1).
It is computationally infeasible to decode the key or the template
without any knowledge of the user’s biometric data. A
crypto-biometric matching algorithm is used to perform authentication
and key release in a single step. In the key generation
mode, the key is derived directly from the biometric data and is
not stored in the database.
Though it is easy to implement a biometric cryptosystem in
the key release mode, such a system is not appropriate for high
security applications because it has two major vulnerabilities.
First, the biometric template is not secure. Template security
is a critical issue in biometric systems because stolen templates
cannot be revoked. Second, since authentication and key release are decoupled, it is possible to override the biometric matcher
using a Trojan horse program [5]. Biometric cryptosystems that
work in the key binding/generation modes are more secure but
difficult to implement due to large intraclass variations in biometric
data (i.e., samples of the same biometric trait of a user
obtained over a period of time can differ substantially). For example,
factors, such as translation, rotation, nonlinear distortion,
skin conditions, and noise lead to intraclass variations in fingerprints
[6] (see Fig. 2).
Juels and Sudan [7] proposed a cryptographic construction
called a fuzzy vault that operates in the key binding mode and,
in principle, can compensate for intraclass variations in the biometric
data. We present a fully automatic implementation of
the fuzzy vault scheme based on fingerprint minutiae. Since the
fuzzy vault scheme stores only a transformed version of the template,
the main implementation challenge is the alignment (registration)
of query fingerprint to the original template. In our
implementation, we store high curvature points derived from the
orientation field of the template fingerprint as helper data to assist
in alignment. The helper data accurately align the template
and query minutiae but do not reveal any information about the
minutia points that form the template.
The rest of this paper is organized as follows. Section II introduces
the basic fuzzy vault construction and Section III gives
the details of the proposed fuzzy vault implementation using
fingerprint minutiae. The automatic fingerprint alignment technique
based on helper data is described in Section IV. The experimental
results are presented in Section V, and Section VI
presents a discussion on the security of the system. Section VII
summarizes our work and provides pointers for future research.
II. BACKGROUND
Several schemes have been proposed in the literature for implementing
a biometric cryptosystem in key binding/generation
modes [8]–[13]. It is also worth mentioning that the problem of
key binding/generation in a biometric cryptosystem is closely
related to other research issues in biometrics, such as template
protection [14], [15] and generation of cancelable templates
[16]. A detailed review of different biometric cryptosystems
has been presented in [17]. Based on this study, it is clear that the techniques proposed in [8]–[15] have their own advantages
and limitations in terms of security, computational cost, storage
requirements, applicability to different kinds of biometric
representations, and ability to handle intraclass variations in
biometric data. In this paper, we focus on a specific algorithm,
known as fuzzy vault, which was originally proposed by Juels
and Sudan in [7].
A. Fuzzy Vault
Fuzzy vault [7] is a cryptographic construction that is designed
to work with biometric features which are represented as
an unordered set (e.g., minutiae in fingerprints). The security of
the fuzzy vault scheme is based on the infeasibility of the polynomial
reconstruction problem, which is a special case of the
Reed–Solomon list decoding problem. The ability to deal with
intraclass variations in the biometric data along with the ability
to work with unordered sets, which is commonly encountered in
biometrics, makes the fuzzy vault scheme a promising solution
for biometric cryptosystems.
Fig. 3 depicts the operation of a fuzzy vault scheme. Suppose
that a user wishes to hide a secret (e.g., a cryptographic
key) using his or her biometric sample (template) which is represented
as an unordered set . The user selects a polynomial
that encodes the secret and evaluates the polynomial on all
elements in . The user then chooses a large number of random
chaff points which do not lie on the polynomial . The entire
collection of points consisting of both points lying on and
those that do not lie on constitute the vault . The chaff points
conceal the genuine points lying on from an attacker. Since
the points lying on encode the complete information about
the template and the secret , concealing these points secures
both the template and the secret simultaneously.
The user can retrieve the secret from the vault by providing
another biometric sample (query). Let the query be represented
as another unordered set . If overlaps substantially
with , then the user can identify many points in that lie on
. If a sufficient number of points on can be identified, an
error correction scheme can be applied to exactly reconstruct
and thereby decode the secret . If does not overlap substantially
with , it is infeasible to reconstruct and the authentication
is unsuccessful. Since the secret can be retrieved
from the vault even when and are not exactly the same,
this scheme is referred to as a fuzzy vault.
The three main parameters in the fuzzy vault scheme are ,
, and . The parameter denotes the number of points in the
vault that lie on the polynomial and it depends on the number
of features that can be extracted from the template (e.g., number
of minutia points in the user’s fingerprint). The parameter represents
the number of chaff points that are added and this parameter
influences the security of the vault. If no chaff points
are added, the vault reveals the information about the template
and the secret. As more chaff points are added, the security increases.
Typically, the number of chaff points is an order of magnitude
larger than the number of genuine points . Parameter
denotes the degree of the encoding polynomial and
it controls the tolerance of the system to errors in the biometric
data.
In order to retrieve the secret from the vault , the user selects
a subset of points from , which is known as the unlocking
set. The unlocking set is selected based on the query
PROPOSED FUZZY VAULT IMPLEMENTATION
The proposed fuzzy vault implementation is based on minutiae
which are local ridge characteristics (endings and bifurcations)
in a fingerprint. We use both the location and orientation
attributes of a minutia point in our implementation. These attributes
are represented as a three-tuple , where and
indicate the row and column indices in the image, and represents
the orientation of the minutia with respect to the horizontal
axis . The algorithm described in [26] is used for
minutiae extraction.
We have implemented the modified fuzzy vault construction
proposed in [24]. This modified fuzzy vault scheme does not require
Reed–Solomon decoding. Instead, several candidate sets
of size (where is the degree of the polynomial which
encodes the secret) are generated from the unlocking set and
polynomials are reconstructed using Lagrange interpolation.
This method gives rise to several candidate secrets and a cyclic
redundancy check (CRC)-based error detection technique is
used to identify the correct polynomial and, hence, decode the
correct secret. The advantage of this scheme is its increased
tolerance to biometric intraclass variations. Since only
points are required to uniquely determine a polynomial of degree
, this scheme can retrieve the secret when the number
of discrepancies in the biometric data is less than
. However, this method has a higher computational cost
because it requires a large number of polynomial interpolations.
Our fuzzy vault implementation significantly differs from the
implementation proposed in [25] in the following aspects.
1) In our implementation, we apply a minutiae matcher [26]
during decoding to account for nonlinear distortion in fingerprints
whereas in [25], the minutia location information
is coarsely quantized to compensate for distortion. Since
deformation of the fingerprint ridges increases as we move
away from the center of the fingerprint area toward the periphery,
uniform quantization alone, as used in [25], is not
sufficient to handle distortion. The minutiae matcher used
in our implementation [26] employs an adaptive bounding
box that accounts for distortion more effectively. This is
one of the main reasons why the proposed approach leads
to a significant improvement in the genuine accept rate
(GAR).
2) Only the location of minutia points was used for vault encoding
in [25]. We use both minutia location and orientation
attributes which increases the number of chaff points
that can be added because we can now add a chaff point
whose location is close to a true minutia but with a different
direction. Chang et al. [27] have shown that the number
of possible chaff points affects the security of the vault.
Hence, using both minutia location and orientation makes
it more difficult for an attacker to decode the vault. At the
same time, when a genuine user is attempting to decode the
vault, it is now easier to filter out chaff points from the vault
because it is less probable that a chaff point will match the
query minutia in both location and direction. This reduces
the decoding complexity by eliminating most of the chaff
points from the unlocking set.
3) We use a local image-quality index estimated from the fingerprint
in order to select the most reliable minutiae for
vault encoding and decoding. This also leads to a higher
GAR compared to the implementation in [25].
4) Although our alignment technique is similar to the one proposed
in [25], we have made significant changes to the
curvature estimation and alignment steps compared to [25]
which results in more accurate alignment between the template
and query.
A. Vault Encoding
Fig. 4 shows the block diagram of the proposed fuzzy vault
encoding scheme. We use the Galois field for
constructing the vault. The specific field was chosen
because it offers a sufficiently large universe (number of elements
in the field) to ensure vault security [12] and is computationally
convenient for the fuzzy vault application. The vault is
encoded as follows.
1) Given the template fingerprint image , we first obtain
the template minutiae set , where
is the number of minutiae in . The local quality index
proposed in [28] is used to estimate the quality of each
minutia in . Let be the quality of the minutia
and be the quality set corresponding to
minutiae set . We also extract the helper data set
from the template image to be used for alignment during
decoding. The details of helper data extraction are presented
in Section IV-A.
2) Since only genuine minutiae points are required to construct
the vault, we apply a minutiae selection algorithm
to the template minutiae set . This selection algorithm
sorts the minutiae based on their quality and sequentially
selects the minutiae starting with the highest quality
minutia. Moreover, the algorithm selects only well-separated
minutiae (i.e., the minimum distance between any
two selected minutia points is greater than a threshold ).
The distance between two minutia points and
is defined as
(1)
where and
are the weight assigned to the orientation attribute (set