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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]