Paper 2017/933

Improving Stateless Hash-Based Signatures

Jean-Philippe Aumasson and Guillaume Endignoux

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.CT-RSA 2018
Keywords
post-quantumsignatureshash functions
Contact author(s)
jeanphilippe aumasson @ gmail com
History
2018-01-09: last of 2 revisions
2017-09-25: received
See all versions
Short URL
https://ia.cr/2017/933
License
Creative Commons Attribution
CC BY

BibTeX

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