Why do we need both bitmasks and keyed hash in SPHINCS+

I think one of them is related to multitarget attacks and the other is related to collision attacks. But I cannot find how hash based crypto related to hash collisions.

1-) Consider the following Lamport one time signature scheme

• Assume a 128 bit hash function $$H$$ is used
• Randomly choose $$p_i$$ and $$r_i$$ for $$1\leq i \leq 128$$
• $$SK=\{(p_i,r_i)\}_i$$ is the secret key and $$PK=\{(H(p_i),H(r_i))\}_i$$ is the public key.
• For the message $$M$$, we take the hash $$h=H(M)$$. Let $$h=h_1h_2\cdots h_{128}$$
• For signing $$M$$, we publish $$p_i$$ if $$h_i=0$$ and $$r_i$$ if $$h_i=1$$ for each $$i$$.

How the adversary can apply $$2^{64}$$-cost attack?

What is the security of this scheme? (I think 120-bit because multitarget applies i.e. it is enough to find at least one of $$p_i,r_i$$'s. A random guess has prob $$\frac{256}{2^{128}}$$)

2-) Consider the original Merkle tree with $$2^{10}$$ Lamport one time signatures without bitmasks with hash function $$H$$ used above. What is the security of this scheme? (Similar to above we have 120-t bit security after $$2^t$$ signatures because $$\frac{256\cdot 2^t}{2^{128}}$$)

I think if we use keyed hash OR bitmasks here, the security of this scheme will be 128-bit. So why we need both?

OR, what is the security of SPHINCS+ without keyed hash or bitmasks?

I think if we use keyed hash OR bitmasks here, the security of this scheme will be 128-bit. So why we need both?

Actually, we don't. Sphincs+ (at least, the round 3 version) has two sets of parameter sets, "simple" and "robust". Simple only has the "keyed hash" (which I will interpret at the address structure which is included in every PRF, F, H and T evaluation; not really a key, as it is not secret), while robust has both the keyed hash and bitmasks.

Why is this? It comes down to provable properties; simple has 128-bit security (for Level 1 parameter sets) if we assume that the hash function acts like a random Oracle; for robust, we get that security level on the weaker assumption that computing second preimages of the hash function takes $$2^{128}$$ time.

• Thanks very much for the clarification. I still cannot find any collision attacks on hash based schemes. The paper "Digital Signatures Out of Second-Preimage Resistant Hash Functions" says that "We propose a new construction for Merkle authentication trees which does not require collision resistant hash functions;". Are there any schemes the security relies on the collision resistant hash functions. What is the case for my examples above?
– user
Mar 18, 2022 at 6:09
• Another interesting sentence from ia.cr/2017/349: "XMSS uses a variant of WOTS (WOTS+ [13]) that eliminates the requirement for a collision resistant hash function." Why the securtity of WOTS suffers from collisions whereas WOTS+ not.
– user
Mar 18, 2022 at 8:01