Paper 2016/1100

Pseudoentropic Isometries: A New Framework for Fuzzy Extractor Reusability

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

Abstract

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 reading w'. Boyen immediately 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 that reusability was indeed a practical vulnerability. More recently, Canetti et al. (Eurocrypt 2016) proposed moving to computational security and constructed a computationally secure reusable fuzzy extractor for the Hamming metric that corrects a sublinear fraction of errors. We propose a generic approach to building reusable fuzzy extractors where the main idea is to separate the reusability property from the key recovery. To do so, 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 such a tool does not reveal information about the original fuzzy secret w and can be used to “decorrelate” noisy versions of w. We show that building a reusable fuzzy extractor from a reusable pseudoentropic isometry is straightforward by 1) randomizing the noisy secret w into $\Omega$ and 2) applying a traditional fuzzy extractor to derive a secret key from $\Omega$. To show the promise of our framework, we propose instantiations that handle the set difference and Hamming metrics. The first one is an original construction based on composable digital lockers (Canetti and Dakdouk, Eurocrypt 2008) yielding the first reusable fuzzy extractor that corrects a linear fraction of errors. For the second one, we show that Construction 2 proposed by Canetti et al. in Eurocrypt 2016 (Section 5.1) can be seen as an instantiation of our framework. In both cases, the pseudoentropic isometry’s reusability requires noisy secrets distributions to have entropy in each symbol of the alphabet. At last, we describe two practical solutions that reap benefits of our results while dealing with the aforementioned limitation.

Note: Add practical use cases.