Cryptology ePrint Archive: Report 2016/854
Algebraic Security Analysis of Key Generation with Physical Unclonable Functions
Matthias Hiller and Michael Pehl and Gerhard Kramer and Georg Sigl
Abstract: Physical Unclonable Functions (PUFs) provide cryptographic keys for embedded systems without secure non-volatile key storage. Several error correction schemes for key generation with PUFs were introduced, analyzed and implemented over the last years. This work abstracts from the typical algorithmic level and provides an algebraic view to reveal fundamental similarities and differences in the security of these error correction schemes.
An algebraic core is introduced for key generation with Physical Unclonable Functions (PUFs). It computes the secret key through the helper data from the input PUF response and an optional random number. For nearly uniformly distributed PUF responses, the leakage of the secret key and the helper data can be brought to zero if and only if the rank of the algebraic core is equal to the sum of the ranks of the key generating part and the rank of the helper data generating part. This rank criterion has the practical advantage that a security check can be performed for linear codes at an early design stage of an algorithm. The criterion is applied to state-of-the-art approaches to show that fuzzy commitment and systematic low leakage coding are the only analyzed schemes that achieve zero leakage.
Category / Keywords: applications / Physical Unclonable Functions (PUFs), Fuzzy Extractor, Coding Theory.
Original Publication (in the same form): PROOFS 2016
Date: received 5 Sep 2016
Contact author: matthias hiller at aisec fraunhofer de
Available format(s): PDF | BibTeX Citation
Version: 20160907:200057 (All versions of this report)
Short URL: ia.cr/2016/854
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]