Jean-Paul Linnartz and Pim Tuyls

WY7, Nat.Lab., Philips Research, 5656 AA Eindhoven, The Netherlands

Measurement of distinguishing features of physical objects and living beings can be used to identify these and distinguish them from others. In some cases, there is a desire to add cryptographic properties to this identification process. In biometrics, a human being is identified by measuring a set of parameters of the body. Biometric data are said to identify a person based on "who he is", rather than on "what he has" (such as a smartcard) or "what he knows" (such as a password). An unresolved issue, however, is that when deployed at large scale, a citizen looses privacy as he must reveal his identifying biometric data to his bank, to the government, to his employer, the car rental company, to the owner of a discotheque or nightclub, etc. Each of them will obtain the same measured data, and unless special precautions are taken there is no guarantee that none of these parties will ever misuse the biometric data to impersonate the citizen.

This paper proposes, reviews and analyzes a novel technique to enhance the privacy and security of authentication and key establishment in biometric applications. In particular, we prevent misuse of templates. Following the tradition in cryptography to name our role players, we will say that prover Peggy allows verifier Victor to measure her object [1] or physiological parameters [2] called "Prop." We are not only interested in security breaches due to a dishonest Peggy, but also in those resulting from an unreliable Victor.

Often the distinction is made between identification and verification. Identification estimates which object is presented by searching for a match in a data base of reference data for many objects. Victor a priori does not know whether he sees Prop1 (belonging to Peggy) or Prop2 (belonging to Petra). On the other hand, verification attempts to establish whether the object presented truly is the object Prop that a known prover Peggy claims it to be. Peggy provides not only Prop but also a message in which she claims to be Peggy and can be linked to Prop, in some direct or implicit way. Here, we address primarily the setting of verification, that is, Victor is assumed to have some a priori knowledge about Prop in the form of certified reference data, but at the start of the protocol he is not yet sure whether Prop or a fake replacement is present.

To further develop the insight in the security aspects of verification, we distinguish (possibly against common practice in biometric literature) between verification and authentication. In a typical verification situation, the reference data itself allows a malicious Victor to artificially construct measurement data that will pass the verification test, even if Prop itself has never been available. In authentication, the reference data gives insufficient information to allow Victor to (effectively) construct valid measurement data.

While such protection is not yet mature for biometric authentication, it is common practice with computer passwords. When a computer verifies a password, it does not compare the password p typed by the user with a stored reference copy. In stead the password is processed by a cryptographic one-way function F and the outcome is compared against a locally stored reference string F(p) [3]. This prevents that the system can be attacked from the inside such that the unencrypted or decryptable password of its users can be stolen.

The main difference with biometrics is that during measurements it is unavoidable that noise or other aberrations occur. Noisy measurement data will be quantized into discrete values before these can be processed by any cryptographic function. Due to external noise, the outcome of the quantization may differ from experiment to experiment. In particular if Peggy's physiological parameter takes on a value close to a quantization threshold, minor amounts of noise can change the outcome. Minor changes at the input of a cryptographic function will be amplified and the outcome will bear no resemblance to the expected outcome. This effect, identified as 'confusion' and 'diffusion' [3], makes it less trivial to use biometric data as input to a cryptographic function. Particularly the comparison of measured data with reference data can not be executed in the encrypted domain.

It is an essential part of this paper to discuss whether the measurement must be stored itself or it suffices to store and exchange only a (one-way) cryptographic derivative. Storage of reference data (user templates) and protecting their privacy is well recognized as a key concern with biometric authentication [4,15]. Preferably the derivative should not allow an attacker to construct fake data. It was previously known that enrollment data can be encrypted. However, a security weakness appears when during authentication the data needs to be decrypted. This problem was also addressed in [6, 7, 9, 10]. In the current paper we further develop and generalize the mathematical formulation, including an information theoretic evaluation of concealing properties and we analyze a new solution.Before an authentication can take place, Prop must have gone through an enrollment phase. During this phase, Peggy and Prop visit a Certification Authority. Prop's parameters are measured. These measurements are processed and stored for later use. In an on-line application, such reference data can be stored in a central (possibly even publicly accessible) data base or these data can be certified with a digital signature of the Certification Authority, and given to Peggy. In the latter case, it is Peggy' responsibility to securely give this certified reference data to Victor.

Key establishment: In addition to authentication, the system can use Prop's (biometric) parameters to generate a secret key [11, 12]. An important property is that Victor should not be able to calculate this key on his own, by misusing reference data that is offered to him. Victor must measure Prop, otherwise he should not be able to find the key.

We illustrate this by the example of access to a data base of highly confidential encrypted documents to which only a (set of) specific users is allowed access. The computer retrieval system authenticates humans and retrieves an\ decryption key from their biometric parameters. This system must be protected against a dishonest software programmer Mallory who has access to the biometric reference data from all users. If Mallory downloads the complete reference data file, all encrypted documents, and possibly reads all the software code of the system, she should not be able to decrypt any document.

We distinguish between to attacks

1. Misuse of templates: a dishonest Victor can attempt to calculate the parameters of Prop or to establish the key without having access to the object. This corresponds to a system operator who attempts to retrieve user passwords from the reference database of data strings F(p).
2. Misuse of measurement data: After having had an opportunity to measure Prop, a dishonest Victor misuses its measurement data. This corresponds to grabbing all keystrokes including the plain passwords typed by a user.

This text primarily addresses attack 1. Attack 2 typically is prevented by mutual cryptographic authentication of Victor and Peggy in addition to the biometric exchange of data from Prop [14].

In order to study countermeasures against misuse of templates, we consider the system depicted in Figure 1. This authentication system consists of a mechanism to extract a measurement Y of the object, some signal processing function G(W,Y) and a cryptographic function F. F is one-way in the sense that it is "easy" to calculate the output given the input signal but it is computationally "infeasible" to find a valid input given an output value [4]. An important aim is to propose and study appropriate choices for G to enhance the reliability and reproducibility of the detection and to shield the information (or 'entropy') in the authentication secret Z from the reference data. The reference data consists of two parts: the cryptographic key value V against which the processed measurement data U is compared, and the data W which assists in achieving reliable detection.

Peggy authenticates herself with Prop as follows:

• When she claims to be Peggy, she sends her identifier message to Victor, and makes Prop available for measurement.
• Victor retrieves the authentication challenge W from an on-line trusted database. Alternatively, in an off-line application Peggy could provide Victor with reference data (V,W) together with a certificate that this data is correct.
• Peggy allows Victor to take a (possibly noisy) measurement Y = X + N of the physiological properties X of Prop
• Victor calculates Z = G(W,Y).
• Optional for key establishment: Victor can extract further cryptographic keys from Z, for instance to generate an access key.
• Victor calculates the cryptographic hash function F(Z).
• The output U = F(Z) is compared with reference authentication response V. If U = V, the authentication is successful.

Here, X, N, and Y are real (or complex) valued vectors of length n₁, X Î Rⁿ1. Vector W contains n₂ values, typically real, complex or high resolution digital numbers, that control the function G(W,X). Further, Z, U and V are discrete-valued (typically binary) vectors of length n₃, n₄, and n₄, resp. During authentication, Z is the estimate of the authentication secret S that was chosen during enrollment, which we will describe next.

Definition 2: Let G(W,X): R ^{n1 + n2 ®} {0,1}ⁿ3 be a function. The function G called "versatile " if and only if for all S Î {0,1}ⁿ³ and all X Î Rⁿ¹, there exists (an efficient algorithm to find) at least one vector W Î Rⁿ² such that G(W,Y) = S.

A trivial ¥ -contracting function is G(W,X) = Constant. However this function is not versatile. The property of versatility is relevant particularly for key establishment. A trivial versatile and ¥ -contracting function is G(W,X) = C(W). However, in this solution W reveals the secret S, or at least, the conditional entropy H(S|W) = 0

Corrolary: The desirable property that biometric data can be verified in the encrypted domain cannot be achieved unless Prop-specific data W is used. Biometric authentication that attempts to process Y without such "helper" data is doomed to store decryptable user templates.

Hence W conceals S: it reveals only a well-defined, small amount of information about S. Similarly, we require that V conceals S. However we do not interpret this in the information theoretic sense but in the complexity theoretic sense, i.e., the computational effort to obtain a reasonable estimate of (X or) S from V is prohibitively large, even though in the information theoretic sense V may (uniquely) define S.

where n= .., -1, 0, 1, 2, ... is chosen such that -q < w_i < q. The value of n is discarded, but the values of w are released as helper data.

where Q(x) is the integral over the Guassian pdf with unity variance. In a practical situation, if one can apply error correction decoding to further reduce the error rate, compared to Figure 3.

Figure 4 plots q * f(w/q) as a function of w/q. The solid lines depict f_W(w|s=0) and the crosses depict f_W(w|s=1). Information leaks whenever f_W(w|s=1) ¹ f_W(w|s=1). The symmetry properties f_W(w|s) = f_W(q- w|s) and f_W(w|s=1) = f_W(-w|s=0) apply. f_W(w|s=1) has a maximum for w = q/2, which corresponds to highly likely values of x near x = 0. The unconditional probability density of W follows from f_W(w) = f_W(w|s=1) P(s=1) + f_W(w|s=0) P(s=0)+. Despite the suggestion by Figure 4, it is neither true that that f_W(w|s=1) = 1 - f_W(-w|s=1) nor that f_W(w) is constant.

Using Bayes rule, the a posteriori probability p_w1 on s = 1 can be expressed as

Similarly, we define p_w0. Then, the mutual information I(W;S) follows from:

Expanding the logarithm into separate terms, i.e., applying the rule log(a/b) = log a - log b), we get

Or simply,