Rock'n'roll PUFs: Crafting provably secure pufs from less secure ones (extended version)

The era of PUFs has been characterized by the efforts put into research and the development of PUFs that are resilient against attacks, in particular, machine learning attacks. Due to the lack of systematic and provable methods for this purpose, we have witnessed the ever-continuing competition between PUF designers/manufacturers, cryptanalysts, and of course, adversaries that maliciously break the security of PUFs. This is despite a series of acknowledged principles developed in cryptography and complexity theory, under the umbrella term "hardness amplification". This paper aims at narrowing the gap between these studies and hardware security, specifically for applications in the domain of PUFs. To this end, this paper provides an example of somewhat hard PUFs and demonstrates how to build a strongly secure construction out of these considerably weaker primitives. Our theoretical findings are discussed in an exhaustive manner and supported by the silicon results captured from real-world PUFs.