Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 5 down vote accepted

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.

share|improve this answer

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 :

  • find preimage m such that h(m) = public key. (preimage resistance) Otherwise, the verifier may be able tricked into thinking that the legitimate user had sent him the valid signatures even through the legitimate user did not.

  • find another valid one-time signature of the message m such that H(m) = H(m'). (second preimage resistance) Otherwise, attacker may be able to forge new signatures.

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.