A method for providing secure authentication comprising: - receiving a communication that includes a first challenge value, a second challenge value and a remote message authenticity value; - generating a first response value to the first challenge value by entering the first challenge value into a physically unclonable function circuit; - generating a plurality of keys by applying the first response value to a key generation circuit; - verifying the received message authenticity value by comparing the remote message authenticity value to a value generated from a first one of the plurality of keys; - generating a second response value to the second challenge value by entering the second challenge value into the PUF circuit; - encrypting, using a second one of the plurality of keys, the second response value; and - generating a local message authenticity value from a third one of the plurality of keys; - transmitting the encrypted second response value and the local message authenticity value; characterized in that, at a remote device configured to authenticate a device containing the PUF circuit using a challenge-response pair, - retrieving the first challenge value and a corresponding stored-response value from a memory; - generating the second challenge value; - generating another plurality of keys by applying the stored-response value to a key generation circuit; - generating the remote message authenticity value from a first one of the other plurality of keys and both of challenge values; - transmitting the communication that includes the first challenge value, the second challenge value and the remote message authenticity value; - receiving the encrypted second response value and the local message authenticity value; - verifying the local message authenticity value; - decrypting the second response value; and - storing the second challenge value and second response value response; the method further including steps of - determining that a current number of challenge-response pairs, stored in an authentication server remote from a device containing the PUF circuit, is below a threshold level; and - in response to determining that the number of challenge-response pairs is below the threshold level, transmitting multiple additional challenge values in connection with a single verification of the received message authenticity value. - receiving a communication that includes a first challenge value, a second challenge value and a remote message authenticity value; - generating a first response value to the first challenge value by entering the first challenge value into a physically unclonable function circuit; - generating a plurality of keys by applying the first response value to a key generation circuit; - verifying the received message authenticity value by comparing the remote message authenticity value to a value generated from a first one of the plurality of keys; - generating a second response value to the second challenge value by entering the second challenge value into the PUF circuit; - encrypting, using a second one of the plurality of keys, the second response value; and - generating a local message authenticity value from a third one of the plurality of keys; - transmitting the encrypted second response value and the local message authenticity value; - retrieving the first challenge value and a corresponding stored-response value from a memory; - generating the second challenge value; - generating another plurality of keys by applying the stored-response value to a key generation circuit; - generating the remote message authenticity value from a first one of the other plurality of keys and both of challenge values; - transmitting the communication that includes the first challenge value, the second challenge value and the remote message authenticity value; - receiving the encrypted second response value and the local message authenticity value; - verifying the local message authenticity value; - decrypting the second response value; and - storing the second challenge value and second response value response; - determining that a current number of challenge-response pairs, stored in an authentication server remote from a device containing the PUF circuit, is below a threshold level; and - in response to determining that the number of challenge-response pairs is below the threshold level, transmitting multiple additional challenge values in connection with a single verification of the received message authenticity value.