Paper 2017/754

Long-Term Secure Time-Stamping using Preimage-Aware Hash Functions

Ahto Buldas, Matthias Geihs, and Johannes Buchmann


Commonly used digital signature schemes have a limited lifetime because their security is based on computational assumptions that will potentially break in the future when more powerful computers are available. In 1993, Bayer et al.\ proposed to renew a digital signature by time-stamping the signature together with the signed document. Based on their idea long-term timestamp schemes have been proposed and standardized that allow to protect data integrity over long periods of time. To minimize the risk of a design failure that affects the security of these schemes, it is important to formally analyze their security. However, many of the proposed schemes have not been subject to a formal security analysis yet. In this paper, we address this issue by formally analyzing the security of a hash-based long-term timestamp scheme that is based on the ideas of Bayer et al. Our analysis shows that the security level of this scheme degrades cubic over time, a security loss that needs to be taken into account when the scheme is used in practice.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ProvSec 2017
Long-Term SecurityTimestampsPreimage Aware Hash Functions
Contact author(s)
mgeihs @ cdc informatik tu-darmstadt de
2017-08-08: revised
2017-08-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ahto Buldas and Matthias Geihs and Johannes Buchmann},
      title = {Long-Term Secure Time-Stamping using Preimage-Aware Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/754},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.