Paper 2017/911

Variable-Length Bit Mapping and Error-Correcting Codes for Higher-Order Alphabet PUFs

Vincent Immler, Matthias Hiller, Qinzhi Liu, Andreas Lenz, and Antonia Wachter-Zeh


Device-specific physical characteristics provide the foundation for PUFs, a hardware primitive for secure storage of cryptographic keys. So far, they have been implemented by either directly evaluating a binary output or by mapping outputs from a higher-order alphabet to a fixed-length bit sequence. However, the latter causes a significant bias in the derived key when combined with an equidistant quantization. To overcome this limitation, we propose a variable-length bit mapping that reflects the properties of a Gray code in a different metric, namely the Levenshtein metric instead of the classical Hamming metric. Subsequent error-correction is therefore based on a custom insertion/deletion correcting code. This new approach effectively counteracts the bias in the derived key already at the input side. We present the concept for our scheme and demonstrate its feasibility based on an empirical PUF distribution. As a result, we increase the effective output bit length of the secret by over 40% compared to state-of-the-art approaches while at the same time obtaining additional advantages, e.g., an improved tamper-sensitivity. This opens up a new direction of Error-Correcting Codes (ECCs) for PUFs that output responses with symbols of higher-order output alphabets.

Available format(s)
Publication info
Published elsewhere. SPACE 2017 (in cooperation with IACR)
Contact author(s)
vincent immler @ aisec fraunhofer de
2017-09-25: revised
2017-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vincent Immler and Matthias Hiller and Qinzhi Liu and Andreas Lenz and Antonia Wachter-Zeh},
      title = {Variable-Length Bit Mapping and Error-Correcting Codes for Higher-Order Alphabet PUFs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/911},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.