12. Kang, B.G., Park, J.H., Hahn, S.G.: A certi¬cate-based signature scheme. In:

Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 99“111. Springer, Hei-

delberg (2004)

13. Li, J., Huang, X., Mu, Y., Susilo, W., Wu, Q.: Certi¬cate-based signature: Security

model and e¬cient construction. In: L´pez, J., Samarati, P., Ferrer, J.L. (eds.)

o

EuroPKI 2007. LNCS, vol. 4582, pp. 110“125. Springer, Heidelberg (2007)

14. Liu, J., Au, M., Susilo, W.: Self-generated-certi¬cate public key cryptography and

certi¬cateless signature/encryption scheme in the standard model. In: ASIACCS

2007, pp. 273“283. ACM Press, New York (2007)

15. Liu, J., Baek, J., Susilo, W., Zhou, J.: Certi¬cate based signature schemes without

pairings or random oracles. In: ISC 2008. LNCS, vol. 5222. Springer, Heidelberg

(to appear, 2008)

16. Morillo, P., R`fols, C.: Certi¬cate-based encryption without random oracles (2006),

a

http://eprint.iacr.org/2006/012/

17. Shamir, A.: Identity-Based Cryptosystems and Signature Schemes. In: Blakely,

G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47“53. Springer,

Heidelberg (1985)

18. Yum, D.H., Lee, P.J.: Identity-based cryptography in public key management. In:

Katsikas, S.K., Gritzalis, S., L´pez, J. (eds.) EuroPKI 2004. LNCS, vol. 3093, pp.

o

71“84. Springer, Heidelberg (2004)

An Improved Robust Fuzzy Extractor

Bhavana Kanukurthi and Leonid Reyzin

Boston University Computer Science

111 Cummington St., Boston, MA 02215, USA

http://cs-people.bu.edu/bhavanak, http://www.cs.bu.edu/˜reyzin

Abstract. We consider the problem of building robust fuzzy extractors,

which allow two parties holding similar random variables W , W to agree

on a secret key R in the presence of an active adversary. Robust fuzzy

extractors were de¬ned by Dodis et al. in Crypto 2006 to be noninterac-

tive, i.e., only one message P , which can be modi¬ed by an unbounded

adversary, can pass from one party to the other. This allows them to be

used by a single party at di¬erent points in time (e.g., for key recovery

or biometric authentication), but also presents an additional challenge:

what if R is used, and thus possibly observed by the adversary, before

the adversary has a chance to modify P . Fuzzy extractors secure against

such a strong attack are called post-application robust.

We construct a fuzzy extractor with post-application robustness that

extracts a shared secret key of up to (2m’n)/2 bits (depending on error-

tolerance and security parameters), where n is the bit-length and m is

the entropy of W . The previously best known result, also of Dodis et al.,

extracted up to (2m ’ n)/3 bits (depending on the same parameters).

1 Introduction

Consider the following scenario. A user Charlie has a secret w that he wants to

use to encrypt and authenticate his hard drive. However, w is not a uniformly

random key; rather, it is a string with some amount of entropy from the point

of view of any adversary A. Naturally, Charlie uses an extractor [NZ96], which

is a tool for converting entropic strings into uniform ones. An extractor Ext is

an algorithm that takes the entropic string w and a uniformly random seed i,

and computes R = Ext(w; i) that is (almost) uniformly random even given i.

It may be problematic for Charlie to memorize or store the uniformly random

R (this is in contrast to w, which can be, for example, a long passphrase already

known to Charlie, his biometric, or a physical token, such as a physical one-way

function [PRTG02]). Rather, in order to decrypt the hard drive, Charlie can

use i again to recompute R = Ext(w; i). The advantage of storing i rather than

R is that i need not be secret, and thus can be written, for example, on an

unencrypted portion of the hard drive.

Even though the storage of i need not be secret, the authenticity of i is

very important. If A could modify i to i , then Charlie would extract some

related key R , and any guarantee on the integrity of the hard drive would

vanish, because typical encryption and authentication schemes do not provide

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 156“171, 2008.

c Springer-Verlag Berlin Heidelberg 2008

An Improved Robust Fuzzy Extractor 157

any security guarantees under related-key attacks. To authenticate i, Charlie

would need to use some secret key, but the only secret he has is w.

This brings us to the problem of building robust extractors: ones in which the

authenticity of the seed can be veri¬ed at reconstruction time. A robust extractor

has two procedures: a randomized Gen(w), which generates (R, P ) such that R

is uniform even given P (think of P as containing the seed i as well as some

authentication information), and Rep(w, P ), which reproduces R if P = P and

outputs ⊥ with high probability for an adversarially produced P = P .

Note that in the above scenario, the adversary A, before attempting to produce

P = P , gets to see the value P and how the value R is used for encryption and

authentication. Because we want robust fuzzy extractors to be secure for a wide

variety of applications, we do not wish to restrict how R is used and, therefore,

what information about R is available to A. Rather, we will require that A has

low probability of getting Rep(w, P ) to not output ⊥ even if A is given both P

and R. This strong notion of security is known as post-application robustness.

An additional challenge may be that the value w when Gen is run is slightly

di¬erent from the value w available when Rep is run: for example, the user may

make a typo in a long passphrase, or a biometric reading may di¬er slightly.

Extractors that can tolerate such di¬erences and still reproduce R exactly are

called fuzzy [DORS08]. Fuzzy extractors are obtained by adding error-correcting

information to P , to enable Rep to compensate for errors in w . The speci¬c

constructions depend on the kinds of errors that can occur (e.g., Hamming errors,

edit distance errors, etc.).

Robust (fuzzy) extractors are useful not only in the single-party setting de-

scribed above, but also in interactive settings, where two parties are trying to

derive a key from a shared (slightly di¬erent in the fuzzy case) secret w that

either is nonuniform or about which some limited information is known to the

adversary A. One party, Alice, can run Gen to obtain (R, P ) and send P to the

other party, Bob, who can run Rep to also obtain R. However, if A is actively

interfering with the channel between Alice and Bob and modifying P , it is impor-

tant to ensure that Bob detects the modi¬cation rather than derives a di¬erent

key R . Moreover, unless Alice can be sure that Bob truly received P before she

starts using R in a communication, post-application robustness is needed.

Prior Work. Fuzzy extractors, de¬ned in [DORS08], are essentially the non-

interactive variant of privacy ampli¬cation and information reconciliation proto-

cols, considered in multiple works, including [Wyn75, BBR88, Mau93, BBCM95].

Robust (fuzzy) extractors, de¬ned in [BDK+ 05, DKRS06], are the noninteractive

variant of privacy ampli¬cation (and information reconciliation) secure against

active adversaries [Mau97, MW97, Wol98, MW03, RW03, RW04].

Let the length of w be n and the entropy of w be m. Post-application robust

fuzzy extractors cannot extract anything out of w if m < n/2, because an extrac-

tor with post-application robustness implies an information-theoretically secure

message authentication code (MAC) with w as the key1 , which is impossible if

1

The MAC is obtained by extracting R, using it as a key to any standard information-

theoretic MAC (e.g., [WC81]), and sending P along with the tag to the veri¬er.

158 B. Kanukurthi and L. Reyzin

m < n/2 (see [DS02] for impossibility of deterministic MACs if m < n/2 and its

extension by [Wic08] to randomized MACs). Without any set-up assumptions,

the only previously known post-application robust extractor, due to [DKRS06],

extracts R of length 2 (m ’ n/2 ’ log 1 ) (or even less if R is required to be

3 δ

very close to uniform), where δ is the probability that the adversary violates ro-

bustness. Making it fuzzy further reduces the length of R by an amount related

to the error-tolerance. (With set-up assumptions, one can do much better: the

construction of [CDF+ 08] extracts almost the entire entropy m, reduced by an

amount related to security and, in the fuzzy case, to error-tolerance. However,

this construction assumes that a nonsecret uniformly random string is already

known to both parties, and that the distribution on w, including adversarial

knowledge about w, is independent of this string.)

Our Results. The robust extractor construction of [DKRS06] is parameterized

by a value v that can be decreased in order to obtain a longer R. In fact, as shown

in [DKRS06], a smaller v can be used for pre-application robustness (a weaker

security notion, in which A gets P but not R). We show in Theorem 2 that the

post-application-robustness analysis of [DKRS06] is essentially tight, and if v is

decreased, the construction becomes insecure.

Instead, in Section 3, we propose a new construction of an extractor with

post-application robustness that extracts R of length m ’ n/2 ’ log 1 , improving

δ

the previous result by a factor of 3/2 (more if R is required to be very close

to uniform). While this is only a constant-factor increase, in scenarios where

secret randomness is scarce it can make a crucial di¬erence. Like [DKRS06], we

make no additional set-up assumptions. Computationally, our construction is