7

What are the differences between Gravity-SPHINCS and SPHINCS+ from security and practicality standpoints? Are they just different implementations of the underlying SPHINCS algorithms or are they functional variations on the underlying algorithms?

CoryG
  • 549
  • 2
  • 9

1 Answers1

7

Gravity-SPHINCS and SPHINCS+ are two different improvements of the original SPHINCS algorithm. Both change the few-time signature scheme HORST (used in SPHINCS) in slightly different ways. However, both are variations of HORST. This leads to variable length signatures for Gravity-SPHINCS and fixed length signatures for SPHINCS+ which are as long as the signatures one would obtain from using the Gravity-SPHINCS few-time signature scheme in SPHINCS+ in the worst case. However, the often shorter variable length signatures come at the cost of far more complicated signing and verification.

Moreover, both change the way the index of the used few-times signature scheme gets computed. While different, both achieve that the index can be verified by the verifier which was not the case for SPHINCS. Finally, Gravity-SPHINCS uses the assumption that collision-finding for quantum computers is as slow as second-preimage finding under certain assumptions about storage access times. Hence, Gravity-SPHINCS slightly simplifies the way hashing is done in the construction at the cost of only achieving a security reduction from collision resistance of the internal hash function. On the opposite, SPHINCS+ gets a security reduction from second-preimage resistance of the internal hash function (there are different assumptions on the hash function used to compress the message in both proposals).

So to summarize, the schemes follow the same high level design principle but instantiate it in very different ways. Which one is better probably depends on what you want.

mephisto
  • 2,870
  • 18
  • 28
  • What kind of a size difference would be espected on average for the signatures? Are they both one-time use and just stateless or are they indefinite-use and stateless like RSA? – CoryG Dec 29 '17 at 17:25
  • @CoryG: they are multiple use; neither can work in the 'indefinite-use' in theory, however in practice (no more than $2^{64}$ signatures per public key), there's not an issue. – poncho Dec 29 '17 at 17:26
  • 3
    (+1) "Which one is better probably depends on what you want." - I think a summary that says "If you require property X, then choose algorithm Y" would make your answer excellent – Ella Rose Dec 29 '17 at 17:40
  • 1
    What's the difference between the two different security reductions in practice? – CoryG Dec 29 '17 at 19:19
  • 1
    The difference between the security reductions is that Gravity-SPHINCS really needs a collision resistant hash function while SPHINCS+ can go with a second-preimage resistant one for the internal functions (the 2n to n bit and n to n bit hashes). The reason is that although a collision for those inner hashes does not really allow an attack on Gravity-SPHINCS, it allows for massive multi-target attacks: Find a preimage for one out of $~2^{80}$ values. – mephisto Dec 29 '17 at 20:20
  • 1
    If I find the time I will extend the answer towards a guide to choose the right scheme. – mephisto Dec 29 '17 at 20:21
  • @mephisto So in something like a blockchain SPHINCS+ would be better than Gravity-SPHINCS even though it would on average require larger amounts of data because the availability of many targets makes Gravity-SPHINCS susceptible to attack across more hash functions than SPHINCS+? – CoryG Dec 29 '17 at 21:37
  • Yes, kind of. Moreover, the SPHINCS+ code allows for far more different parameter sets such that you can choose. However, in a block chain setting, I would normally suggest stateful signature schemes like XMSS or LM-HSS as you already have to deal with a state anyway. – mephisto Dec 30 '17 at 20:52