Paper 2023/1941

Upgrading Fuzzy Extractors

Chloe Cachet, National Research Council Canada
Ariel Hamlin, Northeastern University
Maryam Rezapour, University of Connecticut
Benjamin Fuller, University of Connecticut
Abstract

Fuzzy extractors derive stable keys from noisy sources non-interactively (Dodis et al., SIAM Journal of Computing 2008). Since their introduction, research has focused on two tasks: 1) showing security for as many distributions as possible and 2) providing stronger security guarantees including allowing one to enroll the same value multiple times (reusability), security against an active attacker (robustness), and preventing leakage about the enrolled value (privacy). Existing constructions of reusable fuzzy extractors are direct and do not support as many distributions as the best non-reusable constructions. Constructions of robust fuzzy extractors require strong assumptions even in the CRS model. Given the need for progress on the basic fuzzy extractor primitive, it is prudent to seek generic mechanisms to transform a fuzzy extractor into one that is robust, private, and reusable so that it can inherit further improvements. This work asks if one can generically upgrade fuzzy extractors to achieve robustness, privacy, and reusability. We show positive and negative results: we show upgrades for robustness and privacy, but we provide a negative result on reuse. 1. We upgrade (private) fuzzy extractors to be robust under weaker assumptions than previously known in the common reference string model. 2. We show a generic upgrade for a private fuzzy extractor using multi-bit compute and compare (MBCC) obfuscation (Wichs and Zirdelis, FOCS 2017) that requires less entropy than prior work. 3. We show one cannot arbitrarily compose private fuzzy extractors. It is known one cannot reuse an arbitrary fuzzy extractor; each enrollment can leak a constant fraction of the input entropy. We show that one cannot build a reusable private fuzzy extractor by considering other enrollments as auxiliary input. In particular, we show that assuming MBCC obfuscation and collision-resistant hash functions, there does not exist a private fuzzy extractor secure against unpredictable auxiliary inputs strengthening a negative result of Brzuska et al. (Crypto 2014).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. ACNS 2024
Keywords
Fuzzy extractorsobfuscationbiometricskey derivation.
Contact author(s)
chloe cachet @ nrc-cnrc gc ca
a hamlin @ northeastern edu
maryam rezapour @ uconn edu
benjamin fuller @ uconn edu
History
2023-12-22: approved
2023-12-21: received
See all versions
Short URL
https://ia.cr/2023/1941
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1941,
      author = {Chloe Cachet and Ariel Hamlin and Maryam Rezapour and Benjamin Fuller},
      title = {Upgrading Fuzzy Extractors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1941},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1941}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.