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.