Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the section 2 (page 42) of the book "Post Quantum Cryptography", it says:
Then he generates the one-time signature $\sigma_{\text{OTS}}$ of the digest using the $s$-th one-time signature key $X_s$, $s\in\{0,\dots,2^H-1\}$.
My question: Is $s$ chosen in random form? Is it possible to have $s$ collisions to the signature process?
If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$ $2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures.
If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless,
but can be expected to fail after giving approximately $\:\Theta\left(2^{H/2}\right)\:$ signatures.
If he keeps an initially empty list as state, chooses $s$ at random from the leaves that are not on the list, puts $s$ into the list, and makes the list empty again if at this point it contains all of the leaves , then the scheme will need to keep an amount of state that grows linearly with the number of signatures given.
In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures.
If he chooses $s$ to be one more than the previous value of $s$ when there is a previous
value of $s$ and such a leaf, and chooses $s$ equal to $0$ in all other cases,
then the scheme will be deterministic but will need to keep $H$ bits of state.
In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures, and until that point,
each signature will also reveal and authenticate how many messages were previously signed.
That will stop an adversary from reordering the messages but will also reduce the signer's privacy.
(The following option was suggested by Paŭlo Ebermann in the comments.)
If he chooses $c$ in the way the previous paragraph described him choosing $s$, and chooses
$s$ by applying a PRP to $c$, then the scheme will be deterministic and need to keep $H$ bits
of state and fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ bits of state. $\:$ In this case, the scheme will enable
anyone who has the PRP's key (this will usually just the signer, although anyone else who
learns the signing key will know the PRP key too) to determine how many messages were
signed before a specific signature was given, and hide that information from everyone else.
I suspect that the most important thing is that the scheme be deterministic and stateless.
