A Fuzzy Vault Scheme
`
`Ari Juels1 and Madhu Sudan2
`
`1 RSA Laboratories
`Bedford, MA 01730, USA
`E-mail: ajuels@rsasecurity.com
`2 MIT Laboratory for Computer Science
`200 Technology Square, Cambridge, MA 02139
`E-mail: madhu@mit.edu
`
`Abstract. We describe a simple and novel cryptographic construction
`that we refer to as a fuzzy vault. A player Alice may place a secret value
`(cid:20) in a fuzzy vault and \lock" it using a set A of elements from some
`public universe U . If Bob tries to \unlock" the vault using a set B of
`similar length, he obtains (cid:20) only if B is close to A, i.e., only if A and B
`overlap substantially. In constrast to previous constructions of this (cid:13)avor,
`ours possesses the useful feature of order invariance, meaning that the
`ordering of A and B is immaterial to the functioning of the vault. As
`we show, our scheme enjoys provable security against a computationally
`unbounded attacker.
`
`Keywords: biometrics, error-correcting codes, fuzzy commitment, fuzzy vault
`
`1 Introduction
`
`Alice is a movie lover. She is looking to (cid:12)nd someone who shares her taste in
`movies, but does not want to reveal information about her preferences indis-
`criminately to other people. One approach she might take is to compile a set
`A of her favorite movies and publish it in a concealed form. For instance, Alice
`might post to a Web newsgroup a ciphertext CA representing an encryption of
`her telephone number telA under the set (here, key) A. In this case, if another
`person, say Bob, comes along with a set B of his own favorites that is identical
`to A, then he can decrypt CA and obtain Alice’s phone number. If Bob tries to
`decrypt CA with a set di(cid:11)erent than Alice’s, he will fail to obtain her telephone
`number. A drawback to this approach is its exactitude, or lack of error-tolerance.
`If Bob’s interests are very similar to Alice’s, e.g., if he likes two or three (cid:12)lms
`that Alice doesn’t, then he will not learn telA. It seems very likely in this case,
`though, that Alice would still like Bob to obtain her telephone number, as their
`tastes are quite similar.
`In this paper, we introduce the notion of a fuzzy vault. This is a cryptographic
`construction whereby Alice can lock her telephone number telA using the set A,
`yielding a vault denoted by VA. If Bob tries to unlock the vault VA using his
`own set B, he will succeed provided that B overlaps largely with A. On the
`
`USR Exhibit 2018, Page 1
`
`

`

`other hand, anyone who tries to unlock VA with a set of favorite movies di(cid:11)ering
`substantially from Alice’s will fail, helping to ensure that Alice’s set of favorites
`remains private. Thus, a fuzzy vault may be thought of as a form of error-tolerant
`encryption operation where keys consist of sets. Our fuzzy vault proposal has
`two important features that distinguish it over similar, prior work. First, the
`sets A and B may be arbitrarily ordered, i.e., true sets rather than sequences.
`Second, in contrast to previous work, we are able to prove information-theoretic
`security bounds over some natural non-uniform distributions on the set A.
`Error-tolerant cryptographic algorithms are useful in many circumstances
`in which security depends on human factors, and thus exactitude represents a
`drawback. We o(cid:11)er just a few examples here, all of which might bene(cid:12)t from use
`of our fuzzy vault scheme:
`
`1. Privacy-protected matching: As an extension of our movie lover’s exam-
`ple above, we might consider a business scenario. Bisco Corp. is looking to
`sell routers possessing a set A = fa1; a2; : : : ; akg of speci(cid:12)cations. It might
`publish a fuzzy vault VA with its identity (cid:20), locked under A. If Disco Corp. is
`looking for routers with a set B of similar speci(cid:12)cations, then it will be able
`to open the vault. Anyone who tries to unlock the vault with a dissimilar set
`will not learn (cid:20). (We address this idea in detail later in the paper, and decribe
`an important security enhancement using on-line throttling mechanisms.)
`2. Personal entropy systems: Proposed by Ellison et al. [10], this is a system
`that enables users to recover passwords by answering a series of questions.
`In recognition of the unreliability of human memory, the system permits
`users to answer some of these questions incorrectly. A serious vulnerability
`in this system is exposed in [4], who show more broadly that the underlying
`hardness assumption is weak. Our fuzzy vault scheme o(cid:11)ers an alternative
`implementation that is provably secure in an information-theoretic sense and
`that may involve use of sets, and not just (cid:12)xed-order answers.
`3. Biometrics: Alice authenticates to her server using (cid:12)ngerprint information.
`Her system administrator wishes to store her (cid:12)ngerprint on the server or,
`more precisely, a set A of features characterizing her (cid:12)ngerprint. (Such sets
`are known as biometric templates.) If an attacker breaks into the server,
`however, Alice does not want her template A compromised. An additional
`complication is that biometric systems are error-prone: When Alice tries to
`authenticate herself, her (cid:12)ngerprint reader is likely to produce a template
`A0 that is similar to, but not identical to A (with bit errors and random
`permutation and erasure of elements). Alice might store a PIN locked in a
`fuzzy vault on a set A of features describing her (cid:12)ngerprint, thereby achieving
`both error-tolerance and privacy. Note that order-invariance is critical here.
`It is usually not possible to impose an order e(cid:11)ectively on biometric features
`because of the problem of erasures. For this reason, previous schemes like
`that of Juels and Wattenberg [15] described below are unlikely to work well
`for this problem.
`
`USR Exhibit 2018, Page 2
`
`

`

`1.1 Previous work
`
`A somewhat less na(cid:127)(cid:16)ve approach to a fuzzy vault construction than straightfor-
`ward encryption might be achieved through use of Shamir secret sharing tech-
`niques [23]. Alice partitions her secret value (cid:20) into shares s1; s2; : : : ; sn, and
`encrypt these shares respectively under each of the elements a1; a2; : : : ; an in her
`set A. This would yield a set of ciphertexts e1; e2; : : : ; en. Given use of a (t; n)-
`secret sharing scheme, Bob would only need to decrypt t shares successfully in
`order to unlock Alice’s secret (cid:20). The problem with this approach is twofold.
`First, suppose that Bob’s set B consists of elements b1; b2; : : : ; bn. Because A
`and B are unordered sets, Bob has no way of knowing which of the ciphertexts
`ei to try to decrypt with a given set element bj. Even if Bob tries all n2 pos-
`sible decryption operations, there is a second problem: He still does not know
`which decryptions were successful. Straightforward mechanisms to reveal this
`information to Bob leak substantial information about A. Indeed, this may be
`regarded as the source of the weakness in, e.g., the Ellison et al. construction. It
`is also possible for Bob to try to deduce by means of a brute-force search which
`elements of B do not overlap with those of A. This strategy is in(cid:13)exible and
`likely to be prohibitively slow in many practical scenarios, as the computational
`
`requirements grow exponentially in the size of jAT Bj.
`
`Another idea that does not work well is that of imposing a common order-
`ing on the sets A and B and then using a fuzzy vault construction or similar
`technique that does not have the property of order invariance, e.g., [15]. This
`appeoach fails because a small di(cid:11)erence between sets can produce large di(cid:11)er-
`ences in an ordered element-by-element comparison. Suppose, for example, that
`A and B again represent respective lists of Alice and Bob’s favorite movies. If Al-
`ice and Bob’s favorites include all Oscar winners, except that Alice does not like
`Antonia’s Line, then a movie-by-movie comparison of these lists in alphabetical
`order will yield almost no matches, while in fact A and B overlap consider-
`ably. This problem also applies to attempts to impose ordering on features in
`biometric systems.
`To overcome these di(cid:14)culties, we invoke error-correcting codes as the basis
`for our construction. Given the strong technical and historical a(cid:14)nities between
`error-correcting codes and cryptographic codes, it is not surprising that error-
`correcting codes appear in many areas of cryptography, such as quantum cryp-
`tography [2, 6], public-key cryptography (via the well known McEliece cryptosys-
`tem) [18], identi(cid:12)cation schemes [26], digital signature schemes [1], and crypt-
`analytic techniques [13], just to name a few examples. We do not explore this
`extensive branch of the literature here. We note, however, that Reed-Solomon
`codes, the most popular form of error-correcting code and the one we focus on
`here, may be viewed as a general, error-tolerant form of Shamir secret sharing.
`The starting point for our fuzzy vault construction is the fuzzy commitment
`scheme of Juels and Wattenberg [15], which is also based on the use of error-
`correcting codes. This is a cryptographic primitive whereby a user commits to
`a secret value (cid:20) under a key x. The user may decommit using any key x0 that
`is \close" to x under some suitable metric, such as Hamming distance. An at-
`
`USR Exhibit 2018, Page 3
`
`

`

`tacker without any knowledge of x, however, cannot feasibly decommit (cid:20). One
`application of fuzzy commitment, as suggested by the authors, is to securing
`biometric systems, as described above. An enrolled (cid:12)ngerprint image (known as
`a template), for example, might be viewed as a key x. The user tries to authen-
`ticate using another, slightly di(cid:11)erent image of the same (cid:12)nger, which we may
`denote by x0. Authentication is successful if and only if x0 is \close" to x.
`As the fuzzy commitment scheme in [15] is antecedent to our own, it is worth
`brie(cid:13)y sketching the details. Let F be a (cid:12)eld, and C be the set of codewords
`for some error-correcting code; assume that codewords lie in F n. To commit
`to a value x 2 F n, the user selects a codeword c uniformly at random from C
`and computes an o(cid:11)set of the form (cid:14) = c (cid:0) x 2 F n, i.e., the di(cid:11)erence over
`individual (cid:12)eld elements. The commitment then consists of the pair ((cid:14); y), where
`y = h(c) for some suitable one-way function h. To decommit using key x0, the
`user computes (cid:14) + x0 and, if possible, decodes to the nearest codeword c0. The
`decommitment is successful i(cid:11) h(c0) = y.
`The construction in [15] has the advantageous features of conceptual simplic-
`ity and the ability to make use of any underlying error-correcting code. Moreover,
`provided that x is drawn uniformly at random from F n, the scheme enjoys rigor-
`ously proveable security linear in the cardinality of C. Suppose that the attacker
`gains no information about c or x from y, as would be the case under a random
`oracle assumption on h given su(cid:14)ciently large security parameters. It is easy to
`see then that the task of the attacker is to guess c uniformly over C. A similar,
`less resilient antecedent scheme is proposed in [7, 8], while another system with
`similar goals but no rigorously provable security characteristics is proposed in
`[24, 25].
`Note that if the hashed value h(c) is removed from the Juels and Watten-
`berg scheme, i.e., if we no longer think of it as a commitment scheme, then we
`obtain a kind of fuzzy vault in which the vault itself is equal to (cid:14). If x is uni-
`formly distributed, then the scheme enjoys easily provable information-theoretic
`security, i.e., security against a computationally unbounded attacker (also pro-
`portional to the cardinality of C). Like our own fuzzy vault construction, this
`one can also be applied to any of the three practical scenarios described above,
`i.e., privacy-protected matching, personal entropy systems, or biometrics.
`As a fuzzy vault variant, though, the scheme of Juels and Wattenberg has two
`shortcomings. First, while it tolerates some number of errors in the information
`symbols in x, it does not tolerate substantial re-ordering of these symbols. Given
`that translation and rotation errors are common in, e.g., biometric systems, it is
`reasonable to expect that the image x0 may consist of a permutation of symbols
`in x. The property of order-invariance is thus likely to be desirable in a fuzzy
`commitment scheme. A second shortcoming of [15] is the di(cid:14)culty of proving
`rigorous results about security over non-uniform distributions. Our proposed
`scheme addresses these two shortcomings, and may be thought of as an order-
`invariant version of the Juels-Wattenberg scheme.
`The present work has appeared previously in the form of a one-page abstract
`
`[?].
`
`USR Exhibit 2018, Page 4
`
`

`

`1.2 Our scheme
`
`Like the scheme of Juels and Wattenberg, ours is conceptually simple, and can
`be implemented using any underlying error-correcting code (although we focus
`on Reed-Solomon codes in our exposition here). While possessing the advantages
`of order-invariance and easier analysis on non-uniform distributions, our scheme
`does have a couple of drawbacks that are important to note from the outset.
`First, it typically has substantially greater { though still quite practical { mem-
`ory requirements than the Juels-Wattenberg scheme. Second, it is somewhat less
`(cid:13)exible in terms of available parameter choices at a given security level, as we
`shall see.
`Let us brie(cid:13)y sketch the intuition behind our scheme. Suppose that Alice
`aims to lock a secret (cid:20) under set A. She selects a polynomial p in a single
`variable x such that p encodes (cid:20) in some way (e.g., has an embedding of (cid:20)
`in its coe(cid:14)cients). Treating the elements of A as distinct x-coordinate values,
`she computes evaluations of p on the elements of A. We may think of Alice as
`projecting the elements of A onto points lying on the polynomial p. Alice then
`creates a number of random cha(cid:11) points that do not lie on p, i.e., points that
`constitute random noise. The entire collection of points, both those that lie on
`p and the cha(cid:11) points, together constitute a commitment of p (that is, (cid:20)). Call
`this collection of points R. The set A may be viewed as identifying those points
`in R that lie on p, and thus specifying p (and (cid:20)). As random noise, the cha(cid:11)
`points have the e(cid:11)ect of concealing p from an attacker. They provide the security
`of the scheme.
`Suppose now that Bob wishes to unlock (cid:20) by means of a set B. If B overlaps
`substantially with A, then B identi(cid:12)es many points in R that lie on p, so that Bob
`is able to recover a set of points that is largely correct, but perhaps contains a
`small amount of noise. Using error correction, he is able to reconstruct p exactly,
`and thereby (cid:20). If B does not overlap substantially with A, then it is infeasible
`for Bob to learn (cid:20), because of the presence of many cha(cid:11) points. (If B overlaps
`\somewhat", then he may still be able to recover (cid:20). The gap between feasible
`recovery and infeasible is fairly small, however, as we discuss below.) We present
`details and analysis in the body of the paper.
`The hardness of our scheme is based on the polynomial reconstruction prob-
`lem, a special case of the Reed-Solomon list decoding problem [4]. Other schemes
`making use of this problem include, for example, the scheme proposed by Mon-
`rose, Reiter, and Wetzel for hardening passwords using keystroke data [19]. An
`important di(cid:11)erence between our scheme and previous ones of this (cid:13)avor is our
`range of parameter choices. The [19] scheme bases its security on the compu-
`tational hardness of small polynomial reconstruction instances, while we select
`parameters enabling us to achieve information theoretic security guarantees for
`the same problem.
`
`Organization
`
`We sketch protocol and security de(cid:12)nitions for our scheme in section 2. In sec-
`tion 3, we present protocol details for our fuzzy vault scheme. We o(cid:11)er security
`
`USR Exhibit 2018, Page 5
`
`

`

`analysis in section 4, and conclude brie(cid:13)y with some implementation ideas in
`section 5. Security proofs are included in the paper appendix.
`
`2 De(cid:12)nitions and Background
`
`We work over a (cid:12)eld F of cardinality q and a universe U; for convenience, we
`assume in our exposition that U = F, although this need not be the case in
`generally. Our aim is to lock a secret value (cid:20) 2 F k under a secret set A 2 U t =
`F t, for protocol parameters k and t. We consider a fuzzy vault algorithm Lock
`that takes as input a secret (cid:20) and set A and outputs a vault VA 2 F r for some
`security parameter r. The algorithm Lock may be (and for our purposes will
`be) probabisetic.
`A corresponding decryption algorithm Unlock takes as input a vault VA 2
`F r and a decryption set B 2 U t. The output of this algorithm is a plaintext
`value (cid:20)0 2 F k, or else 0null0 if the algorithm is unable to extract a plaintext.
`Our goal is to come up with a pair of vault locking/unlocking algorithms
`Lock/Unlock that allows reconstruction of the plaintext (cid:20) when the decryp-
`tion set B is close to the encryption set A. At the same time, we want the vault
`VA not to reveal (cid:20). Recall from above that we are interested in algorithms that
`are order invariant. In other words, the ordering on the sets A and B should
`have no real impact on the locking and unlocking procedures.
`
`2.1 Requirements
`
`The next three de(cid:12)nitions formalize the requirements of a good pair (Lock; Unlock)
`of algorithms for our fuzzy vault scheme. We say that a probability is negligible
`if it is asymptotically smaller than any positive polynomial in t and r. We say
`that a probability is overwhelming if it is larger than 1 (cid:0) (cid:16) for some negligi-
`ble quantity (cid:16). Our (cid:12)rst de(cid:12)nition outlines the completeness condition for our
`algorithms, i.e., what should happen when the players are honest.
`
`De(cid:12)nition 1. An locking/unlocking pair (Lock; Unlock) with parameter set
`(k; t; r) is complete with (cid:15)-fuzziness if the following holds. For every (cid:20) 2 F k
`and every pair of sets A; B 2 U t such that jA (cid:0) Bj (cid:20) (cid:15), it is the case that
`Unlock(B; Lock(A; (cid:20))) = (cid:20) with overwhelming probability.
`
`We now formalize the security, and in particular the soundness of the algo-
`rithmic pair (Lock; Unlock) in an information-theoretic sense. Assume that A
`is selected according to some potentially non-uniform distribution d. We seek to
`characterize the ability of an attacker with unlimited computational power to
`determine (cid:20) from Lock(A; (cid:20)). We assume that this attacker is given knowledge
`of a uniformly random (cid:14)-fraction of A, i.e., a random subset A0 of at most (cid:14)t
`elements in A (where we assume (cid:14)t to be an integer). This assumption that the
`adversary has knowledge of part of the secret key A is slightly unorthodox. In a
`
`USR Exhibit 2018, Page 6
`
`

`

`\fuzzy" system, however, it is natural to consider such notions of partial adver-
`sarial knowledge, as highlighted in our examples below. Of course, other security
`assumptions are possible.
`We characterize security in terms of the following experiment with a compu-
`tationally unbounded adversary Adv for a given parameter set. This adversary
`Adv takes as input a set of (cid:14)t elements of A, the parameters t and k, and
`a vault VA on A, and outputs a guess at (cid:20). Formally, Adv is an algorithm
`Adv : U (cid:14)t (cid:2) Z 2 (cid:2)F r ! F k with no bound on computational complexity. Let 2d
`denote selection from probability distribution d, and 2U denote uniform random
`selection. Here, and in all analysis that follows, we assume that (cid:20) is generated
`uniformly at random, as (cid:20) is typically used as a key for some independent ci-
`phertext or cryptographic protocol. Let fAgi denote the set of subsets of A of
`cardinality i. The experiment is as follows.
`
`Experiment Attack(Lock; Adv)
`(cid:20) 2U F k; A 2d U t; A0 2U fAg(cid:14)t;
`if Adv(A0; t; k; Lock(A; (cid:20))) = (cid:20)
`Output010;
`else
`Output000;
`
`This leads to the following de(cid:12)nition.
`
`De(cid:12)nition 2. An encryption/decryption pair (Lock; Unlock) is information
`theoretically secure with parameter pair ((cid:14); (cid:22)) if pr[Attack(Lock; Adv) = 1] (cid:20) (cid:22)
`for any computationally unbounded adversary Adv.
`
`Let d0 be the probability distribution d restricted to sets A such that A0 (cid:26) A.
`Observe that given vault VA, the best strategy a (computationally unbounded)
`adversary can adopt is to output a plaintext (cid:20)0 such that the expression
`
`w((cid:20)0; VA) = prA2d0 U t[Lock(A; (cid:20)0) = VA]
`
`is maximized. For a given vault VA = Lock(A; (cid:20)), the probability of success of
`
`this strategy is easily seen to be w((cid:20); VA)=P(cid:20)02F k w((cid:20)0; VA).
`
`Remark: Note that our de(cid:12)nition of information theoretic security does not nec-
`essarily imply that the secret (cid:20) is fully protected in an information theoretically
`secure manner. In particular, we may have mutual information I(Lock; (cid:20)) > 0.
`This is to say that our scheme may o(cid:11)er information theoretic hiding of (cid:20) over
`a set of possible values smaller than F k.
`
`2.2 Reed-Solomon codes
`
`It is possible to construct a fuzzy vault scheme based on essentially any type of
`linear error-correcting code. To sharpen our conceptual focus and analysis, how-
`ever, we restrict our attention to Reed-Solomon (R-S) codes. We are interested
`
`USR Exhibit 2018, Page 7
`
`

`

`primarily in (k; t)-codes, i.e., those in which codewords consist of t information
`symbols, i.e., (cid:12)eld elements. Each codeword corresponds to a unique polynomial
`p of degree less than k over F; thus there are qk codewords in total. In the
`simplest embodiment of such an R-S code, we may express a codeword as the
`sequence fy1 = p(1); y2 = p(2); : : : ; yt = p(t)g, where 1; 2; : : : ; t represent the
`(cid:12)rst t elements of the (cid:12)eld F.
`If t > k, then a codeword may be seen to contain some redundancy. The
`presence of such redundancy is what permits the code to be used for error cor-
`
`
`
`2; : : : ; y0rection. Suppose that c0 = fy01; y0 tg is a corruption of the codeword c. In
`other words, we have y0
`i 6= yi for some (cid:15)-fraction of the information symbols
`in c0. Provided that (cid:15) is small enough, the redundancy of the code is such that
`given just the corrupted codeword c0, we can recover the original codeword c. For
`this, we use a decoding algorithm that we denote by RSdecode. The algorithm
`RSdecode takes c0 as input, and provided that too much corruption has not
`occurred, outputs c.
`The most common application of a Reed-Solomon or other error-correcting
`code is to message transmission over a noisy channel. For this, the procedure is
`as follows. The sender takes a message (cid:20) 2 F k and encodes it as a polynomial
`of degree at most k. The sender computes the corresponding codeword c and
`transmits it over a noisy channel. The noise on the channel causes a corrupted
`codeword c0 to be obtained by the receiver. The receiver applies RSdecode to
`c0, obtains c, and recovers the original polynomial p and thus the message (cid:20).
`As we shall see, in our scheme we may think of the noise on the channel as
`arising from di(cid:11)erences between the sets A and B. By guessing A inaccurately,
`Bob introduces noise into the channel transmitting (cid:20). (In contrast, the fuzzy
`commitment scheme in [15] never actually makes explicit use of the message
`space.)
`
`2.3 Our special use of Reed-Solomon codes
`
`For our constructions, it is convenient to consider a generalization of Reed-
`Solomon codes. We think of a codeword as consisting of an evaluation of a
`polynomial p over any set of t distinct points in F. In other words, we think of
`
`a codeword as consisting of a set of pairs f(xi; yi)gti=1, where xi 2 F, all of the
`xi are distinct, and yi = p(xi).
`In this generalized view, the decoding algorithm RSdecode takes as input a
`collection of points which are presumed to lie preponderantly on a single polyno-
`mial of pre-speci(cid:12)ed degree at most k(cid:0) 1. The RSdecode algorithm, if successful,
`outputs a polynomial p intersecting the large majority of input points.3 Oth-
`erwise, the algorithm outputs 0null0. This will happen, for instance, if no poly-
`nomial of the right degree matches the inputs adequately, or if computation of
`such a polynomial is too hard because of too much corruption of the associated
`codeword. The following are parameter speci(cid:12)cs for the algorithm RSdecode.
`3 So-called set decoding algorithms may in fact produce a set of candidate polynomials.
`We assume that a successful algorithm outputs one of these selected uniformly at
`random from the entire set.
`
`USR Exhibit 2018, Page 8
`
`

`

`Public parameters: A (cid:12)eld F.
`
`xi; yi 2 F for 1 (cid:20) i (cid:20) t.
`
`Input: A degree parameter k (cid:20) q and a set of points Q = f(xi; yi)gti=1 such that
`
`Output: A polynomial p of degree less than k over F, or else 0null0. We write RSdecode(k; Q)
`to denote the output on inputs k and Q.
`
`For our (practical) purposes, the best choice for RSdecode is generally the
`classical algorithm of Peterson-Berlekamp-Massey [3, 17, 21]. This algorithm
`decodes successfully if at least k+t
`2 points in Q share a common polynomial.
`The best version of RSdecode to date, i.e., the one most likely to recover p
`successfully, is that of Guruswami and Sudan [12]. This algorithm successfully
`determines p provided that the number of points in Q that lie on p is at least
`pkt. Our preference for the classical algorithm is based on the fact that this
`algorithm is in general much more e(cid:14)cient than the Guruswami-Sudan, and has
`the advantage of being well studied and widely implemented. Moreover, for many
`of the parameter choices we are likely to encounter in practice, k+t
`is fairly close
`to pkt.
`2
`
`3 The Fuzzy Vault Algorithms
`
`We are now ready to detail our locking and unlocking algorithms for our fuzzy
`vault scheme. We (cid:12)rst present the algorithm Lock. The basic idea here is to
`create a generalized Reed-Solomon codeword representing the secret (cid:20) (as a
`corresponding polynomial p). This codeword is computed over x-coordinates
`corresponding to elements in the set A. To conceal the codeword, we add cha(cid:11)
`points, i.e., random noise in the form of random (xi; yi) pairs.
`In our exposition here, we assume some straightforward, publicly agreed-
`upon method for representing the secret (cid:20) as a polynomial (e.g., taking the
`information symbols in (cid:20) to be the coe(cid:14)cients of the polynomial). We simply
`write p (cid:20) to represent this conversion. We let 2U denote uniformly random
`selection from a set.
`
`Public parameters: A (cid:12)eld F, a Reed-Solomon decoding algorithm RSdecode.
`Input: Parameters k; t; and r such that k (cid:20) t (cid:20) r (cid:20) q. A secret (cid:20) 2 F k. A set
`
`A = faigti=1, where ai 2 F.
`
`
`Output: A set R of points f(xi; yi)gri=1 such that xi; yi 2 F.
`
`Algorithm Lock
`X; R (cid:30);
`p (cid:20);
`for i = 1 to t do
`(xi; yi) (ai; p(ai));
`X X bigcup xi;
`R R S (xi; yi);
`
`USR Exhibit 2018, Page 9
`
`

`

`for i = t + 1 to r do
`xi 2U F (cid:0) X ;
`yi 2U F (cid:0) fp(xi)g;
`R R S (xi; yi);
`output R;
`
`So as not to leak information about the order in which the xi are chosen, the set
`R may be output in a pre-determined order, e.g., points in order of ascending
`x-coordinates, or else in a random order. Note that cha(cid:11) points in Lock are
`selected so as to intersect neither the set A nor the polynomial p. This is for
`technical reasons, namely to simplify our security proofs. We refer to the set R
`and the parameter triple (k; t; r) together as a fuzzy vault, denoted by VA.
`As explained above, to unlock a vault VA created by Alice as above, Bob
`tries to determine the codeword that encodes the secret (cid:20). Recall that the set
`A speci(cid:12)es the x-coordinates of \correct" points in R, i.e., those that lie on the
`polynomial p. Thus, if B is close to A, then B will identify a large majority of
`these \correct’ points. Any divergence between B and A will introduce a certain
`amount of error. Provided that there is su(cid:14)cient overlap, however, this noise
`may be removed by means of a Reed-Solomon decoding algorithm. We write
`(cid:20)0 p to denote conversion of a polynomial of degree at most k to a secret in
`F k, i.e., the reverse of the procedure employed in Lock. We let (xi; yi)
` (cid:0) R
`denote projection of R onto the x-coordinate bi. In particular, if there is a pair
`(bi; y) 2 R for any y, then (xi; yi) = (bi; y); otherwise a null element is assigned
`to the pair (xi; yi). Our unlocking algorithm is now as follows.
`
`(bi;(cid:14))
`
`Public parameters: A (cid:12)eld F, a Reed-Solomon decoding algorithm RSdecode.
`
`Input: A fuzzy vault VA comprising a parameter triple (k; t; r) such that k (cid:20) t (cid:20) r (cid:20) q
`
`
`and a set R of points f(xi; yi)gri=1 such that xi; yi 2 F. A set B = fbigti=1, where bi 2 F.
`
`Output: A value (cid:20)0 2 F k S f0null0g.
`
`Algorithm Unlock
`Q (cid:30);
`for i = 1 to t do
`(bi;(cid:14))
`(xi; yi)
` (cid:0) R;
`Q Q S (xi; yi);
`(cid:20)0 RSdecode(k; Q);
`output (cid:20)0;
`
`If the (cid:12)nal decoding operation is successful, then the algorithm outputs a
`secret (cid:20)0 which should be equal to (cid:20) if the set B is close to the original set A. If
`the decoding operation fails, then the algorithm outputs 0null0.
`The following proposition characterizes the completeness of our fuzzy vault
`scheme.
`
`USR Exhibit 2018, Page 10
`
`

`

`Proposition 3. Given use of the Peterson-Berlekamp-Massey algorithm for RSdecode,
`the algorithm pair (Lock; Unlock) above with parameter triple (k; t; r) is com-
`plete with ( t(cid:0)k
`2 )-fuzziness.
`
`As an example of how the above algorithms might be applied, we brie(cid:13)y
`consider a parameterization of k and t in what we call the movie lover’s problem,
`i.e., the problem described above in which Alice is seeking someone with similar
`taste in movies. We defer discussion of security parameters for the next section.
`
`Example 1 (The movie lover’s problem). Let us consider the movie lover’s prob-
`lem with a total set of 104 titles in which Alice selects a set A of t = 22 di(cid:11)erent
`favorites.4 We might choose k = 14. Since k+t
`2 = 18, another movie lover with a
`set B of 22 favorite titles will be able to decrypt the digital box via the Peterson-
`Berlekamp-Massey algorithm provided that the original set A and the new set
`B intersect on at least 18 titles. Notice that for this choice of parameters, it is
`feasible to compute all possible subsets of size 18 from the set of size 22, and
`try interpolating from each subset. This would result, however, in an average
`of 3657.5 trials, while the cost of one decoding step is easily within an order of
`magnitude of one interpolation step. Thus the use of RSdecode speeds up5 the
`decommitment step by at least a factor of 300.
`
`4 Security
`
`The security of our fuzzy vault construction depends on the number of cha(cid:11)
`points r (cid:0) t in the target set R. The greater the number of such points, the
`more \noise" there is to conceal p from an attacker. As many cha(cid:11) points are
`added to R, there begins to emerge a set of spurious polynomials that look
`like p, i.e., polynomials that have degree less than k and agree with exactly
`t points in R. Brie(cid:13)y stated, the more cha(cid:11) points there are, the greater the
`probability that some set of t of these cha(cid:11) points (and/or real points) align
`themselves by chance on some polynomial of the desired degree. In the absence
`of additional information, an attacker cannot distinguish between the correct
`polynomial p and all of the spurious ones. Thus, p is hidden in an information-
`theoretically secure fashion in R, with security proportional to the number of
`spurious polynomials. Note that the security of the vault VA depends exclusively
`on the number of such polynomials, and not on the length of the secret key (cid:20);
`the vault is often weaker than the secret (cid:20) it protects (which is acceptable for the
`applications we describe). The following lemma proves that with high probability
`many polynomials degree less than k agree with the target set R in t places, i.e.,
`
`4 We consider 22 titles, as this is the number of password questions used in [10], which
`seems a good example application for our ideas.
`5 Another