Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / post-quantum, signatures, hash functions

Original Publication (with minor differences): CT-RSA 2018

Date: received 25 Sep 2017, last revised 9 Jan 2018

Contact author: jeanphilippe aumasson at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180109:215650 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]