Paper 2009/030

An efficient fuzzy extractor for limited noise

B. Skoric and P. Tuyls


A fuzzy extractor is a security primitive that allows for reproducible extraction of an almost uniform key from a noisy non-uniform source. We analyze a fuzzy extractor scheme that uses universal hash functions for both information reconciliation and privacy amplification. This is a useful scheme when the number of error patterns likely to occur is limited, regardless of the error probabilities. We derive a sharp bound on the uniformity of the extracted key, making use of the concatenation property of universal hash functions and a recent tight formulation of the leftover hash lemma.

Note: The discussion of robustness has been updated.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
fuzzy extractor
Contact author(s)
b skoric @ tue nl
2009-07-21: revised
2009-01-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {B.  Skoric and P.  Tuyls},
      title = {An efficient fuzzy extractor for limited noise},
      howpublished = {Cryptology ePrint Archive, Paper 2009/030},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.