Efficient Searches of Physical Unclonable Function Seed Spaces for Response-Based Cryptography

Response-based cryptography (RBC) is an unequal authentication protocol that is used to secure devices in resource-constrained and noisy environments. Such noisy environments may include securing radar on UAVs and in other autonomous settings. The protocol allows for client devices to be equipped with physical unclonable functions (PUFs), which are hardware elements that assign a unique fingerprint to a client device. Because PUFs are physical devices, they have a bit error rate, meaning that their output at a given address (a seed) may vary over time. Thus, a critical component of RBC is the use of a secure server equipped with hardware that enables very high seed search throughput (e.g., compute clusters, graphics processing units (GPUs)), that can find the target seed that authenticates the device. Once the client has been authenticated by the server, the seed can be used for encryption and other tasks (PKEs, DSAs, or KEMs) to enable secure communication. The state-of-the-art research in this area has assumed that the seed search space is uniform, where all seeds searched on the server have the same probability of authenticating the device. Due to high computational cost, this limits the application of PUFs to those with low levels of noise. In this paper, we propose a new seed search algorithm that uses PUF enrollment data to assign a probability that a seed will authenticate a user's device. This information allows us to increase the level of noise on client devices to enable higher levels of security in addition to being more robust to noisy environments. Additionally, we include an analysis of our proposed work and compare it to the state-of-the-art. We find that our proposed method is at least 3.38× faster than prior work and can search up to a Hamming distance of 5 under 10 seconds using 64×CPU Cores.