We propose a light-weight protocol for authentication of low-power devices. Our construction PUF-HB merges the positive qualities of two families of authentication functions. PUF represents physically unclonable functions and fulfills the purpose of providing low-cost tamper-resilient challenge-response authentication. On the other hand, the Hopper Blum (HB) function provides provable cryptographic strength against passive adversaries. By building on an earlier proof of the security of HB⁺ by Katz et al. [1], we rigorously prove the security of the proposed scheme against active adversaries. While the active adversary model does not include man-in-the-middle attacks, we show that a previously successful man-in-the-middle attack proposed for HB⁺, does not carry to PUF-HB.