Cryptology ePrint Archive: Report 2017/754

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

Ahto Buldas and Matthias Geihs and Johannes Buchmann

Abstract: 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.

Category / Keywords: public-key cryptography / Long-Term Security, Timestamps, Preimage Aware Hash Functions

Original Publication (with major differences): ProvSec 2017

Date: received 4 Aug 2017, last revised 8 Aug 2017

Contact author: mgeihs at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20170808:100825 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]