SPHINCS and HORST: can we sign the same message twice? I was reading about SPHINCS which uses layers of WOTS+ trees and a bottom layer of HORST trees. HORST is a few time signature scheme, using a selection function you can sign at least twice without compromising security.

I was then reading this blogpost where for the description of SPHINCS says:


  Signing the same message again should use the same HORST, signing two
  different messages should make use of two different HORST with good
  probabilities.


So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme. Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?
So as I understand, given the fact that the random bit masks are constant after instantiation of the scheme, SPHINCS is a deterministic scheme.


Actually, Sphincs as originally proposed is deterministic; however there is nothing preventing a signer from selecting a path randomly (rather than making it a secret function of the message).

But yes, if we assume that a signer doesn't decide to do this, you are correct; signing the same message twice will produce the same signature.


  Also it is susceptible to replay attacks since signing the same message twice produces the same signature. Am I correct?


I'm not sure what a 'replay attack' would mean for a signature algorithm.  For any signature algorithm, the adversary can take a message and valid signature pair, and present it multiple times; the verification algorithm would accept it every time; this is not unique to Sphincs.  Now, there may be other things in the protocol to reject this situation; that's not the job of the signature verification algorithm.

In addition, seeing the same signature multiple times would inform the adversary that the same message was being signed multiple times; on the other hand, we don't assume that signature algorithms provide privacy, and so that is also not considered an issue.

BTW: if you look at Sphincs+, things change; they made the signature algorithm nondeterministic (not because they are afraid of determinism, but instead to try to avoid relying on collision resistance of the hash function; everything else within Sphincs+ relies on preimage or second preimage resistance).