Long-Term Secure Time-Stamping under the Preimage Awareness Assumption

16.02.2017, 11:00 – 12:00

2017/02/16 11:00-12:00

Speaker: Matthias Geihs | Location: Hochschulstraße 10 (S2|02), Piloty Building, Room B002, Darmstadt

Organizer: Prof. Johannes Buchmann, Moritz Horsch


We study how to prove and estimate the level of security of long-term timestamp schemes that use Merkle hash trees and in which timestamps are periodically renewed by obtaining new timestamps as described by Bayer, Haber and Stornetta in 1993. Such a renewal procedure is inevitable because the security level of practical hash functions decreases over time. For example, given enough computation time, an adversary will eventually succeed in finding a hash collision. So far, formal security proofs only consider “static” timestamp schemes without renewal.

We present a formal security proof for renewable timestamp schemes in a model in which the hash functions used are assumed to be pre-image aware (PrA) as defined by Dodis et al. in 2009. The (cubic) security loss of our security proofs seems to be unavoidable and causes a decrease in security over time. This shows that the systems that rely on long-term digital evidence must be designed with certain redundancy marginal in order to withstand such a decrease. We provide a framework for obtaining numeric estimations of the practical security loss. Such estimations could be valuable for engineers who design systems for long-term document management.

Short Bio

Website of Mathias Geihs at TU Darmstadt.