[Resource Topic] 2017/933: Improving Stateless Hash-Based Signatures

Welcome to the resource topic for 2017/933

Improving Stateless Hash-Based Signatures

Authors: Jean-Philippe Aumasson, 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.

ePrint: https://eprint.iacr.org/2017/933

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .