I'm reading Merkle tree signatures and I like know if the security of the that scheme depends, also, of the high of the tree or only depends that hash function is resistant to collision?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
If you look at exact security, the height matters. The reason is that it defines the number of OTS key pairs and hence the possible number of one time signatures per MSS key pair. To forge a MSS signature, it is enough to generate a forgery for 1 out of $2^h$ OTS signatures. Hence you get a reduction in the bit security of $h$ bits.
The Merkle tree signature scheme mainly assumes that the underlying hash function used is cryptographically secure. The pre-image and second preimage properties are especially important here as an attacker should not be able to :
From my understanding of the scheme, the height of the tree only affects the number of signatures that can be generated with a single public key (root node), the cost of the tree construction (2^n+1 - 1 hash operations) and the storage cost for the tree (2^n+1 - 1 multiply by size of each hash digest).