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?
