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

Question

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?

Answer 1

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.