Optimizing Proof of Aliveness in Cyber-Physical Systems

At ACSAC 2019, we introduced a new cryptographic primitive called proof of aliveness (PoA), allowing us to remotely and automatically track the running status (aliveness) of devices in the fields in cyber-physical systems. We proposed to use a one-way function (OWF) chain structure to build an efficient proof of aliveness, such that the prover sends every node on the OWF chain in a reverse order periodically, and it can be verified by a remote verifier with the possession of the tail node (last node) of the OWF chain. However, the practicality of this initial construction is limited by the finite number of nodes on an OWF chain. We enhance our first PoA construction by linking multiple OWF chains together using a pseudo-random generator chain in our second PoA scheme. This enhancement allows us to integrate one-time signature (OTS) schemes into the structure of the second construction to realize the auto-replenishment of the aliveness proofs. This implies that securely an initialized PoA instance can be used forever without interruption for reinitialization. In this work, our primary motivation is to further improve our secondary PoA and auto-replenishment schemes. Instead of storing the tail nodes of multiple OWF chains on the verifier side, we use a Bloom Filter to compress them. This saves $ 4.7$ times the storage cost compared to our previous version at ACSAC 2019. Moreover, the OTS-based auto-replenishment solution cannot be applied to our first scheme solely based on OWFs, and it is not so efficient despite its standard model security. To overcome these limitations, we design a new auto-replenishment scheme from a hash-based commitment under the random oracle model in this work, which is much faster and can be used by both PoA schemes. Additionally, we implement and evaluate our PoA constructions on Raspberry Pis to demonstrate their performance. Considering the implementation on a storage/memory-constrained device, we particularly study the strategies for efficiently generating proofs.