On Foundation and Construction of Physical Unclonable Functions.
Jiang Wu, Maire P. O'Neill · 2010
Physical Unclonable Functions (PUFs) have been introduced as a new cryptographic prim-itive, and whilst a large number of PUF designs and applications have been proposed, few studies has been undertaken on the theoretical foundation of PUFs. At the same time, many PUF designs have been found to be insecure, raising questions about their design methodol-ogy. Moreover, PUFs with efficient implementation are needed to enable many applications in practice. In this paper, we present novel results on the theoretical foundation and practical construc-tion for PUFs. First, we prove that, for an ℓ-bit-input and 푚-bit-output PUF containing 푛 silicon components, if 푛 < 푚2 ℓ 푐 where 푐 is a constant, then 1) the PUF cannot be a random function, and 2) confusion and diffusion are necessary for the PUF to be a pseudorandom func-tion. Then, we propose a helper data algorithm (HDA) that is secure against active attacks and significantly reduces PUF implementation overhead compared to previous HDAs. Finally, we integrate PUF construction into block cipher design to implement an efficient physical un-clonable pseudorandom permutation (PUPRP); to the best of our knowledge, this is the first practical PUPRP using an integrated approach. 1