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

Sakura specifies a tree hash mode for e.g. Keccak (SHA-3). Are there any reasons to use the Sakura tree hash mode in a Generalized Merkle Signature Scheme? It seems to me Sakura primarily solves a uniqueness problem with using tree hashes for large data when the depth of the tree is variable.

Trivially, if Sakura mode is not used and the depth $d$ tree-hash of data $M = M_0|M_1|...|M_{n-1}$ is $D$, then the depth $d-1$ tree hash of data $M'$ (where $M'_0 = f(M_0)|f(M_1)$ etc) is also $D$. If Sakura is used, such trivial collisions will be impossible.

This problem doesn't seem to exist in GMSS, considering that the leaf-nodes consist of OTS public keys and not plain text fragments.

share|improve this question
Even if such collision was possible for a GMSS, there was still the problem to retrieve the OTS private keys... Why do you say that this problem doesn't exist for a Merkle signature ? – Dingo13 Jul 17 '14 at 22:05
@Dingo13: The problem with recovering the OTS private keys, seems to make it infeasible for an adversary to produce an existential forgery from a GMSS signature, even if the depth parameter might be altered. – Henrick Hellström Jul 17 '14 at 22:29
That seems exact from a unforgeability standpoint. My question is useless. – Dingo13 Jul 18 '14 at 14:24
up vote 2 down vote accepted

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level.

The possible ambiguity of hashes is not relevant for hash-based signatures as for these the tree height and thereby the number of leaves are predefined.

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.