Paper 2015/854

Efficient Fuzzy Extraction of PUF-Induced Secrets: Theory and Applications

Jeroen Delvaux, Dawu Gu, Ingrid Verbauwhede, Matthias Hiller, and Meng-Day (Mandel) Yu


The device-unique response of a physically unclonable function (PUF) can serve as the root of trust in an embedded cryptographic system. Fuzzy extractors transform this noisy non-uniformly distributed secret into a stable high-entropy key. The overall efficiency thereof, typically depending on error-correction with a binary [n,k,d] block code, is determined by the universal and well-known (n-k) bound on the min-entropy loss. We derive new considerably tighter bounds for PUF-induced distributions that suffer from, e.g., bias or spatial correlations. The bounds are easy-to-evaluate and apply to large non-trivial codes, e.g., BCH and Reed-Muller codes. Apart from an inherent reduction in implementation footprint, the newly developed theory also facilitates the analysis of state-of-the-art error-correction methods for PUFs. As such, we debunk the reusability claim of the reverse fuzzy extractor. Moreover, we provide proper quantitative motivation for debiasing schemes, as this was missing in the original proposals.

Note: This manuscript comprehends an extended version of our CHES 2016 work.

Available format(s)
Publication info
A major revision of an IACR publication in CHES 2016
fuzzy extractorsecure sketchmin-entropyphysically unclonable functionscoding theory
Contact author(s)
jeroen delvaux @ esat kuleuven be
2016-06-14: last of 3 revisions
2015-09-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jeroen Delvaux and Dawu Gu and Ingrid Verbauwhede and Matthias Hiller and Meng-Day (Mandel) Yu},
      title = {Efficient Fuzzy Extraction of PUF-Induced Secrets: Theory and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2015/854},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.