extractor translates into an improved robust fuzzy extractor using the techniques

of [DKRS06], with the same factor of 3/2 improvement.

In addition, we show (in Section 3.2) a slight improvement for the pre-application

robust version of the extractor of [DKRS06], applicable when the extracted string

must be particularly close to uniform.

2 Preliminaries

Notation. For binary strings a, b, a||b denotes their concatenation, |a| denotes

the length of a. For a binary string a, for we denote by [a]j , the substring

i

b = ai ai+1 . . . aj . If S is a set, x ← S means that x is chosen uniformly from S.

If X is a probability distribution (or a random variable), then x ← X means that

x is chosen according to distribution X. If X and Y are two random variables,

then X — Y denotes the product distribution (obtained by sampling X and Y

independently). All logarithms are base 2.

Random Variables, Entropy, Extractors. Let Ul denote the uniform dis-

tribution on {0, 1}l. Let X1 , X2 be two probability distributions over some set

S. Their statistical distance is

1

def

SD (X1 , X2 ) = max{Pr[X1 ∈ T ] ’ Pr[X2 ∈ T ]} = Pr[s] ’ Pr[s]

T ⊆S 2 X1 X2

s∈S

An Improved Robust Fuzzy Extractor 159

(they are said to be µ-close if SD (X1 , X2 ) ¤ µ). We will use the following lemma

on statistical distance that was proven in [DKRS08]:

Lemma 1. For any joint distribution (A, B) and distributions C and D over

the ranges of A and B respectively, if SD ((A, B), C — D) ¤ ±, then SD((A, B),

C — B) ¤ 2±.

Min-entropy. The min-entropy of a random variable W is de¬ned as H∞ (W )

= ’ log(maxw Pr[W = w]) (all logarithms are base 2, unless speci¬ed other-

wise). Following [DORS08], for a joint distribution (W, E), de¬ne the (average)

conditional min-entropy of W given E as

H∞ (W | E) = ’ log( E (2’H∞ (W |E=e) ))

e←E

(here the expectation is taken over e for which P r[E = e] is nonzero). A com-

putationally unbounded adversary who receives the value of E cannot ¬nd the

correct value of W with probability greater than 2’H∞ (W |E) . We will use the

following lemma from [DORS08]:

Lemma 2. Let A, B, C be random variables. If B has at most 2» possible val-

ues, then H∞ (A|B, C) ≥ H∞ ((A, B)|C) ’ » ≥ H∞ (A|C) ’ ». In particular,

H∞ (A|B) ≥ H∞ ((A, B)) ’ » ≥ H∞ (A) ’ ».

Because in this paper the adversary is sometimes assumed to have some external

information E about Alice and Bob™s secrets, we need the following variant,

de¬ned in [DORS08, De¬nition 2], of the de¬nition of strong extractors of [NZ96]:

De¬nition 1. Let Ext : {0, 1}n ’ {0, 1}l be a polynomial time probabilistic

function that uses r bits of randomness. We say that Ext is an average-case

(n, m, l, µ)-strong extractor if for all pairs of random variables (W, E) such that

w ∈ W is an n-bit string and H∞ (W | E) ≥ m, we have SD((Ext(W ; X), X, E),

(Ul , X, E)) ¤ µ, where X is the uniform distribution over {0, 1}r .

Any strong extractor can be made average-case with a slight increase in input

entropy [DORS08, Section 2.5]. We should note that some strong extractors, such

as universal hash functions [CW79, HILL99] discussed next, generalize without

any loss to average-case.

The Leftover Hash Lemma We ¬rst recall the notion of universal hash-

ing [CW79]:

De¬nition 2. A family of e¬cient functions H = hi : {0, 1}n ’ {0, 1} i∈I

is universal if for all distinct x, x we have Pri←I [hi (x) = hi (x )] ¤ 2’l .

H is pairwise independent if for all distinct x, x and all y, y it holds that

Pri∈I [hi (x) = y § hi (x ) = y ] ¤ 2’2 . ™¦

Lemma 3 (Leftover Hash Lemma, average-case version [DORS08]).

For , m, µ > 0, H is a strong (m, µ) average-case extractor (where the index

of the hash function is the seed to the extractor) if H is universal and ¤

m + 2 ’ 2 log 1 .

µ

160 B. Kanukurthi and L. Reyzin

This Lemma easily generalizes to the case when H is allowed to depend on the

extra information E about the input X. In other words, every function in H takes

an additional input e, and the family H is universal for every ¬xed value of e.

Secure Sketches and Fuzzy Extractors. We start by reviewing the def-

initions of secure sketches and fuzzy extractors from [DORS08]. Let M be a

metric space with distance function dis (we will generally denote by n the length

of each element in M). Informally, a secure sketch enables recovery of a string

w ∈ M from any “close” string w ∈ M without leaking too much information

about w.

De¬nition 3. An (m, m, t)-secure sketch is a pair of e¬cient randomized pro-

˜

cedures (SS, SRec) s.t.:

—

1. The sketching procedure SS on input w ∈ M returns a bit string s ∈ {0, 1} .

The recovery procedure SRec takes an element w ∈ M and s ∈ {0, 1}— .

2. Correctness: If dis(w, w ) ¤ t then SRec(w , SS(w)) = w.

3. Security: For any distribution W over M with min-entropy m, the (average)

min-entropy of W conditioned on s does not decrease very much. Speci¬cally,

if H∞ (W ) ≥ m then H∞ (W | SS(W )) ≥ m. ˜

The quantity m ’ m is called the entropy loss of the secure sketch. ™¦

˜

In this paper, we will construct a robust fuzzy extractor for the binary Hamming

metric using secure sketches for the same metric. We will brie¬‚y review the

syndrome construction from [DORS08, Construction 3] that we use (see also

references therein for its previous incarnations). Consider an e¬ciently decodable

[n, n ’ k, 2t + 1] linear error-correcting code C. The sketch s = SS(w) consists

of the k-bit syndrome w with respect to C. We will use the fact that s is a

(deterministic) linear function of w and that the entropy loss is at most |s| = k

bits in the construction of our robust fuzzy extractor for the Hamming metric.

We note that, as was shown in [DKRS06], the secure sketch construction for

the set di¬erence metric of [DORS08] can be used to extend the robust fuzzy

extractor construction in the Hamming metric to the set di¬erence metric.

While a secure sketch enables recovery of a string w from a close string w ,

a fuzzy extractor extracts a close-to-uniform string R and allows the precise

reconstruction of R from any string w close to w.

De¬nition 4. An (m, , t, µ)-fuzzy extractor is a pair of e¬cient randomized pro-

cedures (Gen, Rep) with the following properties:

1. The generation 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 string P ∈ {0, 1}— as inputs.

2. Correctness: If dis(w, w ) ¤ t and (R, P ) ← Gen(w), then Rep(w , P ) = R.

3. Security: For any distribution W over M with min-entropy m, the string R is

close to uniform even conditioned on the value of P . Formally, if H∞ (W ) ≥

m and (R, P ) ← Gen(W ), then we have SD ((R, P ), U — P ) ¤ µ. ™¦

An Improved Robust Fuzzy Extractor 161

Note that fuzzy extractors allow the information P to be revealed to an adversary

without compromising the security of the extracted random string R. However,

they provide no guarantee when the adversary is active. Robust fuzzy extractors

de¬ned (and constructed) in [DKRS06] formalize the notion of security against

active adversaries. We review the de¬nition below.

If W, W are two (correlated) random variables over a metric space M, we say

dis(W, W ) ¤ t if the distance between W and W is at most t with probability

one. We call (W, W ) a (t, m)-pair if dis(W, W ) ¤ t and H∞ (W ) ≥ m.

De¬nition 5. An (m, , t, µ)-fuzzy extractor has post-application (resp., pre-appli-

cation) robustness δ if for all (t, m)-pairs (W, W ) and all adversaries A, the

probability that the following experiment outputs “success” is at most δ: sample

(w, w ) from (W, W ); let (R, P ) = Gen(w); let P = A(R, P ) (resp., P = A(P ));

˜ ˜

output “success” if P = P and Rep(w , P ) =⊥. ™¦

˜ ˜

We note that the above de¬nitions can be easily extended to give average-case

fuzzy extractors (where the adversary has some external information E corre-

lated with W ), and that our constructions satisfy those stronger de¬nitions,

as well.

3 The New Robust Extractor

In this section we present our new extractor with post-application robustness.

We extend it to a robust fuzzy extractor in Section 5. Our approach is similar

to that of [DKRS06]; a detailed comparison is given in Section 4.

Starting point: key agreement secure against a passive adversary.

Recall that a strong extractor allows extraction of a string that appears uniform

to an adversary even given the presence of the seed used for extraction. Therefore,