You are looking at a specific version 20170215:083935 of this paper. See the latest version.

Paper 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.

Note: Rework of some concepts and proofs

Metadata
Available format(s)
PDF
Publication info
Preprint. MAJOR revision.
Keywords
fuzzy extractorsreusabilityreusable pseudoentropic isometryadaptive fuzzy extractors
Contact author(s)
quentin alamelou @ gmail com
History
2018-03-05: last of 8 revisions
2016-11-23: received
See all versions
Short URL
https://ia.cr/2016/1100
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.