{'fraction_non_alphanumeric': 0.04392279430100913, 'fraction_numerical': 0.010407142025901482, 'mean_word_length': 4.154854743337047, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 37, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reusable Fuzzy Extractors for Low-Entropy Distributions

Fuzzy extractors (Dodis et al., in Advances in cryptology—EUROCRYPT 2014, Springer, Berlin, 2014, pp 93–110) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, in Proceedings of the 11th ACM conference on computer and communications security, CCS, ACM, New York, 2004, pp 82–91) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations). We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated. The extractor works for binary strings with Hamming noise; it achieves computational security under the existence of digital lockers (Canetti and Dakdouk, in Advances in cryptology—EUROCRYPT 2008, Springer, Berlin, 2008, pp 489–508). It is simple and tolerates near-linear error rates. Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates—lower than those supported by prior (nonreusable) constructions—assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. Structure beyond entropy is necessary to support distributions with low entropy rates. We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, building a computationally secure and an information-theoretically secure construction for large-alphabet sources.


Introduction
Long-term secrets enable cryptographic key derivation and authentication. However, many sources with sufficient randomness to form long-term secrets provide similar but not identical values of the secret at repeated readings. Prominent examples include biometrics and other human-generated data [14,23,28,50,51,69], physically unclonable functions (PUFs) [34,56,58,63], and quantum information [6]. Turning similar readings into identical values is known as information reconciliation; further converting those values into uniformly random secret strings is known as privacy amplification [6]. Both of these problems have interactive and non-interactive versions. In this paper, we consider the non-interactive case, which is useful for a single user trying to produce the same key from multiple noisy readings of a secret at different times. A fuzzy extractor [26] accomplishes both information reconciliation and privacy amplification non-interactively.
Fuzzy extractors consist of a pair of algorithms: Gen (used once, at "enrollment") takes a source value w, and produces a key r and a public helper value p. The second algorithm Rep (used subsequently) takes this helper value p and a close w to reproduce the original key r . The standard correctness guarantee is that r will be correctly reproduced by Rep as long as w is no farther than t from w according to some notion of distance (specifically, we work with Hamming distance; our primary focus is on binary strings, although we also consider larger alphabets). The security guarantee is that r produced by Gen is indistinguishable from uniform, even given p. In this work, we consider computational indistinguishability [29] rather than the traditional information-theoretic notion.
Reusability A fuzzy extractor is reusable (Boyen [12]) if it remains secure even when a user enrolls the same or correlated values multiple times. For example, if the source is a biometric reading, the user may enroll the same biometric with different noncooperating organizations. Reusability is particularly important for biometrics which cannot be changed or created. It is also useful in other contexts, for example, to permit a user to reuse the same visual password across many services or to make a single physical token (embodying a PUF) usable for many applications.
Each enrollment process will get a slightly different enrollment reading w i , and will run Gen(w i ) to get a key r i and a helper value p i . Security for each r i should hold even when an adversary is given all the values p 1 , . . . , p ρ and even the keys r j for j = i (because one organization cannot be sure how other organizations will use the derived keys).
Dodis et al. [25,Section 6] noted that reusable extractors for the nonfuzzy case (i.e., without p and Rep) can be constructed using leakage-resilient cryptography. However, adding error-tolerance makes the problem harder. Most constructions of fuzzy extractors are not reusable [4,5,12,61]. In fact, the only prior construction of reusable fuzzy extractors [12] required very particular relationships between w i values, which are unlikely to hold for a practical source. We review definitional considerations for reusable fuzzy extractors in Sect. 3. 1

Our Contribution
Sample-then-Lock We construct the first reusable fuzzy extractor, called sample-thenlock, whose security holds even if the multiple readings w i used in Gen are arbitrarily correlated, as long as the fuzzy extractor is secure for each w i individually. Our construction is based on digital lockers. 2 Our construction handles a wide class of sources. It is secure if for some known parameter k, the substring formed by the bits at k randomly chosen positions in w is unguessable (i.e., has minentropy that is superlogarithmic is the security parameter). We call sources with this feature "sources with high-entropy samples." This requirement is in contrast to most constructions of fuzzy extractors that require w to have sufficient minentropy.
All sources of sufficient minentropy have high-entropy samples (because sampling preserves the entropy rate [64]). However, as we now explain, the family of sources with high-entropy samples also includes some low-entropy sources. (Note that, of course, the entropy of a substring never exceeds the entropy of the entire string; the terms "high" and "low" are relative to the length.) Such sources arise naturally whenever w exhibits a lot of redundancy. For example, when the binary string w is obtained via signal processing from some underlying reading (such as an image of an iris or an audio recording of a voice), the signal itself is likely to have a lot of redundancy (for example, nearby pixels of an image are highly correlated). By requiring only high-entropy samples rather than a high entropy rate, 3 we free the signal processing designer from the need to remove redundancy when converting the underlying reading to a string w used in the fuzzy extractor. As an example, the IrisCode transform is estimated to have 249 bits of entropy in a 2048 bit string [23].
Our construction can tolerate n log n k errors (out of the n bits of w) if we allow the running time of the construction (the number of hash function evaluations) to be linear in n. 4 More generally, we can tolerate c n log n to be only slightly superlogarithmic to ensure the high-entropy condition on the samples, our allowable error rate is only slightly sublinear. 5 The Advantage of Exploiting the Structure of the Distribution Following the tradition of randomness extractors [19,55], work on fuzzy extractors has focused on providing constructions that work for any source of a given minentropy m. For randomness extractors, this condition is necessary and sufficient for security. While entropy is necessary to build a fuzzy extractor, minentropy does not appear to be the right characterization of sufficiency for fuzzy extraction. Proposition 1. If the security guarantee of a fuzzy extractor holds for any source of minentropy m and the correctness guarantees holds for any t errors and m < log |B t | (where |B t | denotes the number of points in a ball of radius t), the fuzzy extractor must provide no security.
In particular, for the binary Hamming case, to provide nonzero key length m must exceed nh 2 This proposition holds regardless of whether the fuzzy extractor is information-theoretic or computational. The argument is that if m too small, then a single ball of radius t may contain the entire distribution of 2 m points inside it. For this distribution, an adversary can run Rep on the center of this ball and always learn the key r . In particular, for the binary field, the ball of radius t contains at least 2 nh 2 ( t n )− 1 2 log n− 1 2 points, 6 Thus, a fuzzy extractor that supports t errors out of a string of n bits and works for all sources of minentropy m must have the entropy rate m n at least as big as the binary entropy 7 of the error rate, h 2 ( t n ) (to be exact, m ≥ nh 2 ( t n ) − 1 2 log n − 1 2 ). In the above, the important quantifier is providing security for any distribution, because there is one distribution W of minentropy where all points are within distance t. Note that the above proposition does not rule out securing many distributions of smaller minentropy, rather it should be seen as requiring that some additional property must enable security.
Our construction exploits more about the structure of the distribution than just its entropy. As a result, it supports not only all sources of a given (sufficiently high) minentropy, but also many sources with an entropy rate much lower than the error rate. By taking advantage of the specific properties of the distribution, we can handle all distributions of sufficiently high minentropy, but also some distributions whose minentropy that is much less than t (and thus also less than nh 2 ( t n )). Beating the bound of Proposition 1 is important. For example, the IrisCode [23] produces a source where m is less than nh 2 ( t n ) [11,Section 5]. PUFs with slightly nonuniform outputs suffer from similar problems [43]. 5 The error rate of a string is the number of errors divided by the length of the string. 6 7 Binary entropy h 2 (α) for 0 < α < 1 is defined as −α log α − (1 − α) log(1 − α); it is greater than α log 1 α and, in particular, greater than α for interesting range α < 1 2 .
In applications of fuzzy extractors to physical sources, any constraint on the sourcewhether minentropy or more structured-is necessarily an assumption about the physical world. It is no more possible to verify that a source has high minentropy than it is to verify that it has high-entropy samples. 8 Both statements about the source can be derived only by modeling the source-for example, by modeling the physical processes that generate irises or PUFs.
Some prior work on key agreement from noisy data makes assumptions on the structure of the source (often assuming that it consists of independent identically distributed symbols, e.g. [38,48,52,53,68]). In particular, prior to this work constructions that beat Proposition 1 were known if and only if one allows the construction to run in unbounded time [32,33,39,65].
Fuller et al. [32,33] introduced fuzzy minentropy to measure the suitability of a noisy distribution for key derivation. A distribution has fuzzy minentropy k for parameter t if the total weight of probability mass within any ball of radius t is at most 2 −k . Fuzzy minentropy is a necessary condition for key derivation. Fuzzy minentropy is a more general condition than high entropy samples. If a distribution has entropy samples, it also has fuzzy minentropy. However, there are sources of fuzzy minentropy that don't demonstrate high entropy samples. Consider the following distribution: sample α uniform bits v 1 , . . . , v α and then concatenate β copies of each value v i . That is, the set of possible outcomes are w = v 1 ||v 1 || . . . ||v 1 ||v 2 || . . . .||v 2 || . . . ||v α || . . . ||v α . This distribution has high fuzzy minentropy because the minimum distance between two possible values of w is β. However, the entropy of random subsets is low because for many i the value v i will be sampled multiple times.

Constructions Exploiting the Structure of the Distribution for Larger Alphabets
In addition to the binary alphabet construction that supports reuse and low entropy rates we explore how low entropy rates can be supported when symbols of the string w comes from a large, rather than a binary, alphabet. We obtain two additional constructions, both of which allow for distributions whose total minentropy is lower than the volume of the ball of radius t (in the large-alphabet Hamming space). Both can tolerate a linear error rate (of course, over the larger alphabet, where errors may be more likely, because each symbol carries more information).
Our second construction for large alphabets works for sources with sparse highentropy marginals: sources for which sufficiently many symbols have high entropy individually, but no independence among symbols is assumed (thus, the total entropy may be as low as the entropy of a single symbol).
Our third construction for large alphabets provides information-theoretic, rather than computational, security. It works for sparse block sources. These are sources in which a sufficient fraction of the symbols have entropy conditioned on previous symbols. 8 However, standard heuristics for estimating entropy can also be used to indicate whether a source has high-entropy samples. For a corpus of noisy signals, repeat the following a statistically significant number of times: (1) sample k indices (2) run the heuristic entropy test on the corpus which each sample restricted to the k indices, (3) for estimates est 1 , . . . , est m compute the average min entropy, as defined in Sect. 2, of these estimates by − log i 2 −est i . Both constructions provide evidence that assumptions on the source other than total minentropy may allow polynomial time constructions for more distributions.
Our Approach Our constructions differ from most known constructions of fuzzy extractors, which put sufficient information in p to recover the original w from a nearby w during Rep (this procedure is called a secure sketch). We deliberately do not recover w; known techniques for building secure sketches do not work for sources whose entropy rate is lower than its error rate. Known secure sketches lose at least log |B t | bits of entropy regardless of the source. This loss is necessary when the source is uniform [ [29,Corollary 1]. Instead, our first two constructions lock up a freshly generated random r using parts of w in an error-tolerant way; in the information-theoretic construction, we reduce the alphabet in order to reduce the ball volume while maintaining entropy.
The idea of locking up a random r has appeared in a prior theoretical construction of a computational fuzzy extractor for any source. Namely, Bitansky et al. [8,9] show how to obfuscate a proximity point program that tests if an input w is within distance t of the value w hidden inside the obfuscated program and, if so, outputs the secret r (such a program would be output by Gen as p and run by Rep). However, such a construction is based on very strong assumptions (semantically secure graded encodings [57]) and, in contrast to our construction, is highly impractical in terms of efficiency. Moreover, it is not known to provide reusability, because known obfuscation of proximity point programs is not known to be composable.

Subsequent Reusable Fuzzy Extractors
Multiple reusable fuzzy extractors were described subsequent to the conference publication of this work. There are constructions based on various computational assumptions from Diffie-Hellman variants, learning with errors, and digital lockers.
Before describing these techniques we briefly describe analysis of the first reusable fuzzy extractor [12]. Boyen's definition of reusability assumed that multiple readings w 1 , w j are related by a linear shift δ j = w 1 ⊕ w j specified by the adversary. To prevent correct errors Boyen employed a linear secure sketch. A linear secure sketch allows computation of the sketch of w j knowing only δ j and w 1 . This fact is used to argue that new sketches provide no new information to the adversary (who learns the sketch of w 1 and specifies δ j ). Multiple keys are then extracted using calls to a random oracle.
Boyen used a random oracle to extract keys from each enrollment w i . Wen et al. [67] place a hash function of w i in the exponent of a Diffie-Hellman group. By using a linear hash function, correction is still possible. This construction crucially uses the fact that linear functions are computable in the exponent. Using a Diffie-Hellman group allows the construction to "refresh" the key and keep keys from leaking information about the underlying w i .
Apon et al. [2], Herder et. al [40] and Wen and Liu [66] use random linear codes to provide reusability. We focus on the construction of Wen and Liu since it provides the best error tolerance. The construction of Wen and Liu again uses a linear secure sketch, the resulting key, r i , is embedded in an learning with errors (LWE) instance. Like the Diffie-Hellman construction, error correction can be performed obliviously due to the use of random linear codes.
The described approaches use a linear secure sketch. Current negative results for secure sketches are stronger than current negative results for fuzzy extractors. The described approaches assume that readings are correlated by a linear shift. This is a weaker form of reusability than described in this work (different definitions are discussed in Sect. 3).
Like our work, Alamelou et al. [1] use digital lockers for reusability. They first note that the second construction presented in this work is reusable for a restricted set of sources. Their other construction builds a primitive called a reusable pseudoentropic isometry which preserves distance and refreshes entropy. Like our construction, their security is based on digital lockers. This pseudoentropic isometry is then used to construct a reusable fuzzy extractor for the set difference metric. [18] In addition to editorial and organizational changes, the primary differences between this work and the conference version are as follows:

Differences Between this Work and Conference Publication
1. There is a comprehensive discussion of definitional choices in reusability (Sect. 3).
This section has been expanded due to recent works all proposing new definitions. 2. This version discusses subsequent approaches to reusable fuzzy extractors including the observation that the second construction in this work is reusable under certain circumstances. 3. This version corrects an error in the analysis of the correctness of the main construction. This error was pointed out by Simhadri et al. [59]. This error in the analysis resulted in an overestimate on the correction capability of the construction. This error changes running time to n c+ (1) instead of n c (which was reported previously).

Definitions
Throughout this work we use capital letters to refer to random variables and finite sets. We use the corresponding lower case letters to refer to a particular outcome of a random variable. For example, in Pr[X = x], X is a random variable and x is a particular outcome. For a random variables X i over some alphabet Z we denote by X = X 1 , . . . , X n the tuple (X 1 , . . . , X n ). For a set of indices J , X J is the restriction of X to the indices in J . The set J c is the complement of J . Logarithms are base 2 unless specified. The For a random variable W , let H 0 (W ) be the logarithm of the size of the support of W , that is The statistical distance between random variables X and Y with the same domain is For a distinguisher D we write the computational distance (with respect to D) between ]| (we extend it to a class of distinguishers D by taking the maximum over all distinguishers D ∈ D). We denote by D s the class of randomized circuits which output a single bit and have size at most s. For a metric space (M, dis), the (closed) ball of radius t around x is the set of all points within radius t, that is, B t (x) = {y|dis(x, y) ≤ t}. If the size of a ball in a metric space does not depend on x, we denote by |B t | the size of a ball of radius t. We consider the Hamming metric over vectors in Z n , defined via dis(x, y) = |{i|x i = y i }|. For this metric, |B t | = t i=0 n i (|Z|−1) i . U n denotes the uniformly distributed random variable on {0, 1} n . Unless otherwise noted logarithms are base 2. Usually, we use capitalized letters for random variables and corresponding lowercase letters for their samples.

Fuzzy Extractors
In this section we define computational fuzzy extractors. Similar definitions for informationtheoretic fuzzy extractors can be found in the work of Dodis et al. [ • The generate procedure Gen on input w ∈ M outputs an extracted string r ∈ {0, 1} κ and a helper string p ∈ {0, 1} * . • The reproduction procedure Rep takes an element w ∈ M and a bit string p ∈ {0, 1} * as inputs. The correctness property guarantees that if dis(w, w ) ≤ t and (r, p) ← Gen(w), then Pr[Rep(w , p) = r ] ≥ 1 − δ, where the probability is over the randomness of (Gen, Rep). • The security property guarantees that for any distribution W ∈ W, the string r is pseudorandom conditioned on p, that is δ D ssec ((R, P), (U κ , P)) ≤ sec .
In the above definition, the errors are chosen before P: if the error pattern between w and w depends on the output of Gen, then there is no guarantee about the probability of correctness. In Constructions 1 and 2 it is crucial that w is chosen independently of the outcome of Gen. Information-theoretic fuzzy extractors are obtained by replacing computational distance by statistical distance. We do make a second definitional modification. The standard definition of information-theoretic fuzzy extractors considers W consisting of all distributions of a given entropy. As described in the introduction, we construct fuzzy extractors for parameter regimes where it is impossible to provide security for all distributions with a particular minentropy. As such, we explicitly describe the family W supported by each construction.

Cryptographic Tools
Our first construction uses digital lockers, which are computationally secure symmetric encryption schemes that retain security even when used multiple times with correlated and weak keys [20]. In a digital locker, obtaining any information about the plaintext from the ciphertext is as hard as guessing the key. They have the additional feature that the wrong key can be recognized as such (with high probability). We use notation c = lock(key, val) for the algorithm that performs the locking of the value val using the key key, and unlock(key, c) for the algorithm that performs the unlocking (which will output val if key is correct and ⊥ with high probability otherwise).
The following simple and efficient construction of digital lockers was shown to provide the desired security in the random oracle model of [13] by Lynn, Prabhakaran, and Sahai [47,Section 4]. Let H be a cryptographic hash function, modeled as a random oracle. The locking algorithm lock(key, val) outputs the pair nonce, H (nonce, key)⊕ (val||0 s ), where nonce is a nonce, || denotes concatenation, and s is a security parameter. As long as the entropy of key is superlogarithmic, the adversary has negligible probability of finding the correct key; and if the adversary doesn't find the correct key, then the adversarial knowledge about key and val is not significantly affected by this locker. Concatenation with 0 s is used to make sure that unlock can tell (with certainty 1 − 2 −s ) when the correct value is unlocked.
It is seems plausible that in the standard model (without random oracles), specific cryptographic hash functions, if used in this construction, will provide the necessary security [16, Section 3.2], [22,Section 8.2.3]. Moreover, Bitansky and Canetti [7], building on the work of [16,20], show how to obtain composable digital lockers based on a strong version of the Decisional Diffie-Hellman assumption without random oracles.
The security of digital lockers is defined via virtual-grey-box simulatability [7], where the simulator is allowed unbounded running time but only a bounded number of queries to the ideal locker. Intuitively, the definition gives the primitive we need: if the keys to the ideal locker are hard to guess, the simulator will not be able to unlock the ideal locker, and so the real adversary will not be able to, either. Formally, let idealUnlock(key, val) be the oracle that returns val when given key, and ⊥ otherwise. Definition 2. The pair of algorithm (lock, unlock) with security parameter λ is an -composable secure digital locker with error γ if the following hold: • Correctness For all key and val, Pr[unlock(key, lock(key, val)) = val] ≥ 1 − γ .
Furthermore, for any key = key, Pr[unlock(key , lock(key, val)) =⊥] ≥ 1 − γ . • Security For every PPT adversary A and every positive polynomial p, there exists a (possibly inefficient) simulator S and a polynomial q(λ) such that for any sufficiently large s, any polynomially long sequence of values (val i , key i ) for i = 1, . . . , , and any auxiliary input z ∈ {0, 1} * , Point Functions In one of the constructions for large alphabets, we use a weaker primitive: an obfuscated point function. This primitive can be viewed as a digital locker without the plaintext: it simply outputs 1 if the key is correct and 0 otherwise. Such a function can be easily constructed from the digital locker above with the empty ciphertext, or from a strong version of the Decisional Diffie-Hellman assumption [15]. We use notation c = lockPoint(key) and unlockPoint(key, c); security is defined the same way as for digital lockers with a fixed plaintext.

Computational Fuzzy Conductors and Computational Extractors
We now introduce computational tools used in our second construction. We first define an object weaker than a computational fuzzy extractor: it outputs a key with computational entropy (instead of a pseudorandom key). We call this object a computational fuzzy conductor. It is the computational analogue of a fuzzy conductor (introduced by Kanukurthi and Reyzin [44]). Before defining this object, we define conditional computational "HILL" ( [36]) entropy.

Definition 4.
A pair of randomized procedures "generate" (Gen) and "reproduce" (Rep) is an (M, W,m, t)-computational fuzzy conductor that is ( sec , s sec )-hard with error δ if Gen and Rep satisfy Definition 1, except the last condition is replaced with the following weaker condition: • for any distribution W ∈ W, the string r has high HILL entropy conditioned on P.
That is H HILL sec ,s sec (R|P) ≥m.
Computational fuzzy conductors can be converted to computational fuzzy extractors (Definition 1) using standard techniques, as follows. The transformation uses a computational extractor. A computational extractor is the adaption of a randomness extractor to the computational setting. Any information-theoretic randomness extractor is also a computational extractor; however, unlike information-theoretic extractors, computational extractors can expand their output arbitrarily via pseudorandom generators once a long-enough output is obtained. We adapt the definition of Krawczyk [45] to the average case: Combining a computational fuzzy conductor and a computational extractor yields a computational fuzzy extractor: Let D be such a distinguisher. That is, Then define D as follows. On input (y, p ) sample seed ← U d , compute r ← cext(y; seed) and output D(r, seed, p ). Note that |D| ≈ s + |cext| + d = s cond . Then we have the following: Where the last line follows by noting that D is of size at most s ext . Thus D distinguishes X from all Y with sufficient conditional minentropy. This is a contradiction.

Defining Reusability
Reusability is the ability to support multiple independent enrollments of the same value, allowing users to reuse the same biometric or PUF, for example, with multiple noncooperating providers. 9 More precisely, the algorithm Gen may be run multiple times on correlated readings w 1 , . . . , w ρ of a given source. Each time, Gen will produce a different pair of values (r 1 , p 1 ), . . . , (r ρ , p ρ ). Security for each extracted string r i should hold even in the presence of all the helper strings p 1 , . . . , p ρ (the reproduction procedure Rep at the ith provider still obtains only a single w close to w i and uses a single helper string p i ). Because the multiple providers may not trust each other, a stronger security feature called insider security (which we satisfy) ensures that each r i is secure even when all r j for j = i are also given to the adversary. We first introduce our definition of reusability and then compare other definitions of reusability in the fuzzy extractor literature. The key aspect of the above definition is that the distributions W 1 , . . . , W ρ are arbitrarily correlated. The only requirement on the distributions is on the marginal distribution, W i . This is contrast to other definitions of reusable fuzzy extractors which assume that each w i is a shift of w 1 by a value that is oblivious to the value of w 1 itself (in Boyen's definition w i is a result of a transitive isometry applied to w 1 ). Such a definition is appropriate if one assumes that the noise present in repeated source readings is independent of the underlying value and additive. However, in biometrics noise often depends on the source, for example individuals' eyelashes cause noise. This is a phenomenon associated with the person. There is not reason to expect it is independent of the reading itself. We call this definitional consideration Correlation. The two types of correlations that have been shown are arbitrary correlation and shift correlation. As noted by Boyen [12], it is also natural to consider the case where the correlation is a random process not controlled 9 Reusability and unlinkability are two different properties. Unlinkability prevents an adversary from telling if two enrollments correspond to the same physical source [21,42]. We do not consider this property in this work.
S h i f t − ✓ ✓ ✓ − by the adversary. We are not aware of any works in this setting. In addition, there are other important definitional choices: Information Theoretic Security Whether the construction is secure against informationtheoretic or computational limited adversaries. Our definition above is defined with respect to computationally limited adversaries. Boyen showed that even for shift correlations, any reusable information-theoretic secure sketch must lose at least log |B t | entropy [12,Theorem 11]. For the parameter regimes we consider, this would make security impossible. Insider Whether the adversary is provided with just the public strings p i or additional receives information about the cryptographic keys r i . Our definition is insider secure. Adaptive Whether the adversary creates the distributions W i adaptively after seeing p i−1 (and possibly r i−1 ). Our definition is non-adaptive. Distance Whether the distributions W i , W j are assumed to be bounded by distance.
That is, whether ∀w i ∈ W i , w j ∈ W j , it follows that d(w i , w j ) ≤ t. Our definition supports arbitrary distance. Robustness Whether the definition handles the case when the p i values are actively compromised. We do not consider such an active compromise attack. Protection against such an attack is called "robustness." In the random oracle model robustness is easy [10, Theorem 1]. Achieving reusability and robustness in the standard model is an open question.
It is clear that: (1) an information-theoretic construction implies a computationally secure one, (2) an arbitrary correlation secure construction is shift secure, (3) a construction that does not assume distance is secure when distance is limited and (4) an adaptive secure construction is also statically secure. However as shown in Table 1 there are often multiple changes in the literature making comparison less obvious. In particular, shift secure constructions tend to consider adaptive security. Shift correlation secure constructions are known from assumptions such as decisional Diffie-Hellman [67] and learning with errors [2,66] while known arbitrary correlation constructions rely on digital lockers.

Sample-then-Lock
Sources with High-Entropy Samples Let the source W = W 1 , . . . , W n consist of strings of length n over some arbitrary alphabet Z (the case of greatest interest is that of the binary alphabet Z = {0, 1}; however, we describe the construction more generally). For some parameters k, α, we say that the source W is a source with α-entropy k-samples if H ∞ (W j 1 , . . . , W j k | j 1 , . . . , j k ) ≥ α for uniformly random 1 ≤ j 1 , . . . , j k ≤ n. See the Introduction for a discussion of how sources with this property come up naturally.

The Construction
The construction first chooses a random r to be used as the output of the fuzzy extractor. It then samples a random subset of symbols v 1 = w j 1 , . . . , w j k and creates a digital locker that hides r using v 1 . 10 This process is repeated to produce some number of digital lockers all containing r , each unlockable with v 1 , . . . , v , respectively. The use of the composable digital lockers allows us to sample multiple times, because we need to argue only about individual entropy of V i . Composability also allows reusability. 11 Note that the output r can be as long as the digital locker construction can handle (in particular, the constructions discussed in Sect. 2.2 allow r to be arbitrarily long). Also note that it suffices to have r that is as long as a seed for a pseudorandom generator, because a longer output can be obtained by running this pseudorandom generator on r .  (r, p), where p = p 1 . . . p .

How to Set Parameters: Correctness Versus Efficiency Tradeoff
To instantiate Construction 1, we need to choose a value for . Recall we assume that dis(w, w ) ≤ t.
For any given i, the probability that . This is because 10 We present and analyze the construction with uniformly random subsets; however, if necessary, it is possible to substantially decrease the required public randomness and the length of p by using more sophisticated samplers. See [35] for an introduction to samplers. Security does not depend on the subsets being independently random. It is sufficient for the marginal distribution of each subset to be random. The subsets being distinct (and independent) is used to argue correctness. 11 For the construction to be reusable ρ times the digital locker must be composable · ρ times.
there are at most t errors so the probability that w j i ,1 = w j i ,1 is at least 1 − n/n since j i , 1 is uniform. Conditioned on that event the probability that w j i ,2 = w j i ,2 is at least 1 − t/n − 1 as there is a t/(n − 1) probability of error. Thus, the probability of this entire chain of events is at least Therefore, the probability that no v i matches during Rep, causing Rep output to ⊥, is at most In addition, Rep may be incorrect due to an error in one of the lockers, which happens with probability at most · γ . Thus, to make the overall error probability less than fuzzy extractor's allowable error parameter δ we need to set so that This provides a way to set to get a desirable δ, given a digital locker with error γ and source parameters n, t, k.
To get a bit more insight, we need to simplify the above expression. We can use the approximation e x ≈ 1 + x to get The value γ can be made very small very cheaply in known locker constructions, so let us assume that γ is small enough so that · γ ≤ δ/2. Then if k = o(n) with tk = c n log n = cn ln n for some constants c , c, setting ≈ n c+ (1) log 4 δ suffices as: We now provide the formal statement of security for Construction 1; we consider reusability of this construction below, in Theorem 2.

Theorem 1.
Let λ be a security parameter, Let W be a family of sources over Z n with α-entropy k-samples for α = ω(log λ). Let (lock, unlock) be an -composable secure digital locker with error γ for κ-bit keys and values over Z k . Then for any s sec = poly(λ) there exists some sec = ngl(λ) such that Construction 1 is a (Z n , W, κ, t)computational fuzzy extractor that is ( sec , s sec )-hard with error

(See above for an expression of as a function the other parameters.)
Proof. Correctness is already argued above. We now argue security. Our goal is to show that for all s sec = poly(λ) there exists sec = ngl(λ) such that δ D ssec ((R, P), (U, P)) ≤ sec . Fix some polynomial s sec and let D be a distinguisher of size at most s sec . We want to bound by a negligible function. We proceed by contradiction: suppose this difference is not negligible. That is, suppose that there is some polynomial p(·) such that for all λ 0 there exists some λ > λ 0 such that We note that λ is a function of λ 0 but we omit this notation for the remainder of the proof for clarity. By the security of digital lockers (Definition 2), there is a polynomial q and an unbounded time simulator S (making at most q(λ) queries to the oracles The same is true if we replaced R above by an independent uniform random variable U over {0, 1} κ . We now prove the following lemma, which shows that S cannot distinguish between R and U .

Lemma 2. Let U denote the uniform distribution over {0, 1} κ . Then
where q is the maximum number of queries S can make.
Proof. Fix any u ∈ {0, 1} κ (the lemma will follow by averaging over all u). Let r be the correct value of R. The only information about whether the value is r or u can obtained by S through the query responses. First, modify S slightly to quit immediately if it gets a response not equal to ⊥ (such S is equally successful at distinguishing between r and u, because the first non-⊥ response tells S if its input is equal to the locked value r , and subsequent responses add nothing to this knowledge; formally, it is easy to argue that for any S, there is an S that quits after the first non-⊥ response and is just as successful). There are q + 1 possible values for the view of S on a given input (q of those views consist of some number of ⊥ responses followed by the first non-⊥ response, and one view has all q responses equal to ⊥). By [26,Lemma 2.2b], . Therefore, at each query, the probability that S gets a non-⊥ answer (equivalently, guesses V i ) is at most (q + 1)2 −α . Since there are q queries of S, the overall probability is at most q(q + 1)/2 α . Then since 2 α is ngl(λ), there exists some λ 0 such that for all λ > λ 0 , q(q + 1)/2 α ≤ 1/ (3 p(λ)).
Adding together Eqs. 1, 2, and Eq. 1 in which R is replaced with U , we obtain that This is a contradiction and completes the proof of Theorem 1.
Reusability of Construction 1 The reusability of Construction 1 follows from the security of digital clockers. Consider any ρ number of reuses. For each fixed i ∈ {1, . . . , ρ}, we can treat the keys r 1 , . . . , r i−1 , r i+1 , . . . , r ρ and the sampled positions as auxiliary input to the digital locker adversary. The result follows by simulatability of this adversary, using the same argument as the proof of Theorem 1 above. Note that this argument now requires the digital locker to be ρ · -composable.

Theorem 2. Fix ρ and let all the variables be as in Theorem 1, except that (lock, unlock)
is an · ρ-composable secure digital locker (for κ-bit values and keys over Z k ). Then for all s sec = poly(n) there exists some sec = ngl(n) such that Construction 1 is (ρ, sec , s sec )-reusable fuzzy extractor.
Comparison with work of [60] The work of Škorić and Tuyls [60] can be viewed as a fuzzy extractor that places the entire string into a single digital locker (in their paper, they use the language of hash functions). Their Rec procedure symbol searches for a nearby value that unlocks the digital locker, limiting Rec to a polynomial number of error patterns. We use a subset of symbols to lock and take multiple samples, greatly increasing the error tolerance.

Error-Correct-then-Obfuscate
In this section, we consider an alternative construction that is suited to sources over large alphabets. Intuitively, we use single symbols of w to lock bits of a secret that we then transform into r ; we use error-correcting codes to handle bits of the secret that cannot be retrieved due to errors in w . Our main technical tool is obfuscated point functions (a weaker primitive than digital lockers; see Sect. 2.2 for the definition). This construction requires enough symbols individually to contain sufficient entropy, but does not require independence of symbols, or even "fresh" entropy from them. Unlike the previous construction, it tolerates a linear fraction of errors (but over a larger alphabet, where errors may be more likely.). However, it cannot work for small alphabets, and is not reusable.

Sources with Sparse High-Entropy Marginals
This construction works for distributions W = W 1 , . . . , W n over Z n in which enough symbols W j are unpredictable even after adaptive queries to equality oracles for other symbols. This quality of a distribution is captured in the following definition.

Definition 7.
Let idealPointUnlock(key) be an oracle that returns 1 when given key and 0 otherwise. A source W = W 1 , . . . , W n has β-sparse α-entropy q-marginals if there exists a set J ⊂ {1, . . . , n} of size at least n − β such that for any unbounded adversary S, where S is allowed q queries to the oracles {idealPointUnlock(W i )} n i=1 .
After analyzing the construction, we show some examples of such sources in Sect. 5.2. In particular, any source W where for all j, H ∞ (W j ) ≥ α = ω(log λ) (but all symbols may arbitrarily correlated) is a source with sparse high-entropy marginals (Proposition 3). [16]. Instead of having large parts of the string w unlock r , we have individual symbols unlock bits of the output.

Error-Correct-and-Obfuscate This construction is inspired by the construction of Canetti and Dakdouk
Before presenting the construction we provide some definitions from error correcting codes. We use error-correct codes over {0, 1} n which correct up to t bit flips from 0 to 1 but no bit flips from 1 to 0 (this is the Hamming analog of the Z -channel [62]). 12 12 Any code that corrects t Hamming errors also corrects t 0 → 1 errors, but more efficient codes exist for this type of error [62]. Codes with 2 (n) codewords and t = (n) over the binary alphabet exist for Hamming errors and suffice for our purposes (first constructed by Justensen [41]). These codes also yield a constant error tolerance for 0 → 1 bit flips. The class of errors we support in our source (t Hamming errors over a large alphabet) and the class of errors for which we need codes (t 0 → 1 errors) are different.

Set c = Decode(c ). 4. Output c.
As presented, Construction 2 is not yet a computational fuzzy extractor. The codewords c are not uniformly distributed and it is possible to learn some bits of c (for the symbols of W without much entropy). However, we can show that c looks like it has entropy to a computationally bounded adversary who knows p. Applying a randomness extractor with outputs over {0, 1} κ (technically, an average-case computational randomness extractor) to c, and adding the extractor seed to p, will give us the desired fuzzy extractor. See Sect. 2.2 for details. Construction 2 is secure if no distinguisher can tell whether it is working with r j or w j . By the security of point obfuscation, anything learnable from the obfuscation is learnable from oracle access to the function. Thus, it is prudent to lock uniform points r j in the random case to minimize probability of the adversary unlocking. Therefore, our construction is secure as long as enough symbols are unpredictable even after adaptive queries to equality oracles for individual symbols, which is exactly the property satisfied by sources with sparse high-entropy marginals. The following theorem formalizes this intuition.
Theorem 3. Let λ be a security parameter. Let Z be an alphabet. Let W be a family of sources with β-sparse α = ω(log λ)-entropy q-marginals over Z n , for any q = poly(n). Furthermore, let C be a (t, δ code )-Z code over Z n . Then for any s sec = poly(n) there exists some sec = ngl(n) such that Construction 2, followed by a κ-bit computational randomness extractor (whose required input entropy is ≤ H 0 (C) − β), is a (Z n , W, κ, t)-computational fuzzy extractor that is ( sec , s sec )-hard with error δ code + n(1/|Z| + γ ).
Proof of Theorem 3. It suffices to prove that Construction 2 is a (Z n , W,m = H 0 (C)− β, t)-comp. fuzzy conductor, i.e., that C has HILL entropy H 0 (C)−β conditioned on P. The final extraction step will convert it to a computational fuzzy extractor (see Lemma 1). The security proof of Construction 2 is similar to the security proof of Construction 1. However, it is complicated because the definition of sources with sparse high-entropy marginals (Definition 7) allows for certain weak symbols that can easily be guessed. This means we must limit our indistinguishable distribution to symbols that are difficult to guess. Security is proved via the following lemma: We give a brief outline of the proof, followed by the proof of the new statement. It is sufficient to show that there exists a distribution C with conditional minentropy and δ D ssec ((C, P), (C , P)) ≤ ngl(n). Let J be the set of indices that exist according to Definition 7. Define the distribution C as a uniform codeword conditioned on the values of C and C being equal on all indices outside of J . We first note that C has sufficient entropy, becauseH . It is left to show δ D ssec ((C, P), (C , P)) ≤ ngl(n). The outline for the rest of the proof is as follows: • Let D be a distinguisher between (C, P) and (C , P). By the security of obfuscated point functions, is small. • Show that even an unbounded S making a polynomial number of queries to the stored points cannot distinguish between C and C . That is, is small. • By the security of obfuscated point functions, is small.
Proof of Lemma 3. The overall approach and the proof of the first and third bullet as in Theorem 1. We only prove the second bullet. Define the distribution X as follows: Proof. It suffices to show that for any two codewords that agree on J c , the statistical distance is at most (n − β)2 −(α+1) .

Lemma 5.
Let c * be true value encoded in X and let c a codeword in C . Then, The only information about the correct value of c * j is contained in the query responses. When all responses are 0 the view of S is identical when presented with c * or c . We now show that for any value of c * all queries on j ∈ J return 0 with probability 1 − 2 −α+1 . Suppose not. That is, suppose the probability of at least one nonzero response on index j is > 2 −(α+1) . Since w, w are independent of r j , the probability of this happening when c * j = 1 is at most q/Z or equivalently 2 − log |Z|+log q . Thus, it must occur with probability: We now show that for α ≤ log |Z| − log q: If W is a source with β-sparse α-entropy q-marginals over Z, then α ≤ log |Z| − log q.
Proof. Let J ⊂ {1, . . . , n} the set of good indices. It suffices to show that there exists an S making q queries such that for some Let j ∈ J be some arbitrary element of J and denote by w j,1 , . . . , w j,q the q most likely outcomes of W j (breaking ties arbitrarily). Then q i=1 Pr[W j = w j,i ] ≥ q/|Z|. Suppose not. This means that there is some w j,i with probability Pr[W j = w j,i ] < 1/|Z|. Since there are Z − q remaining possible values of W j for their total probability to be at least 1−q/|Z| at least of these values has probability at least 1/Z. This contradicts the statement w j,1 , . . . , w j,q are the most likely values. Consider S that queries the jth oracle on w j,1 , .., w j,q . Denote by Bad the random variable when W j ∈ {w j,1 , .., w j,q } After these queries the remaining minentropy is at most: This completes the proof of Claim 1.
Rearranging terms in Eq. 3, we have: When there is a 1 response and c j = 0 this means that there is no remaining minentropy. If this occurs with over 2 −α probability this violates the condition on W (Definition 7). By the union bound over the indices j ∈ J the total probability of a 1 in J is at most (n − β)2 −α+1 . Recall that c * , c match on all indices outside of J . Thus, for all c * , c the statistical distance is at most (n − β)2 −α+1 . This concludes the proof of Lemma 5. Lemma 4 follows by averaging over all points in C . This completes the proof of Lemma 3 and the security analysis of Construction 2.
Correctness We now argue correctness of Construction 2. We first assume ideal functionality of the obfuscated point functions. Consider a coordinate j for which c j = 1.
Since w is chosen independently of the points r j , and r j is uniform, Pr[r j = w j ] = 1/|Z|. Thus, the probability of at least one 1 → 0 bit flip (the random choice r i being the same as w i ) is ≤ n(1//|Z|). Note in the case that r j = w j , a 1 → 0 bit flip if it is also the case that r j = w j . Thus, we can bound overall probability of 1 → 0 flips by this probability. Since there are at most t locations for which w j = w j there are at most t 0 → 1 bit flips in c, which the code will correct with probability 1 − δ code , because c was chosen uniformly. Finally, since each obfuscated point function is correct with probability 1 − γ , Construction 2 is correct with error at most δ code + n(1/|Z| + γ ).

Discussion
Entropy Versus Error Rate The minimum entropy necessary to satisfy Definition 7 is ω(log λ) (for example, when all symbols are completely dependent but are all individually unguessable). The construction corrects a constant fraction of errors. When n = λ 1/c then the entropy is smaller than the number of errors m = ω(log λ) < (n) = λ 1/c .

Output Length
The extractor that follows Construction 2 can output H 0 (C) − β − 2 log(1/ sec ) bits using standard information-theoretic techniques (such as the averagecase leftover hash lemma [26, Lemma 2.2b, Lemma 2.4]). To get a longer output, Construction 2 can be run multiple (say, μ) times with the same input and independent randomness to get multiple values c, concatenate them, and extract from the concatenation, to obtain an output of sufficient length μ(H 0 (C) − β) − 2 log(1/ sec ). The goal is to get an output long enough to use as a pseudorandom generator seed: once the seed is obtained, it can be used to generate arbitrary polynomial-length r , just like Construction 1.
Further Improvement If most codewords have Hamming weight close to 1/2, we can decrease the error tolerance needed from the code from t to about t/2, because roughly half of the mismatches between w and w occur where c j = 1.
Reusability Even though Construction 2 uses composable obfuscated point functions, it is not reusable for the set of distributions with sparse high-entropy marginals. Definition 7 allows sources with some "weak" symbols that can be completely learned by an adversary observing p. If a source is enrolled multiple times this partial information may add up over time to reveal the original value w 1 . However, Alamelou et al. [1] noted if all marginals are high entropy, that is J = {1, . . . , n}, then the construction leaks no partial information and is reusable fuzzy extractors. Reusability depends on the composability of the underlying digital locker.

Characterizing sources satisfying Definition 7
Definition 7 is an inherently adaptive definition and a little unwieldy. In this section, we partially characterize sources that satisfy Definition 7. The majority of the difficulty in characterizing Definition 7 is that different symbols may be dependent, so an equality query on symbol i may reshape the distribution of symbol j.
In the examples that follow we denote the adversary by S as the simulator in Definition 2. We first show some sources that have sparse high-entropy marginals and then show sources with high overall entropy that do not have sparse high-entropy marginals. We begin with the case of independent symbols.  (q+1))entropy q-marginals. In particular, when α = ω(log n) and q = poly(n), then W is a source with (n − |J |)-sparse ω(log n)-entropy q-marginals.
Proof. It suffices to show that for all j ∈ J,H ∞ (W j |V iew(S(·))) = α − log(q + 1) where S is allowed q queries to the oracles {idealUnlock(W i )} n i=1 . We can ignore queries for all symbols but the jth, as the symbols are independent. Furthermore, without loss of generality, we can assume that no duplicate queries are asked, and that the adversary is deterministic (S can calculate the best coins). Let A 1 , A 2 , . . . A q be the random variables representing the oracle answers for an adversary S making q queries about the ith symbol. Each A k is just a bit, and at most one of them is equal to 1 (because duplicate queries are disallowed). Thus, the total number of possible responses is q + 1. Thus, we have the following,H where the second line follows from the first by [ is a source with 0-sparse (e − log(q + 1))-entropy q-marginals.
Proof. f is injective on each symbol, sõ Consider a query q k on symbol j. There are two possibilities: either q k is not in the image of f j , or q k can be considered a query on the preimage f −1 j (q k ). Then (by assuming S knows f ) we can eliminate queries which correspond to the same value of U e . Then the possible responses are strings with Hamming weight at most 1 (like in the proof of Claim 2), and by [26,Lemma 2.2] we have for all j, Note the total entropy of a source in Proposition 3 is e, so there is a family of distributions with total entropy ω(log n) for which Construction 2 is secure. For these distributions, all the coordinates are as dependent as possible: one determines all others. We can prove a slightly weaker claim when the correlation between the coordinates W j is arbitrary: Proposition 4. Let W = W 1 , . . . , W n . Suppose that for all j, H ∞ (W j ) ≥ α, and that q ≤ 2 α /4 (this holds asymptotically, in particular, if q is polynomial and α is super-logarithmic). Then W is a source with 0-sparse (α − 1 − log(q + 1))-entropy q-marginals.
Proof. Intuitively, the claim is true because the oracle is not likely to return 1 on any query. Formally, we proceed by induction on oracle queries, using the same notation as in the proof of Proposition 2. Our inductive hypothesis is that Pr[A 1 = 0 ∨ · · · ∨ A i−1 = 0] ≤ (i − 1)2 1−α . If the inductive hypothesis holds, then, for each j, This is true for i = 1 by the condition of the theorem. It is true for i > 1 because, as a consequence of the definition of H ∞ , for any random variable X and event E, where the third line follows by considering that to get A i = 1, the adversary needs to guess some W j , and the fourth line follows by (4)). Thus, using i = q + 1 in (4), we know H ∞ (W j |A 1 = · · · = A q = 0) ≥ α − 1. Finally this means that This completes the proof of Proposition 4.

Negative Examples
Propositions 2 and 3 rest on there being no easy "entry" point to the distribution. This is not always the case. Indeed it is possible for some symbols to have very high entropy but lose all of it after equality queries.
Proof. Let x be the true value for U p×n . We present an adversary S that completely determines x. S computes y 1 . Then S queries on (y 1 ), . . . , (y p ) to the first oracle, exactly one answer returns 1. Let this value be y * 1 and its preimage x * 1 . Then S computes y 1 2 ) and queries y 1 2 , . . . , y p 2 . Again, exactly one of these queries returns 1. This process is repeated until all of x is recovered (and thus w).
The previous example relies on an adversary's ability to determine a symbol from the previous symbols. We formalize this notion next. We define the entropy jump of a source as the remaining entropy of a symbol when previous symbols are known: Definition 10. Let W = W 1 , . . . , W n be a source under ordering i 1 , . . . , i n . The jump of a symbol i j is Jump(i j ) = max w i 1 ,...,w i j−1 H 0 (W i j |W i 1 = w i 1 , . . . , W i j−1 = w i j−1 ).
An adversary who can learn symbols in succession can eventually recover the entire secret. In order for a source to have sparse high-entropy marginals, the adversary must get "stuck" early enough in this recovery process. This translates to having a superlogarithmic jump early enough. Proposition 6. Let W be a distribution and let q be a parameter, if there exists an ordering i 1 , . . . , i n such that for all j ≤ n − β + 1, Jump(i j ) = log q/(n − β + 1), then W is not a source with β-sparse high-entropy q-marginals.
Proof. For convenience relabel the ordering that violates the condition as 1, . . . , n. We describe an unbounded adversary S that determines W 1 , . . . , W n−β+1 . As before S queries the q/n possible values for W 1 and determines W 1 . Then S queries the (at most) q/(n − β + 1) possible values for W 2 |W 1 . This process is repeated until W n−β+1 is learned.
Presenting a sufficient condition for security is difficult as S may interleave queries to different symbols.

Information-Theoretic Construction for Sparse Block Sources
The construction in this section has information-theoretic security, in contrast to only computational security of the previous two constructions. It uses symbol-by-symbol condensers to reduce the alphabet size while preserving most of the entropy, and then applies a standard fuzzy extractor to the resulting string. This construction requires less entropy from each symbol than the previous construction; however, it places more stringent independence requirements on the symbols. It tolerates a linear number of errors.
Sparse Block Sources This construction works for sources W = W 1 , . . . , W n over Z n in which enough symbols W j contribute fresh entropy conditioned on previous symbols. We call this such sources sparse block sources, weakening the notion of block sources (introduced by Chor and Goldreich [19]), which require every symbol to contribute fresh entropy.
The choice of conditioning on the past is arbitrary: a more general sufficient condition is that there exists some ordering of indices where most items have entropy conditioned on all previous items in this ordering (for example, is possible to consider a sparse reverse block source [64]).

The Condense-then-Fuzzy-Extract Construction
The construction first condenses entropy from each symbol of the source and then applies a fuzzy extractor to the condensed symbols. We'll denote the fuzzy extractor on the smaller alphabet as (Gen , Rep ). A condenser is like a randomness extractor, but the output is allowed to be slightly entropy deficient. Efficient condensers are known with smaller entropy loss than possible for randomness extractors (for example k-wise independent hashes [27]). The main idea of the construction it tolerates errors on the large alphabet (before condensing) while the entropy loss for the error correction is incurred on a smaller alphabet (after condensing). For correctness the only requirement on the condenser is deterministic behavior when the seed is fixed.
This completes the proof of Theorem 4.
Overcoming Proposition 1 Proposition 1 shows that no fuzzy extractor can be secure for all sources of a given minentropy m < log |B t |. Construction 3 supports sparse block sources whose overall entropy is less than log |B t |. The structure of a sparse block source implies that H ∞ (W ) ≥ α(n − β) = (n). We assume that H ∞ (W ) = (n). Using standard fuzzy extractors (for Gen , Rep ) it is possible to correct t = (n) errors, yielding log |B t | > (n) when |Z| = ω(1). and important references. Adam Smith performed this work while on the faculty of the Pennsylvania State University's Department of Computer Science and Engineering.