Cryptology ePrint Archive: Report 2016/1100

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

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

Abstract: A Fuzzy Extractor (Dodis et al., Eurocrypt 2004) is a two-step protocol 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 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 showed that any information-theoretically secure reusable fuzzy extractor is subject to strong limitations. Recently, Canetti et al. (Eurocrypt 2016) proposed a computationally secure reusable fuzzy extractor for the Hamming metric that corrects a sublinear fraction of errors.

We propose a generic framework to solve the reusability problem. We introduce 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. A reusable pseudoentropic isometry can be combined with a traditional fuzzy extractor to provide a reusable fuzzy extractor.

To show the promise of our framework, we construct a reusable pseudoentropic isometry for the set difference metric. Our work construction handles a linear fraction of errors and is secure in the nonprogrammable random oracle model. Furthermore it is efficient, requiring only hash function evaluations and decoding an error correcting code.

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). 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 pseudoentropic isometries.

Category / Keywords: fuzzy extractors, reusability, reusable pseudoentropic isometry, adaptive fuzzy extractors

Date: received 21 Nov 2016, last revised 15 Feb 2017

Contact author: quentin alamelou at gmail com

Available format(s): PDF | BibTeX Citation

Note: Rework of some concepts and proofs

Version: 20170215:083935 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]