Paper 2016/854

Algebraic Security Analysis of Key Generation with Physical Unclonable Functions

Matthias Hiller, Michael Pehl, Gerhard Kramer, and Georg Sigl


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.

Available format(s)
Publication info
Published elsewhere. PROOFS 2016
Physical Unclonable Functions (PUFs)Fuzzy ExtractorCoding Theory.
Contact author(s)
matthias hiller @ aisec fraunhofer de
2016-09-07: received
Short URL
Creative Commons Attribution


      author = {Matthias Hiller and Michael Pehl and Gerhard Kramer and Georg Sigl},
      title = {Algebraic Security Analysis of Key Generation with Physical Unclonable Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/854},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.