I'm reading about Merkle tree signatures, and I would like to know whether the security of that scheme depends on the height of the tree, or does it only depend on the hash function being resistant to collision?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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).
