σ. This improvement applies to both pre- and post-application robustness.

164 B. Kanukurthi and L. Reyzin

For post-application robustness, suppose the uniformity constraint dominates,

i.e., 2 log 1 > (2m’n+log 1 )/3. Modify the construction of [DKRS06] by setting

µ δ

v = (2n’m+log δ )/3 and R = [ia]n’v’β , where β = 2 log 1 ’(2m’n’log 1 )/3.

1

v+1 µ δ

This will result in an extracted key of length = (4m ’ 2n ’ log 1 )/3 ’ 2 log 1 .

δ µ

However, even with the improvement, the extracted key will be always shorter

than the key extracted by our scheme, as explained in Section 4.2

In contrast, this improvement seems useful in the case of pre-application ro-

bustness. Again, suppose the uniformity constraint dominates, i.e., 2 log 1 > µ

log 1 . Modify the construction of [DKRS06] by setting v = n ’ m + log 1 and

δ δ

R = [ia]n’v’β , where β = 2 log 1 ’ log 1 . This will result in an extracted key of

v+1 µ δ

length = 2m ’ n ’ 2 log 1 ’ log 1 , which is 2 log 1 ’ log 1 longer than the key

µ δ µ δ

extracted without this modi¬cation.

4 Comparison with the Construction of [DKRS06]

4.1 When the Robustness Constraint Dominates

Recall that the construction of Dodis et al. [DKRS06] parses w as two strings

a and b of lengths n ’ v and v, respectively. The values σ, R are computed as

σ = [ia]v + b and R = [ia]n ; P = (i, σ). Notice that, like in our construction,

1 v+1

increasing v improves robustness and decreases the number of extracted bits. For

pre-application robustness, setting v = n ’ m + log 1 su¬ces, and thus the con-

δ

struction extracts nearly (2m’n) bits. However, for post-application robustness,

a much higher v is needed, giving only around 1 (2m ’ n) extracted bits.

3

The post-application robustness game reveals more information to A about w

than the pre-application robustness game. This additional information”namely,

R”may make it easier for A to guess σ for a well-chosen i . The key to our

improvement is in the pairwise independence of the function ia+b that computes

both σ and R: because of pairwise independence, the value (σ, R) of the function

on input i tells A nothing about the value (σ , R ) on another input i . (This

holds, of course, for uniformly chosen key (a, b); when (a, b) has entropy m, then

A can ¬nd out n ’ m bits of information about σ .)

In contrast, in the construction of [DKRS06], only σ is computed using a

pairwise independent hash function. This works well (in fact, better than our

construction, because b can be shorter) for pre-application robustness, where A

does not ¬nd out R. But it makes it possible for R to decrease A™s uncertainty

about σ by as much as = |R|, thus necessitating the length v of σ (and hence

σ) to be v > + (n ’ m) (the (n ’ m) term is the amount of entropy already

potentially “missing” from σ because of the nonuniformity of w). See Section 4.3

for a detailed description of an adversarial strategy that utilizes R to obtain σ

in the [DKRS06] construction.

Another way to see the di¬erences between the two constructions is through

the proof. In the proof of post-application robustness, the transcript tr includes

R, which makes for 2 times more transcripts than in the proof of pre-application

robustness. However, the fact that this R imposes an additional constraint of w,

An Improved Robust Fuzzy Extractor 165

thus reducing the size of the set Badtr , can compensate for this increase. It turns

out that for the construction of [DKRS06], this additional constraint can be

redundant if the adversary is clever about choosing i and σ , and the size of

Badtr doesn™t decrease. Using a pairwise-independent function for computing R

in our construction ensures that this additional constraint decreases the size

of Badtr by 2 . Thus, our construction achieves the same results for pre- and

post-application robustness.

4.2 When the Uniformity Constraint Dominates

It should be noted that there may be reasonable cases when the uniformity con-

straint µ on R is strong enough that the construction of [DKRS06] extracts even

fewer bits, because it needs to take v ≥ n ’ m + 2 log 1 to ensure near-uniformity

µ

of R given P . In that case, as long as m ≥ n/2 + 2 log 1 , our construction will

µ

extract the same amount of bits as before, thus giving it an even bigger advan-

tage. And when m < n/2 + 2 log 1 , our construction still extracts at least 3/2

µ

times more bits than the construction of [DKRS06], even with the improvement

of Section 3.2 applied (this can be seen by algebraic manipulation of the relevant

parameters for the post-application robustness case).

4.3 Why the Construction of [DKRS06] Cannot Extract More Bits

Recall that the robust fuzzy extractor of [DKRS06] operates as follows: parse w

as two strings a, b of lengths n ’ v, v respectively and compute σ = [ia]v + b and

1

R = [ia]n ; P = (i, σ).

v+1

For post-application robustness, the concern is that R can reveal information

to the adversary about σ for a cleverly chosen i . Because the length of σ is v

and + (n ’ m) bits of information about σ may be available (the term comes

from |R|, and (n ’ m) term comes from the part of w which has no entropy), this

leads to the requirement that v ≥ + n ’ m + log 1 to make sure the adversary

δ

has to guess at least log 1 bits about σ . Plugging in = n ’ 2v, we obtain

δ

¤ 2 (m ’ n/2 ’ log 1 ), which is the amount extracted by the construction.

3 δ

Here we show an adversarial strategy that indeed utilizes R to obtain infor-

mation about σ to succeed with probability δ/2. This demonstrates that the

analysis in [DKRS06] is tight up to one bit. To do so we have to ¬x a particular

(and somewhat unusual) representation of ¬eld elements. (Recall that any rep-

resentation of ¬eld elements works for constructions here and in [DKRS06], as

long as addition of ¬eld elements corresponds to the exclusive-or of bit strings.)

Typically, one views F2n’v as F2 [x]/(p(x)) for some irreducible polynomial p

of degree n ’ v, and represents elements as F2 -valued vectors in the basis

(xn’v’1 , xn’v’2 , ..., x2 , x, 1). We will do the same, but will reorder the basis ele-

ments so as to separate the even and the odd powers of x: (xn’v’1 , xn’v’3 , . . . , x,

xn’v’2 , xn’v’4 , . . . , 1) (assuming, for concreteness, that n ’ v is even). The ad-

vantage of this representation for us is that the top half of bits of some value

z ∈ F2n’v is equal to the bottom half of the bits of z/x, as long as the last bit

of z is 0.

166 B. Kanukurthi and L. Reyzin

Now suppose the distribution on w is such that the top n ’ m bits of b are 0

(the rest of the bits of w are uniform). Then by receiving σ and R, the adversary

gets to see the top +(n’m) bits of ia. Therefore, the adversary knows +(n’m)

bits from the bottom half of ia/x as long as the last bit of ia is 0, which happens

with probability 1/2. To use this knowledge, the adversary will simply ensure

that the di¬erence between σ and σ is [ia/x]v , by letting i = i + i/x.

1

Thus, the adversarial strategy is as follows: let i = i + i/x; let „ consist of

the bits of R, the top n ’ m bits of σ, and log 1 = v ’ ’ (n ’ m) randomly

δ

guessed bits, and let σ = σ + „ . The adversary wins whenever „ = [ia/x]v , 1

which happens with probability 2v’ ’(n’m) /2 = δ/2, because all but log 1 bitsδ

of „ are de¬nitely correct as long as the last bit of ia is 0.

The above discussion gives us the following result.

Theorem 2. There exists a basis for GF (2n’v ) such that for any integer m

there exists a distribution W of min-entropy m for which the post-application

robustness of the construction from [DKRS06, Theorem 3] can be violated with

probability at least δ/2, where v is set as required for robustness δ by the con-

struction (i.e., v = (n ’ )/2 for = (2m ’ n ’ 2 log 1 )/3).

δ

Note that our lower bound uses a speci¬c representation of ¬eld elements, and

hence does not rule out that for some particular representation of ¬eld elements, a

lower value of v and, therefore, a higher value of is possible. However, a security

proof for a lower value of v would have to then depend on the properties of that

particular representation and would not cover the construction of [DKRS06] in

general.

5 Tolerating Binary Hamming Errors

We now consider the scenario where Bob has a string w that is close to Alice™s

input w (in the Hamming metric). In order for them to agree on a random string,