[Resource Topic] 2014/700: Bounded Pre-Image Awareness and the Security of Hash-Tree Keyless Signatures

Welcome to the resource topic for 2014/700

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

Authors: Ahto Buldas, Risto Laanoja, Peeter Laud, Ahto Truu


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.

ePrint: https://eprint.iacr.org/2014/700

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .