Converse PUF-based authentication

Physically Unclonable Functions (PUFs) are key tools in the construction of lightweight authentication and key exchange protocols. So far, all existing PUF-based authentication protocols follow the same paradigm: A resource-constrained prover, holding a PUF, wants to authenticate to a resource-rich verifier, who has access to a database of pre-measured PUF challenge-response pairs (CRPs). In this paper we consider application scenarios where all previous PUF-based authentication schemes fail to work: The verifier is resource-constrained (and holds a PUF), while the prover is resource-rich (and holds a CRP-database). We construct the first and efficient PUF-based authentication protocol for this setting, which we call converse PUF-based authentication. We provide an extensive security analysis against passive adversaries, show that a minor modification also allows for authenticated key exchange and propose a concrete instantiation using controlled Arbiter PUFs.