Paper 2016/1100

Reusable Fuzzy Extractors for the Set Difference Metric and Adaptive Fuzzy Extractors

Quentin Alamélou and Paul-Edmond Berthier and Chloé Cachet and Stéphane Cauchie and Benjamin Fuller and Philippe Gaborit

Abstract

A fuzzy extractor (Dodis et al., Eurocrypt 2004) is a pair of procedures that turns a noisy secret into a uniformly distributed key R. To eliminate noise, the generation procedure takes as input an enrollment value w and outputs R and a helper string P that enables further reproduction of R from some close w'. 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.

Note: Rework of some concepts and usage of Digital Lockers for handling set difference.