Paper 2017/933

Improving Stateless Hash-Based Signatures

Jean-Philippe Aumasson and Guillaume Endignoux


We present several optimizations to SPHINCS, a stateless hash-based signature scheme proposed by Bernstein et al. in 2015: PORS, a more secure variant of the HORS few-time signature scheme used in SPHINCS; secret key caching, to speed-up signing and reduce signature size; batch signing, to amortize signature time and reduce signature size when signing multiple messages at once; mask-less constructions to reduce the key size and simplify the scheme; and Octopus, a technique to eliminate redundancies from authentication paths in Merkle trees. Based on a refined analysis of the subset resilience problem, we show that SPHINCS' parameters can be modified to reduce the signature size while retaining a similar security level and computation time. We then propose Gravity-SPHINCS, our variant of SPHINCS embodying the aforementioned tricks. Gravity-SPHINCS has shorter keys (32 and 64 bytes instead of $\approx1$ KB), shorter signatures ($\approx30$ KB instead of 41 KB), and faster signing and verification for a same security level as SPHINCS.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. CT-RSA 2018
post-quantumsignatureshash functions
Contact author(s)
jeanphilippe aumasson @ gmail com
2018-01-09: last of 2 revisions
2017-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean-Philippe Aumasson and Guillaume Endignoux},
      title = {Improving Stateless Hash-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2017/933},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.