Paper 2017/755

Efficient, Reusable Fuzzy Extractors from LWE

Daniel Apon, Chongwon Cho, Karim Eldefrawy, and Jonathan Katz


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.

Available format(s)
Publication info
Published elsewhere. Major revision. International Symposium on Cyber Security, Cryptography, and Machine Learning 2017
fuzzy extractorsbiometrics
Contact author(s)
jkatz2 @ gmail com
2017-08-20: last of 2 revisions
2017-08-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Apon and Chongwon Cho and Karim Eldefrawy and Jonathan Katz},
      title = {Efficient, Reusable Fuzzy Extractors from LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/755},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.