After quite some time without writing any news (too busy) I want to take a moment to announce our submission to the NIST “not-a-competition”. While I am involved in three submissions, I took lead for the hash-based signature submission which I will talk about here.

Over the two years since we published SPHINCS, we collected a lot of nice ideas to reduce the signature size and to speed up the scheme.  So, for the NIST submission we reviewed all of them and built SPHINCS+ in the process. SPHINCS+ is SPHINCS in terms of high level scheme design but we tweaked some of the internals — especially the few-times signature scheme. Let me summarize the changes we made:

• Multi-target attack protection: We added the mitigation techniques which we
  proposed in our PKC 2016 paper (Mitigating Multi-Target Attacks in Hash-Based Signatures). This was already the plan when publishing that paper. We just discussed it in terms of XMSS there as that was the smaller example. The basic concept is to use a different hash function for each call. Each hash function call is
  keyed with a different key and applies different bitmasks. Keys and bitmasks are
  pseudorandomly generated from an address specifying the context of the call, and
  a public seed. To get an abstraction we now introduced the notion of tweakable hash functions which in addition to the input value takes a public seed and an address.
• Tree-less WOTS+ public key compression: The last nodes of the WOTS+ chains
  are not compressed using an L-tree but using a single tweakable hash function
  call. This call again receives an address and a public seed to key this call and to
  generate a bitmask as long as the input. This was not possible before without blowing up the public key. Now, as we generate bitmasks pseudorandomly, this has no influence on public key size.
• FORS: We replace the few-time signature scheme (FTS) HORST by FORS — Forest Of Random Subsets. A FORS key pair does not consist of a single
  monolithic tree but of k trees of height log t. The leaves of these trees are the hashes of t secret key elements making a total secret key of kt elements.
  The public key is the tweakable hash of the concatenation of all the root
  nodes as for the WOTS+ public key.  The big difference to HORST is that we now got a dedicated set of secret key values per index derived from the message. While it first might look as if the key size goes up and speed goes down, this only applies when using the same parameters as for HORST. The advantage is that we can now use much smaller parameters and thereby in the end gain in signature size and speed.
• Verifiable index selection: In SPHINCS the HORST key pair used to sign the message was selected generating an index in a pseudorandom manner. As a secret seed value was involved, a verifier was unable to check if that index was actually generated that way.  This had the disadvantage that an adversary targeting HORST was able to mount a multi-target attack, using one hash computation to target all HORST instances at once.
  This is not possible anymore. We now compute the index together with the message
  digest as
  ( md || idx ) = H ( R, PK, M )
  where PK is the SPHINCS+ public key and R is a (pseudo-)randomly generated value which becomes part of the signature. Hence, every message that an adversary tries becomes now directly linked to a FORS instance and is unusable for any other instance. In addition, this allows us to omit the index in the SPHINCS+ signature.

We were discussing a lot of other ideas including a trade-off between secret key and signature size using a higher top tree and storing intermediate layers in that tree as well as short-term state (STS) versions. The former we discarded as it massively slows down key generation and complicates implementation at only a minimal size reduction (about one WOTS+ signature). The latter seems incompatible to the verifiable index selection (and would not have fit the NIST API anyway).

These changes allowed us to define parameter sets with signature sizes of as little as 8kb! Admittedly, at NIST security level 1 and a few seconds for signing. However, the implementation is unoptimized and for many use-cases like certificate or code signing about one second actually seems fine. Even at the highest security level (NIST 5) we get down to 30kb at about the same speed. This is compared to SPHINCS with 41kb. Moreover, NIST asked to assume a key pair is used for 2^{64] signatures. For the old SPHINCS we assumed 2^{50} signatures. This number of signatures has a huge impact on SPHINCS(+) signature size. Hence, if we are willing to make less conservative assumptions on the number of signatures (I personally find 2^{50} already pretty conservative) we could get even smaller signatures. Of course, the parameters we proposed are just what we consider well balanced. At the same level of security there exists a magnitude of possible parameters (one can still get smaller at the cost of speed). We deliver a script that allows to enumerate those parameters so you can optimize for any metric of your choosing.

Finally, we present three different incarnations of SPHINCS+:

• SPHINCS+-SHA3 (using SHAKE256)
• SPHINCS+-SHA2 (using SHA2)
• SPHINCS+-Haraka (using the Haraka short-input hash function)

We are currently setting up a website for the submission and will publish all material also there. I will add the link here as soon as we are done.