This is an accepted version of a paper published in Elsevier Information Fusion.
If you wish to cite this paper, please use the following reference:
T. Murakami, T. Ohki, K. Takahashi, Optimal sequential fusion for multibiometric
cryptosystems, Elsevier Information Fusion (Special Issue on Information Fusion in
Biometrics), vol.32, pp.93-108, 2016.
http://dx.doi.org/10.1016/j.inffus.2016.02.002

Optimal Sequential Fusion for Multibiometric
Cryptosystems
Takao Murakamia,∗, Tetsushi Ohkia , Kenta TakahashibaNational Institute of Advanced Industrial Science and Technology, Tokyo 135-0064,
Japanb
Hitachi, Ltd., Yokohama 244-0817, Japan

Abstract
Biometric cryptosystems have been widely studied in the literature to protect
biometric templates. To ensure suﬃcient security of the biometric cryptosystem against the oﬄine brute-force attack (also called the FAR attack), it iscritical to reduce FAR of the system. One of the most eﬀective approaches
to improve the accuracy is multibiometric fusion, which can be divided into
three categories: feature level fusion, score level fusion, and decision level fusion. Among them, only feature level fusion can be applied to the biometric
cryptosystem for security and accuracy reasons. Conventional feature level
fusion schemes, however, require a user to input all of the enrolled biometricsamples at each time of authentication, and make the system inconvenient.
In this paper, we first propose a general framework for feature level sequential fusion, which combines biometric features and makes a decision eachtime a user inputs a biometric sample. We then propose a feature level sequential fusion algorithm that can minimize the average number of input,
and prove its optimality theoretically. We apply the proposed scheme to thefuzzy commitment scheme, and demonstrate its eﬀectiveness through experiments using the finger-vein dataset that contains 6 fingers from 505 subjects.
We also analyze the security of the proposed scheme against various attacks:
attacks that exploit the relationship between multiple protected templates,
the soft-decoding attack, the statistical attack, and the decodability attack.

∗

Corresponding author
Email addresses: takao-murakami@aist.go.jp (Takao Murakami),
tetsushi.ohki@aist.go.jp (Tetsushi Ohki), kenta.takahashi.bw@hitachi.com(Kenta Takahashi)
Preprint submitted to Information Fusion

January 21, 2016

Keywords: multimodal biometrics, sequential fusion, biometric
cryptosystems, sequential probability ratio test
1. Introduction
Protecting biometric data is a critical issue in biometric authentication
systems, since biometric information such as faces, fingerprints, irises andvein patterns are personal and privacy information. Although many conventional systems rely on standard encryption to protect biometric templates,
the encrypted templates have to be decrypted at the time of verification to
perform pattern matching, and thus a skilled attacker who aims at this timing
can break them. Other systems use tamper-proof devices, such as hardware
tokens, to protect biometric templates. However, these systems require auser to possess a token or to use limited devices in which a user’s templateis enrolled. These limitations can reduce the usability of the authentication
systems.
To solve the problem fundamentally, various studies have been made on
so-called biometric template protection techniques that keep biometric templates secret in the algorithm level even during verification. Among them,
biometric cryptosystems have particularly attracted attention, in which abiometric feature is used as a source of a secret key of cryptosystems andverified without being revealed using cryptographic techniques [1, 2, 3, 4].
Biometric cryptosystems typically take a strategy of embedding a secret key
into a biometric feature yielding so-called auxiliary data (AD), and releasing
the secret key from the AD using a genuine biometric feature. For authentication, the secret key is verified using a pseudo identifier (PI), which is a
public key or a hash value of the secret key. A set (AD, PI) is referred toas a protected template, and is enrolled into a database or smart card, alongwith a user ID.
There are two possible models for storing a protected template (AD,PI) in the biometric cryptosystem. The first model is to store AD and PI
separately. For example, AD is stored into a smart card of a user, while
PI is stored into the database in the authentication server. Then, even ifeither of AD or PI is compromised, we can restore the security by updating
both of the two. In this model, the security requirement for the biometric
cryptosystem is that it is suﬃciently hard to guess a biometric feature orimpersonate a user by use of either of AD or PI.
2

The second model is to store both AD and PI into a single place (e.g. theauthentication server). In this case, it can happen that both of AD and PI are
compromised from the place at the same time. Thus, the security requirement
for the biometric cryptosystem in this model is that it is suﬃciently hard to
guess a biometric feature or to impersonate a user even if both of AD and
PI are available to the adversary. If this security requirement is satisfied, we
can realize an authentication system where a user is not required to have asmart card that stores AD secretly nor required to present the smart card at
the authentication phase. We can even disclose the protected template (AD,PI) to the public, or share it across multiple organizations. Thus, we referto this model as a public template model. The aim of this paper is to realize
this model in a secure manner.
In the public template model, it is required that the biometric cryptosystem defends against the oﬄine brute-force attack (also called the FAR
attack); the attack where the adversary prepares a large number of biometric features, and matches each of them with a protected template (AD, PI)
oﬄine to find a biometric feature that successes in authentication (i.e. a correct secret key is reproduced). Let α be FAR (False Acceptance Rate) of thebiometric cryptosystem. Then, this attack results in success after matchingon average 1/(2α) biometric features. Thus, it is required that FAR α is
suﬃciently small to realize the public template model.
It is diﬃcult to achieve suﬃcient security (comparable to typical cryptographic keys) against the oﬄine brute-force attack using only one source of
biometric information (e.g. one finger-vein). For example, to achieve at least
64-bit security, FAR should be smaller than 2−64 ≃ 5.4 × 10−20 , whereas FAR
of many commercial biometric authentication systems is 10−5 ∼ 10−7 .
Multibiometric fusion [5], which combines multiple sources of biometric
information (e.g. fingerprint, face, and iris; multiple finger-veins) for authentication, is expected to fill this gap. Some studies also applied multibiometricfusion to the biometric cryptosystem [6, 7, 8, 9]. However, most of the conventional fusion schemes (including [6, 7, 8, 9]) require users to input all
the enrolled biometric information (e.g., 10 finger-veins) at the authentication phase. Such schemes are referred to as parallel fusion schemes [10], andcause inconvenience for users.
To make the authentication system convenient for users, some studies
proposed a sequential (or serial) fusion scheme [11, 10, 12, 13], which makes
a decision each time a user inputs his/her biometric sample. Some sequential
fusion schemes [12, 13] can optimize the trade-oﬀ between the accuracy and3the number of biometric inputs required before acceptance, and thus realize
a secure and convenient biometric system. These schemes combine multiple
sources of biometric information at the matching score level (i.e. score level
fusion) to make such an optimal decision.
However, it must be noted that biometric cryptosystems must not output a matching score for a security reason; an attacker can reconstruct theoriginal biometric feature by using the score as a clue (i.e. hill-climbing attack [14]). Thus, the conventional sequential fusion schemes using scorescannot be applied to biometric cryptosystems. To reduce FAR as much as
possible without disclosing scores during verification, we should construct a
multibiometric cryptosystem based on feature level fusion, which combines
biometric features into a single (but large-sized) feature. To the best of ourknowledge, no studies have attempted to develop a sequential fusion schemeat the feature level.
In this paper, we propose an optimal sequential fusion scheme at thefeature level to realize secure and convenient biometric cryptosystems in the
public template model. The main contributions are as follows:• We firstly propose a general framework for feature level sequential fusion. To the best of our knowledge, this is the first framework thatenables secure and convenient biometric cryptosystems in the public
template model (Section 3.1).
• Based on this framework, we secondly propose an optimal algorithm
for feature level sequential fusion. This algorithm is based on the SPRT
(Sequential Probability Ratio Test) [15, 16], and minimizes the average
number of input while keeping FAR less than or equal to the required
value. We also provide a formal proof of this optimality (Section 3.2 3.4).
• We apply the proposed scheme to the fuzzy commitment scheme, anddemonstrate its eﬀectiveness through experiments using the finger-vein
dataset in [17], which contains 6 fingers from 505 subjects (33298 fingervein images in total) (Section 4).
• We finally analyze the security of the proposed scheme against various attacks: attacks that exploit the relationship between multiple
protected templates, the soft-decoding attack [18, 19], the statistical
attack [18, 20], and the decodability attack [21, 22] (Sections 5 and 6).
4

Enrollment

Protected template

Template
Generation(Gen)
X

Reproduce
(Rep)
Y

AD

PI

S

VerifyS’

Authentication

Figure 1: Architecture of a biometric cryptosystem (X, Y : biometric feature, S, S ′ : secretkey, AD: auxiliary data, PI: pseudo identifier). If dis(X, Y ) ≤ δ, then S = S ′ (δ: distancethreshold).

2. Related work
2.1. Biometric cryptosystems
Biometric cryptosystems have been widely studied in the literature [23].
Examples include fuzzy commitment [3], fuzzy vault [2], and fuzzy extractor[1].
Figure 1 shows an architecture of a typical biometric cryptosystem (wealso describe the fuzzy commitment scheme [3] as an example of the biometric
cryptosystem in Section 2.2). At the enrollment phase, a template generation
algorithm Gen receives a biometric feature X from a user. It then encodes
a secret key S (typically a random string) using an ECC (error-correctingcode), and embeds it into X to make AD (auxiliary data; it is also called
helper data). AD is designed so that if the user inputs a biometric feature
Y that is suﬃciently close to X according to some distance metric dis (i.e.
dis(X, Y ) ≤ δ for a predetermined distance threshold δ), a secret key S is
reproduced from AD. Gen also makes PI (pseudo identifier), which is used
to verify the reproduced secret key. PI is a public key, or a hash value of S.
A protected template (AD, PI) is enrolled into a database (or smart card),
along with a user ID.

5Gen
X ∈ {0,1}nS ∈ {0,1}k

EncodeC(S)={0,1}n

Hash

X

PI = H(S)Rep

Y ∈ {0,1}nAD = C(S)AD = C(S)X

C(S) ε(ε = X Y )DecodeS’ ∈ {0,1}kFigure 2: Realization of the template generation algorithm Gen and the reproduce algorithm Rep using the fuzzy commitment scheme (PI is a hash value of S).

At the authentication phase, a reproduce algorithm Rep receives a new
biometric feature Y and AD, and reproduces a secret key S ′ from AD using
Y . As described above, if X and Y are suﬃciently close (i.e. dis(X, Y ) ≤ δ),a correct secret key is reproduced (i.e. S = S ′ ). The system authenticates auser using S ′ and PI.
As described in Section 1, we do not have to store the protected template(AD, PI) secretly in the public template model. We can even disclose it to
the public, or share it across multiple organizations. To achieve this ultimate
goal, FAR needs to be suﬃciently small.
2.2. Fuzzy Commitment
We now briefly explain the fuzzy commitment scheme [3], which was proposed by Juels and Wattenberg in 1999, as an example of the biometric
cryptosystem. Figure 2 shows the realization of the template generation algorithm Gen and the reproduce algorithm Rep using the fuzzy commitment
scheme. This scheme assumes that a biometric feature is represented as abinary string, and uses the Hamming distance as a distance metric. Examples of such biometric features include the IrisCode [24, 25]. We also extracta finger-vein feature represented as a binary string in our experiments in
Section 4.
At the enrollment phase, the template generation algorithm Gen receives
a biometric feature X ∈ {0, 1}n that is represented as an n-bit binary string.
6

Gen generates a codeword C(S) ∈ C ⊆ {0, 1}n (C is a set of codewords)
by passing a secret key S ∈ {0, 1}k (k-bit random string) through an errorcorrecting encoder. Note that C(S) is a codeword of an (n, k, dmin ) linear
ECC (error-correcting code), where n, k, and dmin (= 2δ + 1) represent thecodeword length, the number of information symbols, and the minimum distance, respectively (it can correct up to δ errors). It then generates auxiliary
data (also called a “commitment”) AD as AD = X ⊕ C(S) (⊕ denotes a
bitwise XOR operator). Gen also makes PI by computing the hash value
H(S) of the secret key S (or a public key corresponding to S), and stores(AD, PI) into a database along with a user ID.
At the authentication phase, the reproduce algorithm Rep receives a
new biometric feature Y ∈ {0, 1}n and AD. Rep computes S ′ by passing
Y ⊕ AD = C(S) ⊕ ϵ (ϵ = X ⊕ Y ) through an error-correcting decoder. If
the Hamming distance between X and Y is less than or equal to δ (i.e. if||ϵ|| ≤ δ, where || · || denotes the Hamming weight), a correct secret key isreproduced (i.e. S = S ′ ). The system can determine whether the user is agenuine user or an impostor by checking whether PI = H(S ′ ) or not.
2.3. Multibiometric fusion
A number of studies have been made on multibiometric fusion, which
combines multiple sources of biometric information, to improve accuracy ofbiometric authentication systems [5]. Some studies also applied multibiometric fusion to biometric cryptosystems [6, 7, 8, 9].
According to the type of information sources to be combined, multibiometric fusion can be divided into the following categories: feature level fusion,
score level fusion, and decision level fusion. They combine multiple biometric features, scores, and decision results (i.e. match/non-match), respectively.
Examples of feature level fusion include feature concatenation [6, 7, 8, 9, 26](e.g. concatenating feature vectors or binary strings), and those of score level
fusion include Bayesian fusion [27], SVM-based fusion [28], and combination
rules such as the sum rule, product rule, and max rule [29]. Examples ofdecision level fusion include the AND rule [11] and majority voting [30].
Most of the conventional multibiometric fusion schemes are parallel fusion
schemes that make a decision after a user inputs all of the enrolled biometricsamples. The major problem of these schemes is that it can make the systeminconvenient. For example, a fingerprint sensor generally allows a user to
input only one finger at a time. If the system requires the user to input all7

of 10 fingers to such a sensor at the authentication phase, the user has torepeat the input operation as many as 10 times.
To solve this problem, some studies proposed a sequential (or serial) fusion scheme that makes a decision each time a user inputs his/her biometricsample [11, 10, 12, 13]. Since this scheme uses less biometric inputs, it canoﬀer a more convenient way to improve accuracy. The simplest sequential
fusion scheme is the OR rule [11], which makes a match/non-match decisionby comparing a matching score (similarity or distance) to the threshold eachtime a user inputs his/her biometric sample. If some biometric sample isdecided as “match”, this rule accepts a user and terminates the authentication process. Thus, the OR rule is a kind of decision level sequential fusion.
Since binary decision results (i.e. match/non-match) have much less information than scores or features, decision level fusion has only a limited eﬀect
in improving accuracy.
Some studies proposed a sequential fusion scheme that uses scores as
information sources (i.e. score level sequential fusion). Examples include
the likelihood-ratio rule [13] and the posterior probability rule [12]. These
rules are based on SPRT (Sequential Probability Ratio Test) [15, 16], which
minimizes the average number of observations among all binary hypothesis
tests with the same error probabilities, or MSPRT (Multi-hypothesis SPRT)[31], which is a multi-hypothesis version of SPRT. Thus, they can minimize
the average number of biometric inputs among all sequential fusion schemeswith the same error probabilities in verification (or identification).
However, the biometric cryptosystem must not output a matching score(similarity or distance) but output only a decision result (i.e. match/nonmatch) at the matching phase. This is because the adversary can carry out
a hill-climbing attack [14] based on the matching score; he/she can construct
a biometric feature that is suﬃciently close to the feature of the target user
by changing a biometric feature little by little based on a matching score asa clue. For the same reason, the threshold at the matching phase must not
be changed in the biometric cryptosystem. Unfortunately, since both thelikelihood-ratio rule and posterior probability-based rule mentioned above
use matching scores as information sources (i.e. score level fusion), theycannot be applied to the biometric cryptosystem.
Table 1 shows the classification of conventional multibiometric fusion
schemes. Unfortunately, parallel fusion makes the system inconvenient, decision level fusion has only a limited eﬀect in improving accuracy, and scorelevel fusion cannot be applied to biometric cryptosystems, as mentioned
8

Table 1: Classification of conventional multibiometric fusion schemes. Parallel fusion
makes the system inconvenient. Decision level fusion has only a limited eﬀect in improving
accuracy. Score level fusion cannot be applied to the biometric cryptosystem.

ParallelSequential

Feature levelfeature concatenation [6, 7][8, 9, 26], etc.

Score level
Bayes [27], SVM [28], combination rules (e.g. sum,product, max) [29], etc.
likelihood-ratio rule [13],posterior probability rule[12], etc.

Decision level
AND rule [11],majority voting[30], etc.
OR rule [11],etc.

above. Although some studies applied feature level fusion (feature concatenation) to biometric cryptosystems [6, 7, 8, 9], all of their approaches fallunder parallel fusion that makes the system inconvenient. To the best of ourknowledge, no studies have attempted to develop a sequential fusion schemeat the feature level.
3. Optimal sequential fusion for multibiometric cryptosystems
We propose an optimal sequential fusion scheme at the feature level for
secure and convenient biometric cryptosystems. We first propose a framework for feature level sequential fusion (Section 3.1). We then propose asequential fusion algorithm that minimizes the average number of inputs
while keeping FAR less than or equal to the required value, and prove its
optimality under some assumptions (Section 3.2 - 3.4). We finally describe
how to set parameters k (the number of information symbols) and dmin (theminimum distance) of the error-correcting code in the proposed sequential
fusion scheme (Section 3.5).
3.1. Feature level sequential fusion
Let T be the number of modalities (or fingers) used in the multibiometric
cryptosystem. The conventional feature level fusion schemes for the biometric
cryptosystem [6, 7, 8, 9] create a large biometric feature by combining all of
T biometric features at the enrollment phase (e.g. T n-bit binary string by
concatenating T biometric features each of which is represented as an n-bit
string), and makes a protected template based on the large biometric feature.
However, it must be noted that to reproduce a secret key from AD that is9

composed of T biometric features, a user has to input all of the T biometricsamples in the same order as the enrollment. In other words, we cannot
construct a sequential fusion scheme using only the large biometric featurethat is composed of T biometric features.
We therefore propose to create a large biometric feature (and the corresponding protected template) for every possible combination of biometricfeatures. If the input order at the authentication phase is determined inadvance, there are T∑possible combinations. If the input order is not deTT1
termined, there are
t=1 T Ct = 2 − 1 possible combinations . After auser inputs the t-th biometric sample at the authentication phase, the system combines the t biometric features into one large biometric feature andmatches it with the corresponding protected template. If a correct secret key
is reproduced, the system accepts the user and terminates the authentication
process.
Figure 3 shows the proposed framework for feature level sequential fusion.
Here, X t and Y t (1 ≤ t ≤ T ) denote the t-th biometric feature at theenrollment phase and authentication phase, respectively. In this example,
the input order is determined to be Y 1 → Y 2 → · · · → Y T . Thus, thesystem creates a large biometric feature and a protected template for eachof T possible combinations. ft (1 ≤ t ≤ T ) denotes a mapping function thatcombines X 1 , · · · , X t into a large biometric feature Xt = ft (X 1 , · · · , X t ) (e.g.
bit concatenation). After creating a large biometric feature Xt (1 ≤ t ≤ T )using ft , the system generates a secret key St and creates a protected template(ADt , PIt ) from Xt and St using a template generation algorithm Gent . Then

1
This is because the system can assign a number to each modality, and combine biometric features in ascending order of the numbers. For example, when the system uses fingerprint, face, and voice (T = 3), it can assign numbers 1, 2, and 3 to fingerprint, face, and∑3voice, respectively, and combine them in this order. Then, there are t=1 3 Ct = 23 −1 = 7
possible combinations in this case: [fingerprint], [face], [voice], [fingerprint → face], [fingerprint → voice], [face → voice], and [fingerprint → face → voice]. The system createsa protected template for each of the 7 combinations. Similarly, the system combines biometric features in ascending order of the numbers at the authentication phase (in the caseof multiple fingerprints (or finger-veins), the user indicates which type of finger is input at
the authentication phase (by pressing a button, for example), since a single sensor is usedin common). For example, if the user inputs voice, fingerprint, and face at the 1st, 2nd,
and 3rd input, respectively, the system creates large biometric features as follows: [voice],[fingerprint → voice], and [fingerprint → face → voice] at the 1st, 2nd, and 3rd input,
respectively. Then the system compares each of them with the corresponding template.

10Enrollment
1st

X1

2nd

X2

T-th

XT

f2

fT

X2

Protected templates

S1

Gen1

(AD1, PI1)

S2

Gen2

(AD2, PI2)

ST

GenT

(ADT, PIT)XT

Authentication
PI1
AD1
1st

Y1

Rep1

S1’

Y2

f2

Y2

Rep2

S2’

T-th

fT

YT

RepT

Verifyaccept/next input

PIT

ADT
YT

accept/next input

PI2

AD2
2nd

VerifyS T’Verifyaccept/reject

Figure 3: Proposed framework for feature level sequential fusion.

it stores (ADt , PIt ) (1 ≤ t ≤ T ) into the database.
After a user inputs Y t (1 ≤ t ≤ T ) at the authentication phase, the system
combines Y 1 , · · · , Y t into a large biometric feature Yt = ft (Y 1 , · · · , Y t ), andreproduces a secret key St′ from Yt and ADt using a reproduce algorithm
Rept . Then it verifies whether St′ = St or not using PIt , and makes a decision
as follows: if St′ = St , accept the user and terminate the authentication
process; otherwise, require the next biometric input (if t = T , reject).
This framework improves accuracy of the biometric cryptosystem while
keeping down the number of biometric inputs. The following question now
arises: how can we minimize the number of biometric inputs? We propose
such an optimal sequential fusion algorithm by appropriately setting a distance threshold in creating each protected template. More specifically, we
set a distance threshold so that the proposed sequential fusion algorithm isequivalent to SPRT [15, 16]. In the following, we describe the details.
113.2. Assumptions
Assume that the input order at the authentication phase is determined
to be Y 1 → Y 2 → · · · → Y T for simplicity. The discussion below can also be
applied to the case where the input order is not determined.
Suppose that a user (claimant) claims an identity corresponding to the enrolled biometric features X 1 , · · · , X T at the authentication phase. Let H1 bea hypothesis that the claimant is a genuine user, and H0 be a hypothesis thathe/she is an impostor. Then, after the t-th input (i.e. after Y 1 , · · · , Y t are
obtained), the posterior probability that the claimant is a genuine user (referred to as a genuine probability) can be expressed as pt = P (H1 |Y 1 , · · · , Y t ).
Let dist (Xt , Yt ) be a distance between Xt = ft (X 1 , · · · , X t ) and Yt =ft (Y 1 , · · · , Y t ) (e.g. hamming distance). In this paper, we make the following
assumptions on the distance function dist and genuine probability pt :(i) For each number of inputs t = 1, 2, · · · , T , there exist a template generation algorithm Gent and a reproduce algorithm Rept such thata correct secret key is reproduced iﬀ dist (Xt , Yt ) ≤ δt , where δt is adistance threshold.
(ii) The genuine probability pt depends only on the distance dt = dist (Xt , Yt ).
That is, there exists a function ρt such that pt = ρt (dt ).
(iii) ρt (·) is a monotonically decreasing function. That is, the smaller the
distance dt is, the higher the genuine probability pt is.
For example, if the fuzzy commitment scheme, which is described in Section 2.2, is used as a biometric cryptosystem (i.e. if biometric features are
expressed as n-bit binary strings and the Hamming distance is used as a
distance metric) and a bit concatenation is used as ft , large biometric features are expressed as tn-bit binary strings (i.e. Xt , Yt ∈ {0, 1}tn ). Thus,
the assumption (i) can be satisfied by using an (tn, k, dmin ) linear ECC andappropriately setting parameters k (the number of information symbols) anddmin (= 2δt + 1) (the minimum distance). We describe how to set theseparameters in details in Section 3.5.
The assumption (ii) is made in score level fusion schemes that compute
posterior probabilities from scores [12, 27]. More specifically, they assume
that a matching score (distance) d from a genuine user (genuine score) is generated according to g1 (d), and a matching score from an impostor (impostor
score) is generated according to g0 (d), and express the genuine probability p

12

after observing a biometric feature Y , using Bayes’ theorem, as follows:p = P (H1 | Y ) = P (H1 | d)
P (d | H1 )P1=
P (d | H1 )P1 + P (d | H0 )P0
g1 (d)P1=,
g1 (d)P1 + g0 (d)P0

(1)
(2)
(3)

where P1 = P (H1 ) and P0 = P (H0 ) (i.e. P1 and P0 are prior probabilities).
Since it is shown that these schemes work very well through the experiments,
we can assume that (ii) is an appropriate assumption.
A distance metric is generally designed so that the smaller the distancedt is, the higher the genuine probability pt is. Thus, the assumption (iii) is
also an appropriate assumption.
3.3. Algorithm
We now describe the proposed sequential fusion algorithm, which is divided into the enrollment algorithm and the authentication algorithm.
3.3.1. Enrollment algorithm
The enrollment algorithm uses biometric features X 1 , · · · , X T as input
data, and repeats the following procedure for each of t = 1, 2, · · · , T :1. Combine biometric features X 1 , · · · , X t into a large biometric feature
Xt = ft (X 1 , · · · , X t ).
2. Set a distance threshold δt as follows:
(
)
P1
−1
δ t = ρt,
(4)
P1 + P0 αmax
where P1 = P (H1 ), P0 = P (H0 ) (i.e. P1 and P0 are prior probabilities),and αmax is a required FAR. A function ρt can be computed by assuming that a genuine score (distance) dt is generated from gt,1 (dt ) andan impostor score is generated from gt,0 (dt ), and express the genuine
probability pt , in the same way as (3), as follows:
gt,1 (dt )P1
gt,1 (dt )P1 + gt,0 (dt )P0= ρt (dt ).

pt =

13

(5)
(6)

In Section 3.4, we prove that by setting a distance threshold in thisway, the proposed algorithm minimizes the average number of inputs
while keeping FAR less than or equal to αmax .
3. Generate a secret key St , and create a protected template (ADt , PIt ) =Gent (Xt , St ). St is reproduced from ADt iﬀ a large biometric feature
Yt such that dist (Xt , Yt ) ≤ δt is input.
Then, it outputs AD = (AD1 , · · · , ADT ) as auxiliary data, and PI =(PI1 , · · · , PIT ) as pseudo identifiers.
For example, if the fuzzy commitment scheme is used as a biometric
cryptosystem (i.e. if biometric features are expressed as n-bit binary strings)
and a bit concatenation is used as ft , Gent receives a large biometric feature
Xt ∈ {0, 1}tn (tn-bit binary string), and generates a codeword C(St ) ∈ C ⊆{0, 1}tn (C is a set of codewords) by passing a secret key St ∈ {0, 1}k (k-bit
random string) through an error-correcting encoder. C(St ) is a codeword ofan (tn, k, dmin ) linear ECC (dmin = 2δt + 1). It then generates auxiliary data
ADt as ADt = Xt ⊕C(St ), and makes PIt by computing the hash value H(St )of the secret key St (or a public key corresponding to St ).
3.3.2. Authentication algorithm
The enrollment algorithm uses auxiliary data AD, pseudo identifiers PI,
and biometric features Y 1 , · · · , Y T that are input sequentially as input data,and carries out the following procedure:
1. t = 1.
2. Combine biometric features Y 1 , · · · , Y t into a large biometric feature
Yt = ft (Y 1 , · · · , Y t ).
3. Reproduce a secret key St′ = Rept (Yt , ADt ).
4. Verify whether St = St′ or not using PIt .
5. If St = St′ , accept a user and terminate the authentication process.
6. If St ̸= St′ and t < T , increment t by 1 (t = t + 1) and go back to thestep 2.
7. If St ̸= St′ and t = T , reject a user and terminate the authentication
process.
For example, if the fuzzy commitment scheme is used as a biometric
cryptosystem and a bit concatenation is used as ft , Rept receives a large
biometric feature Yt ∈ {0, 1}tn and ADt (= Xt ⊕ C(St )), and computes St′
by passing Yt ⊕ ADt = C(St ) ⊕ ϵt (ϵt = Xt ⊕ Yt ) through an error-correcting
14

decoder. If the Hamming distance between Xt and Yt is less than or equal
to δt (i.e. if ||ϵ|| ≤ δt , where || · || denotes the Hamming weight), a correct
secret key is reproduced (i.e. St = St′ ). The system can determine whether
St = St′ by checking whether PIt = H(St′ ) or not.
3.4. Optimality
The proposed algorithm minimizes the average number of inputs while
keeping FAR less than the required value αmax . We prove this optimality byshowing that the proposed algorithm is equivalent to SPRT [15, 16].
3.4.1. SPRT
Although the original SPRT, which was proposed by Wald [16], assumes
that the observed data are i.i.d. (independent and identically distributed),
we describe the algorithm that is extended to the case where the observed
data are non-i.i.d [15].
Assume that either of a null hypothesis H0 and an alternate hypothesis
H1 is true, and the data Y 1 , Y 2 , · · · are sequentially observed according to
the true hypothesis. Let p0 (t) = P (Y 1 , · · · , Y t | H0 ) be the probability that
Y 1 , · · · , Y t are observed when H0 is true, p1 (t) = P (Y 1 , · · · , Y t | H1 ) be
the probability that Y 1 , · · · , Y t are observed when H1 is true, and Zt =p1 (t)/p0 (t) be a ratio between the two probabilities (i.e. likelihood-ratio).
After the t-th data Y t is observed, SPRT computes a likelihood-ratio Zt
and makes the following decision: if Zt ≥ A, accept H1 ; otherwise if Zt ≤ B,
accept H0 ; otherwise, continue observing data (A and B are thresholds).
It is proved that SPRT minimizes the average number of observations
among all binary hypothesis tests with the same error probabilities in theasymptotic case where the error probabilities are suﬃciently small [15]. Let
α be the probability that H1 is accepted when H0 is true, and β be theprobability that H0 is accepted when H1 is true. It is also proved that SPRT
keeps these error probabilities as follows [16]:α ≤ 1/A, β ≤ B.

(7)

3.4.2. Optimality of the proposed algorithm
We now prove the optimality of the proposed algorithm by showing that
it is equivalent to SPRT:
Theorem 1. Under the assumptions (i)(ii)(iii), the proposed sequential fusion algorithm described in Section 3.3 minimizes the average number of15

inputs while keeping FAR less than or equal to αmax in the asymptotic casewhere the error probabilities (FAR and FRR) are suﬃciently small.
Proof. Assume that a user inputs the t-th biometric feature Y t . The likelihoodratio after observing Y 1 , · · · , Y t can be expressed as Zt = P (Y 1 , · · · , Y t |H1 )/P (Y 1 , · · · , Y t | H0 ).
Under the assumption (i), the user is accepted iﬀ the following inequality
holds:
dist (Xt , Yt ) ≤ δt .
(8)
Under the assumption (ii)(iii), this inequality can be further written as follows:(8) ⇔ ρt (dist (Xt , Yt )) ≥ ρt (δt )⇔ ρt (dt ) ≥ ρt (δt )⇔ P (H1 | Y 1 , · · · , Y t ) ≥ ρt (δt )P (H1 | Y 1 , · · · , Y t )ρt (δt )⇔≥1
t
1 − P (H1 | Y , · · · , Y )1 − ρt (δt )P (H1 | Y 1 , · · · , Y t )ρt (δt )≥1t
P (H0 | Y , · · · , Y )1 − ρt (δt )1tP (Y , · · · , Y | H1 )P (H1 )ρt (δt )⇔≥1
t
P (Y , · · · , Y | H0 )P (H0 )1 − ρt (δt )P0 ρt (δt )⇔ Zt ≥P1 (1 − ρt (δt ))
⇔

(9)
(10)
(11)
(12)

(13)
(14)
(15)

(recall that P1 = P (H1 ), and P0 = P (H0 )). From (13) to (14), we used
Bayes’ theorem.
The equality (4) can be written as follows:()
P1
P1 (1 − ρt (δt ))−1
δt = ρt⇔= αmax .
(16)
P1 + P0 αmax
P0 ρt (δt )By (15)(16), we have
Zt ≥

1

.
(17)
αmax
This means that the proposed algorithm is equivalent to SPRT in the casewhere we set thresholds as A = 1/αmax and B = 0. Since α and β in
16

(7) are FAR and FRR in this case, the proposed algorithm minimizes theaverage number of inputs while keeping FAR less than or equal to αmax
in the asymptotic case where the error probabilities (FAR and FRR) are
suﬃciently small.
It should be noted that the proposed sequential fusion scheme is optimal
only when FAR and FRR are suﬃciently small. This can be achieved by
setting the required FAR αmax suﬃciently small and the maximum numberof inputs T suﬃciently large (e.g. T = 10 fingers). Otherwise, the optimalityof the proposed algorithm is not theoretically guaranteed. However, since
the same holds true for the conventional score level fusion schemes basedon SPRT or MSPRT [12, 13], the proposed scheme has the same theoreticalproperty as the conventional schemes. We emphasize again that the proposed
scheme has the advantage that it can be applied to biometric cryptosystems.
3.5. Setting parameters of the error-correcting code
We now describe how to set parameters k (the number of information
symbols) and dmin (= 2δt + 1) (the minimum distance) in the (tn, k, dmin )linear ECC to satisfy the assumption (i) when we use the fuzzy commitment
scheme.
If the codeword length (i.e. the dimension of large biometric features) tn
can be expressed as tn = 2m − 1 (m is a positive integer), we can use a cyclic
code such as the BCH code [32]. Specifically, we can satisfy the assumption(i) by computing the number of information symbols k corresponding to thecodeword length tn = 2m − 1 and the minimum distance dmin = 2δt + 1,
and using the (tn, k, dmin ) BCH code. For example, in our experiments in
Section 4, we used finger-vein features represented as 511-bit binary strings(i.e. n = 511 = 29 − 1), and used the (511, 448, 15) BCH code at the 1st
input (t = 1) in the case when the distance threshold is δ1 = 7.
If tn cannot be expressed as tn = 2m − 1, we can use a shortened cyclic
code [32], which forms a (tn, k, dmin ) linear code from a (tn + i, k + i, dmin )cyclic code (i is a positive integer) by omitting the first i rows and columnsof the generator matrix. For example, in our experiments in Section 4, weused the (1022, 142, 253) shortened cyclic code, which is obtained from the(1023, 143, 253) BCH code (i = 1), at the 2nd input (n = 511, t = 2) when
the distance threshold is δ2 = 126.
However, it must be noted that the number of information symbols k(i.e. codeword space) needs to be suﬃciently large to defend against an
17attack that exhaustively searches codewords oﬄine to recover an original
biometric feature Xt from auxiliary data ADt (referred to as the codeword
search attack). For example, if the fuzzy commitment scheme is used as abiometric cryptosystem (i.e. ADt = Xt ⊕ C(St )), the attacker can recoverXt from ADt by computing, for every C ′ ∈ C (C is a set of codewords),
ADt ⊕C ′ (if C ′ = C(St ), then Xt = ADt ⊕C ′ ). In other words, we needto defend against both the FAR attack and the codeword search attack toachieve high-level security (e.g. we need to satisfy FAR ≤ 2−64 and k ≥ 64
to achieve the 64-bit security).
If the number of omitted rows/columns i in the shortened cyclic code
(which forms the (tn, k, dmin ) linear code from the (tn + i, k + i, dmin ) linearcode) is large, the number of information symbols k can be small. Similarly,
if the minimum distance dmin in the (tn, k, dmin ) BCH code is large (i.e. thedistance threshold δt is large), the number of information symbols k can besmall. In such cases, we can use the LDPC (Low-Density Parity-Check) code[33], which provides a performance very close to the Shannon limit. Since
the LDPC code is more eﬃcient than the BCH code (especially in the casewhen the codeword length tn is very large), we can increase the number of
information symbols k by using the LDPC code. Also, we can construct the
LDPC code for any codeword length tn (unlike a cyclic code such as theBCH code). Specifically, we can satisfy the assumption (i) by determining
the parameters k and dmin of the LDPC code with the codeword length tn
so that the distance threshold δt (dmin = 2δt + 1) is as close as the value
determined by the proposed scheme (using (4)(5)(6)). Here, we can estimate
the minimum distance dmin for a given tn and k by using, for example, thenearest nonzero codeword search (NNCS) approach [34].
In our experiments in Section 4, we used the LDPC code at the 3rd input(n = 511, t = 3) and the 4th input (n = 511, t = 4), since the number of
information symbols k in the shortened cyclic code was small at the 3rd and4th inputs. We obtained an enough large k by using the LDPC code, whilesatisfying the assumption (i) (see Sections 4.2 and 4.5 for details). Notethat the LDPC code uses an iterative decoding algorithm such as the sumproduct algorithm [33] to correct errors (noise) in a code. It can happen that
the LDPC code (whose minimum distance is dmin = 2δt + 1) does not correct
δt errors within a small number of iterations, depending on the noise strength
or the noise pattern. In our experiments, we assumed, for simplicity, that auser is accepted with overwhelming probability if a distance dt = dist (Xt , Yt )(i.e. the number of errors in a code) is less than or equal to the threshold δt ,18

and rejected with overwhelming probability if dt is more than δt when the
LDPC code is used. The experimental evaluation implementing the iterative
decoding algorithm is left as future work (i.e. although the LDPC code
may not correct δt errors within a small number of iterations, we leave theinvestigation of its eﬀects on the performance as future work).
4. Experimental evaluation
We carried out experiments to evaluate the security and convenience ofthe proposed sequential fusion scheme when we store AD and PI into a single
place, or disclose them to the public (i.e. public template model describedin Section 2.1). We first describe the experimental set-up: the finger-vein
dataset used in our experiments (Section 4.1), protected template generation (Section 4.2), training score distributions (which is necessary in setting
the distance threshold δt ) (Section 4.3), and an evaluation procedure (Section 4.4). We then report the experimental results (Section 4.5). We finallydiscuss storage requirements and authentication time (Section 4.6).
4.1. Dataset
We used finger-vein, which is one of the most accurate modalities, as
biometric information. There are publicly available finger-vein databases
such as the SDUMLA-HMT database [35] and the Hong Kong Polytechnic
University Finger Image Database Version 1.0 [36]. However, we used thefinger-vein database that is used in [17], because it contains more subjects andmore finger-vein images than [35, 36] (note that a large number of subjects
and finger-vein images are required in our experiments, since the required
FAR is very small).
The finger-vein database in [17] contains 505 subjects (while the datasetsin [35] and [36] contain 106 and 156 subjects, respectively). Each subject
provided images of 6 fingers (index finger, middle finger, and ring finger ofboth hands), and the collection for each finger was repeated for 11 times toobtain 11 images (one image was for the enrollment phase, and 10 images were
for the authentication phase). We eliminated 32 images at the authentication
phase that are not appropriately captured (the corresponding fingers were notappropriately put on the sensor). Thus, we used 505×6 = 3030 images at theenrollment phase, and 505×6×10−32 = 30268 images at the authentication
phase (i.e. 33298 images in total).

19

Figure 4: Example of the binary finger-vein image (32 × 16 = 512 pixels). While pixels
and black pixels represent 1 (vein) and 0 (background), respectively.

We randomly selected 200 subjects from 505 subjects for evaluation, andused the remaining 305 subjects for training the genuine score distribution
gt,1 (dt ) and the impostor score distribution gt,0 (dt ) (recall that gt,1 (dt ) and
gt,0 (dt ) are necessary in setting the distance threshold δt ; see (4)(5)(6)). We
set the number of enrolled fingers per user (i.e. the maximum number ofbiometric inputs) T as T = 4. Here we tried all the 360 (= 6 P4 ) ways
to choose the 1st, 2nd, 3rd, and 4th fingers (each of the 200 subjects forevaluation input his/her fingers in this order at the authentication phase),and carried out, for each case, the experiments described in Sections 4.2, 4.3,
and 4.4.
4.2. Protected template generation
We extracted, for each image, a finger-vein feature represented as a 511bit binary string (i.e. X t , Y t ∈ {0, 1}511 (1 ≤ t ≤ 4)). Specifically, we firstextracted a finger-vein pattern from each finger-vein image using the feature
extraction method in [37]. Then we resized each finger-vein pattern image to
32 × 16 (= 512) pixels and transformed it to a binary (2-level) image (eachpixel takes the value of either 1 (vein) or 0 (background)). Figure 4 shows
an example of the binary image. For each binary image, we eliminated apixel of the bottom right corner, and used the remaining 511 (= 29 − 1)
pixels as a 511-bit binary string to use the (511, k, dmin ) BCH code at the 1st
input (see Section 3.5). We used the Hamming distance as a distance metric,
and evaluated the accuracy of a single biometric feature (i.e. 511-bit binary
string) using the 200 subjects for evaluation. EER (Equal Error Rate; theoperating point where FAR = FRR) was 8.0 × 10−4 .
We used the fuzzy commitment scheme [3] as a biometric cryptosystem.
We used a bit concatenation as a mapping function ft , and constructed a
template generation algorithm Gent and a reproduce algorithm Rept using
an error-correcting code. Specifically, we used the (511, k, dmin ) BCH code at
the 1st input, and the (1022, k, dmin ) shortened cyclic code, which is obtained
from the (1023, k + 1, dmin ) BCH code (i = 1), at the 2nd input. We used the20

(1533, k, dmin ) LDPC code at the 3rd input, and the (2044, k, dmin ) LDPC
code at the 4th input. We determined the parameters k and dmin of the
LDPC code in the way described in Section 3.5. We verified that we canset the parameters k and dmin (= 2δt + 1) for the distance threshold δtthat is very close to the value determined by the proposed scheme (using(4)(5)(6)). In other words, we verified that the assumption (i) is satisfied inour experiments.
4.3. Training score distributions
We trained the genuine score distribution gt,1 (dt ) and the impostor score
distribution gt,0 (dt ) using genuine scores and impostor scores obtained fromthe 305 subjects. Specifically, we assumed that a distance d = dis(X i , Y i )between two finger-vein features X i ∈ {0, 1}511 and Y i ∈ {0, 1}511 is generated from a beta-binomial distribution if H1 is true (i.e. X i and Y i are
input by the same user), and generated from a normal distribution N (µ, σ 2 )otherwise (irrespective of the type of the fingers), in the same way as [17].
The beta-binomial distribution is a binomial distribution B(n, p) (n = 511
in our experiments) where p is not fixed but randomly generated from a beta
distribution Beta(a, b). Thus, we denote it by BB(n, a, b) (n = 511) in thispaper. We trained the parameters a, b in BB(n, a, b) (n = 511) using themethod of moments [38], and the parameters µ, σ 2 in N (µ, σ 2 ) using the ML(Maximum Likelihood) estimation method. Figure 5 shows how well BB(n,a, b) (n = 511) and N (µ, σ 2 ) trained from the 305 subjects fit the genuine
scores and impostor scores from the 200 subjects for evaluation, respectively.
After training BB(n, a, b) (n = 511) and N (µ, σ 2 ), we can compute thegenuine score distribution gt,1 (dt ) and the impostor score distribution gt,0 (dt )between two large finger-vein features (i.e. concatenated binary strings)
Xt , Yt ∈ {0, 1}tn (n = 511) as follows:
gt,1 (dt ) = (BB(n, a, b) ∗ · · · ∗ BB(n, a, b))(dt ) (n = 511)
|
{z
}

(18)

t-times convolution

gt,0 (dt ) = (N (µ, σ 2 ) ∗ · · · ∗ N (µ, σ 2 ))(dt ).
|
{z
}

(19)

t-times convolution

We set the required FAR αmax as αmax = 2−128 , 2−80 , 2−64 , or 2−13.7 (i.e.
128-bit, 80-bit, 64-bit, or 13.7-bit security; we explain the reason we evaluated the case of 13.7-bit security later in details). Then we set the prior21

Frequency

0.16
0.14

Histogram (genuine)
Histogram (impostor)

0.12

BB, ,    511,   25.1,   134.5
,  ଶ    180.4,   12.4

0.1
0.08
0.06
0.04
0.02
0
20

40

60

80

100

120

140

160

180

200

220

240

Score (distance)
Figure 5: The beta-binomial distribution BB(n, a, b) (n = 511, a = 25.1, b = 134.5) andthe normal distribution N (µ, σ 2 ) (µ = 180.4, σ = 12.4) trained from the 305 subjects.
They fit the histograms of genuine scores and impostor scores from the 200 subjects forevaluation, respectively.

probabilities P1 and P0 in (4) as P1 = P0 = 0.5, and a distance threshold δtusing (4)(5)(6).
It should be noted that since gt,1 (dt ) and gt,0 (dt ) in (5) can be computedfrom BB(n, a, b) (n = 511) and N (µ, σ 2 ), respectively, the assumption (ii) is
satisfied. We also verified that the assumption (iii) was satisfied in most cases(when the FAR value computed from gt,0 (dt ) is more than 2−148 ). Indeed, we
can see from Figure 6 that the function ρ1 (p1 = ρ1 (d1 )) at the 1st input ismonotonically decreasing (similar curves were obtained for the 2nd, 3rd, and4th inputs). Since we also verified that the assumption (i) is satisfied (seeSection 4.2), we can say that all of the assumptions (i)(ii)(iii) are satisfied inour experiments.
4.4. Evaluation procedure
We evaluated the performance of the proposed scheme and the OR rule[11] using the 200 subjects for evaluation. Specifically, we evaluated the performance in the case when each of the 200 subjects attempts verification
against each of them by sequentially inputting 4 fingers. Here, it must be
22

1

Genuine probability p1

ρ1
0.8
0.6
0.4
0.2
0
0

120

130

140

150

160

Score (distance) d1
Figure 6: Function ρ1 at the 1st input (p1 = ρ1 (d1 ), where p1 is a genuine probability
and d1 is a score (distance)). ρ1 was computed from gt,1 (dt ) = BB(n, a, b) (n = 511, a =25.1, b = 134.5) and gt,0 (dt ) = N (µ, σ 2 ) (µ = 180.4, σ = 12.4) using (5).

noted that we cannot evaluate too small FAR such as FAR = 2−128 , 2−80 ,and 2−64 with high statistical confidence based only on “real” data, evenif we use the database in [17] that contains a large number of finger-vein
images2 . According to the rule of three [39], more than 3α independent impostor attempts are required to conclude that FAR = α with 95% confidence.
Assuming that all of the 200 subjects are independent, the least value of FAR
that can be estimated with 95% confidence based only on the “real” data is
3/(200 × 199) = 2−13.7 (i.e. 13.7-bit security).
Thus, in the case of 128-bit, 80-bit, or 64-bit security, we evaluated FAR
through simulation experiments. Specifically, we estimated a normal distribution N (µ′ , σ ′2 ) using impostor scores from the 200 subjects for evaluation, and randomly generated impostor scores from N (µ′ , σ ′2 ) to obtainenough impostor scores. Figure 7 shows the normal distribution N (µ′ , σ ′2 ),whose parameters µ′ , σ ′2 were estimated using the ML estimation method(µ′ = 180.2, σ ′ = 12.3). It can be seen that N (µ′ , σ ′2 ) fits a histogram of imWe also confirmed that there were “no” false accepts when we set αmax = 2−128 , 2−80 ,or 2(i.e. 128-bit, 80-bit, or 64-bit security) and used “real” impostor scores from the
200 subjects.
2

−64

23

0.04

Histogram (impostor)′, ′ଶ ᇱ  180.2,  ᇱ  12.3

0.035

Frequency

0.03
0.025
0.02
0.015
0.01
0.005
0
120

130

140

150

160

170

180

190

200

210

220

230

240

Score (distance)
Figure 7: Histogram of impostor scores from the 200 subjects for evaluation and the fitted
normal distribution N (µ′ , σ ′2 ) (µ′ = 180.2, σ ′ = 12.3). In the case of 128-bit, 80-bit, or
64-bit security, we randomly generated impostor scores from N (µ′ , σ ′2 ) to obtain enoughimpostor scores. In the case of 13.7-bit security, we used the impostor scores from the 200
subjects to evaluate the performance based completely on the “real” data.

postor scores (from the 200 subjects for evaluation) well3 . We evaluated FAR
by randomly generating impostor scores from this normal distribution. Weemphasize that we evaluated FRR based only on “real” genuine scores evenin this case (i.e. 128-bit, 80-bit, or 64-bit security). We also evaluated theperformance in the case of 13.7-bit security (not by simulation but) by using
the “real” impostor scores from the 200 subjects to compare the proposed
scheme with the OR rule based completely on the “real” data.
As a performance measure, we used the rate that a genuine user is not still
3

Note that impostor score values that cause false accepts are much lower than 120(leftmost value in Figure 7) in the proposed scheme, since the distance threshold δt is verysmall. For example, the threshold δt at the first input is δt = 63, 47, and 7 in the case of
the 64-bit, 80-bit, and 128-bit security, respectively (see Figure 10 for details). However,since there is “no” impostor score whose value is less than such a threshold, we cannot fit
an impostor distribution to an area that causes false accepts. Thus, we fit an impostor
distribution to the histogram using the ML estimation method, which we believe the bestthat could be done.

24

FusionschemeProposed

OR

FAR

t=4

Averagenumber of
inputs

5.5×10-2

3.22

2^(-133)

0.27

3.3×10-2 5.3×10-3

2.28

2^(-87)

0.83

0.13

1.1×10-2 2.3×10-3

1.97

2^(-70)2^(-13.7)

1.5×10-2

1.5×10-4

0

0

1.01

2^(-16.3)

2^(-128)

1.0

1.0

1.0

1.0

4.00

2^(-133)

2^(-80)

0.98

0.95

0.93

0.91

3.86

2^(-86)

2^(-64)

0.84

0.72

0.62

0.54

3.18

2^(-69)2^(-13.7)

1.5×10-2

5.2×10-4

2.5×10-5

0

1.02

2^(-16.3)

Unaccepted rate

Required
FAR

t=1

t=2

t=3

2^(-128)

1.0

0.90

0.32

2^(-80)0.98

2^(-64)

Figure 8: The unaccepted rate, the average number of inputs, and FAR in the proposed
scheme and the OR rule.

accepted after the t-th input (1 ≤ t ≤ 4), which we call the unaccepted rate
(it is equivalent to FRR when t = 4). We also evaluated the average numberof inputs over all genuine attempts, which measures how many biometricsamples on average a genuine user needs to input until acceptance or rejection
at the authentication phase4 . We further evaluated FAR to see whether FAR
is less than the required value αmax . We averaged these performances over all
the 360 (= 6 P4 ) ways to choose the 1st, 2nd, 3rd, and 4th fingers to obtaina stable performance.
4.5. Experimental results
Figure 8 shows the unaccepted rate, the average number of inputs, and
FAR. We also show in Figure 9 the graphs representing the unaccepted rate
after the 1st, 2nd, 3rd, and 4th input, respectively. In the case of the 13.7bit security, there were “no” false rejects after the 3rd and 4th input in the
proposed scheme and the OR rule, respectively.
It can be seen from Figures 8 and 9 that the proposed scheme significantly

4

The average number of inputs can be computed from the unaccepted rate. For example, if the maximum number of inputs is T = 4 and the unaccepted rate at the 1st,
2nd, and 3rd input is 0.4, 0.3, and 0.1, respectively, the average number of inputs is
1 × (1 − 0.4) + 2 × (0.4 − 0.3) + 3 × (0.3 − 0.1) + 4 × 0.1 = 1.8.

25

Unaccepted rate

1

Number of inputs
342

1.E+00
ProposedOR

1.E-01αmax=2^(-128)
1.E-02

Unaccepted rate1

2

Number of inputs
34

1.E+00
1.E-01

ProposedOR

1.E-02αmax=2^(-80)
1.E-03

Unaccepted rate1

2

Number of inputs
34

1.E+00
1.E-01

ProposedOR

1.E-02αmax=2^(-64)
1.E-03
1

2

Number of inputs
3
4Unaccepted rate

1.E-01
1.E-02αmax=2^(-13.7)
ProposedOR

1.E-03
1.E-04
1.E-05Figure 9: Unaccepted rate after the 1st, 2nd, 3rd, and 4th input in the proposed schemeand the OR rule.

26

Required
FAR

Parameters (tn, k, dmin) in the error-correcting code
t=1

t=2

t=3

t=4

2^(-128)(511, 448, 15)(δt = 7)(1022, 142, 253) (1533, 245, 510)
(δt = 126)(δt = 254)

(2044, 277, 788)(δt = 393)

2^(-80)(511, 166, 95)(δt = 47)(1022, 100, 351)
(δt = 175)

(1533, 83, 618)(δt = 308)

(2044, 100, 876)(δt = 437)2^(-64)(511, 85, 127)(δt = 63)(1022, 65, 379)
(δt = 189)

(1533, 66, 652)
(δt = 325)

(2044, 64, 898)
(δt = 448)

Figure 10: Parameters (tn, k, dmin ) of the error-correcting code in the proposed scheme.
We also show the corresponding distance threshold δt .

outperforms the OR rule. For example, FRR (the unaccepted rate after the
4-th input) of the OR rule is very high in the case of the 64-bit, 80-bit, and128-bit security: 54% and 91% and 100%, respectively. On the other hand,in the propose scheme, the unaccepted rate is reduced to 0.23%, 0.53%, and5.5% after the 4th input in the case of the 64-bit, 80-bit, and 128-bit security,
respectively. The average number of inputs is also much lower: in the caseof the 80-bit security for example, it is 3.86 in the OR rule while 2.28 in the
proposed scheme. It can also be seen that FAR in the proposed scheme isalways less than the required FAR5 .
We would like to emphasize that the proposed scheme also outperforms
the OR rule in the case of the 13.7-bit security. For example, there are somefalse rejects at the 3rd input in the OR rule, while there are “no” false rejects
at the 3rd input in the proposed scheme. This means that the eﬀectivenessof the proposed scheme is shown based completely on the “real” data.
We also examined whether the number of information symbols k in theNote that FAR of the proposed scheme was 2−16.3 (less than 2−13.7 ) in the case of
13.7-bit security, despite the fact that the least value of FAR that can be estimated with
95% confidence is 3/(200 × 199) = 2−13.7 (according to the rule of three). It can happen
that FAR is less than 2−13.7 because we tried all the 360 (= 6 P4 ) ways to choose the
1st, 2nd, 3rd, and 4th fingers. For example, when there is only one false accept, FAR iscomputed to be 1/(200 × 199 × 360) = 2−23.8 . However, since the 360 ways to choose
four fingers are not independent, the least value of FAR that can be estimated with 95%
confidence is 3/(200 × 199) = 2−13.7 as explained above. Thus, when FAR was computed
to be 2−16.3 , we can only conclude with high confidence that FAR was less than 2−13.7 .
However, this conclusion is suﬃcient in our experiments, since 2−13.7 is the required FAR.
527

proposed scheme is more than or equal to 64, 80, and 128 in the case of the
64-bit, 80-bit, and 128-bit security, respectively (we did not examine k in thecase of the 13.7-bit security since the security level is not high; the system
is not secure against the FAR attack). Figure 10 shows the parameters(tn, k, dmin ) of the error-correcting code in our experiments. It can be seenthat the number of information symbols k is really more than or equal to 64,
80, and 128 in the case of the 64-bit, 80-bit, and 128-bit security, respectively,
which means that the proposed scheme is secure against not only the FAR
attack but also the codeword search attack described in Section 3.5.
We finally evaluated EER by changing the required FAR until we findthe operating point where FAR = FRR (the unaccepted rate after the 4-th
input). Here, since not only FAR but also FRR is too small to be evaluatedbased only on real data, we estimated a beta-binomial distribution BB(n,a′ , b′ ) (n = 511) using genuine scores from the 200 subjects for evaluation(a′ = 23.5, b′ = 126.6), and randomly generated genuine scores from BB(n, a′ ,b′ ) to obtain enough genuine scores. In other words, we evaluated EER using
the fitted beta-binomial distribution BB(n, a′ , b′ ) (n = 511, a′ = 23.5, b′ =126.6) and the fitted normal distribution N (µ′ , σ ′2 ) (µ′ = 180.2, σ ′ = 12.3)(see Figure 7). The results were as follows: EER = 4.0 × 10−7 in the OR
rule, while EER = 7.3 × 10−14 in the proposed scheme.
These results demonstrate that the secure and convenient public templatemodel in the biometric cryptosystem is made possible by using the proposed
scheme.
4.6. Discussions on storage requirements and authentication time
It should be noted that the proposed scheme requires larger storage capacity than the conventional feature level fusion scheme for the biometric
cryptosystem [6, 7, 8, 9] (i.e. parallel feature level fusion), since it requires
several pairs of ADs and PIs. Time required for authentication can also
increase, since multiple decoding attempts are required when a user inputs
more than one biometric sample. Thus, we discuss storage requirements andauthentication time in our experiments.
In our experiments, we used a finger-vein feature represented as a 511binary string, and set the number of enrolled fingers per user (i.e. the maximum number of biometric inputs) T as T = 4. Thus, 511 × 4 = 2044 bits
(about 256 bytes) per user are required for storage when we use the conventional parallel feature level fusion scheme [6, 7, 8, 9]. If the input order is
not determined, the proposed scheme requires much larger storage capacity,28

Required
FAR

Encoding/decoding time
t=1

t=2

t=3

t=4

2^(-128)73 µs (encode)
87 µs (decode)

306 µs (encode)
1.89 ms (decode)

1.32 ms (encode)
76.5 ms (decode)

5.80 ms (encode)
351 ms (decode)2^(-80)144 µs (encode)
500 µs (decode)

263 µs (encode)
280 µs (decode)

2.63 ms (encode)
165 ms (decode)

5.60 ms (encode)
353 ms (decode)2^(-64)89 µs (encode)
608 µs (decode)

168 µs (encode)
3.31 ms (decode)

2.58 ms (encode)
155 ms (decode)

6.20 ms (encode)
683 ms (decode)

Figure 11: Encoding/decoding time.

∑since there are Tt=1 T Ct = 2T − 1 = 15 possible combinations (as describedin Section 3.1). Specifically, since there are 4 C1 = 4, 4 C2 = 6, 4 C3 = 4, and4 C4 = 1 possible combinations for the 1st, 2nd, 3rd, and 4th input, respectively, the proposed scheme requires (4×1+6×2+4×3+1×4)×511 = 16352
bits (2044 bytes) per user in this case (i.e. 8 times as much as the conventional scheme). However, if the input order is determined in advance, thestorage capacity required in the proposed scheme becomes much smaller:(1 + 2 + 3 + 4) × 511 = 5110 bits (about 639 bytes) per user (i.e. 2.5 times
as much as the conventional scheme).
We then show that the increase of the authentication time does not matter much in practice by measuring the decoding time in our experiments.
Specifically, we measured the decoding time of the BCH code, the shortened
cyclic code, and the LDPC code, whose parameters (tn, k, dmin ) were set in
the same way as Figure 10, on the Intel Core i5-4690 (3.5GHz) with 24GB
1600MHz DDR3 RAM (recall that we used the BCH code at the 1st input,
the shortened cyclic code at the 2nd input, and the LDPC code at the 3rd
and 4th inputs). We set the number of iterations in the LDPC code as 100,
assuming that errors in a code can be corrected within the 100 iterations.
Figure 11 shows the results (we also show the encoding time, which is
required in the enrollment phase). Note that the conventional parallel featurelevel fusion scheme [6, 7, 8, 9] also requires the decoding attempt after a user
inputs all of the 4 fingers. Thus, the increase of the decoding time causedby using the proposed scheme (when a user is required to input all of the 4
fingers) is 78.5 ms (= 87 µs + 1.89 ms + 76.5 ms), 166 ms (= 500 µs + 280µs + 165 ms), 159 ms (= 608 µs + 3.31 ms + 155 ms), in the case of the
128-bit, 80-bit, and 64-bit security, respectively. Since they can be regarded29

as small (for example, they are much smaller than one second), we can saythat the increase of the decoding time does not cause much inconvenience inour experiments (similarly, we can say that the increase of the encoding timeat the enrollment phase is small).
5. Security of multiple protected templates
In Section 4, we showed that the proposed scheme can provide a convenient way of authentication while achieving security against both the FAR
attack and the codeword search attack (i.e. it can simultaneously achieve asuﬃciently small FAR and a suﬃciently large number of information symbolsk). However, since multiple protected templates (ADt , PIt ) (1 ≤ t ≤ T ) areenrolled per user in the proposed scheme, the attacker may try to exploit therelationship between the multiple protected templates.
Thus, we analyze the security of the proposed scheme against such attacks
in this section. In our analysis, we assume that the fuzzy commitment scheme
is used (in the same way as Section 4), and the input order is determinedin advance for simplicity (we can analyze the security in the case when the
input order is not determined in the same way). We firstly consider what wecall the partial codeword search attack as an attack that exploits the relationship between the multiple protected templates (Section 5.1). We secondly
analyze the security of the proposed scheme against this attack (Section 5.2).
We thirdly consider another attack, which we call the partial feature searchattack, and discuss the security against this attack (Section 5.3). We finallydiscuss the security against other possible attacks (Section 5.4).
5.1. Partial codeword search attack
In the proposed scheme applied to the fuzzy commitment scheme, multiple protected templates (ADt , PIt ) (1 ≤ t ≤ T ) are enrolled per user (recall
that ADt = Xt ⊕ C(St ) and PIt = H(St ), where Xt ∈ {0, 1}tn is a large
biometric feature, St ∈ {0, 1}k (k < n) is a secret key, C is an (tn, k, dmin )linear ECC, and H is a hash function). Then, the attacker may try to exploit the relationship between the multiple protected templates (ADt , PIt )(1 ≤ t ≤ T ). In particular, the attacker may try to exploit the fact that thefirst n-bit part of X1 , · · · , XT are exactly identical to each other (since they
are the first biometric feature at the enrollment phase X1 ∈ {0, 1}n ). As one
such example, we consider what we call the partial codeword search attack,which is described in the following.
30

ADt
ADt'
Xt

Xt' (=X1)

C(St)

C(St)'
n-bit
tn-bitFigure 12: AD′t , Xt′ , and C(St )′ (the first n-bit part of ADt , Xt ,, and C(St )).

Let AD′t , Xt′ , C(St )′ ∈ {0, 1}n be the first n-bit part of ADt , Xt , C(St ) ∈{0, 1}tn , respectively. Note that Xt′ = X1 . Figure 12 shows AD′t , Xt′ , andC(St )′ . We refer to C(St )′ (i.e. the first n-bit part of a valid codeword C(St ))as a valid partial codeword. Let C ′ be a set of valid partial codewords (i.e.
C(St )′ ∈ C ′ ), and k ′ be the entropy of valid partial codewords (i.e. there′
are 2k valid partial codewords). If k ′ ≪ k (i.e. the entropy of valid partial
codewords is much smaller than that of valid codewords), the attacker can
exploit this as follows:gt )′ ∈ {0, 1}n from C ′ (C ′1. Randomly choose a valid partial codeword C(Sis a set of valid partial codewords).
gt )′ ⊕ AD′ (recall
f1 of X1 as follows: X
f1 = C(S2. Compute a guess value Xtthat X1 = Xt′ = C(St )′ ⊕ AD′t ).
g1 ) of C(S1 ) as follows: C(Sg1 ) = X
f1 ⊕ AD1 .
3. Compute a guess value C(Sg1 ). Let Se1 be a decoded value.
4. Decode C(S5. Verify whether Se1 = S1 or not using PI1 = H(S1 ).
gt )′ = C(St )′ , then X
f1 = X1 and Se1 = S1 . Thus, theNote that if C(Sattacker can recover the first biometric feature X1 by exhaustively searching′valid partial codewords (there are 2k valid partial codewords in total) via
the above algorithm. We refer to this attack as the partial codeword searchattack, which is much stronger than the codeword search attack (described in
Section 3.5) if and only if k ′ ≪ k (i.e. the entropy of valid partial codewords
is much smaller than that of valid codewords).

31

tn - kG-1

H-1T

tn - nG1

ntn - n
k

k
St

n

H 1T

0

C(St)

Figure 13: The generator matrix G = [G1 |G−1 ] and the parity check matrix H = [H1 |H−1 ](C(St ) = St G and C(St )H T = 0).

5.2. Security against the partial codeword search attack
The partial codeword search attack is much stronger than the codeword
search attack if and only if the entropy of valid partial codewords k ′ is muchsmaller than that of valid codewords k. However, we show that k ′ = k (i.e.
the partial codeword search attack is only as strong as the codeword searchattack) in most cases.
Let G (k × tn matrix that has full rank: rank(G) = k (< tn)) bea generator matrix of the (tn, k, dmin ) linear error-correcting code C (i.e.
C(St ) = St G). Let further G1 (k × n matrix) and G−1 (k × (tn − n) matrix)
be the first n columns of G and the remaining part of G, respectively (i.e.
G = [G1 |G−1 ]). Then, a valid partial codeword C(St )′ ∈ {0, 1}n can be generated by multiplying a k-bit random string (i.e. secret key) St ∈ {0, 1}k by
G1 : C(St )′ = St G1 . When we attempt 2k possible random strings as St , weobtain 2rank(G1 ) valid partial codewords. Thus, the entropy of valid partial
codewords k ′ can be expressed as k ′ = rank(G1 ), and we have k ′ = k if andonly if G1 has full rank (i.e. rank(G1 ) = k (< n)).
Taking this into account, we focus on the LDPC code for simple analysis,
and show both theoretically and experimentally that the matrix G1 has fullrank in most cases.
5.2.1. Theoretical analysis
We begin by a theoretical analysis. Let H ((tn − k) × tn matrix) be aparity check matrix of the (tn, k, dmin ) linear error-correcting code C (i.e.
for any valid codeword C(St ) ∈ {0, 1}tn , C(St )H T = 0 (0 is a zero vector)).
32

Let further H1 ((tn − k) × n matrix) and H−1 ((tn − k) × (tn − n) matrix)
be the first n columns of H and the remaining part of H, respectively (i.e.
H = [H1 |H−1 ]). Figure 13 shows the generator matrix G = [G1 |G−1 ] and theparity check matrix H = [H1 |H−1 ].
In the following, we firstly prove that if H−1 has full rank, then G1 has
full rank (Proposition 1). We secondly show that H−1 has full rank in mostcases.
Proposition 1. For any ϵ > 0, we haverank(H−1 ) > tn − n − ϵ =⇒ rank(G1 ) > k − ϵ.

(20)

Thus, if H−1 has full rank, then G1 has full rank (i.e. rank(H−1 ) = tn−n =⇒rank(G1 ) = k, which is obtained by substituting ϵ = 1 in (20)).
Proof. Since G and H are the generator matrix and the parity check matrix,
respectively, we haveT
GH T = 0 ⇐⇒ G1 H1T + G−1 H−1
= 0.

(21)

Suppose that rank(G1 ) ≤ k − ϵ (ϵ > 0). Then, there exists a k × k regularmatrix M such that the bottom ϵ rows of M G1 are 0 (such M can be foundby Gaussian elimination). By multiplying the both sides of (21) by M , wehaveT
M G1 H1T + M G−1 H−1
= 0.

(22)

T
Since the bottom ϵ rows of M G1 H1T are 0, the bottom ϵ rows of M G−1 H−1
are also 0. Let L−1 be the bottom ϵ rows of M G−1 (L−1 is an ϵ × (tn − n)matrix). Then,T
L−1 H−1= 0.

(23)Here, suppose that L−1 is rank deficient. Then, since the bottom ϵ rows of
M G1 are 0, the bottom ϵ rows of M G = M [G1 |G−1 ] is also rank deficient, andso is G (since M is a regular matrix). However, this violates the assumptionthat G has full rank, which is described in the 2nd paragraph of Section 5.2.
Thus, L−1 has full rank (i.e. rank(L−1 ) = ϵ). Then, it follows from (23)that rank(H−1 ) ≤ tn − n − ϵ. The contrapositive of “rank(G1 ) ≤ k − ϵ =⇒rank(H−1 ) ≤ tn−n−ϵ” is “rank(H−1 ) > tn−n−ϵ =⇒ rank(G1 ) > k−ϵ”.
33

T
We now show that H−1((tn − n) × (tn − k) matrix; tn − n < tn − k) has
Tfull rank (i.e. rank(H−1 ) = rank(H−1 ) = tn − n) in most cases. We show
this in the case of the (irregular) LDPC code, since it is easy to analyze. LetTu = tn−n and v = tn−k (i.e. H−1
is a u×v matrix; u < v). Assume that eachTelement of H−1 follows the Bernoulli distribution with success probability p(i.e. each element takes the value “1” with probability p and the value “0”Twith probability 1 − p). Let further P (u, v) be the probability that H−1
hasT
full rank (i.e. rank(H−1 ) = u), which is evaluated in the following.
T
The matrix H−1
is rank deficient if and only if there exist l rows (1 ≤ l ≤Tu) in H−1 such that the summation of the l rows is 0. Consider a specific setof l rows. The summation of the first column in the l rows is 0 if and only ifthere are even numbers of “1”s in the column. Thus, the probability Q1 (l)that the summation of the first column in the l rows is 0 is given by

Q1 (l) = (1 − p)l + l C2 p2 (1 − p)(l−2) + l C4 p4 (1 − p)(l−4) + · · · .

(24)TSince there are v columns in H−1, the probability Q2 (l, v) that the summationof the l rows is 0 is given by

Q2 (l, v) = Q1 (l)v .

(25)

Let Q3 (l, u, v) (1 ≤ l ≤ u) be the probability that there is no set of lTrows in H−1
such that the summation of the l rows is 0. There are u Cl
Tways to choose l rows in H−1, and for each of them, the probability thatthe summation is 0 is given by Q2 (l, v). We assume that each of them isindependent for simplicity. Then, the probability Q3 (l, u, v) can be written
as follows:
Q3 (l, u, v) = (1 − Q2 (l, v))u Cl .

(26)

Similarly, we assume that each of Q3 (1, u, v), Q3 (2, u, v), · · · , and Q3 (u, u, v)
Tis independent for simplicity. Then, the probability P (u, v) that H−1
has fullrank can be written as follows:
P (u, v) = Q3 (1, u, v) · Q3 (2, u, v) · · · · · Q3 (u, u, v).

(27)

When p is much smaller than 1 (p ≪ 1), the probabilities Q1 (l), Q2 (l, v),
Q3 (l, u, v), and P (u, v) in (24), (25), (26), and (27) can be approximated as34

Frequency

Frequency

1
0.8
0.6
0.4
0.2
0

0

100

200 277(=k)

1
0.8
0.6
0.4
0.2
0

Rank of G1

0

511

1022

1533(=tn-n)

Rank of H-1

Figure 14: Frequency distribution of the rank of G1 (left) and H−1 (right). G1 and H−1
have full rank in all of the 1000 cases.

follows:
Q1 (l)Q2 (l, v)
Q3 (l, u, v)
P (u, v)

≈
≈
≈
≈
≈

(1 − p)l(1 − p)lv
1 − u Cl (1 − p)lv
1 − (u C1 (1 − p)v + u C2 (1 − p)2v + · · · )1 − u(1 − p)v .

(28)
(29)
(30)
(31)

Since the probability that elements in a specific row are 0 is (1 − p)v , the
2nd term of the right side of (31) approximates the probability that thereT
exists a row in H−1
whose elements are 0. This probability is almost equal
to 0 (and hence P (u, v) ≈ 1) when v is suﬃciently large. We also verified bynumerical calculations that both P (u, v) in (27) and P (u, v) in (31) converge
to 1 as v increases.
Thus, the matrix H−1 has full rank (and hence the matrix G1 also has
full rank) in most cases when we use the LDPC code with suﬃciently large
v = tn − k. In the next subsection, we show that the matrices G1 and H−1
indeed have full rank in most cases through experiments.
5.2.2. Experimental analysis
We carried out experiments to verify whether the matrices G1 and H−1
indeed have full rank in most cases. In our experiments in Section 4, weused the (2044, 277, 788) LDPC code at the 4th input in the case of the 128bit security (see Figure 10). In this setting, we randomly generated both
the generator matrix G and the parity check matrix H for 1000 times, andexamined the rank of G1 and H−1 for each case. Figure 14 shows the results.
It can be seen that G1 and H−1 have full rank in all of the 1000 cases, which35supports the theoretical analysis in Section 5.2.1. As a consequence, we cansay that the partial codeword search attack in Section 5.1 is only as strongas the codeword search attack in our experiments.
Note that it is (very unlikely but) still theoretically possible that thematrix H−1 is rank deficient, as analyzed in Section 5.2.1. However, even insuch cases, the proposed scheme is secure against the partial codeword searchattack if the rank of H−1 is very large. Recall that the entropy of valid partial
codewords k ′ is k ′ = rank(G1 ). By Proposition 1, if rank(H−1 ) > tn − n − ϵ(ϵ > 0), then k ′ = rank(G1 ) > k − ϵ. Thus, if ϵ is very small, the strength ofthe partial codeword search attack is almost the same as that of the codeword
search attack. For example, it is (very unlikely but) theoretically possible
T
that there is a row in H−1
whose elements are 0 (which makes H−1 rank
deficient). However, even such a event increases ϵ by only one. Thus, we
can conclude that the proposed scheme, whose security against the codeword
search attack is shown in Section 4, is also secure against the partial codeword
search attack.
5.3. Security against the partial feature search attack
We have so far considered the security of the proposed scheme against
the partial codeword search attack. However, we can consider another attack
against multiple protected templates as follows. Suppose that the attacker
guesses some n′ (< n)-bit part of the first biometric feature X1 ∈ {0, 1}n ,which we call a partial feature. Then, he/she adds the partial feature to thecorresponding n′ bits of ADt (1 ≤ t ≤ T ), and checks whether the resulting
n′ -bit string (i.e. the n′ -bit part of X1 ⊕ ADt ) is valid (i.e. it is a part of avalid codeword C(St )) or not. Figure 15 shows the n′ -bit part of X1 , ADt ,and C(St ) (gray area). If the n′ -bit part of X1 ⊕ADt is not valid, the attacker
discards the guess, and attempts another guess for the partial feature. By
doing so, the attacker may narrow down the search for X1 . We refer to this
attack as the partial feature search attack.
We analyze the security of the proposed scheme against this attack. Recall that G (k × tn matrix) is a generator matrix of the (tn, k, dmin ) linear
error-correcting code C (i.e. C(St ) = St G). Let G′1 (k × n′ matrix) be apartial generator matrix corresponding to the n′ -bit part of C(St ) (i.e. St G′1
generates the n′ -bit part of C(St )), and G′−1 (k × (tn − n′ ) matrix) be theremaining part of G. We can theoretically show that G′1 has full rank (i.e.
rank(G′1 ) = min(k, n′ )) in most cases in the same way as Section 5.2.1 (weomit the proof). Thus, in the following, we explain that the proposed scheme
36

n'-bit
X1
ADt

=
C(St)
n-bit
tn-bitFigure 15: n′ -bit part of X1 , ADt , and C(St ) (gray area).

is secure against the partial feature search attack if G′1 has full rank and thenumber of information symbols k is suﬃciently large.
Firstly, suppose that G′1 has full rank and n′ < k. Then, rank(G′1 ) =′min(k, n′ ) = n′ . Thus, there are 2n possible strings as an n′ -bit part of avalid codeword C(St ). In other words, the n′ -bit part of X1 ⊕ ADt is always
valid, and hence the attacker cannot narrow down the search for X1 using
the partial feature search attack.
Secondly, suppose that G′1 has full rank and n′ ≥ k. Then, rank(G′1 ) =min(k, n′ ) = k, and there are 2k possible strings as an n′ -bit part of a valid
codeword C(St ). In other words, the entropy of the n′ -bit part of C(St ) isk, which is the same as the entropy of C(St ). Thus, the attacker cannot
suﬃciently reduce the entropy of the partial feature (i.e. n′ -bit part of X1 )if k is suﬃciently large. For example, suppose that the attacker prepares alarge number of biometric features Z (1) , · · · , Z (M ) ∈ {0, 1}n (M is the numberof biometric features), and uses the n′ -bit part (n′ ≥ k) of each biometricfeature Z (m) (1 ≤ m ≤ M ) as a guess value. Then, by the partial featuresearch attack, he/she can obtain only a set of valid codewords computedfrom Z (m) ⊕ ADt (since the entropy of the n′ -bit part of C(St ) (= k) is thesame as the entropy of C(St ), a set of valid codewords computed from then′ -bit part of Z (m) ⊕ ADt is equal to a set of valid codewords computed from
Z (m) ⊕ ADt ). If he/she chooses the most likely codeword from them, thenthis attack is equivalent to the statistical attack [18, 20], which is describedin Section 6.2. If k is suﬃciently large, the proposed scheme is secure against
the statistical attack, as discussed in Section 6.2. Similarly, if k is suﬃciently37large, the proposed scheme is secure against the partial feature search attack.
To sum up, if G′1 has full rank and k is suﬃciently large, the proposed
scheme is secure against the partial feature search attack. Since G′1 has fullrank in most cases (which can be shown in the same way as Section 5.2.1),
and k is very large (k = 128, 80, or 64) in our experiments in Section 4, we
can say that the proposed scheme is secure against the partial feature searchattack.
5.4. Security against other attacks
We finally discuss the security of the proposed scheme against other possible attacks. We partition a generator matrix G (k ×tn matrix) and a parity
check matrix H ((tn − k) × tn matrix) as follows: G = [G1 |G2 | · · · |Gt ] andH = [H1 |H2 | · · · |Ht ], where Gi is a k × n matrix and Hi is a (tn − k) × n
matrix (1 ≤ i ≤ t). The partial codeword search attack, which is described in
Sections 5.1 and 5.2, is threatening if the rank of G1 is low (and the entropyof valid partial codewords k ′ is small). The attacker may try to generalize
this attack to an attack that is threatening if the rank of Gi (1 ≤ i ≤ t) islow. In other words, the attacker may try to utilize the generator matrix Giwith the lowest rank for his/her attack.
However, we can show that each Gi (1 ≤ i ≤ t) has full rank (i.e.
rank(Gi ) = k, ∀i = 1, · · · , t) in most cases as follows. Let G−i (k×(tn−n) matrix) be a matrix that is obtained by concatenating G1 , · · · , Gt except for Gi(i.e. G−i = [G1 | · · · |Gi−1 |Gi+1 | · · · |Gt ]). Similarly, let H−i ((tn−k)×(tn−n)matrix) be a matrix that is obtained by concatenating H1 , · · · , Ht except for
Hi (i.e. H−i = [H1 | · · · |Hi−1 |Hi+1 | · · · |Ht ]). Then, we can prove that for any
ϵ > 0 and any i (1 ≤ i ≤ t), we haverank(H−i ) > tn − n − ϵ =⇒ rank(Gi ) > k − ϵ(32)(and therefore, rank(H−i ) = tn − n =⇒ rank(Gi ) = k). We can prove this inexactly the same way as Proposition 1 in Section 5.2.1 (and hence we omit
the proof). We can also extend the argument in Section 5.2.1 to show thateach H−i (1 ≤ i ≤ t) has full rank (i.e. rank(H−i ) = tn − n, ∀i = 1, · · · , t) inmost cases. Thus, each Gi (1 ≤ i ≤ t) has full rank (i.e. rank(Gi ) = k, ∀i =1, · · · , t) in most cases. It is (very unlikely but) still theoretically possiblethat H−i is rank deficient. However, even in such cases, we can say that therank of Gi is very close to k (since rank(Gi ) > k − ϵ and ϵ is very small), as
discussed in Section 5.2.2. Thus, we can conclude that the proposed scheme,38whose security against the codeword search attack is shown (i.e. k is verylarge) in Section 4, is also secure against an attack that utilizes the generator
matrix Gi with the lowest rank.
We can also generalize the partial feature search attack, which is describedin Section 5.3, to an attack that tries to narrow down the search for the i-th
biometric feature X i ∈ {0, 1}n (1 ≤ i ≤ t) as follows: (i) Guess some n′(< n)-bit part of X i (i.e. partial feature); (ii) Add the partial feature to thecorresponding n′ bits of ADt ; (iii) Check whether the resulting n′ -bit stringis valid (i.e. it is a part of a valid codeword C(St )) or not. We can easily
extend the arguments in Section 5.3 to show that the proposed scheme isalso secure against this attack.
Finally, we consider what we call the partial FAR attack, which is somewhat similar to the partial feature search attack (described in Section 5.3).
We partition auxiliary data ADt ∈ {0, 1}tn and a codeword C(St ) ∈ {0, 1}tn
as follows: ADt = [AD1t |AD2t | · · · |ADtt ] and C(St ) = [C(St )1 |C(St )2 | · · · |C(St )t ],where ADit , C(St )i ∈ {0, 1}n (1 ≤ i ≤ t). In the partial FAR attack, the attacker first guesses a value of the i-th biometric feature X i ∈ {0, 1}n . Letfi ∈ {0, 1}n a guess value of X i . Then, the attacker computes a guess valueXgt )i ∈ {0, 1}n of C(St )i as follows: C(Sgt )i = X
fi ⊕ ADi . Finally, the atC(Stgt )i using, for example, Gi and Hi (i.e.
tacker tries to recover St from C(Sthe i-th submatrix of G and H, respectively). This attack diﬀers from thegt )ipartial feature search attack in that the attacker attempts to decode C(Sgt )i is valid).
to obtain St (instead of verifying whether C(SIf Gi is a generator matrix of some (eﬃcient) linear ECC, the attacker cangt )i and recover St . However, a linear ECC does not generally havedecode C(Sa property that a submatrix Gi of a generator matrix G is also a generator
matrix of some linear ECC (if Gi should be a generator matrix of somelinear ECC, we could obtain a very eﬃcient linear ECC that corrects total
errors while correcting partial errors). In other words, in general, Gi is nota generator matrix of some linear ECC, and therefore the attacker cannot
gt )i to recover St . For example, if Gi H T = 0, Gi is a generator
decode C(Simatrix and Hi a parity check matrix corresponding to Gi . However, as we
can see below, Gi HiT is not 0 in general. Since G and H are the generator
matrix and the parity check matrix, respectively, we have
GH T = 0 ⇐⇒

t
∑
i=1

39

Gi HiT = 0.

(33)

However, (33) does not imply Gi HiT = 0. Thus, in general, Gi HiT is not
0, which means that Hi is not a parity check matrix corresponding to Gi .
gt )i using Gi and Hi .
Therefore, the attacker cannot recover St from C(Sgt )i ∈ {0, 1}n as a guess
From another perspective, we can regard C(Stnvalue of the codeword C(St ) ∈ {0, 1} that has (t − 1)n-bit erasures (i.e.
we can regard guess values of C(St )1 , · · · , C(St )i−1 , C(St )i+1 , · · · , C(St )t as
erasures). For example, in our experiments in Section 4, we can regard
g4 )i (1 ≤ i ≤ 4) as a guess value of C(S4 ) that has (4 − 1) × 511 = 1533C(Sbit erasures (n = 511). Since there are too many erasures, the attacker
cannot recover S4 from the guess value of C(S4 ). For example, in the caseof the 64-bit security, we used the (2044, 64, 898) LDPC code (δt = 448) at
the 4th input (see Figure 10). Since the number of erasures is more than 2δt(i.e. 1533 > 2 × 448), the attacker fails to recover S4 from the guess value ofC(S4 ). Thus, the attacker cannot perform the partial FAR attack.
As a conclusion, we can say that the proposed scheme is secure against
the partial codeword search attack, the partial feature search attack, theirgeneralizations, and the partial FAR attack.
6. Security of the fuzzy commitment scheme
In our experiments in Section 4, we used the fuzzy commitment scheme.
However, some studies proposed attacks against the fuzzy commitment scheme,
such as the soft-decoding attack [18, 19], the statistical attack (or ECC (errorcorrection code) histogram attack) [18, 20], and the decodability attack (orcross-matching attack) [21, 22]. Thus, we discuss the security of the proposed
scheme applied to the fuzzy commitment scheme against these attacks. We
discuss the security against the soft-decoding attack, the statistical attack,and the decodability attack in Sections 6.1, 6.2, and 6.3, respectively.
6.1. Security against the soft-decoding attack
In the soft-decoding attack [18, 19], the attacker prepares a large numberof biometric features Z (1) , · · · , Z (M ) ∈ {0, 1}n (M is the number of biometricfeatures), and matches each of them with a protected template (AD, PI)(AD = X ⊕ C(S) and PI = H(S), where X ∈ {0, 1}n is an enrolled biometricfeature, S ∈ {0, 1}k (k < n) is a secret key, C is an (n, k, dmin ) linear ECC,
and H is a hash function). Specifically, the attacker adds Z (m) (1 ≤ m ≤M ) to AD (i.e. Z (m) ⊕ AD), and runs a soft decoder that always outputs
40Z(1), …, Z(M)

C(S))Z(1) AD, …, Z(M)AD

Frequency

AD (= X

C(S)* Codeword

Figure 16: Statistical attack. The attacker computes a histogram of codewords from acommitment AD (= X ⊕ C(S)) using M biometric features Z (1) , · · · , Z (M ) that he/she
prepares, and chooses the most likely codeword C(S)∗ as an estimate of C(S).

one or more nearest codewords (even if the number of errors exceeds the
distance threshold). Then, the attacker checks whether each of the nearest
codewords is a correct codeword C(S) or not by using PI (= H(S)). If theattacker finds a correct codeword C(S), he/she can recover the biometricfeature X as follows: X = AD ⊕ C(S). In the FAR attack, the attacker
fails to decode Z (m) ⊕ AD (and hence, fails to obtain a codeword) if thenumber of errors exceeds the distance threshold. On the other hand, inthe soft-decoding attack, the attacker always obtains one or more nearest
codewords even in such cases by using a soft decoder. Thus, the soft-decoding
attack has a higher success probability (i.e. the probability of obtaining acorrect codeword C(S)) than the FAR attack when the attacker searches
the same biometric features Z (1) , · · · , Z (M ) . However, since nearest neighbordecoding (or maximum likelihood decoding) takes much time in general, thesoft-decoding attack takes much more time than the FAR attack.
One way to defend against this attack is to increase the number of information symbols k (as well as the codeword search attack described in Section 3.5). This is because the Voronoi region (also called the Voronoi cell) of
a correct codeword C(S) becomes very small (and hence the probability thata soft decoder outputs C(S) becomes very small) if the number of possible
codewords 2k is very large. Since k is very large (k = 128, 80, or 64) in our
experiments in Section 4, we consider that the proposed scheme is secureagainst the soft-decoding attack. Also, we note again that the soft-decoding
attack takes much more time than the FAR attack.
6.2. Security against the statistical attack
In the statistical attack [18, 20], the attacker runs, for each of Z (m) ⊕ AD
(1 ≤ m ≤ M ), a soft decoder that always outputs one or more nearest codewords in the same way as the soft-decoding attack. Then, the attacker counts
41the number of appearances for each possible codeword, and computes a histogram of codewords. Using the histogram, the attacker chooses a codeword
C(S)∗ corresponding to the most likely codeword (i.e. histogram maximum).
If C(S)∗ = C(S), the attacker can recover the biometric feature X as follows: X = AD ⊕ C(S)∗ = AD ⊕ C(S). Figure 16 shows an overview of thestatistical attack.
In the soft-decoding attack, the attacker checks whether each of the nearest codewords (computed from Z (m) ⊕ AD (1 ≤ m ≤ M )) is correct or notusing a pseudo identifier PI. On the other hand, in the statistical attack, theattacker computes the most likely codeword C(S)∗ from the nearest codewords, and tries to recover the biometric feature X without using PI. As
described in Section 1, one of the possible models for storing a protected
template (AD, PI) is to store AD and PI separately. In this model, it canhappen that the attacker (does not obtain PI but) obtains only AD, andhence cannot perform the soft-decoding attack. The statistical attack can
be a threat even in this case, since this attack does not require PI. It should
be noted, however, that this paper focuses on the public template model inwhich both AD and PI are stored into a single place (or made public). In
this model, since the attacker can obtain both AD and PI simultaneously,
he/she can perform both the soft-decoding attack and the statistical attack.
Also, it is important to note that the statistical attack has a lower successprobability than the soft-decoding attack when the attacker searches thesame biometric features Z (1) , · · · , Z (M ) . The soft-decoding attack checks, foreach of the nearest codewords (computed from Z (m) ⊕ AD (1 ≤ m ≤ M )),whether it is a correct codeword C(S) or not using PI. Thus, this attack
results in success if the number of appearance for C(S) is more than or equal
to 1. On the other hand, the statistical attack results in success only if thenumber of appearance for C(S) is the highest among all possible codewords.
In other words, the statistical attack has a lower success probability than thesoft-decoding attack, because it does not perform a checking process using
PI. Since the proposed scheme is secure against the soft-decoding attack (asdiscussed in Section 6.1), we consider that the proposed scheme is also secureagainst the statistical attack.
As described in Section 6.1, the soft-decoding attack takes much moretime than the FAR attack, since nearest neighbor decoding (or maximum
likelihood decoding) takes much time in general. Taking this into account,
the attacker may run a hard-decoder that decodes Z (m) ⊕ AD (1 ≤ m ≤ M )only if the number of errors is within the distance threshold (as well as the42

FAR attack) in the statistical attack. In this case, the statistical attack has alower success probability than the FAR attack (because it does not performa checking process using PI). Since the proposed scheme in our experiments
in Section 4 is secure against the FAR attack, it is also secure against thestatistical attack that runs the hard-decoder.
6.3. Security against the decodability attack
Consider a scenario where the same person uses two biometric authentication systems A and B, both of which use the fuzzy commitment scheme.
Let XA (resp. XB ) ∈ {0, 1}n be the biometric feature at the enrollment phasein the system A (resp. B). The system A (resp. B) computes a commitment
ADA = XA ⊕ C(SA ) (resp. ADB = XB ⊕ C(SB )) ∈ {0, 1}n (SA , SB ∈ {0, 1}k(k < n) are secret keys, and C is an (n, k, dmin ) linear ECC), and stores it
into the database. Kelkboom et al. [21] proposed the decodability attack(or cross-matching attack), which determines whether ADA and ADB are
from the same user or not to break the unlinkability [40] of the protected
templates.
In the decodability attack in [21], the attacker adds ADA to ADB , which
can be written as follows:
ADA ⊕ ADB = (XA ⊕ C(SA )) ⊕ (XB ⊕ C(SB ))= ϵAB ⊕ (C(SA ) ⊕ C(SB )),(34)

where ϵAB = XA ⊕ XB . Then, the attacker checks whether ADA ⊕ ADB
is decodable (i.e. the number of errors is within the distance threshold δ(= (dmin − 1)/2)) or not, and decides that ADA and ADB are from the sameuser if and only if it is decodable. Since C is linear, C(SA ) ⊕ C(SB ) in (34) isa codeword. Thus, if ϵAB (= XA ⊕ XB ) ≤ δ, the attacker successfully decodes
ADA ⊕ ADB , and decides that ADA and ADB are from the same user (ifϵAB > δ and ϵAB is not decodable, the attacker decides that ADA and ADB
are from diﬀerent users). Since the distance between XA and XB from thesame user is small in general, the attacker breaks the unlinkability with highaccuracy.
To prevent this attack, Kelkboom et al. [21] proposed a bit-permutation
randomization process, which shuﬄes a biometric feature vector using a random permutation matrix that is made public. Let PA (resp. PB ) be a random permutation matrix (n × n matrix) in the system A (resp. B). The
system A (resp. B) generates a commitment AD′A (resp. AD′B ) as follows:
43

AD′A = PA XA ⊕ C(SA ) (resp. AD′B = PB XB ⊕ C(SA )), and stores (AD′A ,PA ) (resp. (AD′B , PB )) into the database (at the authentication phase, thesystem shuﬄes a biometric feature in the same way). Then, the XOR of thecommitments AD′A and AD′B can be written as follows:
AD′A ⊕ AD′B = ϵ′AB ⊕ (C(SA ) ⊕ C(SB )),(35)

where ϵ′AB = PA XA ⊕ PB XB . Since PA and PB are random, we can assume
that PA XA and PB XB are also random, and hence ϵ′AB does not have discriminative information. Kelkboom et al. [21] showed that the performanceof the decodability attack was close to that of a random classifier when thesystems use the bit-permutation randomization process.
The proposed scheme applied to the fuzzy commitment scheme can also
prevent the decodability attack by using the bit-permutation randomization
process as follows. Let XA,t ∈ {0, 1}tn (resp. XB,t ∈ {0, 1}tn ) be the t-th large
biometric feature at the enrollment phase in the system A (resp. B). Let
further PA,t (resp. PB,t ) be a random permutation matrix (tn × tn matrix)
at the t-th input in A (resp. B). The system A (resp. B) shuﬄes XA,t (resp.
XB,t ) using PA,t (resp. PB,t ), and computes a commitment AD′A,t ∈ {0, 1}tn(resp. AD′B,t ∈ {0, 1}tn ) at the t-th input. That is, AD′A,t and AD′B,t can be
written as follows:
AD′A,t = PA,t XA,t ⊕ C(SA,t )AD′B,t = PB,t XB,t ⊕ C(SB,t ),

(36)
(37)

where SA,t , SB,t ∈ {0, 1}k (k < tn) are secret keys, and C is an (tn, k, dmin )linear ECC. The system A (resp. B) stores (AD′A,t , PA,t ) (resp. (AD′B,t , PB,t ))(1 ≤ t ≤ T ) into the database. Since PA,1 , · · · , PA,T , PB,1 , · · · , PB,T are random, we can assume that PA,1 XA,1 , · · · , PA,T XA,T , PB,1 XB,1 , · · · , PB,T XB,T
are also random, and hence the proposed scheme is secure against the decodability attack.
We also analyze storage requirements in the proposed scheme when we use
the bit-permutation randomization process. In our experiments in Section 4(n = 511, T = 4), the conventional parallel feature level fusion scheme [6,7, 8, 9] requires a random permutation matrix whose size is 522 kB (= (4 ∗511)2 /8) per user. On the other hand, the proposed scheme requires random
permutation matrices whose size is, in total, 979 kB (= (12 + 22 + 32 + 42 ) ×
5112 /8) per user (i.e. 1.9 times as much as the conventional scheme). Since
the size of finger-vein data in the proposed scheme is 639 bytes per user (as44discussed in Section 4.6), the size of random permutation matrices (= 979kB) is relatively large. However, since the storage capacity of the HDD ismuch larger in recent years (e.g. more than terabytes) and is still increasing,we consider the storage requirements for the proposed scheme do not mattermuch in practice.
Finally, we note that Tams [22] showed that the binary fuzzy commitment
scheme with the bit-permutation randomization process is vulnerable to an
attack called the generalized decodability attack. To prevent this attack, Tams
[22] proposed to use a modification of the bit-permutation randomization
process to use a random bijection (instead of random permutation) in a nonbinary case, and to use the improved fuzzy vault scheme [1] in a binary case.
Similarly, the proposed scheme can also prevent this attack by using themodified randomization process or the improved fuzzy vault scheme.
7. Conclusions
In this paper, we proposed a framework for feature level sequential fusion,and a sequential fusion algorithm that minimizes the average number of inputs, which can be applied to multibiometric cryptosystems. We proved its
optimality under three assumptions (Theorem 1). We applied the proposed
scheme to the fuzzy commitment scheme, and showed its security (against
the FAR attack and the codeword search attack) and convenience throughexperiments using the finger-vein dataset that contains 6 fingers from 505
subjects (33298 finger-vein images in total). We also analyzed the security ofthe proposed scheme applied to the fuzzy commitment scheme against various attacks: attacks that exploit the relationship between multiple protected
templates (e.g. the partial codeword search attack, the partial feature searchattack), the soft-decoding attack [18, 19], the statistical attack [18, 20], andthe decodability attack [21, 22]. We believe these results significantly contribute to the secure and convenient public template model.
References[1] Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith, Fuzzy extractors: Howto generate strong keys from biometrics and other noisy data, SIAM J.
Comput. 38 (1) (2008) 97–139.

45

[2] A. Juels, M. Sudan, A fuzzy vault scheme, in: Proc. IEEE Int. Symposium on. International Symposium on Information Theory (ISIT’02),
2002.
[3] A. Juels, M. Wattenberg, A fuzzy commitment scheme, in: Proc. the 6th
ACM conference on Computer and communications security (CCS’99),
1999, pp. 28–36.
[4] U. Uludag, S. Pankanti, S. Prabhakar, A. Jain, Biometric cryptosystems:
Issues and challenges, Proc. IEEE 92 (6) (2004) 948–960.
[5] A. Ross, K. Nandakumar, A. K. Jain, Handbook of Multibiometrics,
Springer, 2006.
[6] E. Kelkboom, X. Zhou, J. Breebaat, R. Veldhuis, C. Busch, Multialgorithm fusion with template protection, in: Proc. IEEE 3rd International Conference on Biometrics: Theory, Applications, and Systems(BTAS’09), 2009, pp. 1–7.
[7] J. Merkle, T. A. M. Kevenaar, U. Korte, Multi-modal and multi-instancefusion for biometric cryptosystems, in: Proc. of the International Conference Biometrics Special Interest Group (BIOSIG’12), 2012.
[8] A. Nagar, K. Nandakumar, A. K. Jain, Multibiometric cryptosystems
based on feature-level fusion, IEEE Trans. Information Forensics andSecurity 7 (1) (2012) 255 – 268.
[9] C. Rathgeb, A. Uhl, P. Wild, Reliability-balanced feature level fusion
for fuzzy commitment scheme, in: Proc. IEEE/IAPR International Joint
Conference on Biometrics (IJCB’11), 2011, pp. 1–7.
[10] G. L. Marcialis, F. Roli, Serial fusion of fingerprint and face matchers,
in: Proc. the Seventh International Workshop on Multiple Classifiers
Systems (MCS’07), Vol. 4472 of Lecture Notes in Computer Science,
2007, pp. 151–160.
[11] R. M. Bolle, J. H. Connell, S. Pankanti, N. K. Ratha, A. W. Senior,
Guide to Biometrics, Springer, 2003.

46

[12] T. Murakami, K. Takahashi, Accuracy improvement with high convenience in biometric identification using multihypothesis sequential probability ratio test, in: Proc. the First IEEE International Workshop on
Information Forensics and Security (WIFS ’09), 2009, pp. 66–70.
[13] K. Takahashi, M. Mimura, Y. Isobe, Y. Seto, A secure and user-friendly
multimodal biometric system, in: Proc. SPIE, Vol. 5404, 2004, pp. 12–
19.
[14] C. J. Hill, Risk of masquerade arising from the storage of biometrics(2001).
URL http://www.enhyper.com/content/biometricmasquerading.
pdf[15] T. L. Lai, Asymptotic optimality of invariant sequential probability ratio
tests, Ann. Statist 9 (2) (1981) 318–333.
[16] A. Wald, Sequential Analysis, Wiley & Sons, New York, 1947.
[17] T. Yanagawa, S. Aoki, T. Ohyama, Diversity of human finger vein patterns and its application to personal identification, Bulletin of Informatics and Cybernetics 41 (2007) 1–9.
[18] A. Stoianov, T. Kevenaar, M. van der Veen, Security issues of biometricencryption, in: Proceedings of the 2009 IEEE Toronto International
Conference on Science and Technology for Humanity (TIC-STH’09),
2009, pp. 34–39.
[19] A. Stoianov, Security of error correcting code for biometric encryption,
in: Proceedings of the 8th Annual International Conference on Privacy
Security and Trust (PST’10), 2010, pp. 231–235.
[20] C. Rathgeb, A. Uhl, Statistical attack against fuzzy commitment
scheme, IET Biometrics 1 (2) (2012) 94–104.
[21] E. J. Kelkboom, J. Breebaart, T. A. Kevenaar, I. Buhan, R. N. Veldhuis, Preventing the decodability attack based cross-matching in a fuzzycommitment scheme, IEEE Transactions on Information Forensics andSecurity 6 (107–121).

47

[22] B. Tams, Decodability attack against the fuzzy commitment schemewith public feature transforms, CoRR abs/1406.1154.
URL http://arxiv.org/abs/1406.1154[23] A. K. Jain, K. Nandakumar, A. Nagar, Biometric template security,
EURASIP Journal on Advances in Signal Processing (2008) 1–17.
[24] J. Daugman, How iris recognition works, IEEE Trans. Circuits and Systems for Video Technology 14 (2004) 21–30.
[25] F. Hao, R. Anderson, J. Daugman, Combining crypto with biometrics
eﬀectively, IEEE Trans. Computers 55 (9) (2006) 1081–1088.
[26] A. Ross, R. Govindarajan, Feature level fusion using hand and facebiometrics, in: Proc. the SPIE Conference on Biometric Technology for
Human Identification, 2005, pp. 196–204.
[27] K. Nandakumar, A. K. Jain, A. Ross, Fusion in multibiometric identification systems: What about the missing data?, in: Proc. 3rd International Conference on Advances in Biometrics (ICB ’09), 2009, pp.
743–752.
[28] S. Ben-Yacoub, Y. Abdeljaoued, E. Mayoraz, Fusion of face and speech
data for person identity verification, IEEE Trans. Neural Networks 10 (5)(1999) 1065–1074.
[29] J. Kittler, M. Hatef, R. P. Dulin, J. Matas, On combining classifiers,
IEEE Trans. Pattern Analysis and Machine Intelligence 20 (3) (1998)
226–239.
[30] L. Lam, C. Y. Suen, Application of majority voting to pattern recognition: An analysis of its behavior and performance, IEEE Trans. Systems,
Man, and Cybernetics, Part A: Systems and Humans 27 (5) (1997) 553–
568.
[31] V. P. Dragalin, A. G. Tartakovsky, V. V. Veeravalli, Multihypothesis
sequential probability ratio tests, part I: Asymptotic optimality, IEEE
Trans. Information Theory (1999) 2448–2461.
[32] W. W. Peterson, E. J. Weldon, Error-Correcting Codes, MIT Press,
1972.
48

[33] D. J. MacKay, Information Theory, Inference and Learning Algorithms,
Cambridge University Press, 2003.
[34] X.-Y. Hu, M. P. Fossorier, E. Eleftheriou, On the computation of theminimum distance of low-density parity-check codes, in: Proceedings ofthe 2004 IEEE International Conference on Communications (ICC’04),
Vol. 2, 2004, pp. 767 – 771.
[35] Y. Yin, L. Liu, X. Sun, SDUMLA-HMT: a multimodal biometric
database, in: Proceedings of the 6th Chinese Conference on Biometric Recognition (CCBR’11), 2011, pp. 260–268.
[36] A. Kumar, Y. Zhou, Human identification using finger images, IEEE
Trans. Image Processing 21 (4) (2012) 2228–2244.
[37] N. Miura, A. Nagasaka, T. Miyatake, Feature extraction of finger-vein
patterns based on repeated line tracking and its application to personal
identification, Machine Vision and Applications 15 (2004) 194–203.
[38] P. J. Bickel, K. A. Doksum, Mathematical Statistics, Prentice Hall New
Jersey, 1976.
[39] J. Hanley, A. Lippman-Hand, If nothing goes wrong, is everything alright?, Journal of the American Medical Association 249 (1984) 1743–
1745.
[40] ISO/IEC 24745:2011: Information technology – security techniques –biometric information protection.

49