Old School, New Primitive: Toward Scalable PUF-Based Authenticated Encryption Scheme in IoT

The Internet of Things (IoT) facilitates the information exchange between people and smart devices. It needs cryptographic measures to secure its communications and interconnected objects. However, cyber-physical attacks pose a great challenge to the protection of secret keys inside. Physically unclonable function (PUF) is a promising hardware primitive with unclonable structures providing tamper evidence for a device. Moreover, a PUF instance has a unique set of randomized challenge-response pairs. Although it can be integrated into a security scheme to replace long-term keys, designing a dedicated PUF-based cryptographic algorithm that supports peer-to-peer communication remains a challenging field to explore. In this article, we propose SPEAR, a scalable PUF-based authenticated encryption (AE) scheme that uses no cryptographic primitives other than PUF and hash functions. SPEAR can be deployed on peer IoT devices that have performed a handshake protocol to obtain shared credentials. Its security under the chosen ciphertext attack is formally proved using the game-playing technique, and it is still secure when attackers physically extract the credentials. In addition, we give a variant, $x$ SPEAR, to involve associated data and avoid the nonce reuse problem. Compared to other PUF-based ciphers, it performs better in terms of storage overhead and PUF evaluation times. SPEAR first realizes scalable AE based on PUF and can be a practical solution for IoT.