Long-Term Time-Stamping Schemes Based on MACs, Archives, and Transient Keys

A time-stamping scheme proves the existence time of a data item by using cryptographic algorithms. For example, the ISO/IEC 18014 and ANSI X9.95 standards specify time-stamping schemes based on digital signatures, hash functions, message authentication codes (MACs), archives, and transient keys. The fact is that any single cryptographic algorithm has a limited lifespan due to operational life cycles or the advanced computational power of attackers. To deal with this issue, the standards support the time-stamp renewal mechanisms of these schemes, in which the core idea is to renew a time-stamp token by using a stronger algorithm before it is compromised. Such schemes are referred to as Long-Term Time-Stamping (LTTS) schemes. In the literature, the LTTS schemes based on signatures and hash functions have been formally defined and analyzed. However, the formal security definition and analysis of the LTTS schemes based on MACs, archives, and transient keys are still missing. From the standard point of view, it is critical to have formal treatments for every presented technology. Otherwise, the security of the widely-used applications based on these schemes is in question. In this paper, we fill this gap by formally defining the MAC-based, archive-based, and transient key-based LTTS schemes, and analyzing their security based on a formal LTTS security model.