<<

. 3
( 11 .)



>>

airport, for example, employs iris scan cards to
jected based on the matching score (veri¬cation).
speed up the passport and visa control procedures.
Alternately, the system may identify a user based
Passengers enrolled in this scheme insert their
on the matching scores (identi¬cation).
card at the gate and look into a camera; the cam-
In order to analyze the performance of a bio-
era acquires the image of the traveler™s eye and
metric system, the probability distribution of gen-
processes it to locate the iris, and computes the
uine and impostor matching scores is examined.
Iriscode; the computed Iriscode is compared with
A genuine matching score is obtained when two
the data residing in the card to complete user ver-
feature sets corresponding to the same individual
i¬cation. A similar scheme is also being used to
are compared, and an impostor matching score is
verify the identity of Schiphol airport employees
obtained when feature sets from two different in-
working in high-security areas. Thus, biometric
dividuals are compared. When a matching score
systems can be used to enhance user convenience
exceeds a certain threshold, the two feature sets
while improving security.
are declared to be from the same individual; oth-
A simple biometric system has four important
erwise, they are assumed to be from different in-
modules: (i) Sensor module which acquires the bio-
dividuals. Thus, there are two fundamental types
metric data of an individual. An example would be
of errors associated with a biometric system: (i)
a ¬ngerprint sensor that images the ¬ngerprint
a false accept, which occurs when an impostor
ridges of a user. (ii) Feature extraction module in
matching score exceeds the threshold, and (ii) a
which the acquired biometric data is processed to
false reject, which occurs when a genuine match-
extract a feature set that represents the data. For
ing score does not exceed the threshold. The error
example, the position and orientation of ridge bi-
rates of systems based on ¬ngerprint and iris are
furcations and ridge endings (known as minutiae
usually lower compared to those based on voice,
points) in a ¬ngerprint image are extracted in the
face, and hand geometry. A receiver operating
feature extraction module of a ¬ngerprint system.
characteristic (ROC) curve plots the false reject
(iii) Matching module in which the extracted fea-
rate (FRR”the percentage of genuine scores that
ture set is compared against that of the template
do not exceed the threshold) against the false ac-
by generating a matching score. For example, in
cept rate (FAR”the percentage of impostor scores
this module, the number of matching minutiae
that exceed the threshold) at various thresholds.
points between the acquired and template ¬nger-
The operating threshold employed by a system de-
print images is determined, and a matching score
pends on the nature of the application. In forensic
reported. (iv) Decision-making module in which
36 Birthday Paradox




Threshold
Genuine Distribution
Impostor Distribution

Forensic Applications
Probability




False Accept Rate (FAR)
Equal Error Rate (FAR = FRR)
Civilian
Applications High Security Access
Applications
Matching Score
False Reject Rate (FRR)
False Reject False Accept

(a) (b)
Fig. 3. Evaluating the matching accuracy of a biometric system: (a) histograms of genuine and impostor matching
scores and the two types of errors that are possible in a biometric system; (b) a receiver operating characteristic
curve indicating the operating point (threshold) for different kinds of applications

ranging from grocery stores to airports. The emer-
applications, for example, a low FRR is preferred,
gence of multimodal biometrics has further en-
while in high security access facilities like nuclear
hanced the matching performance of biometric
labs, a low FAR is desired (Figure 3). Besides FAR
systems [2]. It is only a matter of time before bio-
and FRR, other types of errors are also possible
metrics integrates itself into the very fabric of so-
in a biometric system. The failure to enroll (FTE)
ciety and impacts the way we conduct our daily
error refers to the inability of a biometric system
business.
to enroll an individual whose biometric trait may
not be of good quality (e.g., poor quality ¬ngerprint
Anil K. Jain
ridges). Similarly, a biometric system may be un-
Arun Ross
able to procure good quality biometric data from
an individual during authentication resulting in a
References
failure to acquire (FTA) error.
A biometric system is susceptible to various
types of attacks. For example, an impostor may [1] Jain, Anil K., Ruud Bolle, and Sharath Pankanti,
attempt to present a fake ¬nger or a face mask eds. (1999). Biometrics: Personal Identi¬cation in
Networked Society. Kluwer Academic Publishers,
or even a recorded voice sample in order to cir-
Dordrecht.
cumvent the system. The problem of fake biomet-
[2] Jain, Anil K. and Arun Ross (2004). “Multibiometric
rics may be mitigated by employing challenge-
systems.” Communications of the ACM, 47 (1), 34“
response mechanisms or conducting liveness
40.
detection tests. Most biometric systems currently
[3] Prabhakar, Salil, Sharath Pankanti, and Anil K.
deployed are used for local authentication, i.e., sel- Jain (2003). “Biometric recognition: Security and
dom is the biometric data acquired from a user privacy concerns.” IEEE Security and Privacy Mag-
transmitted across a network channel. This avoids azine, 1 (2), 33“42.
problems that would arise if a channel is compro- [4] Wayman, James L. (2001). “Fundamentals of bio-
mised. Privacy concerns related to the use of bio- metric authentication technologies.” International
metrics and protection of biometric templates are Journal of Image and Graphics, 1 (1), 93“113.
issues that are currently being studied [3].
The increased demand for reliable and conve-
nient authentication schemes, availability of in-
BIRTHDAY PARADOX
expensive computing resources, development of
cheap biometric sensors, and advancements in sig-
nal processing have all contributed to the rapid de- The birthday paradox refers to the fact that there
ployment of biometric systems in establishments is a probability of more than 50% that among
Blind signature 37


BLIND SIGNATURE
a group of at least 23 randomly selected peo-
ple at least 2 have the same birthday. It follows
from
In a blind signature scheme signers have indi-
365 365 ’ 1 365 ’ 22
· ··· ≈ 0.49 < 0.5; vidual private signing keys and distribute their
365 365 365 corresponding public verifying keys, just as in
normal cryptographic digital signature schemes.
it is called a paradox because the 23 is felt to be
Public verifying keys are distributed via authen-
unreasonably small compared to 365. Further, in
tication channels, for example, by means of public
general, it follows from
key infrastructures. There is also a publicly avail-
p’ i able verifying algorithm such that anyone who has
≈ 0.5
p
√ retrieved a public verifying key y of a signer can
0¤i¤1.18 p
verify whether a given signature s is valid for a
given message m with respect to the signer™s pub-
that it is not unreasonable to expect a duplicate

lic verifying key y.
after about p elements have been picked at ran-
In a blind signature scheme, the signers neither
dom (and with replacement) from a set of cardinal-
learn the messages they sign, nor the signatures
ity p. A good exposition of the probability analysis
the recipients obtain for their messages. A veri¬er
underlying the birthday paradox can be found in
who seeks a signature for a message m from a
Corman et al. [1], Section 5.4.
signer with verifying key y prepares some related
Under reasonable assumptions about their in-
message m and passes m to the signer. The signer
puts, common cryptographic k-bit hash functions
provides a response s back to the recipient, such
may be assumed to produce random, uniformly
that the recipient can derive a signature s from
distributed k-bit outputs. Thus one may expect
y, m, m , s such that s is valid for m with respect
that a set of the order of 2k/2 inputs contains two
to y. The resulting signature s is called a “blind
elements that hash to the same value. Such hash
signature,” although it is not the signature that is
function collisions have important cryptanalytic
blind, but the signer.
applications. Another prominent cryptanalytic ap-
The ¬rst constructions of cryptographic blind
plication of the birthday paradox is Pollard™s rho
signatures were proposed by David Chaum. These
factoring method (see integer factoring) where el-
early blind signature schemes were based on
ements are drawn from Z/nZ for some integer n
RSA signatures. An example is the Chaum Blind
to be factored. When taken modulo p for any un-
Signature [7, 8].
known p dividing n, the elements are assumed to
The security of blind signature schemes is de-
be uniformly distributed over Z/ pZ. A collision
¬ned by a degree of unforgeability and a degree
modulo p, and therefore possibly a factor of n,

of blindness. Of the notions of unforgeability (see
may be expected after drawing approximately p
forgery) for normal cryptographic signature
elements.
schemes de¬ned by Goldwasser et al. [16], only
Cryptanalytic applications of the birthday para-
unforgeability against total break and universal
dox where the underlying distributions are not
break apply to blind signature schemes. However,
uniform are the large prime variations of sieving
the notions of selective forgery and existential
based factoring methods. There, in the course of
forgery are inappropriate for blind signature
the data gathering step, data involving so-called
schemes, because they assume an active attack
large primes q is found with probability approxi-
to be successful if after the attack the recipient
mately inversely proportional to q. Data involving
has obtained a signature for a (new) message that
large primes is useless unless different data with
the signer has not signed before. Obviously, this
a matching large prime is found. The fact that
condition holds for every message a recipient gets
smaller large primes occur relatively frequently,
signed in a blind signature scheme, and therefore
combined with the birthday paradox, leads to
the de¬nition cannot discriminate attacks from
a large number of matches and a considerable
normal use of the scheme. For blind signatures,
speed-up of the factoring method.
one is interested in other notions of unforgeability,
Arjen K. Lenstra namely unforgeability against one-more forgery
and restrictiveness (see forgery), both of which are
mainly motivated by the use of blind signatures in
Reference
untraceble electronic cash.
A one-more-forgery [19] is an attack that for
[1] Cormen, Thomas L., Charles E. Leiserson, Ronald
some polynomially bounded integer n comes up
L. Rivest, and Clifford Stein (2001). Introduction to
with valid signatures for n + 1 pairwise different
Algorithms (2nd ed.). MIT Press, Cambridge, MA.
38 Blind signature


messages after the signer has provided signa- restricted (computational complexity). These are
tures only for n messages. Blind signatures un- formalizations of the intended property that the
forgeable against one-more forgery have attracted signer does not learn “anything” about the mes-
attention since Chaum et al. [10] and Chaum sage being signed.
[9] used them to build practical of¬‚ine and on- On a spectrum between keeping individuals ac-
line untraceable electronic cash schemes. Most countable and protecting their identities against
practical electronic cash schemes employ one- unduly propagation or misuse, blind signature
time blind signatures, where a customer can ob- schemes tend toward the latter extreme. In many
tain only one signed message from each inter- applications this strongly privacy oriented ap-
action with the bank during withdrawal of an proach is not acceptable in all circumstances.
electronic coin. This helps to avoid the problem While the identities of honest individuals are pro-
of counterfeiting electronic coins [3“6, 22]. For- tected in a perfect way, criminal dealings of in-
mal de¬nitions of one-time blind signatures have dividuals who exploit such systems to their own
been proposed by Franklin and Yung [15] and by advantage are protected just as perfectly. For ex-
Pointcheval [19]. ample, Naccache and van Solms [17] have de-
In a restrictive blind signature scheme, a re- scribed “perfect crimes” where a criminal black-
cipient who passes a message m to a signer (us- mails a customer to withdraw a certain amount of

<<

. 3
( 11 .)



>>