Proof of Persistent Aliveness

Proof of Aliveness (PoA) has emerged as a useful cryptographic concept for periodically ascertaining the operational status (aliveness) of devices, especially for those in cyber-physical systems. However, existing PoA schemes exhibit shortcomings stemming from intermittent aliveness proofs and a lack of resilience against the threats caused by malicious verifiers. Motivated by this, we introduce a new security notion called Proof of Persistent Aliveness (PoPA), which encompasses two new properties: persistent aliveness (PAlive) and audit (Audit). Our PAlive strengthens prior work by addressing the security concerns associated with generating persistent aliveness proofs in a continuous time manner, while Audit covers the threats posed by malicious verifiers. To efficiently realize PoPA, we developed two new building blocks: a deterministic hash-based Proof of Work (HPoW) scheme and private tweakable hash (PTH) functions. Using these primitives, we propose a scalable and lightweight PoPA construction, named SPAC, which is provably secure in our PoPA model without relying on random oracles. SPAC leverages HPoW and a customized authenticated credential structure that employs a variant of the Winternitz one-time signature scheme derived from PTH, enabling unlimited aliveness proofs with very small proof size. Over 93% of aliveness proofs are 84 bytes in size, with the worst-case proof size being only 372 bytes.