1
$\begingroup$

The state of the art hash-based post-quantum signature schemes, like Sphincs and XMSS, are using variations of WOTS (Winternitz OTS), like WOTS+, that require extra random bitmasks along with the public key.

Some history: These bitmasks were initially introduced from Dahmen et al. in order to build hash-based signatures out of 2nd-preimage resistant functions. The main benefit is that collision-resistance is not required and the signature schemes are NOT affected by the birthday paradox. The aforementioned allows WOTS+ to use hash functions with shorter output than original WOTS for the same security level.

However, a drawback of W-OTS+ compared to previous W-OTS variants is the increased public key size due to the inclusion of these bitmasks; even if we reuse the bitmasks, we still need a list of them. For instance this affects the Sphincs key size. On the other hand, if I understand correctly, the XMSS rfc makes reference on a single SEED required, that will be used in a PRF to generate all required bitmasks.

That said, is it correct to say that we don't need to send a list of bitmasks, but a single n-sized SEED is enough?

Note that WOTS+ key compression using L-trees is out of scope. I know bitmasks are used there as well. This question focuses on the original WOTS+ scheme without public key compression.

$\endgroup$
2
$\begingroup$

The XMSS Internet Draft actually does not implement the original XMSS scheme but XMSS-T as described in Mitigating Multi-Target Attacks in Hash-based Signatures, by Hülsing, Rijneveld, and Song (PKC 2016). There also a security reduction is given that shows that exactly this is ok (using a SEED instead of a list). It also introduces keying all hash function calls (which is also implemented in the Internet Draft) to prevent multi-target (second-)preimage attacks. The drawback of using a SEED is that this step requires a (Q)ROM proof. The reason is that the standard model PRF / PRG security properties all require the seed / PRF key to be kept secret (while it gets published in the given scenario).

$\endgroup$
  • $\begingroup$ Exactly what I was looking for (+1 for the reference). Is there a reason for the SEED being part of the public key and not just attaching it to the signature? Reasoning: smaller pubKey, SEED is secret until I sign. $\endgroup$ – Kostas Chalkias Mar 5 '18 at 10:00
  • 1
    $\begingroup$ Well, for XMSS / SPHINCS this did not make any sense... for WOTS I see the point. However, then the security reduction does not apply anymore as it would allow an adversary to select the seed in a forgery. I guess this really gets you into trouble. So I would strongly advise against this. From the seed being secret until you sign, you do not gain any additional security and the combined size of sig and pk also does not change. $\endgroup$ – mephisto Mar 5 '18 at 12:33
  • $\begingroup$ Btw. If this is exactly what you are looking for, you can mark this as right answer :-) $\endgroup$ – mephisto Mar 5 '18 at 12:34

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.