4
$\begingroup$

Based on the NIST submission it looks like the SPHINCS+-256s algorithm comes in at public key sizes of 64 bytes, private key sizes of 128 bytes, and signature sizes of 29,792 bytes.

What I can't seem to locate (or understand from the submission documentation) are implementation details suggesting how to use it. For that I have the following questions (all specifically for the SPHINCS+-256s algorithms)

  • How many signatures can you safely get out of it?

  • Are the signatures one-time use, or can you sign something and have it verified repeatedly without giving up the private key? (I'm assuming this is the "stateless" aspect, but want to be certain I'm not misunderstanding it.)

  • Are there any specific caveats involved?

The protocol I'm thinking of implementing with it would be along the lines of:

  • Publish the public key, signed with a different signature algorithm.

  • Retain the secret key.

  • Sign N messages, post signatures and messages publicly for verification.

What I'm trying to avoid would be the one-time signature aspects of most hash-based signature protocols where you sign something, distribute the thing, then post the solution proving you signed it at some later point while simultaneously making it unverifiable to future parties (since you give up the private information in the process of proving the signature belonged to you.)

Improve this question
$\endgroup$
5
  • $\begingroup$ "then post the solution proving you signed it at some later point while simultaneously making it unverifiable to future parties". Huh??? Valid signatures can be verified repeatedly to future parties; this is true both a stateless schemes such as Sphincs, and stateful schemes such as XMSS and LMS $\endgroup$
    – poncho
    Commented Dec 30, 2017 at 20:52
  • $\begingroup$ He probably misunderstood how the scheme works. When you reveal half your private key that half can only ever be used to sign the exact sequence of 1s and 0s which you revealed the private key for. $\endgroup$
    – user10653
    Commented Dec 30, 2017 at 20:57
  • $\begingroup$ I thought the point of one-time signatures was that you can only sign things once because it consisted of a process of share a public key securely --> sign content --> post signature of content --> other party receives signature and content --> signer posts solution --> other party confirms it was signer posting it or rejects it --> if it was the correct secret the private portion is public knowledge and no longer of use. $\endgroup$
    – CoryG
    Commented Dec 30, 2017 at 21:03
  • $\begingroup$ However, Sphincs is not a one-time signature scheme; it doesn't have the same limitations. Instead, you can sign a large number ($2^{50}$ or $2^{64}$) different messages with the same private key, while maintaining security... $\endgroup$
    – poncho
    Commented Dec 30, 2017 at 21:06
  • $\begingroup$ Also, I believe that you misunderstand a one-time signature. Instead, they're extensions of the original Lamport signature; the private key consists of two random values $r_0, r_1$, and the public key is $H(r_0), H(r_1)$; to sign the bit $i$, the signer reveals $r_i$ (and discards the other one); the value $r_i$ is the signature (and if the signer discarded $r_{1-i}$, no one can produce any other signature) $\endgroup$
    – poncho
    Commented Dec 30, 2017 at 21:16

1 Answer 1

Reset to default
7
$\begingroup$

Most of this was already explained in the comments but let me summarize this.

a) SPHINCS+ as SPHINCS are stateless signature schemes like RSA or (EC)DSA. You can use the secret key to sign a virtually unlimited number of messages. In practice, you can sign up to $2^{64}$ messages with SPHINCS+ ($2^{50}$ for SPHINCS) without allowing any kind of forgery.

b) Your idea of a one-time signature is wrong. A one-time signature scheme is a signature scheme which allows the user to sign a single (arbitrary) message securely. The resulting signature is a standard signature as you know it from RSA that can be verified by everyone and as often as you want. The limitation of one-time signature schemes is just that you can only use your key pair to sign one message. As soon as you sign two different messages, security drops almost instantly to zero (depends a bit on the setting, but lets ignore this). So, a one-time signature is no interactive protocol. Just think of it as an RSA signature where you are only allowed to use your secret key once.

c) SPHINCS (with and without +) is no one-time signature scheme as a) already states. It internally uses a one-time and a few-time signature scheme. So, you can use it like RSA / (EC)DSA.

[Details] If you would use a key pair more than $2^{64}$ times (which is almost impossible if you don't rent a massive server farm that does nothing else than signing messages with the same key pair for the next 20 years or so) security will slowly degrade as the probability of using a few-time signature key pair too often increases. [/Details]

d) There are no specific caveats involved. As stated above, you can use it like any other signature scheme. (Actually, it follows the NIST call so you can see the requirements there...)

e) As there also seems to be some confusion about stateless vs stateful: The difference between stateless and stateful signature schemes is that stateful schemes require the secret key to change after every signature. So, we should rather talk about a secret key state than a static secret key. The crucial point is, a secret key state must not be used twice. This means, you have to make sure that you do not accidentally reuse it (e.g., back-ups are a problem in this case if you cannot recover the last used state somehow). Stateless schemes are actually the "standard setting", i.e., RSA, (EC)DSA are stateless. For hash-based signatures stateless schemes are not trivial to build. They avoid all this trouble with state handling at the cost of worse performance.

Improve this answer
$\endgroup$
7
  • $\begingroup$ "If you would use a key pair more than $2^{64}$ times, security will slowly degrade"; that depends on how much more than $2^{64}$ you go (and what you consider "slowly"); if you use it $2^{65}$ times, security is only somewhat affected; if you use it $2^{74}$ times, security is effectively toast... $\endgroup$
    – poncho
    Commented Dec 31, 2017 at 17:52
  • $\begingroup$ Yes and no. The main question is how many signatures you see for a single FORS key pair. The probability that you see sufficiently many that breaking subset-resilience gets easy increases with the number of signatures made. I would have to check the actual numbers. However, indeed you should just try to avoid going beyond $2^{64}$. Shouldn't be that hard anyway ;-) $\endgroup$
    – mephisto
    Commented Jan 1, 2018 at 15:03
  • $\begingroup$ Actually, the main question is "given $2^z$ signatures, and the attacker selects another message and $R$, what is the probability that the attacker has seen all the hashes required to generate a signature. For $z=64$, this probability is tuned to be at most $2^{-256}$; for larger values of $z$, it decreases quite a bit. $\endgroup$
    – poncho
    Commented Jan 1, 2018 at 15:32
  • $\begingroup$ For the original Sphincs, analyzing FORS (HORST in Sphincs) in isolation made sense (as a forger could select which HORST tree to attack, hence he could directly attack the HORST trees that he has the most signatures based on). In Sphincs+, the exact FORS tree is selected based on the message (and $R$); hence the attacker has to select those, and hopes he selects a FORS tree that has been used a lot, and that all the values he needs from the FORS tree has actually been revealed $\endgroup$
    – poncho
    Commented Jan 1, 2018 at 15:37
  • $\begingroup$ You are right, that actually changed for SPHINCS+. Actually, with the parameter generation script you can exactly compute the remaining bit security after $2^p$ signatures. Intuitively, it should not drop super fast. But I will leave it to the reader to check the exact speed of degradation. $\endgroup$
    – mephisto
    Commented Jan 2, 2018 at 1:15

Your Answer

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

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