International Association
for Cryptologic Research

We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damg\\aa rd (MD) hash functions with Preimage Aware (PrA) compression functions. It is known that the PrA assumption alone is insufficient for proving the security of unbounded hash tree schemes against back-dating attacks. We show that many known PrA constructions satisfy a stronger \\emph{Bounded Pre-Image Awareness (BPrA)} condition that assumes the existence of an extractor $\\EXT$ that is bounded in the sense that for any efficiently computable query string $\\alpha$, the number of outputs $y$ for which $\\EXT(y,\\alpha)$ succeeds does not exceed the number of queries in $\\alpha$. We show that blockcipher based MD-hash functions with rate-1 compression functions (such as Davies-Meyer and Miyaguchi-Preneel) of both type I and type II are BPrA.

We also show that the compression function of Shrimpton-Stam that uses non-compressing components is BPrA. The security proof for unbounded hash-tree schemes is very tight under the BPrA assumption. In order to have $2^s$-security against back-dating, the hash function must have $n=2s + 4$ output bits, assuming that the security of the hash function is close to the birthday barrier, i.e. that there are no structural weaknesses in the hash function itself. Note that the previous proofs that assume PrA gave the estimation $n=2s + 2 \\log_2 C + 2$, where $C$ is the maximum allowed size of the hash tree. For example, if $s=100$ ($2^{100}$-security) and $C=2^{50}$, the previous proofs require $n=302$ output bits, while the new proof requires $n=204$ output bits.