Convert a state-dependent hash-based signature scheme into a stateless message-dependent one

Question

Suppose we have an XMSS^MT instance that is capable of signing up to 2^60 messages securely when given some state-dependent information, I could envision making it stateless as follow:

1. Hash the message and truncate the digest $t$ to 60 bits.

2. Split $t$ into $d$ (Hypertree layers) chunks and interpret as integer leaf indicies at every layer.

3. At each layer, each leaf signs a WOTS+ public key generated from a seed created by encrypting the leaf index.

Obviously this would reduce the security of the scheme from acceptable to merely 30 bits, because the signing key is selected based on a 60-bit hash digest.

Q1: Can this be salvaged by using some unique-mapping function? Or we have a better chance rely on UTC time or use SPHINCS-family schemes?

Q2: What benefit can we get out of using XMSS^MT over SPHINCS-family schemes?

Answer 1

Can this be salvaged by using some unique-mapping function?

A "unique-mapping function"; that is, a hash function that somehow never gets a collision???

Or we have a better chance rely on UTC time

Which means that it's still stateful (it's just that the state resides in the time)

Or use SPHINCS-family schemes?

Actually, what you propose isn't that far off of Sphincs+ (or Gravity Sphincs); both take your general approach of taking the message, hashing it, and using that value to select the path through the hypertree (or, as you put it, interpret as integer leaf indicies at every layer). The difference is that, at the bottom, they use a Few-Time signature scheme rather than a one-time signature scheme (and so the hypertree doesn't have to be so tall as to make collisions improbable; they just need to make sure that you are unlikely to get too many collisions at the same spot).

What benefit can we get out of using XMSS^MT over SPHINCS-family schemes?

Well:

• The signatures are considerably smaller

• The signature generation time is considerably faster (and the generation time for the related LMS scheme is faster still)