A&S Departments and Programs   • Graduate Study Offered   American Studies • Anthropology • Applied Science • Art & Art History Biology • Black Studies Chemistry • Classical Studies Computer Science • Economics English Environmental Science & Policy Film Studies Geology Global Studies Government History • International Relations Kinesiology Linguistics Literary & Cultural Studies Mathematics Medieval & Renaissance Studies Military Science Modern Languages Music Neuroscience Philosophy Physics • Psychology • Public Policy • Religious Studies Sociology Theater, Speech & Dance Women's Studies

Search

Find People

Computer Science Department

Computer Science Department

Forward Secure Fuzzy Extractors

David Goldenberg
Thursday, April 12, 2PM, McGl 002

Many cryptographic tools rely on the existence of a secret key. A fuzzy extractor is a cryptographic tool which allows for cryptographically secure keys to be extracted from biometric data. This is useful, as there is a link between biometric data and the user. Also, biometric data is easily stored as it is part of the user. The keys generated from biometric data are uniformly random and can be used in cryptographic tools such as encryption functions, signature schemes, or authentication protocols. However, biometric information can be easily recorded/retrieved by a malicious adversary which means that the result ing extracted keys can be stolen. This is different from other key generation methods, where the key is merely remembered, or stored in some encrypted state. To solve this problem, this thesis applies the idea of forward security to a fuzzy extractor, creating a forward secure fuzzy extractor, an extractor that retains some security even when the adversary gains knowledge about the biometric data of the user. Such a forward secure fuzzy extractor depends on a second factor, and if one factor is corrupted many extracted keys still remain computationally indistinguishable from random.

To create a forward secure fuzzy extractor we define a new primitive, an enhanced extractor. An enhanced extractor functions as an extractor in that for an unknown input of high enough entropy and known random seed the extractor outputs a string which is close to random. However, should the high entropy input become known and the seed remain secret the enhanced extractor functions as a pseudorandom generator. Such a tool may have its own uses independent of a fuzzy extractor.

After constructing an enhanced extractor we show how a forward secure fuzzy extractor can be created out of any enhanced extractor. We also develop an enhanced update function which allows for greater security even when both factors are compromised, and show how we can add robustness to a forward secure fuzzy extractor, even when one factor of our system is revealed.