Abstract
Traditional time-stamping services confirm the existence time of data items by using a time-stamping authority. To eliminate trust requirements on this authority, decentralized Blockchain-based Time-Stamping (BTS) services have been proposed. In these services, a hash digest of users' data is written into a blockchain transaction. The security of such services relies on the security of hash functions used to hash the data, and of the cryptographic algorithms used to build the blockchain. It is well-known that any single cryptographic algorithm has a limited lifespan due to the increasing computational power of attackers. This directly impacts the security of the BTS services from a long-term perspective. However, the topic of long-term security has not been discussed in the existing BTS proposals. In this paper, we propose the first formal definition and security model of a Blockchain-based Long-Term Time-Stamping (BLTTS) scheme. To develop a BLTTS scheme, we first consider an intuitive solution that directly combines the BTS services and a long-term secure blockchain, but we prove that this solution is vulnerable to attacks in the long term. With this insight, we propose the first BLTTS scheme supporting cryptographic algorithm renewal. We show that the security of our scheme over the long term is not limited by the lifespan of any underlying cryptographic algorithm, and we successfully implement the proposed scheme under existing BTS services.