Cryptology ePrint Archive: Report 2017/755

Efficient, Reusable Fuzzy Extractors from LWE

Daniel Apon and Chongwon Cho and Karim Eldefrawy and Jonathan Katz

Abstract: A fuzzy extractor (FE), proposed for deriving cryptographic keys from biometric data, enables reproducible generation of high-quality randomness from noisy inputs having sufficient min-entropy. FEs rely in their operation on a public "helper string" that is guaranteed not to leak too much information about the original input. Unfortunately, this guarantee may not hold when multiple independent helper strings are generated from correlated inputs as would occur if a user registers their biometric data with multiple servers; reusable FEs are needed in that case. Although the notion of reusable FEs was introduced in 2004, it has received relatively little attention since then.

We first analyze an FE proposed by Fuller et al. (Asiacrypt 2013) based on the learning-with-errors (LWE) assumption, and show that it is not reusable. We then show how to adapt their construction to obtain a weakly reusable FE. We also show a generic technique for turning any weakly reusable FE to a strongly reusable one, in the random-oracle model. Finally, we give a direct construction of a strongly reusable FE based on the LWE assumption, that does not rely on random oracles.

Category / Keywords: foundations / fuzzy extractors, biometrics

Original Publication (with major differences): International Symposium on Cyber Security, Cryptography, and Machine Learning 2017

Date: received 4 Aug 2017, last revised 20 Aug 2017

Contact author: jkatz2 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170820:221717 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]