1
$\begingroup$

Suppose a 256 bit hash is used (SHA2, SHA3, ...). How does the Winternitz OTS perform at various signature sizes?

I'd want to compare to a generalized K-teeth Haircomb:

  • It's signature is $K$ of these 256-bit hashes
  • the public key is one hash.
  • We are signing a 256-bit message digest as well
  • the chain length is approximated¹ (per Whitepaper) by: $$X\approx2^{256/(K-1)}\times{(K-1)!}^{1/(K-1)}-K/2$$
  • Key Generation performs $X\times K+1$ hashes
  • Signing invocations perform $X\times(K-1)$ hashes
  • Verification invocations perform $X+1$ hashes.

Question: What are the equivalent Hash invocation counts for Winternitz OTS, as used by the SPHINCS+ standard for instance?

Note that I'm specifically asking for the number of hash invocations used for signing, verifying and key generation.

¹ $X$ (for one chain) is approximated as in this table (rounded numbers, inexact).

Improve this question
$\endgroup$
5
  • $\begingroup$ The original description of Winternitz OTS seems to be this. A more recent exposition and discussion is there. For the current SPHINCS(+) proposal, see this. Without the equivalent on haircomb OTS, the question is not answerable, and might be closed as such. Please give a definition of Haircomb OTS, or a link to that $\endgroup$
    – fgrieu ♦
    Jul 20, 2022 at 18:14
  • $\begingroup$ I've seen both. I don't get it. Only thing I see that w bits are signed simultaneously. That would suggest w = 256/K. Still, I don't understand the rest of it. The question is about Winternitz OTS, why should I explain haircomb? [Update] edited. Thanks a lot. I hope it's answerable now, I'm specifically asking for ballpark performance figures by various signature sizes, thanks. $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 18:40
  • $\begingroup$ Yes that should makes the question answerable. Would you mind that I edit the question to beautify the formula into $X\approx2^{256/(K-1)}\,{(K-1)!}^{1/(K-1)}-K/2$, and replace the huge table with a link to an online program computing that? $\endgroup$
    – fgrieu ♦
    Jul 20, 2022 at 18:43
  • $\begingroup$ Please do. thanks. There is no generalized haircomb paper that I'm aware of. The inventor defined haircomb OTS for K=21, here. $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 18:52
  • $\begingroup$ Haircomb may be a decent solution if what you care about is signature size ($K$) and the verification time and don't care about the public key generation or signature generation time. If those things are also important, haircomb makes little sense. $\endgroup$
    – poncho
    Jul 20, 2022 at 21:26

2 Answers 2

Reset to default
2
$\begingroup$

Question: What are the equivalent Hash invocation counts for Winternitz OTS, as used by the SPHINCS+ standard for instance?

Well, that at least I can answer.

For Sphincs+ (or, in general, WOTS with $w=16$), with $n=32$ (256 bit hashes), we have $x=15$ (because $w=16$ and the chain is one less than that), and $k=67$.

So, during OTS key generation, we perform $kx+1 = 1006$ hashes [1], signing is approximately [2] $(k/2)x = 503$ hashes, and verification is approximately $(k/2)x + 1 = 504$ hashes.

For Sphincs+, OTS key generation is the main cost (as we perform it quite a lot during Sphincs+ signature generation); Haircomb appears to require considerably more, and so it would not be a good fit.

[1]: Somewhat misleading; the final hash is rather more expensive, as the amount of data hashed is considerably larger.

[2]: Approximately because it depends on the weight of the value being hashed.

Improve this answer
$\endgroup$
5
  • $\begingroup$ how do you one time sign a w=16bit number with a 2 chains of length x=15 hashes? $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 20:05
  • $\begingroup$ I get it now. You are actually signing a 128bit number. So what makes me unable then, for instance, take one of those 67 values, calculate one more hash, and claim a distinct 256bit msg m2 was what was actually signed?? I can solve that different m2 quite easily. $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 20:25
  • $\begingroup$ Furthermore there is haircomb signing 128bits with 67 teeth and 64 hashes for verification. How is the 504 hashes for verification superior then? $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 20:42
  • $\begingroup$ @HugoFranklin: actually, we're signing a 256 bit number. As for why a forger can't advance one of the hashes, that's because of the inverse checksum (which takes up 3 of the chains); advancing one chain always requires some other chain to back up (which the forger cannot do) $\endgroup$
    – poncho
    Jul 20, 2022 at 21:00
  • $\begingroup$ @HugoFranklin: as for why WOTS is better for Sphincs+ (even though it requires more hashes during verification): the number of hashes done during verification isn't that important (as long as it is not excessive); it's the number of hashes during public key generation time that's considerably more critical in this use case. $\endgroup$
    – poncho
    Jul 20, 2022 at 21:01
0
$\begingroup$

Per Hulsing's 2017 WOTS+ paper, section 2.2, messages of $m$-bits and chains of length $w-1$ requires $\ell=\ell_1+\ell_2$ hash outputs to form a signature where $$\ell_1=\left[\frac m{\log w}\right],\quad\ell_2=\left[\frac{\log(\ell_1(w-1))}{\log w}\right]+1$$ and logarithms are to base 2. In your notation $K$ corresponds to $\ell$, $X$ corresponds to $w-1$ and $m$ corresponds to 256.

WOTS+ signatures make most sense when $\log w$ is a power of 2 and we can tabulate the obvious range

$\log w$ $w-1=X$ $\ell=K$
2 3 128+5=133
4 15 64+3=67
8 255 32+2=42
16 65535 16+2=18
32 4294967295 8+2=10

The numbers in your haircomb table bear closest comparison to the two last entries. The entries for $K=18-20$ are all majorised by the WOTS+ signature with $w=2^{16}$ and the WOTS+ signature with $w=2^{32}$ is majored by the $K=10$ haircomb.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Aren't you actually signing a 128bit number (message digest)? What makes me unable to calculate one more hash if any of the say 67 hashes and claim that a different msg is what was actually signed? $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 20:49
  • $\begingroup$ Furthermore there is haircomb signing 128bits with 67 teeth and 64 hashes for verification. How is the 504 hashes for verification superior then? $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 20:52
  • $\begingroup$ I am signing a 256-bit number. The check sum of $\ell_2$ chains prevents forgery from subchains. I really do recommend that you read Hulsing's paper. The haircomb has a good verification time, but this is hugely outweighed by the issue of key generation for multi-signature constructions such as SPHINCS+. $\endgroup$
    – Daniel S
    Jul 20, 2022 at 21:02
  • $\begingroup$ thanks a lot, for a hobbyist like me it means a lot. $\endgroup$
    – Hugo Franklin
    Jul 20, 2022 at 21:26

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.