Spatial Context Tree Weighting for Physical Unclonable Functions

Physical Unclonable Functions (PUFs) are hardware primitives for, e.g., secure storage of cryptographic keys. Unpredictability of their output is essential for their security and, thus, it is important to evaluate this property, which is often done by assessing the PUF's entropy. However, existing entropy estimation methods do not consider spatial information and provide no corresponding information to the designer. Therefore, we study how spatial effects in PUF structures can be considered when estimating entropy by means of an improved Context Tree Weighting (CTW) algorithm. Our Spatial CTW is practically implemented and tested on various real-world data sets, including binary and higher order alphabet PUFs. The obtained experimental results clearly support the necessity of taking spatial effects into account to not overestimate a PUF's entropy.