Paper 2017/755

Efficient, Reusable Fuzzy Extractors from LWE

Daniel Apon, Chongwon Cho, 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.