**Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures**

*Ahto Buldas and Risto Laanoja and Peeter Laud and Ahto Truu*

**Abstract: **We present a new tighter security proof for unbounded hash tree keyless signature (time-stamping) schemes that use Merkle-Damgå 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.

**Category / Keywords: **hash functions, Pre-image awareness, time-stamping

**Original Publication**** (with minor differences): **ProvSec 2014

**Date: **received 4 Sep 2014, last revised 4 Sep 2014

**Contact author: **ahto buldas at guardtime com, risto laanoja@guardtime com, ahto truu@guardtime com

**Available format(s): **PDF | BibTeX Citation

**Note: **A missing author (Peeter Laud) added.

**Version: **20140905:191021 (All versions of this report)

**Short URL: **ia.cr/2014/700

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]