A tamper-proof and lightweight authentication scheme

We present a tamper-proof and lightweight challenge-response authentication scheme, based on 2-level noisy Physically Unclonable Functions (PUF). We present a security reduction, which shows the scheme to be secure against passive attacks, provided that it is hard to learn a threshold of halfspaces under the uniform distribution. Furthermore, we provide an extensive analysis of PUFs. In particular, we thoroughly derive a linear model for delay based PUFs, and finally we explore extensions of PUFs to produce efficient and tamper-resilient nn-to-nn mappings.