Reusable cryptographic fuzzy extractors.
We show that a number of recent definitions and constructions of fuzzy extractors are not adequate for multiple uses of the same fuzzy secret---a major shortcoming in the case of biometric applications. We propose two particularly stringent security models that specifically address the case of fuzzy secret reuse, respectively from an outsider and an insider perspective, in what we call a chosen perturbation attack. We characterize the conditions that fuzzy extractors need to satisfy to be secure, and present generic constructions from ordinary building blocks. As an illustration, we demonstrate how to use a biometric secret in a remote fuzzy authentication protocol that does not require any storage on the client's side.
Introduction
Often, one would like to be able to use some piece of cryptographic machinery, not with an exact,
strictly random string as secret, but with an approximate, noisy rendition of it, which furthermore
would not be perfectly random either. Such a "fuzzy" secret could be a measurement on a somewhat
hidden biometric feature-a retinal scan rather than a thumbprint-, a long password imperfectly
committed to memory, or even one's spontaneous answers to a list of subjective questions [EHMS00,
FJ01]. Ideally, one would like to have a method to convert the above into as many cryptographically
strong secrets usable for any purpose we like. A number of constructions geared toward specific
applications have surfaced in the last few years [DFM98, JW99, MRW99, JS02]. Not surprisingly,
related lines of work have also been pursued in di#erent contexts, e.g., for privacy amplification
[BBCM95, BBR88], or for coping with noisy channels [Cre97].
The general idea is based on a two-step process, where an extraction function first transforms
any su#ciently random fuzzy secret into an almost uniform random private string, and outputs
some public information which is used in the regeneration step to reconstitute the exact same
private string from a close enough approximation of the original fuzzy secret. Dodis et al. [DRS04]
propose the most general definitions, and also introduce the notion of secure sketch (here renamed
fuzzy sketch to avoid ambiguities), which works like an extractor except that no private string
is extracted; rather, the goal is to allow an exact reconstruction of the original input given an
approximation thereof. Although the repeated use of the regeneration function on many inputs is
typically allowed, all these schemes implicitly assume that no more than a single extraction is ever
performed from any secret-clearly a problematic state of a#airs for biometric applications.
Toward a more robust definition of fuzzy sketch and extractor, we propose a security model
based on the stringent notion of adaptive chosen perturbation attacks, wherein the adversary may
query an oracle to perform extractions and regenerations based on chosen perturbations of the secret
under attack. If the adversary is only given an extraction oracle, we speak of an outsider attack; in
the general case we have an insider attack. We first show under the outsider security requirements
how to achieve information theoretic security, and prove that certain existing constructions already
satisfy these conditions. We then show how to harden the generic construction to withstand insider
attacks, although in this case unconditional security is no longer feasible. We give fairly detailed
security analysis based on simple assumptions, which we keep as general as possible to fit the generic
nature of our constructions, and justify by showing their necessity; we rely on random oracles only
in the case of extractors. Finally, we illustrate the power of our model by contructing a simple "zero
storage" biometric authentication protocol based on universally reusable biometric certificates.
Preliminaries
We briefly recall a few classic notions needed in our constructions, mostly following [DRS04].
Metric Spaces. For the purpose of this paper, we define a metric space M as a finite set equipped
with a non-negative integer distance function d : M-M# Z#0 which obeys the usual properties
of a distance (symmetry, triangle inequality, zero distance between equal points). The elements of
are assumed to admit an e#cient compact representation as bit strings of length O[log 2 #M].
Hamming Distance. We usually consider multi-dimensional metric spaces of the form
for some alphabet # (usually a finite field F p ), equipped with the Hamming distance. For any two
words the Hamming metric d[w, w # ] is the number of coordinates in which they di#er.
Correcting Codes. For a given choice of metric d, one can define error correcting codes
in the corresponding space M. A code is a subset M. The set C is sometimes
called its K elements are the codewords. The (minimum) distance of a code is the
smallest distance d between two distinct codewords (according to the metric d). Given a codebook
C, we can define a pair of functions #C, D#. The encoding function C is an injective map from
the elements of some domain of size K to the elements of C. The decoding function D maps any
element to the pre-image C of the codeword w k that minimizes the distance d[w, w k ].
The error correcting distance is the largest radius t such that for every element w # M there is at
most one codeword in the ball of radius t centered on w. For integer distance functions we have
standard shorthand notation in coding theory is that of a (M,K, t)-code.
We also define a complementary notion and say that the code has error correction limit t # if for
any codeword w k # C and any element w # M such that we have that d[w, w k
Linear Codes. If the alphabet is a finite field is a finite vector space.
A linear code of parameters [n, k, d] over F p is a code whose codebook C is a vector subspace of
-i.e., C is closed under vector addition and scalar multiplication by elements of F p -such that C
has size n k and distance d. The natural notion of distance for linear codes is the Hamming metric.
The "square bracket" parameter notation [n, k, d] is also used for non-linear codes over spaces
of the form
#C is integral. Such a code is said to have dimension k.
Entropy. Let A and B be two random variables with values in the discrete domains A and B. The
entropy of A is defined as the expectation
a]]. The conditional entropy
of A given B is written H[A |
(Average) Min-Entropy. The notion of entropy quantifies the "expected randomness" of a
random variable. To quantify the cryptographically more robust notion notion of "worst-case ran-
domness", we consider the min-entropy of A which is defined as H#
For conditional distributions, we use the notion of average min-entropy, which for A given B is
defined as -
This is not the expected min-
entropy of A given B, but rather the (negative) logarithm of the average probability of the most
likely value of A given B; it is more pessimistic since -
Statistical Distance. The statistical distance between two probability distributions A 1 and A 2
over a common discrete domain A is written D[A 1 , A 2
It is often useful to consider the statistical distance to a uniform distribution. We use the
notation U # to denote a uniformly distributed random variable over {0, 1} # .
Permutation Groups. Let be a family of functions indexed by p in some
finite set. P is said to be a permutation group if #P, # is a group (observe that the # p must be
permutations of M since they have inverses in P). The group operation # in P and the action
of the permutations # p on M are implicitly assumed to be e#ciently computable from canonical
representations. We define the following properties of any such permutation group P:
. P is transitive if for any pair of points w, w # M, there is an (e#ciently determinable)
permutation
. P is isometric with respect to the distance d in M if for all permutation # p # P and points
it holds that d[# p [w], # p [w #
3 Previous Notions Of Extractors
In this section, we review the definition of a fuzzy extractor as introduced by Dodis et al. [DRS04]
and related notions. We then show by a counterexample that fuzzy extractors may be quite insecure
if the same noisy secret is reused a few times.
3.1 Randomness Extractors
Intuitively, a (non-fuzzy) strong randomness extractor [NZ96] is a randomized function that tran-
forms its input from any biased distribution of su#cient min-entropy into an output that appears
to be drawn from an almost uniform distribution. We require that this be the case even if one is
given access to the random bits used by the extractor (but not its input).
Definition 1. An e#cient (n, m #)-strong randomness extractor (or randomness extractor for
short) is a polynomial time randomized algorithm Ext : {0, 1} n
# {0, 1} # such that, for any random
variable W over {0, 1} n with min-entropy m # , it holds that D[#Ext[W ; R], R#U # , R#. Here,
denotes the application of Ext to the input word W using randomization bits R; the
random variable R is required to have a uniform distribution independent from W and U # .
As shown in [RTS97], the theoretical limit is given by # m # - 2 log 2 [1/#] +O[1]. A number of
optimal constructions that also minimize the size of r are surveyed in [Sha02]. If the size of r is not
critical, simpler optimal constructions can be obtained from pairwise independent hash functions
[BBR88, HILL89].
3.2 From Fuzzy Sketches To Fuzzy Extractors
Dodis et al. [DRS04] define the following notions of fuzzy sketch (or secure sketch, in their termi-
nology) and fuzzy extractor, and show how to construct the former can be transformed into the
latter using a randomness extractor.
Definition 2. A (M,m,m # , t)-fuzzy sketch is a pair #Fsk, Cor# where:
Fsk is a (typically randomized) sketching function that on input w # M outputs a sketch or
redundancy data p # {0, 1} # , such that for all random variable W over M with min-entropy
m, the average min-entropy of W given Fsk[W
is a correction function that given a word w # M and a sketch p outputs a word w # M,
such that for any p # Fsk[w] and d[w, w # t, it holds that w
When we need to explicitly consider the random bits r used by Fsk on input w, we write Fsk[w; r].
The functions Fsk and Cor are assumed e#ciently computable, and the domain of r finite.
Definition 3. A (M,m, #, t, #)-fuzzy extractor is a pair #Gen, Reg# where:
Gen is a (necessarily randomized) generation function that on input w # M extracts a private
string s # {0, 1} # and a public string q, such that for all random variable W over M such that
dependent variables #s, q# Gen[W ], it holds that D[#s, q#U # , q#.
Reg is a regeneration function that given a word w # M and a public string q outputs a string
, such that for any words w, w # M satisfying d[w, w # t and any possible pair
#s, q# Gen[w], it holds that
When we need to explicitly consider the random bits r used by Gen on input w, we write Gen[w; r].
The functions Gen and Reg are assumed e#ciently computable, and the domain of r finite.
be a (M,m,m # , t)-fuzzy sketch. Suppose that
Ext is a (n, m #)-randomness extractor, assumed optimal and based on pairwise independent
hashing so that uniformly distributed randomization strings r 1 and
r 2 , the following pair of algorithms #Gen, Reg# defines a (M,m, #, t, #)-fuzzy extractor:
#, and output #s, q#.
3.3 Concrete Constructions
Working towards showing a flaw in the above definitions, we recall for concreteness some fuzzy
extractor constructions given in [DRS04].
Construction For Hamming Distance. A fuzzy extractor is easily obtained by viewing the
notion of "fuzzy commitment" from [JW99] as a fuzzy sketch. We follow [DRS04, Section 4].
# {0, 1} n be a (non-necessarily linear) binary code of parameters [n, k,
and let D : {0, 1} n
# {0, 1} k be the matching decoding function. For random r # $ {0, 1} k we define
the Juels-Wattenberg (M,m,m over the Hamming space as:
By combining the Juels-Wattenberg fuzzy sketch above with a randomness extractor as in Lemma 4,
we immediately obtain a (M,m, #, t, #)-fuzzy extractor #Gen, Reg# where
and t measures Hamming distance. We call it the JW-DRS fuzzy extractor.
Permutation Based Extractors. Let C # M be a code with encoding and decoding functions
#C, D#, and P a transitive group of isometric permutations in M. Given such a family, a generic
(randomized) "permutation based" fuzzy sketch #Fsk, Cor# is easily to construct:
The principle is as follows. On input word w, the sketching function Fsk returns a permutation
# p that maps w to a randomly chosen codeword -
the permutation is an isometry, the
same permutation is used in the correction function Cor to turn any input w # in the vicinity of w
into some word # p [w # ] in the vicinity of -
w; from there, the application of C # D reconstitutes -
and the subsequent inverse permutation # -1
maps it back to the original w. From there, the rest
of the fuzzy extractor construction is as in Lemma 4. Dodis et al. [DRS04] show that if C is a
(M,K, t)-code and P is a transitive family of isometric permutations, the permutation based fuzzy
sketch above is a (M,m,m # , t)-fuzzy sketch with entropy loss m-m [K], from
which Lemma 4 gives a (M,m, #, t, #)-fuzzy extractor of output size
[1/#].
4 On The Insecure Reuse Of Fuzzy Extractors
Whereas Definitions 2 and 3 may be adequate for single-use fuzzy secrets, we now demonstrate
various ways in which multiple invocations can coerce otherwise compliant fuzzy sketches and
extractors to completely expose the secret. The avenues of attack we explore are: an insecure fuzzy
sketch, a biased code, and a overly broad permutation family, respectively.
4.1 Fuzzy Sketch Indiscretion
Our first counterexample illustrates how a careless-yet compliant-fuzzy sketch and the extractor
constructed from it can rapidly leak information about the input secret, if used multiple times.
A Flawed Construction. Let #Fsk, Cor# be a Juels-Wattenberg (M,m,m+k-n, t)-fuzzy sketch
as in Section 3.3. We construct a modified fuzzy sketch as follows:
are randomization strings assumed to be independently and
uniformly distributed, and 1} is the inner product of w and r # .
By the properties of #Fsk, Cor#, for any random variable W of min-entropy m we know that
is independent of W and b is a single bit, it follows that
We combine the fuzzy sketch #Fsk # , with a randomness extractor Ext as in Lemma 4, to yield
a (M,m, #, t, #)-fuzzy extractor #Gen # , Reg # with
An Outsider Attack. We claim that the modified fuzzy extractor #Gen # , Reg # is flawed, though
it is in all respects a "good" extractor according to the definition of [DRS04]. Indeed, assume that
one makes a number q of independent calls to Gen # on the same (secret) input w # . Assume for
simplicity that q # n. Then, with high probability the q public strings q # 1 , ., q # q contain enough
information to uniquely determine the secret word w # . Furthermore, recovering w # from that
information amount to solving an (over-constrained) n - q linear system in F 2 , which can be done
very e#ciently. Once w # is known, recovering the extracted private strings s 1 , ., s q is as easy as
computing
4.2 Coding Vulnerability
Improper fuzzy sketch constructions are not the only sources of information leaks. Even the a
priori secure JW-DRS construction of Section 3.3 is prone to a total break when used with the
wrong error correction code, if used multiple times. We outline the general argument. More details
can be found in Appendix C.
Biased Codes. The argument is based on the notion of (non-linear) binary codes with a special
property: on average over all the codewords in the codebook, the value 0 is more likely to appear
than the value 1, at every coordinate of the code space. Specifically, we say that a p-ary [n, k, d]-code
C has bias #, if, for a uniformly sampled random codeword w # $ C, we have:
There are many ways to construct e#ciently decodable biased codes. As an illustration, we refer
to

Appendix

C for an explicit construction of such a code in the binary case. For now, we assume
that C is a binary #-biased [n, k, d]-code with e#cient encoding and decoding functions C and D.
When the JW-DRS construction of Section 3.3 is applied to the code #C, D#, we obtain a
({0, 1} n , m, #, t, #)-fuzzy extractor #Gen, Reg# where
Majority Vote Attack. Recall that in the JW-DRS scheme the public string q produced by a
call to Gen[w # ] contains the substring w #C[r] for some r chosen uniformly at random. Since we
are using a binary code with bias #, it follows that each bit of w #C[r] is equal to the corresponding
bit of w # with probability at least 1+ #. Thus, given a su#ciently large number
of public strings q 1 , ., q q derived from independent calls to Gen[w # ], it is indeed quite easy for an
attacker to recover the secret w # from public information: simply do a majority vote among all q
public strings q 1 , ., q q for each of the n bits of w # C[r], one coordinate at a time.
4.3 Permutation Leaks
A third source of potential information leak can be found in the abstractions used in generic fuzzy
sketches and extractors, such as the permutation based construction of Section 3.3. We show that
a poor implementation of a particular abstraction can easily leak damaging information, if used
multiple times.
Assume for the sake of illustration that M is the Hamming space F n
p with vector addition +.
Consider the permutation group consisting of all linear
shifts (the # p ) and their mirror images (the - # p ). Clearly, P is a transitive isometric permutation
group of size and it is easy to see that for any pair of words
there is
exactly one "direct" and one "mirror" permutation in P maping w to -
which we denote by #w, -
and - #w, -
w . Now, assume that #Fsk, Cor# is a permutation based (M,m,m # , t)-fuzzy sketch as in
Section 3.3. The construction must specify how to select p s.t. # p [w #
w given a random -
We specify it as follows: let r # H[#w # , -
w fixed hash function H. If the parity of (a bit
string representation of) w #r # is 0, then pick p s.t. #
w .
In an attack, the adversary can easily determine whether p corresponds to #w # , -
w or -
w , and
from there find the value of w # r # . If w # r easily recovered. Over q
queries, an attacker can thus expect to obtain q/2 distinct p i for which r # i can be recovered this
way. Given enough of these, it is easy to reconstruct the secret w # using the method of Section 4.1.
This attack may seem contrived, but similar leaks can realistically occur in practice, e.g., whenever
p is selected deterministically among multiple choices from a set P that is ordered haphazardly.
Although randomizing the choice of p would thwart this particular vulnerability, it is possible to
mount much more powerful attacks in the same spirit if the adversary is allowed to obtain public
strings for distinct secrets with a known or chosen relationship.
4.4 From Noisy Inputs
All the previous attacks assume that that multiple public strings are independently extracted from
the same secret input. Since the secret is fuzzy, a more realistic scenario is to consider that the
multiple extractions are performed on noisy variants of the fuzzy secret. We dispell the notion that
such noise could somehow drastically hamper the above attacks.
Regarding the scheme of Section 4.2, observe that the attack is robust to small Hamming
perturbations of the secret word w # . Specifically, instead of Gen being applied multiple times to
the same secret w # , suppose that Gen is applied to q variations w 1 , ., w q of the secret w # . It
is easy to see that if all the w i are contained within a ball of radius t centered on w # , then the
"majority vote" attack of Section 4.2 will produce a word -
w that with high probability is also
within distance t of the secret w # (and possibly quite closer if the various perturbations cancel each
other on average). From there, in virtue of the error tolerance that defines fuzzy extraction, the
attacker can exactly regenerate the extracted private key strings s 1 , ., s q from the corresponding
public strings q 1 , ., q q , simply by computing s i # Reg[ -
The attacks of Section 4.1 and 4.3 can also be adapted to cope with noisy secrets. Recall that in
Section 4.1 we engineer fuzzy sketches that leak one bit of the input secret along a randomly chosen
projection. Under noisy conditions, this results in an over-determined inconsistent set of contraints.
The attacker can nonetheless attempt to solve, e.g., for the least squared error approximation -
using techniques of linear algebra.
5 Secure Fuzzy Sketches And Extractors
The counterexamples of Section 4 clearly demonstrate the need for stronger notions of security for
fuzzy sketches and extractors.
Our first notion is that of security against outsider chosen perturbation attacks; it directly
addresses the vulnerabilities exposed in Section 4, and is mostly relevant to fuzzy sketches. In such
attacks, the challenger holds a secret, and the adversary adaptively asks the challenger to run the
sketching function Fsk on chosen perturbations of the secret-where a perturbation is a function
specified by the adversary and applied by the challeger to the secret prior to processing a query.
The adversary must not learn undue information about the secret from any number of such queries.
(In the case of fuzzy extractors, the challenger runs Gen instead of Fsk, and shows the resulting
public strings to the adversary, but not the private strings.)
Our second notion is that of security against insider chosen perturbation attacks; it is much more
stringent and only applies to fuzzy extractors. In addition to making chosen perturbation queries
on Gen as in the outsider attack, the adversary may adaptively ask the challenger to reconstruct
certain private strings by applying Reg on chosen perturbations of the secret for arbitrary public
strings (including ones from previous queries to Gen). The adversary must be computationally
unable to recreate or distinguish any private string that it has not queried.
Perturbation Families. We need a manageable notion of perturbation that is useful to the
adversary and manageable by the challenger. At the very least, perturbations should be e#ciently
computable. We keep the formal definition as simple and general as possible. Later, we will impose
additional restrictions.
Definition 5. We call perturbation (the canonical representation of) any e#ciently computable
We call perturbation family any family # d : M# M} of such functions,
indexed by d in some finite set.
To fix ideas, suppose that M is a Hamming metric space, and define # as the set of all
d. In this case, the admissible perturbations
are precisely the ones whose maximum displacement is bounded by -
d; for example, the "shift"
perturbations are #-admissible provided that
d.
In general, perturbations are not required to be invertible, or even composable in the sense that
the composition of perturbations from a family may not itself be in the family.
5.1 Outsider Chosen Perturbation Security
Let # be a family of perturbations over some metric space M as previously defined. We define
an adaptive outsider chosen perturbation attack against a fuzzy sketch (or a fuzzy extractor
constructed from it) as the following game between a challenger and an adversary:
Preparation: The adversary sends to the challenger the specification (such as an e#cient
sampling procedure) of a random variable W # M.
Randomization: The challenger selects a secret word w # M by randomly sampling W ,
and signals to the adversary that the query phase may begin.
Queries: The adversary presents arbitrarily many fuzzy sketching queries to the challenger.
The queries are made adaptively, where for the k-th query proceeds as follows.
The adversary chooses a perturbation # d k # and sends d k to the challenger. The
challenger runs Fsk on input word w k # d k
using fresh random bits r k , obtaining a
sketch and responds to the query by giving p k to the adversary.
Outcome: When the adversary decides that the queries are over, it produces a word -
The winning condition for the adversary is that -
We call the unbounded adversary A info in the above game a Fuz-CPA adversary.
Definition 6. Let #Fsk, Cor# be a (M,m,m # , t)-fuzzy sketch. If in the above game we have for all
Fuz-CPA adversary whenever H# [W
then we say that the fuzzy
sketch is unconditionally secure against adaptive outsider chosen perturbation attacks in #.
Outsider security for fuzzy extractors is defined in a similar way, except that the challenger
responds to adversarial queries with the public output of Gen instead of the output of Fsk, and has
to guess the private string corresponding to one of the public outputs it received. This corresponds
to the game described in the coming section, where all private queries are disallowed.
5.2 Insider Chosen Perturbation Security
Let again # be a family of perturbations over some metric space M as previously defined. We
define an adaptive insider chosen perturbation attack against a fuzzy extractor as the following
game between a challenger and an adversary (which simultaneously describes a computational and
a decisional version of the attack):
Preparation: The adversary specifies to the challenger a random variable W # M.
Randomization: The challenger randomly samples W to obtain a secret word w # M.
Public queries: The adversary presents up to q fuzzy generation queries to the challenger.
The queries are made adaptively. For the i-th public query goes as follows.
The adversary chooses a perturbation # d i # and sends d i to the challenger. The
challenger runs Gen on input word w
using fresh random bits r i , obtaining a
The challenger discards the private string s i , and responds
to the query by giving the public string q i to the adversary.
Private queries: The adversary also presents up to q # fuzzy regeneration queries to the
challenger. These queries are made adaptively and may be interspersed with public
queries. For , the j-th private query goes as follows. The adversary chooses
a perturbation # d # j # and a public string q # j
, and sends both to the challenger. The
challenger runs Reg on input word w
string q # j , obtaining a private
string
]. The challenger responds by giving s # j
to the adversary.
Challenge: At some point, the adversary selects any public string -
that was
returned by the challenger in a previous public query, under the constraint that in any
private query #, -
q# involving - q the perturbation # must have minimum displacement
t. The adversary gives -
q to the challenger.
In the Decisional version only, the challenger then flips a fair coin b # $ {0, 1}. If
it computes the corresponding private string Reg[w # , -
q] and gives it to the adversary,
otherwise it draws a random string #= Reg[w # , -
q] of equal length # and returns it instead.
Additional queries: The adversary may make further public and private queries up to the
respective quotas q and q # . An additional restriction is imposed that no private query
#, -
q# be made on the challenge -
unless # has minimum displacement greater than - t.
Output: The adversary eventually outputs a private string candidate - s. The winning condition
for the adversary is that -
In the Decisional version, the adversary only outputs a single bit - b, and wins if -
We call the adversary A comp in the computational game an OW-Fuz-CPA adversary 1 . For the
decisional version, we refer to the adversary A deci as an IND-Fuz-CPA adversary 2 . If # is the size
of the extracted private strings, we define each adversary's advantage in its respective game as:
Definition 7. Let #Gen, Reg# be a (M,m, #, t, #)-fuzzy extractor. Let A be a (randomized) adversary
for the (computational or decisional) game above, such that H# [W
perturbations are chosen from some family #. Suppose that A runs in time # and makes q public
and q # private queries, and that the private queries involving the challenge public string are further
subject to the minimum displacement requirement minw#M d[w, t.
If for all such OW-Fuz-CPA adversary A we have AdvA #, we say that the fuzzy extractor is
(#, q, q # , - t, #)-one-way secure against adaptive insider chosen perturbation attacks in #.
If for all such IND-Fuz-CPA adversary A we have AdvA #, we say that the fuzzy extractor is
(#, q, q # , - t, #)-indistinguishable against adaptive insider chosen perturbation attacks in #.
Model Rationale. We require the challenge public string -
q to be one of the strings previously
generated by the challenger, rather than any well-formed public string, since the point of the attack
is to break a system under someone else's control, here represented by the challenger. Similarly, the
adverary's objective is to guess the private string for the specific secret w # , as opposed to, say, any
perturbation thereof, since the point of the attack is to impersonate whomever the system was set
up to protect or authenticate. Note that we could allow the target to be any small perturbation of
the secret, but this would not substantially change the security properties thanks to error correction.
In the query phases however, the attacker is given much greater flexibility in its ability to probe
and disturb the challenger using a wide range of perturbations and faulty inputs. This captures
the idea of an adversary set out to "break into the system, by any means necessary".
Minimum Displacements. The reason for the minimum displacement restriction on challenge
private queries is to ward against trivial queries that by design are intended to reveal the target
private string, e.g., #, -
q# for any # whose maximum displacement is no greater than the error
correction distance t. Incidentally we must take - t # t for this to be of any use. The smaller the
di#erence t, the tighter the requirement, and the stronger the resulting security notion.
More generally, it is enough to require that the chosen perturbations for the relevant queries
displace all but a negligible fraction of the points in M by a distance greater than - t (as would, e.g.,
a rotation about the origin). Specifically, the relaxed requirement asks that all perturbation # used
in a private query in conjunction with the challenge public string satisfy P[d[W, #[W
one-wayness of fuzzy extraction against adaptive chosen perturbation attacks.
indistinguishability of fuzzy extraction against adaptive chosen perturbation attacks.
for all random variable W # M with minimum entropy H# [W ] # m. To keep things simple, we
stick with the previously stated definition.
5.3 An Alternative: Random Perturbation Security
Weaker forms of secure reusability can be achieved using relaxed security definitions. For instance,
we can define the notion of a random perturbation attack. Here, instead of answering the queries
using a perturbation function specified by the adversary to produce the perturbed secret w i , the
challenger would sample w i from some distribution, possibly specified by the adversary, conditionally
on the secret w # . For instance, random perturbations could be distributed such that P[w i | w # ]
decreases exponentially with the distance d[w i , w # ].
It may be argued that random perturbations are a plausible model of the physical reality of
imperfect biometric measurements. However, it is not clear how appropriate it models the mental
processes involved in the imperfect recall of a password-e.g., if a user's secret is based on a list of
favorite movies [JS02], the adversary could attempt to selectively distract her memory by playing
movie themes in the computer room while she is entering her secret. In such circumstances, asking
for chosen perturbation security may be erring on the side of caution.
Although this paper does not delve any further into this topic, the notion of security against
random perturbations is worthy of further study.
6 Unconditional Outsider Security From Symmetric Subcodes
Our first general results show that unconditional outsider security can be achieved in a generic way
from codes that feature su#cient "symmetry" with respect to the selected perturbation operator.
6.1 Fundamental Limitations
To temper one's optimism, we start by showing that no viable fuzzy extractor can withstand an
active attack with unrestricted perturbations.
Admissible Perturbations. Suppose that the fuzzy sketch or extractor to break is non trivial,
i.e., there exist two words on which it behaves di#erently. Then the adversary can
recover any q-bit challenger secret w # in only q public queries, using the following perturbation for
query
i.e., the k-th perturbation tests the k-th bit of its input and outputs w 1 or w 2 accordingly.
To avoid giving such an unfair advantage to the adversary, we need a reasonable notion of
perturbation that treats all possible secret words in a comparable way. A natural solution is to
require all perturbations to be isometric permutations. The theorems that follow in this section
show that this is indeed a very natural notion of admissible perturbation.
6.2 Generic Construction
Our reusable fuzzy sketch construction is based on codes with certain symmetry properties, which
we now define.
Weakly Symmetric Subcodes. We previously showed how to break fuzzy sketches and extractors
by exploiting various asymmetries, e.g., in the error correcting code or in the permutation
family (in the case of a permutation based extractor). We need a notion of symmetry in order to
close these loopholes. Since natural definitions of symmetry are based on groups of permutations,
we define the following (very weak) notion of symmetry for a code C based on a permutation group.
Definition 8. Let C be a code in some finite space M. Let Q be a group of permutations in M.
We say that an element # 0 # C is a Q-pivot of C if:
In other words, the set of images of # 0 under the permutations in Q forms a subcode C # C
closed under Q and on which Q acts transitively (i.e., mapping any of its elements to any other).
We emphasize that nothing is said about the e#ect of Q on the remainder of the code C \ C # .
A Generic Fuzzy Sketch. Equipped with the above notion of symmetry, we can construct a
generic fuzzy sketch based on permutations that is unconditionally secure against outsider attacks.
Let C be a (not necessarily linear) code over a metric space M. Let P be a transitive group of
isometric permutations over M. Suppose that C contains a Q-pivot # 0 where Q is some subgroup
of P. We define the generic fuzzy sketch #Fsk, Cor# as follows:
r
r
Here, the assigmnents p 1
r
r
are randomized using di#erent portions of r.
6.3 Information Theoretic Security
The following theorem relates the "entropy loss" achieved by the generic fuzzy sketch to the relative
sizes of P and Q. We see that the construction has an active (outsider) security comparable to the
passive security of the permutation based construction of [DRS04], provided that the chosen code
o#ers enough symmetry for the chosen family of perturbations.
Theorem 9. Let C # M be a (M,K, t)-code in a finite metric space M. Let Q # P be a subgroup
of a transitive isometric permutation group P. Assume that the code C admits a Q-pivot # 0 # C.
Then the generic algorithms #Fsk, Cor# above form a (M,m,m # , t)-fuzzy sketch with unconditional
security against adaptive outsider chosen perturbation attacks in any perturbation family # P,
provided that m-m # log 2 [#P
Proof. First, we show that the above construction is a fuzzy sketch with the required error correction
capabilities. Specifically, we have the following.
9.1. #Fsk, Cor# is a fuzzy sketch with error correction distance # t for all inputs in M.
This already shows the security of the construction in the case of a single sketch or extraction.
Next, we bound the information that an adversary can obtain from repeated identical queries
(i.e., without perturbation). Consider the function Fsk : w # {Fsk[w; r] : #r} that maps any
to the set of values taken by Fsk[w; r] for all possible random drawings of the hidden
randomization parameter r. We successively obtain the following.
9.2. Fsk[w] captures all information about w that can be gathered from an Fsk[w] oracle.
9.3. The map Fsk defines a partition of M into n equivalence classes with n #P/#Q.
9.4. The value of Fsk[w # ] reveals at most log 2 [#P/#Q] bits of information about w # .
It follows that #Fsk, Cor# is a (M,m,m # , t)-fuzzy sketch for any m - m # log 2 [#P/#Q], which
furthermore is unconditionally secure against repeated queries (i.e., a "chosen perturbation" attack
where the only perturbation available to the adversary is the identity map).
Last, we show that the ability to specify perturbations in # P does not provide additional
information to the adversary. Precisely, we show that for any secret w # M, the challenger's
answers to any (multi-)set of chosen perturbation queries in the family # do not collectively contain
more information than Fsk[w # ] itself. Using our previous claims, we find the following.
9.5. The value of Fsk[#[w # is computable from Fsk[w # ] and #.
The security of the generic construction against adaptive chosen perturbation outsider attacks
follows immediately from Claims 9.1, 9.2, 9.4, and 9.5. We refer to Appendix A.1 for detailed proofs
of all the claims.
We then easily obtain an outsider secure fuzzy extractor using the construction of Lemma 4.
Corollary 10. Under the assumptions of Theorem 9, there exists a (M,m, #, t, #)-fuzzy extractor
that is (#, 0, 0, #)-IND-Fuz-CPA secure against adaptive chosen perturbation attacks in #, for
arbitrary # > 0, with
6.4 Generic Tightness
Our next theorem shows that the assumptions of Theorem 9 are "tight", in the sense that if
there exists any fuzzy sketch (not necessarily based on permutations) with outsider security vs.
a su#ciently powerful perturbation family, then we necessarily have all the elements we had to
assume for the generic fuzzy sketch construction to go through.
This theorem serves to show that the requirements from the results of the previous section are
far from being arbitrary.
Theorem 11. Assume that #Fsk, Cor# is a (M,m,m # , t)-fuzzy sketch unconditionally secure against
adaptive outsider chosen perturbation attacks in a family # (containing the identity perturbation).
Suppose that a subset # generates a transitive group P of isometric permutations in M.
Then there exists a subgroup Q # P and a (M,K, t)-code C # M that contains a Q-pivot # 0 # C
with
Proof. Since the challenger responses may be randomized, we start by deterministically characterizing
the information that an unbounded adversary may gather in an outsider attack.
1. We define the function Fsk : w # {Fsk[w; r] : #r} that maps any element w # M to the set
of all possible randomized values of Fsk[w]. The function Fsk is e#ectively computable with
arbitrarily high probability given a black box simulator for Fsk, since with enough queries
one will eventually exhaust the finite set of possible randomization strings used by Fsk.
2. We define the function Fsk : w #, Fsk[#[w]]#} that maps any element w # M to
the relation between the admissible perturbations # and the values taken by Fsk on the
perturbated input #[w]. Since the set # is finite, this function can be computed from Fsk.
We now successively show the following claims.
11.1. Given a randomized oracle for Fsk[#[w # chosen #, the value of w # can be
disambiguated with arbitrarily high probability up to the set of preimages of Fsk[w # ].
11.2. Conversely, the value of Fsk[w # ] captures the total information about w # that can be
gathered from arbitrarily many queries to Fsk[#[w # chosen perturbation in #.
11.3. The number n of equivalence classes induced over M by Fsk is bounded as n # 2 m-m # ,
which case the theorem is vacuous).
11.4. There is a subgroup Q # P that preserves the equivalence structure between classes,
where log 2 [#P] - log 2
Claim 11.5. Each equivalence class C i forms a (M,K, t)-code of size
are all Q-pivots of C i .
The theorem follows from Claims 11.4 and 11.5. We refer to Appendix A.2 for detailed proofs
of all the claims.
6.5 Example: Linear Codes In Hamming Spaces
Let M be the n-dimensional vector space F n
p with the Hamming metric d : M-M# {0, 1, ., n},
and suppose that C # M is a linear p-ary [n, k, d]-code in that space. Let P be the transitive
isometric permutation group of all maps Q be the
subset of maps # p # P such that p # C. Since the code C is linear, it is easy to see that Q is closed
under function inversion and function composition; Q is thus a subgroup of P, and any element
a Q-pivot of C. We have . By Theorem 9 the
generic construction of Section 6.2 immediately gives us a (M,m,m # , t)-fuzzy sketch unconditionally
secure against outsider attacks with
Corollary 10 we get a (M,m, #, t, #)-fuzzy extractor unconditionally secure against outsider attacks
with binary output size
In the binary case F is easy to show that this construction precisely reduces to the
JW-DRS fuzzy extractor previously mentioned. This proves that the JW-DRS construction is
unconditionally secure against outsider attacks provided that it is used with a linear code.
We note that the use of linear codes for reconstructing imperfectly shared secret information has
been extensively studied, e.g., in the context of privacy amplification and information reconciliation
[BBR88, BBCM95]. It has also been observed in [DRS04] that the fuzzy commitment scheme of
[JW99] described in Section 3.3 reduces when applied on a linear code to a deterministic fuzzy
sketch equal to the code's syndrome function
6.6 Counterexample: Text Edit Distance
Dodis et al. [DRS04] also present a fuzzy sketch construction for text, based on the notion of
edit distance. Roughly speaking, the edit distance between two texts A and B is the length of
an "edition script" that turns A into B using combinations of three basic commands: insertion,
deletion, and displacement of sequences of characters at specified locations in the text.
A natural choice for the family of perturbations is the set of all edition scripts, possibly with a
length restriction. Unfortunately, it is easy to see that this gives too much power to the adversary.
Consider the script Subst[char, pos] that substitutes the supplied character char for the character
at the given position pos in the text. It is easy to see that the instantiation of this script for specific
char and pos gives a perturbation that allows the adversary to test whether the pos-th character
in the secret text is equal to char. This allows the adversary to quickly recover the hidden secret
text character by character, in a similar way as in the example given in Section 6.1.
7 Ideal Insider Security Through Random Hashing
We now convert an unconditionally outsider secure fuzzy sketch, such as the one of the previous
section, into a fuzzy extractor with insider security using random oracles [BR93]. The security is
no longer unconditional, but is "ideal" in the sense that all incurred security losses result either
from random collisions or from the adversary's ability to defeat the randomness assumption.
Recall how in our previous construction we arranged to confine all public queries to a symmetric
subcode steering clear from any potentially recognizable "landmark" lurking in C \ C # .
Unfortunately, private queries cannot be confined so easily, as a clever query #, q# can always cause
any secret w # to be corrected to any codeword in C, not just C # . However, we can randomly shu#e
things around at decoding time to render all codewords indistinguishable up to permutations in Q,
thereby preventing too much information from being leaked. Nevertheless, by the Q-symmetry of
the subcode C # , any legitimate query that only involves codewords in the subcode will be impervious
to the randomization. See Appendix B for a more detailed explanation.
Let thus # 0 # C # M and Q # P be as in Section 6. First, we define the fully randomized
generic fuzzy sketch #Fsk, Cor# as follows:
r
r
for random # Q .
Again, the assigmnents p 1
r
r
are randomized using di#erent portions of r.
Next, assuming a random oracle H, we define the full generic fuzzy extractor #Gen, Reg# as
follows:
Here, H is a hash function treated as a random oracle in the analysis, with inputs in M-{0, 1} #
{0, 1} # and outputs in {0, 1} # . We assume that the random input r # is drawn from some {0, 1} #
and that the representation of the fuzzy sketch p fits in {0, 1} # .
Notice that both functions Fsk and Cor are now randomized, and thus so are Gen and Reg.
Theorem 12. Under the conditions of Theorem 9 where the code C has error correction limit # - t,
the algorithms #Gen, Reg# constitute a (M,m, #, t, #)-fuzzy extractor, for any # 2 #-m # , that is
(#, q # , - t, #)-OW-Fuz-CPA and IND-Fuz-CPA secure whenever # q #
#, in the
random oracle model, where q # also includes direct queries to the random oracle.
Proof. The stated bound on # follows immediately from the fact that a random oracle is an optimal
#)-randomness extractor, and thus m # - 2 log 2
[#] +O[1] per [RTS97].
The rest of the proof is an information theoretic argument that bounds the knowledge available
to the adversary under the stated randomization of Reg. See Appendix B for details.
It is currently an open problem to achieve OW-Fuz-CPA security without random oracles.
8 "Zero Storage" Remote Biometric Authentication
To demonstrate the power of the reusable fuzzy extractor machinery, we briefly present a remote
biometric authentication protocol with third party certification, that does not require Alice to
securely or insecurely store anything-other than her fuzzy secret.
Suppose that Alice wishes to remotely authenticate herself to Bob using biometrics. Due to privacy
concerns, she does not wish to reveal any of them to Bob (even if he does not play the protocol
by the rules, and/or colludes with other Bobs against her). Conversely, for the authentication to
be meaningful, Bob wants some assurance that Alice is in fact in possession of her purported biometrics
at the time the authentication is taking place (i.e., that nobody is impersonating her). We
assume that there is a third party, Trent, whom Bob trusts to honestly certify Alice's biometrics,
and to whom Alice will temporarily grant access to her biometrics for the purpose of generating
such a certificate. Alice will want to be able to obtain as many or as few of those certificates as she
wants, and to reuse as many of them with multiple Bobs, some of whom may be dishonest, without
fearing privacy leaks or risking impersonation. The protocol is as follows.
Certification: Under Trent's supervision, and using Alice's own secret biometrics
1. Alice generates a random string pair #s, q# Gen[w # ] using an insider secure fuzzy
extractor as that of Section 7;
2. Alice derives the public key pbk s
that corresponds to the private string s viewed as a
private key in some existentially unforgeable (UF-CMA) signature scheme #Sign, Verify#.
(If s is not a legitimate private key, one is deterministically derived from it first).
If Trent is satisfied that Alice has executed the steps honestly, he certifies the binding between
Alice's name and the public key pbk s , i.e., he signs the pair #``Alice'', pbk s #. In the sequel, we
take pbk s to denote the public key accompanied with its certificate.
At this point, Alice may send the pair #q, pbk s # to Bob, or even publish it for everyone to see.
Challenge: At any time when appropriate (e.g., whenever Alice desires to authenticate to Bob),
sends Alice a fresh random challenge c nonce and reminds her of her public string q.
Response: Using what Bob claims to be her public string q, and an approximation of her fuzzy
secret biometrics -
Alice responds to the challenge as follows:
1. Alice recovers her private string - s # Reg[ -
2. Alice signs the challenge and gives Bob the signature s nonce # nonce ].
Verification: Bob authenticates Alice by checking the validity of the signature under her authentic
public evaluating nonce , s nonce ].
Other black box identification schemes can be substituted for the last three steps.
The important point is that the protocol does not require Alice to "remember" anything other
than her fuzzy secret (and in particular does not have to obtain Trent's authentic public key to
verify a certificate). Alice's credentials remain secure in an attack where Alice is given corrupted
q by a malicious Bob.
Analysis. The protocol passes muster with Bob in that it properly authenticates Alice.
Indeed, since the signatures are existentially unforgeable, we have non-repudiation, and, thus,
knowledge of the private key is required to properly respond to a new challenge.
The protocol is also to Alice's taste in terms of protection of her privacy, at least against a
computationally bounded adversary. Regarding certification, since the signature scheme is secure,
we know that neither pbk s nor the signatures created from s computationally reveal anything about
the private string s. Thus, in the adversary's view, each instance of the certification phase reduces to
nothing more than a public query in the insider game of Section 5.2. Regarding the authentication
handshakes, there are two cases to consider: whether Bob honestly or dishonestly "reminds" Alice
of her public string q. In the honest case, Alice's responses to Bob are safe, since when she uses
the correct q she creates a signature under her genuine private key s, which as we noted earlier
does not computationally leak anything about s. In the dishonest case, the fuzzy extractor's insider
security property ensures that, for any bogus public string q #= q of Bob's crafting, Alice will not
leak any computational knowledge about s by recreating an (incorrect) private string s # using q # .
Signatures generated from s # are a fortiori devoid of useful information.
The above properties continue to hold if Alice uses the same certificate with multiple Bobs, or
conversely obtains multiple certificates and uses them with the same correspondent.
Related Key Attacks. Observe that we need a fuzzy extractor with insider security for the
following (rather counter-intuitive) reason: although we know that issuing signatures under UF-
CMA signature scheme does not computationally leak the private key, we cannot assume that this
remains the case when signatures are also issued under other, related private keys. If the signature
is well behaved in this respect then a (suitably defined) outsider secure fuzzy extractor su#ces for
this application.
9 Conclusion
We have studied the question of generating keys of cryptographic quality from non uniformly
distributed, non perfectly reproducible "fuzzy" processes, focusing on the notions of fuzzy sketches
and fuzzy extractors. Dealing with fuzzy secrets is a problem of great practical significance in
applications where security relies at least in part on fuzzy secrets such as biometric measurements
or imperfectly memorized passwords.
We demonstrated with a number of simple attacks that the existing definitions and constructions
are inadequate and may lead to a total break of security in any circumstance where one is compelled
to reuse the same fuzzy secret-which severely undermines their adequacy for biometrics.
We introduced two strong security models for fuzzy sketches and extractors that allow reusable
secrets; in the first model the adversary is an outsider, and the other in which it is an insider. Our
models are based on the security notion of "chosen perturbation attack".
We presented generic outsider secure fuzzy sketch and extractor constructions, and precisely
characterized the conditions under which information theoretic security can be achieved.
We then extended our method to handle the case of insider attacks, and showed how to transform
any outsider secure fuzzy sketch into an insider secure fuzzy extractor using random oracles.
We finally illustrated the power of our model with a simple zero storage fuzzy authentication
protocol that remains secure even if the secret holder is unable or unwilling to remember anything
but her fuzzy secret.

Acknowledgements

The author thanks Yevgeniy Dodis and Jonathan Katz for insightful comments.



--R

Generalized privacy amplifi- cation
Privacy amplification by public discussion.
Random oracle are practical: A paradigm for designing e

On enabling secure applications through
Fuzzy extractors and cryptography
Fuzzy extractors: How to generate strong keys from biometrics and other noisy data.
Protecting keys with personal entropy.

A pseudorandom generator from any one-way function
A fuzzy vault scheme.
A fuzzy commitment scheme.
Password hardening based on keystroke dy- namics
Randomness is linear in space.
Tight bounds for depth-two superconcentrators
Recent developments in explicit constructions of extractors.

"map"

--TR
Privacy amplification by public discussion
Pseudo-random generation from one-way functions
Random oracles are practical
Randomness is linear in space
A fuzzy commitment scheme
Password hardening based on keystroke dynamics
Protecting secret keys with personal entropy
password recovery
Tight bounds for depth-two superconcentrators

--CTR
Ileana Buhan , Jeroen Doumen , Pieter Hartel , Raymond Veldhuis, Fuzzy extractors for continuous distributions, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
Ee-Chien Chang , Ren Shen , Francis Weijian Teo, Finding the original point set hidden among chaff, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
fuzzy extractor;chosen perturbation security;biometric keying;zero storage biometric authentication