sketch s = SS(w) to Bob along with (i, σ). To prevent an undetected modi¬cation

of s to s , she could send an authentication of s (using w as the key) as well.

The nontriviality of making such an extension work arises from the fact that

modifying s to s also gives the adversary the power to in¬‚uence Bob™s veri¬cation

key w— = SRec(w , s ). The adversary could perhaps exploit this circularity to

succeed in an active attack (the de¬nition of standard authentication schemes

only guarantee security when the keys used for authentication and veri¬cation

are the same).

We break this circularity by exploiting the algebraic properties of the Ham-

ming metric space, and using authentication secure against algebraic manipula-

tion [DKRS06, CDF+ 08]. The techniques that we use are essentially the same

as used in [DKRS06], but adapted to our construction. We present the con-

struction here and then discuss the exact properties that we use in the proof of

security.

An Improved Robust Fuzzy Extractor 167

Construction. Let M be the Hamming metric space on {0, 1}n. Let W be a

distribution of min-entropy m over M. Let s = SS(w) be a deterministic, linear

secure sketch; let |s| = k, n = n ’ k. Assume that SS is a surjective linear

function (which is the case for the syndrome construction for the Hamming

metric mentioned in Section 2). Therefore, there exists a k — n matrix S of rank

k such that SS(w) = Sw. Let S⊥ be an n — n matrix such that n — n matrix

has full rank. We let SS⊥ (w) = S⊥ (w).

S

S⊥

To compute Gen(w), let s = SS(w), c = SS⊥ (w); |c| = n . We assume that

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

a be the ¬rst half of c and b the second. View a, b as elements of F2n /2 . Let

k

L = 2 n (it will important for security that L is even). Pad s with 0s to

length Ln /2, and then split it into L bit strings sL’1 , . . . , s0 of length n /2 bits

each, viewing each bit string as an element of F2n /2 . Select i ← F2n /2 . De¬ne

fs,i (x) = xL+3 + x2 (sL’1 xL’1 + sL’2 xL’2 + · · · + s0 ) + ix. Set σ = [fs,i (a) + b]v ,

1

n /2

and output P = (s, i, σ) and R = [fs,i (a) + b]v+1 .

Gen(w):

1. Set s = SS(w), c = SS⊥ (w), k = |s|, n = |c|.

n /2

- Let a = [c]1 , b = [c]n /2+1

n

k

- Let L = 2 n . Pad s with 0s to length Ln /2.

- Parse the padded s as sL’1 ||sL’2 || . . . ||s0 for si ∈ F2n /2 .

2. Select i ← F2n /2 .

n /2

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

1

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

1. Compute w— = SRec(w , s )

- Verify that dis(w— , w ) ¤ t and SS(w— ) = s . If not, output ⊥.

2. Let c = SS⊥ (w— ). Parse c as a ||b .

3. Compute σ — = [fs ,i (a ) + b ]v .

1

— n /2

- Verify that σ = σ . If so, output R = [fs ,i (a )+b ]v+1 , else output ⊥.

In the theorem statement below, let B denote the volume of a Hamming ball

or radius t in {0, 1}n (log B ¤ nH2 (t/n) [MS77, Chapter 10, §11, Lemma 8] and

log B ¤ t log(n + 1) [DKRS06]).

Theorem 3. Assume SS is a deterministic linear (m, m ’ k, t)’secure sketch

of output length k for the Hamming metric on {0, 1}n . Setting v = (n ’ k)/2 ’ l,

the above construction is an (m, l, t, µ) fuzzy extractor with robustness δ for any

m, l, t, µ satisfying l ¤ m ’ n/2 ’ k ’ log B ’ log 2 n’k + 2 ’ log 1 as long

k

δ

as m ≥ 1 (n + k) + 2 log 1 .

2 µ

Again, if m < 1 (n + k) + 2 log 1 , the construction can be modi¬ed, as shown in

2 µ

Section 5.1.

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

(i, s, σ). To do so, we ¬rst note that for every s, the function hi (c) = (σ, R) is a

168 B. Kanukurthi and L. Reyzin

universal hash family. Indeed for c = c there is a unique i such that hi (c) = hi (c )

(since i(a ’ a ) is ¬xed, like in the errorless case). We also note that H∞ (c |

SS(W )) ≥ H∞ (c, SS(W )) ’ k = H∞ (W ) ’ k = m ’ k by Lemma 2. Because

|(R, σ)| = n /2, Lemma 3 (or, more precisely, its generalization mentioned in the

paragraph following the lemma, needed here because hi depends on s) gives us

SD (R, P ), U|R| — SS(W ) — Un /2 — Uv ¤ µ/2

for n /2 ¤ m ’ k + 2 ’ 2 log(2/µ). This is equivalent to saying that (R, P ) is

1

2(n /2’m+k) 2 ’1 -close to U|R| — SS(W ) — Un /2 — Uv .

Applying Lemma 1 to A = R, B = P , C = Un /2’v , D = SS(w) — Un /2 — Uv ,

n

’m+k)/2

— P , for µ = 2( 2

we get that (R, P ) is µ-close to U n .

’v

2

From here it follows that for extraction to be possible, m ≥ 1 (n + k) + 2 log 1 .

2 µ

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

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

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

P ) § Rep(w , s ) = ⊥. In our analysis, we will assume that (i , s ) = (i, s). We

claim that this does not reduce A™s success probability. Indeed, if (i , s ) = (i, s)

then, c computed within Rep will equal c. So, for P = P to hold, A would

have to output σ = σ. However, when (i , c , s ) = (i, c, s), Rep would compute

σ — = σ, and therefore 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.

Since i is ¬xed and A is deterministic, the tr = (i, s, σ, R, i , s , σ ) is deter-

mined completely by (s, σ, R). Recall that the prime challenge in constructing a

robust fuzzy extractor was that A could somehow relate the key used by Rep to

verify σ to the authentication key that was used by Gen to come up with σ. As

was done in [DKRS06], we will argue security of our construction by showing

that the MAC scheme implicitly used in our construction remains unforgeable

even when A could force the veri¬cation key to be at an o¬set (of her choice) from

the authentication key. We will formalize such an argument by assuming that

A learns ” = w ’ w. Recall that w— = SRec(w , s ) and c = a ||b = SS⊥ (w— ).

The following claim that was proven in [DKRS06] states that given (”, s), A

can compute the o¬sets ”a = a ’ a, ”b = b ’ b induced by her choice of s .

Claim. Given ” = w ’ w, and the sketches s, s , A can compute ”a = a ’ a

and ”b = b ’ b, or determine that Rep will reject before computing a , b .

In other words, she can compute the o¬set between the authentication key that

Gen used to come up with σ and the veri¬cation key that Rep will use to verify σ .

We will now argue that as long as W has su¬cient min-entropy, even knowing

the o¬set does not help A succeed in an active attack. Recall that since i is

arbitrarily ¬xed by A, A™s success depends on w, w , or, alternatively, on w, ”.

Fix some ”. For any particular tr, let Succtr,” be the event that the transcript

An Improved Robust Fuzzy Extractor 169

is tr and A wins, i.e., that fs,i (a) + b = σ||R § [fs ,i (a ) + b ]v = σ § SS(w) = s,

1

conditioned on the fact that w ’ w is ”. We denote by Badtr,” the set of w

that make Succtr,” true. We now partition the set Badtr,” into 2 disjoint sets,

indexed by R ∈ {0, 1} :

def

BadR = {w | w ∈ Badtr,” § [fs ,i (a ) + b ]v+1 = R }

tr,”

= {w | (fs,i (a) + b = σ||R) § (fs ,i (a ) + b = σ ||R ) § SS(w) = s}.

By Claim 1, ¬xing (tr, ”), also ¬xes ”a , ”b . It follows that every w ∈ BadR

tr,”

needs to satisfy

fs,i (a) ’ fs ,i (a + ”a ) = (”b + σ ’ σ )||(R ’ R ) § SS(w) = s.

For a given tr, ”, R , the right hand side of the ¬rst equation takes a ¬xed value.