Cryptology ePrint Archive: Report 2009/030

An efficient fuzzy extractor for limited noise

B. Skoric and P. Tuyls

Abstract: 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.

Category / Keywords: fuzzy extractor

Date: received 13 Jan 2009, last revised 21 Jul 2009

Contact author: b skoric at tue nl

Available formats: PDF | BibTeX Citation

Note: The discussion of robustness has been updated.

Version: 20090721:093141 (All versions of this report)

Discussion forum: Show discussion | Start new discussion