# Is NOTS a valid one time signature scheme?

I've just learn about NOTS, a quantum-resistant signature scheme based on hash functions that claims to have much shorter signature and key sizes. Is this signature scheme known to be secure? From looking at the paper, I'm suspicious about the way it uses modulus of indices (couldn't an adversary just generate a hash with the same char counts?). Is it legit?

Is it legit?

No, and you hit on the reason - the algorithm converts the message into a series of 16 values from 1 to 128, and then signs based only on that. That's a total of 112 bits; actually, it's somewhat worse than that, as the algorithm they use to convert the message hash into the series of 16 values will generate values that always sum (mod 128) to 64;. That means that with a valid message/signature pair, you can find a second image that translates into the same first 15 values [1] (and thus would be a valid message for the same signature) with an expected $$O(2^{105})$$ effort. Even worse, because the translation doesn't involve any randomization, you can expect to find a collision (and then ask one message to be signed; the second message with that same signature would be a forgery) with an expected $$O(2^{52.5})$$ effort.

The paper also makes a series of erroneous statements; here are the ones that jump out to me:

• They claim that "Other type of OTS/FTS schemes (except WOTS and its variants) are not capable for allowing computation of the public key from the signatures unless a huge additional set of information is provided to the verifier."; this is incorrect. For every every hash based signature scheme I've seen, the verification process was essentially "take the message, the signature and possibly some small amount of data from the public key, compute a series of hashes, and if the result matches what's in the public key, you win". That is, all you need to reconstruct the public key is this "possibly small amount of data", not "a huge additional set of information". A minor point, except that they emphasize this repeatedly.

• Their evaluation, which consists of comparison with some selected other hash based signature schemes (but nothing with a large W parameter); however they insist that they run the competitive schemes with an unrealistically large hash size (n value) - they note that their scheme (which does have a large W parameter and smaller n value) results in smaller signatures; not surprising when they put their thumb on the scale so heavily.

• They also state that "Finally, NOTS has achieved all these reductions in key and signature sizes without compromising the security level"; even though a glance at their table shows that they claim NOTS has significantly lower security level (not counting the point I made above about how it doesn't even achieve that).

• As for their security proofs, well, that consists of algorithms they provide which takes a forgery and generates a collision; however going through the algorithm shows that, even when given a forgery, it can fail (that is, not produce a collision); hence it is invalid as a proof.

[1]: Once you first a match on the first 15, you'll always get a match in the sixteenth.

• Thank you. So right now the state of art in terms of quantum resistant signature size is WOTS+ right? Commented Jul 7, 2021 at 23:39
• @MaiaVictor: for hash based signatures, LM-OTS signatures is smaller (mostly because it supports larger W values). Of course, if you don't restrict yourself to hash based signatures, Rainbow is far smaller... Commented Jul 8, 2021 at 3:33
• @poncho... "Rainbow..." didn't you forget a teeny-tiny detail their...:-P and the originally published WOTS+ allows for arbitrary (even non integral powers of 2) values for w. Only the RFC restricted w to 16 (although it does allow other values, it just does not define parameter sets using them). Commented Jul 16, 2021 at 16:42
• @mephisto: at NIST level 1, Rainbow (at least, the round 3 submission) has a signature size of 66 bytes. To achieve such short signatures (even assuming 16 byte hashes), WOTS+ would require a $W≈2^{64}$, and even if we consider such a huge $W$ practical, the WOTS+ ADDR structure assumes that $W<2^{32}$ Commented Jul 16, 2021 at 18:10
• @poncho: Sure, but in this context you should also mention the public key size which may be relevant to a user. Commented Jul 18, 2021 at 1:05