Cryptology ePrint Archive: Report 2017/911

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

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

Abstract: 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.

Category / Keywords:

Original Publication (in the same form): SPACE 2017 (in cooperation with IACR)

Date: received 18 Sep 2017, last revised 25 Sep 2017

Contact author: vincent immler at aisec fraunhofer de

Available format(s): PDF | BibTeX Citation

Version: 20170925:071159 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]