Boyen highlighted the need for reusable fuzzy extractors (CCS 2004) that remain secure even when numerous calls to the generation procedure are made on a user’s noisy secret. Boyen proved that any information-theoretically secure reusable fuzzy extractor is subject to strong limitations. In subsequent work, Simoens et al. (IEEE S&P, 2009) showed this is a practical vulnerability. Canetti et al. (Eurocrypt 2016) recently proposed moving to computational security and constructed a computationally secure reusable fuzzy extractor for the Hamming metric that corrects a sublinear fraction of errors. In this work, we propose a different and generic approach: the idea is to separate the reusability property from key recovery. We define a new primitive called a reusable pseudoentropic isometry that projects an input metric space in a distance and entropy preserving manner even if applied multiple times. Generation of multiple randomized secrets $\Omega$s via a reusable pseudoentropic isometry does not reveal information about the original fuzzy secret w and can be used to “decorrelate” noisy versions of w. Given a reusable pseudoentropic isometric building a reusable fuzzy extractor is easy by 1) randomizing the noisy secret w into $\Omega$ and 2) using a traditional fuzzy extractor to derive a secret key from $\Omega$. To show the promise of our framework, we construct a reusable pseudoentropic isometry for the set difference metric using composable digital lockers (Canetti and Dakdouk, Eurocrypt 2008). This construction allows us to build the first reusable fuzzy extractor that corrects a linear fraction of errors. Lastly, we propose browser and device fingerprints as new authentication sources. These fingerprints are a list of features with entropy that undergo deeper variation over time than biometrics. However, they still enable user identification (Eckersley, PETS 2010). Extending reusable fuzzy extractors, we define adaptive fuzzy extractors to handle such sources. An adaptive fuzzy extractor enables recovery of R from w'as long as w' has naturally drifted from w. We construct adaptive fuzzy extractors from reusable fuzzy extractors.
Category / Keywords: fuzzy extractors, reusability, reusable pseudoentropic isometry, adaptive fuzzy extractors Date: received 21 Nov 2016, last revised 13 Jul 2017 Contact author: quentin alamelou at gmail com Available format(s): PDF | BibTeX Citation Note: Rework of some concepts and usage of Digital Lockers for handling set difference. Version: 20170713:073053 (All versions of this report) Short URL: ia.cr/2016/1100 Discussion forum: Show discussion | Start new discussion