2
$\begingroup$

In post-quantum signature schemes that are (to put it simply) built out of merkle trees, they usually employ some sort of OTS scheme on the very bottom leaves. I.e WOTS Winternitz scheme.

A relatively simple scheme such as Merkle is making a bunch of Lamport/WOTS keys and putting them on a merkle tree.

Is it possible to instead put the WOTS scheme itself on a tree, where each leaf represents a byte value, and where each leaf is a simple chain of 1 hash?

By tripling the computation required to make a single use WOTS key, it becomes a potentially finite use key, and you don't have the problem of being able hash forward that is usually resolved with checksums.

Are there some obvious security downsides to doing this?

Improve this question
$\endgroup$
4
  • $\begingroup$ "To put simply, the first 16 bytes of a message digest are signed based on the second 16 bytes."; no, in Sphincs/Spincs+, bits from the hash are used to select individual entries in the few-time-signature scheme (HORST or FORS), which are authenticated using the authentication path. There isn't any intrabyte interaction such as you describe. Now, I don't quite follow your question; does it arise from this misunderstanding of Stateless schemes/ $\endgroup$
    – poncho
    Nov 25, 2020 at 21:28
  • $\begingroup$ @poncho I wouldn't proclaim to understand SPINCS very well. I have edited, hopefully it is a little clearer. My question is more around placing WOTS into a Merkle tree. I just wanted to try and show (poorly in retrospect) I understand how trees are used in general. I don't expect this is an original idea (if it is tangible). I just can't find it by searching anywhere. $\endgroup$
    – Modal Nest
    Nov 25, 2020 at 21:36
  • $\begingroup$ WOTS works by hashing a secret key by an amount determined by the "units" of the message. Am I reading this question correctly that you're suggesting to replace that "chain" operation with a "tree" operation / positioning? $\endgroup$
    – SEJPM
    Nov 25, 2020 at 21:45
  • $\begingroup$ @SEJPM Yeah exactly, except by leaf position. Each bottom leaf being the single hash of a secret value. In the diagram here the L1,etc being the secret key provided to sign a byte value. $\endgroup$
    – Modal Nest
    Nov 25, 2020 at 22:00

2 Answers 2

Reset to default
0
$\begingroup$

This question is essentially "can we put the HORS scheme on a tree". And the answer is yes, as it is the basically HORST.

The question adds confusion by mentioning a Merkle tree and not mentioning an index. The actual question is (or should've been) "can x HORS public key sets be put on trees with each HORS tree being used to sign each of the x bytes".

Maybe it is not normal to think of HORS/T as WOTS compressed (or Lamport inflated) on an index/tree, but I will leave the question in case it helps anyone else who does.

Improve this answer
$\endgroup$
-3
$\begingroup$

Yes, any one time scheme (such as lamport, WOTS) can be turned many time scheme by placing the public keys into a merkle tree leaves and considering the merkle root to be the new public key.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have removed the "haircomb" example from your answer as it seems to incite negative feelings based on prior aggressive promotion attempts for this scheme and doesn't add much to the answer as it stands anyways. Note however that the given interpretation of the question seems to be incorrect as it asks more about a variant of WOTS with the chain processing replaced by a tree processing instead of aggregating multiple schemes. $\endgroup$
    – SEJPM
    Nov 25, 2020 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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