  A physical unclonable function (PUF) generates hardware intrinsic volatile
secrets by exploiting uncontrollable manufacturing randomness. Although PUFs
provide the potential for lightweight and secure authentication for increasing
numbers of low-end Internet of Things devices, practical and secure mechanisms
remain elusive. We aim to explore simulatable PUFs (SimPUFs) that are
physically unclonable but efficiently modeled mathematically through privileged
one-time PUF access to address the above problem. Given a challenge, a securely
stored SimPUF in possession of a trusted server computes the corresponding
response and its bit-specific reliability. Consequently, naturally noisy PUF
responses generated by a resource limited prover can be immediately processed
by a one-way function (OWF) and transmitted to the server, because the
resourceful server can exploit the SimPUF to perform a trial-and-error search
over likely error patterns to recover the noisy response to authenticate the
prover. Security of trial-and-error reverse (TREVERSE) authentication under the
random oracle model is guaranteed by the hardness of inverting the OWF. We
formally evaluate the TREVERSE authentication capability with two SimPUFs
experimentally derived from popular silicon PUFs.
