Classical cryptography offers several measures for securing electronic devices. These mainly rely on a secret key and expensive resources due to the device permanently storing a piece of digital information that's unknown to our adversaries. In practice, it is difficult to keep this information confidential. This problem motivated the invention of PUF – physical devices that produce an output that's quick to evaluate yet hard to predict.
To authenticate using a PUF, we need to construct a database of Challenge-Response Pairs (CRPs). A challenge is a binary string (for example, 1100101...01) of length n, and a response is some other binary string of length m. To find out whether an unknown device is the aforementioned PUF, we need to issue it a number of challenges, verifying that it produces the correct responses until we reach the desired...
