We describe a simple and novel cryptographic construction that we refer to as a fuzzy vault. A player Alice may place a secret value κ 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 κ only if B is close to A, i.e., only if A and B overlap substantially. In constrast to previous constructions of this flavor, 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.
Alice is a movie lover. She is looking to find someone who shares her taste in movies, but does not want to reveal information about her preferences indiscriminately 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 different 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 films 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 other hand, anyone who tries to unlock VA with a set of favorite movies differing 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.
Publisher : ISIT
By : A Fuzzy Vault Scheme
File Information: English Language/ 18 Page / size: 171 KB
سال : 2002
ناشر : ISIT
کاری از : A Fuzzy Vault Scheme
اطلاعات فایل : زبان انگلیسی / 18 صفحه / حجم : KB 171
لینک دانلود : روی همین لینک کلیک کنید