A method and system for authenticating a device is disclosed. The method includes the steps of: receiving a helper bit string and a first MAC; measuring a first response bit string of a physical unclonable function of the device with respect to a challenge bit string; subtracting the first response bit string from the helper bit string; decoding a result of the subtraction using a uniformly distributed random matrix, the shared secret bit string being provided from the decoding if the helper bit string was encoded using a previously measured second response bit string that is within a threshold level of similarity to the first response bit string, the decoding outputting an error value otherwise; determining a second MAC based on the shared secret bit string, the uniformly distributed random matrix, and the helper bit string; and determining whether the second MAC matches the first MAC.