A Fuzzy Commitment Scheme
`
`Ari Juels
`
`Martin Wattenberg
`
`RSA Laboratories
`
`328 West 19th Street
`
`2D Crosby Drive
`Bedford, MA 01730
`E-mail: aricrsaxom
`
`Apt. ZC
`New York, New York 10011
`E-mail: waewitched.com
`
`Abstract
`
`We combine well~known techniques from the areas of error-
`correcting codes and cryptography to achieve a new type of
`cryptographic primitive that we refer to as a fuzzy commit
`ment scheme. Like a conventional cryptographic commit-
`ment scheme, our fuzzy commitment scheme is both can-
`cealing and binding:
`it is infeasibie for an attacker to learn
`the committed value, and also for the committer to de-
`commit a value in more than one way.
`In a conventional
`scheme, a commitment must be opened using a unique wit-
`ness, which acts, essentially, as a decryption key. By con‘
`trast, our scheme is fuzzy in the sense that it accepts a wit-
`ness that is close to the original encrypting witness in a
`suitable metric, but not necessarily identical.
`This characteristic of our fuzzy commitment scheme
`makes it useful for applications such as biometric authen-
`tication systems, in which data is subject to random noise.
`Because the scheme is tolerant of error, it is capable of pro-
`tecting biometric data just as conventional cryptographic
`techniques, like hash functions, are need to protect alphanu—
`meric passwords. This addresses a major outstanding prob-
`lem in the theory of biometric authentication. We prove the
`security characteristics of our fuzzy commitment scheme rel-
`ative to the properties of an underlying cryptographic hash
`function.
`
`1
`
`Introduction
`
`Cryptographic protocols are conventionally predicated on
`exact knowledge. An authentication system using BSA sig-
`natures, for example, derives its security largely from the
`presumption that a legitimate user with public key (N,e)
`possesses a corresponding secret key of the uniquely speci-
`fiable form (N, d). There are situations, however, in which
`human and other factors undermine the possibility of exact-
`ness in a security system. In biometric systems Where users
`identify themselves by means of fingerprint features, for ex-
`ample, variability in user interaction is such that a finger is
`rarely read exactly the same way twice. Moreover, even if
`knowledge in asystem is exact, its transmission may only be
`
`Fermisrnon to make digital or hard copies of all or part of this work lo:
`personal or classroom use is granted Without lee prowded that
`copies are not made or distributed for profit or commercial advant
`—ags and that copies bear this notice and the full Citation on the first page
`To copy otherWIse, to republish. to post on sewers or to
`redistribute to bats, requires prior specific permission aridlor a fee
`CCS ‘99 111'99 Singapore
`© 1999 ACM 1-58113-146-8/99I0010 55 00
`
`approximate. Users typically make typing errors, for exam-
`ple, when entering passwords on keyboards. Similarly, data
`transmission channels are often subject to random noise.
`Our aim in this paper is to describe a simple cryptographic
`primitive, namely a type of commitment scheme, that uses
`well-known algorithms to facilitate the use of approximate
`information in cryptographic systems. As a model for ap-
`proximate reasoning in humans, researchers in artifical in-
`telligence have elaborated a notion known as “fuzzy logic”
`[37]. By analog, we call the primitive introduced in this
`paper a fuzzy commitment scheme.
`In a conventional bit commitment scheme, one player,
`whom we denote the sender, aims to entrust a concealed
`bit I) to a second player, known as the receiver. The sender
`gives to the receiver an encryption y of b. A bit commit-
`ment scheme should be such that it is infeasible for the
`second player to learn the bit b from 3;. Additionally, the
`sender should later be able to “open” the commitment y,
`that is, to prove to the receiver that y indeed represents
`an encryption of b. It should only be feasible, however, for
`the sender to “open" 3: in one way, that is, to decrypt the
`value b uniquely. We may view this, intuitively, as a pro-
`cess whereby the sender places the bit b in a safe and gives
`the safe to the receiver. Only the sender can open the safe,
`since she alone knows the combination. Moreover, she Can-
`not change the value contained in the safe while it is in the
`keeping of the receiver.
`Formally, a bit commitment scheme consists of a function
`F : {0, 1} x X —> Y. To commit a bit b, the sender chooses a
`witness a: E X, generally uniformly at random. The sender
`then computes y = F(b,:z:). This value 3; is known as a
`blob. It represents the bit b sealed in a “safe”. To “open”
`or decommit the blob y, the sender produces the bit b and
`the witness 3:. The blob is successfully opened if the receiver
`has been convinced that y indeed represents an encryption
`of b.
`A bit commitment scheme is said to be concealing if it
`is infeasible for the receiver to guess b with probability sig-
`nificantly greater than 1/2. It is said to be binding if it is
`infeasible for the sender to decommit the blob y with the
`incorrect bit, that is, with 1 —-
`(1. Note that it is possiw
`ble to deploy a bit commitment scheme as a commitment
`scheme on an arbitrarily long string of bits by committing
`each bit independently. We shall use the term commitment
`scheme in this paper to refer to a scheme that involves com—
`mitment of a bit string c (or other potentially non-binary
`value) in a single blob, and for which it is possible to extract
`(3 efficiently given a witness for the blob. Thus we assume
`
`28
`
`Apple 1027
`Apple v. USR
`|PR2018—00810
`
`Apple 1027
`Apple v. USR
`IPR2018-00810
`
`

`

`F : C x X ~+ Y, where C is some potentially non-binary
`space. Additionally, our scheme will be such that produc-
`tion of a valid witness allows the committed value c to be
`efficiently determined from a commitment F(c, as). This is
`not the casein general for commitment schemes; often, both
`c and a valid witness are required to enable the sender to
`prove that F (c, n) represents a commitment of c. Finally, we
`offer a stronger notion of binding than that conventionally
`employed in the literature. We require not just the infeasi-
`bility of decommitting two distinct values c and c’ from a
`single commitment, but also that decommitment using two
`distinctly difierent witnesses be infeasible. This notion of
`strong binding is discussed in detail in Section 5. For fur-
`ther details on bit commitment, the reader may consult a
`standard cryptography textbook, such as [33], or one of the
`seminal papers on the subject, such as [12].
`Our aim in designing a fuzzy commitment scheme F is
`to achieve a new property that we loosely call “fuzziness”.
`By this, we mean that the commitment scheme should be
`resilient to small corruptions in witness values. More pre-
`cisely, we aim to allow a blob y :— F(b, z) to be opened using
`any witness x’ that is close to a: in some appropriate metric,
`such as Hamming distance, but not necessarily identical to
`2:. At first glance, the requirement for this type of resilience
`seems contradictory to the requirements that F be binding
`and concealing. After all, to achieve these two security aims,
`F must be an encryption function of sorts. It would there-
`fore seem necessary, in accordance conventional encryption
`or hash function design, for small changes in input values to
`yield large, unpredictable changes in output values. In other
`words, F should thoroughly and unpredictably “scramble”
`input bits. On the other hand, the requirement of fuzziness
`in F suggests exactly the opposite, namely a. high degree
`of local structure. In this paper, we show how to reconcile
`these ostensibly conflicting goals using well-known compo-
`nents drawn from error-correcting codes and cryptography.
`We combine a conventional hash function h with an error-
`correcting code used in a somewhat unorthodox way. Our
`construction is quite simple, and provably secure with re-
`spect to the underlying hash function h.
`
`1.1 Organization of this paper
`
`In Section 2, we give an overview of biometric authentica-
`tion and a. description of related work. We provide a brief
`introduction to error-correcting codes in Section 3. We de-
`scribe our fuzzy commitment construction in Section 4, and
`also discuss some applications to general security protocols.
`In Section 5, we state theorems regarding the security char-
`acteristics of our construction and analyze its resilience. We
`conclude in Section 6 with some suggestions for future areas
`of research. Short proofs of our theorems are provided in
`the appendix.
`
`2 Background
`
`2.1 Biometrics
`
`An important motivation for our investigation of fuzzy com-
`mitment is the problem of secure storage of data in biometric
`systems. We now give a brief overview of this area.
`Biometric authentication is the process of establishing
`the identity of an individual using measurements of some
`collection of his or her biological characteristics. Applied
`in its broadest sense, biometric authentication describes the
`
`processes that human beings use naturally to recognize one
`another, primarily through the senses of sight and hearing.
`When you recognize a friend by her face, you are performing
`a type of biometric authentication.
`Biometric authentication can also assume automated
`forms involving the identification of individuals to computer
`systems by such means as retinal and fingerprint scans.
`Until recently, biometric technologies have been the pre—
`serve of government agencies and science fiction movies, as
`in [2,
`ID, 27]. Recent improvements in on-chip scanning
`technologies as well as a proliferation of peripheral devices
`such as microphones and video cameras in desktop comput-
`ers have promised to bring automated biometric authenti-
`cation technologies to a consumer level in the near future
`{11, 19]. A plethora of relatively inexpensive biometric au-
`thentication techologies are now available,
`including ones
`based on fingerprint scanning, iris scanning, voice authenti-
`cation, face recognition — and even body odor. These tech-
`nologies promise to play a major role in a broad range of
`data security applications.
`Much of the appeal of biometric authentication is its
`promise of heightened security relative to passwords. As
`security specialists know Well, users often choose passwords
`poorly and write them down in conspicuous places, mak-
`ing them vulnerable to attack. Biometrics eliminate the
`problem of forgotten passwords and, according to industry
`claims, are largely resistant to remote capture.
`Biometrics, however, pose a security risk that passwords
`do not. In many operating systems, as in most implementa-
`tions of UNIX, a given password P is not stored explicitly
`in the system password file.
`Instead, a commitment of P
`is stored in the form of a hash h(P) [18, 26].1 (Note that
`this hash may be regarded as a commitment on a null value
`for which P is the witness.) Thus it is possible to verify
`that a user has entered her password correctly, while even a
`system administrator cannot feasibly extract a well-chosen
`password P from the password file entry MP). Protect-
`ing user secrets through a. straightforward means of com-
`mitment like hashing is not possible, though, for biometric
`authentication. The reason is this: two readings of the same
`biometric are rarely identical. Changes occur naturally in
`biological characteristics over time. Additionally, there is
`substantial variability in human execution of physical tasks.
`Because users are inconsistent in the position and pressure
`with which they apply their fingers to readers, for example,
`fingerprint reading devices almost always extract different
`information from multiple readings of the same finger - even
`when these readings occur in rapid succession.
`To handle the variability inherent in biometric authen-
`tication, most systems store for each user what is called a
`template. The template mg for user U consists of a biometric
`reading or set of readings obtained from U during an initial
`registration or enrollment process. When a user claiming to
`be U later authenticates herself, resulting in biometric read-
`ing m', a matching algorithm is invoked to compare 92' with
`my and determine whether the two belong to the same user.
`How much r’ must look like my to generate a match depends
`on the matching algorithm and its parameterization. The
`parameterization of a matching algorithm depends in turn
`on the false rejection and false acceptance rates desired in a
`given authentication system.
`Because of the resilience required for biometric authen-
`
`Jflashed passwords are typically also salted as a. defensive measure
`against dictionary attacks.
`
`29
`
`

`

`tication systems, templates are usually stored, unlike pass-
`words, in explicit form. Yet the protection of biometric in-
`formation is far more critical than that of passwords. It is
`easy to use separate passwords for different systems, and to
`change passwords on a frequent basis. Using multiple bio-
`metrics across systems and changing biometric passwords is
`harder. In a system employing fingerprints, for example, a
`user can change her “password" at most nine times. Addi-
`tionally, many users have serious concerns about the threat
`to privacy posed by compromised biometric information.
`These issues have been persistent points of contention in the
`development of biometric authentication systems [11, 19].
`
`2.2 Related Work
`
`The idea of fuzziness in commitment schemes perhaps first
`arises in the literature in connection with “collisionful” hash
`functions, intended for use in password protection.
`(Recall
`that the hash of a password may be viewed as a commit-
`ment.) “Collisionful” hash functions, introduced in [9], aim
`to discourage guessing attacks against passwords by means
`of a dense pro-image space. Gong [20] describes methods of
`carefully determining collision sets for this purpose, enabling
`the selection of multiple, plausible passwords (or witnesses)
`as preoimages for a given hash value. Other research in this
`area includes that of Bakhtiari et all. [3, 4, 5].
`As mentioned above, error-correcting codes play a cen—
`tral role in our fuzzy commitment construction. The ap-
`plication of error—correcting codes to cryptography has a
`long history. Error-correcting codes are particularly impor-
`tant in non-standard cryptographic models. They serve, for
`example, as a means of eliminating errors introduced by
`“dark counts” and other apparatus faults in quantum cryp
`tographic key distribution protocols (see, e.g., [6]). They
`are likewise a critical component in the implementation of
`oblivious transfer and key agreement protocols over both
`quantum [7, 14] and noisy channels (see, e.g., [13]).
`Error-correcting codes can also be employed in the con—
`struction of traditional cryptographic primitives.
`In [24],
`McEliece elaborates a well-known public-key cryptosystem
`whose hardness is based on the NP—hard problem of decod—
`ing an arbitrary linear code [8]. Researchers have also pro-
`posed identification [32] and digital signature Schemes [1]
`based on error-correcting codes, among other applications.
`In a recent paper [21], Jakobsen demonstrates that a class
`of error'correcting codes known as Reed-Solomon codes can
`even assist in the cryptanalysis of block ciphers.
`A notable feature of these efforts is their uSe of error-
`
`correcting codes to subserve conventional cryptographic
`goals.
`In an important divergence from this tradition,
`Davida, Frankel, and Matt [16] propose a synthesis of error-
`correcting codes with cryptographic techniques to achieve a
`new and somewhat unusual security goal. They describe a
`system in which a biometric template can be stored in non»
`explicit, protected form, but such that some corruption in
`subsequent readings can be tolerated. They achieve this by
`computing check bits on the template using a linear error-
`correcting code, and storing these check bits along with a
`hash of the template. Their construction offers important
`new ideas, and may in fact be regarded as a kind of fuzzy
`commitment. Their system does not have the necessary er-
`ror tolerance to work in many real-world applications. They
`require, for instance, that a. biometric scan be repeated many
`times in succession under the assumption that the errors in
`these scans will be wholly independent. Follow-up analysis
`
`of their work may be found in [17].
`Vendors of biometric systems have for some time recog-
`nized the importance of achieving a practical system along
`the lines of that proposed by Davida et at. To this end, the
`company Mytec Technologies has developed a related tech-
`nology, consisting of an encryption process in which biomet-
`ric data serves as an unlocking key. Sold under the brand
`name BioscryptT”, this technology overcomes the problem
`of biometric data corruption by means of Fourier transforms.
`While fairly efiicient, however, it carries no rigorous security
`guarantees (see, e.g., [30, 31]).
`Our work on fuzzy commitment may be regarded as an
`improvement on and generalization of that of Davida at
`al. As mentioned above, their scheme involves the exten-
`sion of a biometric template into an emr-correcting code—
`word through the addition of check bits. (See Section 3 for
`the definition of a codeword.)
`In contrast, our fuzzy com-
`mitment scheme, as applied to biometric templates, treats
`the template itself without any modification as a corrupted
`codeword. This diflerence in perspective yields several ad-
`vantages. Most importantly, our construction links the num-
`ber of codewords to the security parameter, while that of
`Davida et al. links it to the significantly larger message (i.e.,
`template) size. in consequence, our construction use: much
`smaller error-correcting codes than that of Davida et al. and
`achieves significantly higher resilience. Our fuzzy commit-
`ment construction thereby promises to bring the idea of se-
`cure biometric template storage farther into the realm of
`practical application.
`
`3 Error-Correcting Codes
`
`To provide background for the fuzzy commmitment con-
`struction presented in the next section, we now give a brief
`overview of error-correcting codes. The goal of an error-
`correcting code is to enable transmission of a message m
`intact over a noisy communication channel. This is accom-
`plished by mapping in to a longer string 6 prior to transmis-
`sion. The string c is constructed so as to contain redundant
`elements. Therefore, even if some of the bits of this string
`are corrupted by noise, it remains possible for a receiver to
`reconstruct c, and consequently the message m.
`More formally, an error-correcting code consists of a set
`C Q {0, 1}” of codewords. This set contains the strings to
`which messages are mapped prior to transmission. Hence,
`in a code for use with k-bit messages, 0 contains 2" dis-
`tinct elements. To achieve redundancy, it is a requirement
`that n > k. Error-correcting codes may of course be easily
`defined on non-binary spaces as well, and our constructions
`are straightforwardly extensible to such spaces.
`To use an error-correcting code, We require functions for
`encoding and decoding of messages. Let M = {0,1}" rep-
`resent the space of messages. The function g : M —> C,
`which we calla translation function, represents a one-to~one
`mapping of messages to codewords. In other words, 9 is the
`mapping used prior to message transmission.
`(Conversely,
`g‘
`is used upon message receipt to retrieve the transmit-
`ted message from a reconstructed codeword.) The function
`f : {0,1}“ —v CU{¢}, known as a decoding function,
`is
`used to map arbitrary n-bit strings to codewords. When
`successful, 1‘ maps a given n—bit string a: to the nearest Code-
`word in C (i.e., nearest in terms of Hamming distance).2
`
`2The task of mapping an arbitrary string to its nearest codeword
`is known as the maximum lakel-ihaod decod-mg problem. Practical
`
`30
`
`

`

`Otherwise, 1’ fails, and outputs (as
`The robustness of an error-correcting code depends upon
`the minimum distance between codewords. To make this
`idea precise, we require some basic notation regarding
`strings of binary digits. Let the symbol + (and equiva-
`lently, the symbol —) denote the bitwise XOR operator on
`bitstrings. (In this context, the symbols + and -— are more
`intuitively appealing than 63-) The Hamming weight of an
`n-bit string 11., denoted by i! u 1|, is defined to be the number
`of ‘1’ bits in n. The Hamming distance between two bit—
`strings u and o is likewise defined to be the number of digits
`in which the two strings differ. Equivalently, the Hamming
`distance is equal to I] u. — 11 ll.
`We say that a decoding function f has a correction
`threshold of size 13 if it can correct any set of up to t bit
`errors. More precisely, for any codeword c e C and any
`error term 6 6 {0,1}" with H e I] S t, it is the case that
`f(c+ e) = c. We say that a code C has a. correction thresh-
`old of size t if there exists a decoding function f for C that
`has correction threshold t. Observe that the distance be-
`tween any two codewords in 0 must be at least 2t + 1. We
`define the neighborhood of a codeword c to be f‘1(c).
`In
`other words, the neighborhood of c consists of a subset of
`the 72-bit strings that f maps to c. The decoding function
`f is generally such that any codeword in f‘1(c) is closer to
`c than to any other codeword.
`
`Example 1 Let n = 3,}: = 1, and C' = {000,111}. Let
`the decoding function f compute majority,
`i.e., f maps a
`bitstring :c 6 {0,1}3 to 000 If at least two bits of a: are Us
`and to 111 if of. least two bits are ls. This decoding function
`has t = 1. In other words, f can correct a single error, since
`changing a single digit in either 000 or 111 does not change
`the majority.
`
`The ratio left: in an error-correcting code is known as its
`coding ejfimency, and measures the degree of redundancy in
`the code. (The lower the coding efficiency, the more redun-
`dancy in the codewords.) The {000, 111} code, for instance,
`has a. coding efiiciency of 1/3.
`In general, codes that can
`correct a large number of errors must have a low coding
`efficiency.
`Further details on error-correcting codes are available in
`any of a number of textbooks on the topic, such as, e.g.,
`[23, 28, 36].
`
`3.1 How we use error-correcting codes
`
`As explained above, an error-correcting code traditionally
`involves changing a message to a codeword before transmit-
`ting it across a noisy channel. In some situations, however,
`this initial encoding step is impossible because the message
`cannot be modified. For instance, in the case of biometric
`identification the noisy channel might be an error-prone fin-
`gerprint reading machine, and the “message” might be an
`actual fingertip. Thus, we do not have the ability to add re-
`dundancy to the “message”. Because this constraint arises
`classes of codes with polynomial—time solutions to this broad prob—
`lem are at present unknown. Conventional decoding functions per-
`form a more limited task: they successfully decode any word that lies
`Within a certain radius of some codeword. This is all that our fuzzy
`commmitment algorithm requires.
`3Error correcting codes may work somewhat differently. For ex—
`ample, wnth use of list decoding, f may yield a set of candidate code-
`words, rather than a single correct one. The underlying principles in
`our construction remain the same in such settings.
`
`in our use of fuzzy commitment, we treat a witness (e.g.,
`biometric template) as a corrupted codeword, rather than
`a message. In consequence, our construction does not map
`messages from the space M to the set of codewords. In fact,
`we do not make use of M at all. Rather, we make use of
`only half of an error-correcting code: we use the decoding
`function 1', but not really the translation function g. This
`use of error»correcting codes is somewhat unorthodox.
`It
`represents the novel element in our construction.
`The commonest class of error-correcting codes consists of
`what are known as linear codes. These are codes whose set of
`codewords, in the binary case, forms a vector space over the
`field with two elements. Almost all of the error-correcting
`codes used in practice are linear. Although not strictly nec-
`essary, it is for several reasons convenient to choose a linear
`code for our construction. For example, one property of lin-
`ear codes useful in a number of applications of our fuzzy
`commitment construction, as we shall see, is that it is very
`easy to select a codeword c uniformly at random from C.
`
`4 Construction of our fuzzy commitment scheme
`
`4.1
`
`Intuition
`
`Let us now describe the construction of our fuzzy commit-
`ment scheme F. We shall construct F so as to commit a
`codeword c using a witness cc, where both c and :r. are n-bit
`strings.
`Observe that an n-bit witness :r; can be uniquely ex-
`pressed in terms of the codeword (committed value) c along
`with an offset 5 s {0,1}" such that :c = 6+ 6. Given a.
`witness 2: expressed in this way, the idea behind the fuzzy
`commitment function F is to conceal c using a conventional
`hash function )2, while leaving 6 in the clear. The infor-
`mation 5 provides resilence in the witness required to open
`F. In particular, 5 provides some partial information about
`2:. On the other hand, the remaining information needed to
`specify 3, namely the codeword c, is presented in a concealed
`form as h(c).
`Recall that we define ICl = 2". The amount of infor-
`mation contained in the codeword c, and thus the amount
`of information about the witness a: concealed in Me) de-
`pends on k, that is, on the number of codewords in G. The
`greater the number of codewords, the greater the amount of
`information about the witness a: that is concealed in Me).
`In contrast, the amount of information in 6 determines the
`level of resilience in F. If we are presented with a witness a."
`that is near 1:, we can use 5 to translate .r' in the direction
`of :c, facilitating our recovery of the committed codeword c.
`As we shall see, we achieve a tradeoff between resilience and
`security by varying in, and thus the relative distribution of
`information between 5 and h(c).
`In biometric scenarios, :1: will typically represent a bio-
`metric template, such as a fingerprint. The codeword c will
`represent a secret key protected under this template. For
`example, c might be a decryption key protected under the
`user’s fingerprint a: as the commitment F{c, as). In order to
`unlock and reveal this key, it suffices for the user to present
`a corrupted fingerprint image 92’ sufficiently close to a. Note
`that in some scenarios where is not necessary to protect c
`itself, the codeword c must still be drawn from a large space
`C, in order to conceal the witness cc. Consider, for example,
`a straightforward fingerprint authentication scenario meant
`to model the use of hashed passwords on UNIX systems (and
`presented as the “fuzzy authentication” protocol in Section
`
`31
`
`

`

`4.3). Here, F(c, (1;) is stored on a server. In order to demon-
`strate her identity, it suffices for the user simply to present
`to the server a fingerprint image that succesfully decommits
`F(c, 2:). The committed value c does not serve in this exam—
`ple as a cryptographic key. Nonetheless, c must be drawn
`from a large enough space 0 to ensure that F(c, 3:) does not
`reveal a. If iCl (or, equivalently k) is small, then an attacker
`can guess c and extract a from F(c, s).
`It is helpful to describe these ideas in terms of a geo—
`metric analogy. Let C be the set of points on the lattice
`{100a, 1001:} for integer values it and 1). Let us think of the
`witness a: as a point on the Euclidian plane, say, (745, 260).
`Let the decoding function 1' map a given point to the nearest
`lattice point in C. E.g., f(120, 94) = (100, 100]. Suppose
`we choose an arbitrary lattice point, say, c = (300, 300). We
`can express a: in the form a: = 0+6 by letting 6 = (445, —40).
`Suppose now that without knowing the codeword c, we
`are given the blob y = (h(c),5).
`(This 31, as we shall see,
`is exactly the fuzzy commitment of c.) Observe that 6 tells
`us the position of :2; relatiVe to c, but gives us no infor—
`mation about what 0 is. Thus, assuming that h is a se-
`cure one-way function, the only information that y effec-
`tively reveals about the witness a: is that it takes the form
`(1001! +45, 1001)’ + 60) for some integers u’ and '0'. Subject
`to this constraint, :1: could otherwise lie anywhere in plane.
`Suppose we are now presented with some point :c' that
`is close to at, say if = (720, 240). By subtracting 5, we
`translate I’ to the region near the codeword c. In particular,
`32’ — 6 = (275, 280). By applying the decoding function f to
`this last point, we obtain f (:c’ — J) = c. Thus, knowledge of
`35' and use of the decoding function I enable us to determine
`a: from the blob y and decommit c.
`Say that 3: Were the fingerprint template of a user. Then
`an attacker with knowledge of 3; alone would be unable to
`find a witness to decommit c. On the other hand, as demon-
`strated above, if the user were to present her finger to a read
`ing device, generating read data :I' , then it would be possible
`to extract c from y. It is easy to see, in consequence, that
`knowledge of ,1; makes it possible to verify that 91’ is close to
`m, and thus to authenticate the user. In loose terms, rc’ may
`be viewed as a fuzzy representation of the original witness
`.11. Let us proceed to make this intuition more precise.
`
`4.2 Construction of F
`
`Our construction for F is now quite straightforward. Let
`h : {0, 1}" —-» {0, 1}: be a hash (or one-way) function such as,
`e.g., SHA-l. We now formally define F : ({O, 1}", {0, 1}“) -—»
`({0, 1}z, {0, 1}") as follows:
`
`F(c,:c) = (h(c), a — c).
`
`To decommit F(c,m) = (0,5) using witness :c’, the re-
`ceiver computes c' = f(s’—5) = f(c+(:c’-:r)). Ifo: = h(c’),
`then the blob has been successfully decommitted, with c'
`representing the extracted commitment. Otherwise, :r' is an
`incorrect witness. Provided f is an efficient decoding func-
`tion (which is the case, of course, for codes used in prac-
`tice), then decommitment is likewise an efficient process. In
`the remainder of the paper, we shall denote the entire com-
`mitment scheme, both the commitment and decommitment
`processes, informally by F.
`Recall that the “fuzziness” of 1“ consists of the notion
`that if :c’ is close to m, then 32’ can be used to decommit
`
`F(c,a:). This notion formalized in the following lemma,
`whose proof is given in the appendix. Note that the con-
`verse does not necessarily hold.
`
`Lemma 1 Suppose that H a: — z’ |i _<_ t. Then for any c, the
`witness :1." can be used to decommit F(c,m) successfully.
`I
`
`4.3 Applications of the fuzzy commitment function F
`
`To provide a flavor of how fuzzy commitment might be de-
`ployed in a biometric system, We now sketch how F can be
`used to achieve three different security goals, namely static
`(or off-line) authentication, challenge-response authentica-
`tion, and encryption/decryption. We assume that a user
`presents a secret :1: in an enrollment (or encryption) phase
`and in any given subsequent interaction presents some :c'
`that, if legitimate, differs from a: by at most the correction
`threshold t.
`In a biometric system, once again, 3: might
`be the fingerprint template presented by the user in an en-
`rollment phase.
`In this case, 31' is fingerprint information
`presented for authentication at the initiation of a login ses-
`sion. We use 63 in what follows to denote uniform random
`selection from a. set.
`In all three protocols, the basic idea is the same. The wit-
`ness 9: is used to commit to a secret codeword c. Presenta~
`tion of a witness :2:' close to 2: opens this secret c, which may
`then be used to achieve the desired security goal, be it en-
`cryption, decryption, or authentication. Note as mentioned
`above, however, that in the first authentication protocol, the
`committed value c does not play a direct role as a crypto-
`graphic key.
`It must nonetheless be selected from a large
`space 0 in order to ensure that .1: remains well concealed, as
`well as to achieve a sufiiciently high level of security in the
`authentication scheme.
`
`Fuzzy authentication Let 5' denote the authentication en-
`tity, such as a server verifying biometric data to control re-
`source access. Let U denote the user. Our protocol is as
`follows.
`
`I Enrollment The user U presents biometric data 3:.
`The system S selects a codeword c an C. Then S com-
`putes the fuzzy Commitment ya = F(c, 2:), and stores
`it in a file for user U. Alternatively, for off-line applica-
`tions, it is possible to store up and a digital signature
`of S on ya in, say, a smart card.
`
`0 Authentication A user purporting to be U presents a
`value :z’ for authentication. S looks up ya and checks
`whether the witness m' yields a successful decommit-
`ment. If so, the user is authenticated as U; otherwise,
`the authentication fails. The authentication may, al—
`ternatively, take place off—line in some trusted module.
`
`Note that the l