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: ia.cr/2016/1100 Discussion forum: Show discussion | Start new discussion