Paper 2017/493

Robust Fuzzy Extractors and Helper Data Manipulation Attacks Revisited: Theory vs Practice

Georg T. Becker


Fuzzy extractors have been proposed in 2004 by Dodis et al. as a secure way to generate cryptographic keys from noisy sources. In recent years, fuzzy extractors have become an important building block in hardware security due to their use in secure key generation based on Physical Unclonable Functions (PUFs). Fuzzy extractors are provably secure against passive attackers. A year later Boyen et al. introduced robust fuzzy extractors which are also provably secure against active attackers, i.e., attackers that can manipulate the helper data. In this paper we show that the original provable secure robust fuzzy extractor construction by Boyen et al. actually does not fulfill the error-correction requirements for practical PUF applications. The fuzzy extractors proposed for PUF-based key generation on the other hand that fulfill the error-correction requirements cannot be extended to such robust fuzzy extractors, due to a strict bound $t$ on the number of correctable errors. While it is therefore tempting to simply ignore this strict bound, we present novel helper data manipulation attacks on fuzzy extractors that also work if a ``robust fuzzy extractor-like'' construction without this strict bound is used. Hence, this paper can be seen as a call for action to revisit this seemingly solved problem of building robust fuzzy extractors. The new focus should be on building more efficient solutions in terms of error-correction capability, even if this might come at the costs of a proof in a weaker security model.

Note: Minor revision, mainly editorial (Final version for TDSC)

Available format(s)
Publication info
Published elsewhere. Minor revision.IEEE Transactions on Dependable and Secure Computing
Fuzzy ExtractorPhysical Unclonable Functions (PUFs)Helper Data Manipulation Attacks
Contact author(s)
georg becker @ ruhr-uni-bochum de
2017-10-16: revised
2017-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Georg T.  Becker},
      title = {Robust Fuzzy Extractors and Helper Data Manipulation Attacks Revisited: Theory vs Practice},
      howpublished = {Cryptology ePrint Archive, Paper 2017/493},
      year = {2017},
      doi = {10.1109/TDSC.2017.2762675},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.