pick a random seed i for a strong extractor and send it to Bob (in the clear).

They could then use R = Ext(w; i) as the shared key. As long as the adversary

is passive, the shared key looks uniform to her. However, such a protocol can

be rendered completely insecure when executed in the presence of an active

adversary because A could adversarially modify i to i such that R extracted by

Bob has no entropy. To prevent such malicious modi¬cation of i we will require

Alice to send an authentication of i (along with i) to Bob. In our construction,

we authenticate i using w as the key and then extract from w using i as the

seed. Details follow.

Construction. For the rest of the paper we will let w ∈ {0, 1}n. We will assume

that n is even (if not, drop one bit of w, reducing its entropy by at most 1). To

n/2

compute Gen(w), let a be the ¬rst half of w and b the second: a = [w]1 , b =

n/2+1 . View a,b as elements of F2n/2 . Let v = n ’ m + log δ , where δ is the

1

[w]n

desired robustness. Choose a random i ∈ F2n/2 . Compute y = ia + b. Let σ

consist of the ¬rst v bits of y and the extracted key R consist of the rest of y:

n/2

σ = [y]v , R = [y]v+1 . Output P = (i, σ).

1

162 B. Kanukurthi and L. Reyzin

Gen(w):

n/2

1. Let a = [w]1 , b = [w]n n/2+1

2. Select a random i ← F2n/2

n/2

3. Set σ = [ia + b]v , R = [ia + b]v+1 and output P = (i, σ)

1

Rep(w, P = (i , σ )):

n/2

1. Let a = [w]1 , b = [w]n

n/2+1

n/2

2. If σ = [i a + b]v then compute R = [i a + b]v+1 else output ⊥

1

Theorem 1. Let M = {0, 1}n. Setting v = n/2 ’ , the above construction

is an (m, , 0, µ) ’ fuzzy extractor with robustness δ, for any m, , µ, δ satisfying

¤ m ’ n/2 ’ log 1 as long as m ≥ n/2 + 2 log 1 .

δ µ

If µ is so low that the constraint m ≥ n/2 + 2 log 1 is not satis¬ed, then the

µ

construction can be modi¬ed as shown in Section 3.1.

Proof. Extraction. Our goal is to show that R is nearly uniform given P . To

do so, we ¬rst show that the function hi (a, b) = (σ, R) is a universal hash family.

Indeed, for (a, b) = (a , b ) consider

Pr[hi (a, b) = hi (a , b )] = Pr[ia + b = ia + b ]

i i

= Pr[i(a ’ a ) = (b ’ b )]

i

’n/2

¤2 .

To see the last inequality recall that (a, b) = (a , b ). Therefore, if a = a , then

b = b making the Pri [i(a ’ a ) = (b ’ b )] = 0. If a = a , then there is a unique

i = (b ’ b )/(a ’ a ) that satis¬es the equality. Since i is chosen randomly from

F2n/2 , the probability of the speci¬c i occurring is 2’n/2 .

Because |(R, σ)| = n/2, Lemma 3 gives us SD (R, P ), U|R| — U|P | ¤ µ/2 as

long as n/2 ¤ m + 2 ’ 2 log 2 , or, equivalently, (R, P ) is 2(n/2’m)/2’1 -close to

µ

U|R| — U|P | . Applying Lemma 1 to A = R, B = P , C = U n ’v , D = U n — Uv ,

2 2

we get that (R, P ) is µ-close to U( 2 )’v — P , for µ = 2 (n/2’m)/2

. From here it

n

follows that for extraction to be possible, m ≥ n/2 + 2 log µ .

1

Post-Application Robustness. In the post-application robustness security

game, the adversary A on receiving (P = (i, σ), R) (generated according to

procedure Gen) outputs P = (i , σ ), and is considered successful if (P = P ) §

[i a + b]v = σ . In our analysis, we will assume that i = i. We claim that this

1

does not reduce A™s success probability. Indeed, if i = i then, for P = P to

hold, A would have to output σ = σ. However, when i = i, Rep would output

⊥ unless σ = σ.

In our analysis, we allow A to be deterministic. This is without loss of gen-

erality since we allow an unbounded adversary. We also allow A to arbitrarily

¬x i. This makes the result only stronger since we demonstrate robustness for a

worst-case choice of i.

An Improved Robust Fuzzy Extractor 163

Since i is ¬xed and A is deterministic, (σ, R) determines the transcript tr =

(i, σ, R, i , σ ). For any particular tr, let Succtr be the event that the transcript

is tr and A wins, i.e., that ia + b = σ||R § [i a + b]v = σ . We denote by Badtr

1

the set of w = a||b that make Succtr true. For any tr, Prw [Succtr ] ¤ |Badtr |2’m ,

because each w in Badtr occurs with probability at most 2’m . We now partition

the set Badtr into 2 disjoint sets, indexed by R ∈ {0, 1} :

def

BadR = {w | w ∈ Badtr § [i a + b]v+1 = R }

tr

= {w | (ia + b = σ||R) § (i a + b = σ ||R )}

For a particular value of (tr, R ), w = a||b is uniquely determined by the con-

straints that de¬ne the above set i.e; |BadR | = 1. Since Badtr = R ∈{0,1} BadR ,

tr tr

we get |Badtr | ¤ 2 = 2 n/2’v

. From here it follows that

Pr[Succtr ] ¤ |Badtr |2’m ¤ 2n/2’v’m .

Pr[Succtr ] measures the probability that the transcript is tr and A succeeds.

To ¬nd out the probability that A succeeds, we need to simply add Pr[Succtr ]

over all possible tr. Since a transcript is completely determined by σ, R, the total

number of possible transcripts is 2|σ|+|R| = 2n/2 and, therefore, A™s probability

of success is at most 2n’v’m .

To achieve δ-robustness, we need to set v to at least n ’ m + log 1 . From here

δ

it follows that = n ’ v ¤ 1 (2m ’ n ’ 2 log 1 ).

2 2 δ

3.1 Getting Closer to Uniform

If µ is so low that the constraint m ≥ n/2 + 2 log 1 is not satis¬ed, then in

µ

our construction we can simply shorten R by β = n/2 + 2 log 1 ’ m bits, as

µ

follows: keep v = n ’ m + log δ (regardless of ), and let R = [ia + b]v+1 , for any

+v

1

¤ 2m ’ n ’ log 1 ’ 2 log 1 . This keeps σ the same, but shortens R enough for

δ µ

the leftover hash lemma to work. The proof remains essentially the same, except

n/2

that to prove robustness, we will give the remaining bits [ia + b] +v+1 for free

to A.

3.2 Improving the Construction of [DKRS06] When the Uniformity

Constraint Dominates

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

1

and R = [ia]n ; P = (i, σ). In order to get R to be uniform given P , the value

v+1

v is increased until the leftover hash lemma can be applied to (R, σ). However,

we observe that this unnecessarily increases the length of σ (i.e., for every bit

added to v, two bits are subtracted from R). Instead, we propose to improve this

construction with essentially the same technique as we use for our construction