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?
1 Answer
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.
-
$\begingroup$ 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? $\endgroup$– CoryGDec 29, 2017 at 17:25
-
3$\begingroup$ (+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 $\endgroup$ Dec 29, 2017 at 17:40
-
1$\begingroup$ What's the difference between the two different security reductions in practice? $\endgroup$– CoryGDec 29, 2017 at 19:19
-
1$\begingroup$ 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. $\endgroup$– mephistoDec 29, 2017 at 20:20
-
1$\begingroup$ If I find the time I will extend the answer towards a guide to choose the right scheme. $\endgroup$– mephistoDec 29, 2017 at 20:21