Return to Question

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.

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.

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? (either as part of the public key or signature).

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.

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.