Cryptology ePrint Archive: Report 2015/854

Secure Sketch Metamorphosis: Tight Unified Bounds

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

Abstract: A noisy non-uniformly distributed secret often needs to be transformed into a stable high-entropy key. Biometric systems and physically unclonable functions (PUFs) exemplify the need for this conversion. Secure sketches are a useful tool hereby as they alleviate the noisiness while keeping the corresponding min-entropy loss to a minimum. The novelty of our work is twofold. First, seven secure sketch constructions, all based on a binary $[n,k,d]$ block code, are proven to be largely interchangeable. Despite having different looks and properties, all exhibit the same min-entropy loss, when fed with the same probability distribution. Second, for PUF-induced distributions with practical relevance, we derive new unified bounds on the min-entropy loss, considerably tighter than the more general well-known $(n-k)$ bound. Our bounds allow for an efficient evaluation and are hence suitable for reducing the implementation footprint of the sketch. This is beneficial for resource-constrained devices in particular.

Category / Keywords: secure sketch, fuzzy extractor, min-entropy, physically unclonable functions, biometrics, coding theory

Date: received 3 Sep 2015, last revised 6 Oct 2015

Contact author: jeroen delvaux at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20151007:024338 (All versions of this report)

Short URL: ia.cr/2015/854

Discussion forum: Show discussion | Start new discussion