1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user
    Mar 18 at 6:09
  • $\begingroup$ 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. $\endgroup$
    – user
    Mar 18 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.