Paper 2025/2236

Extending the SPHINCS+ Framework: Varying the Tree Heights and Chain Lengths

Abstract

The SPHINCS+ framework provides the underlying architecture for modern quantum resistant stateless hash-based signatures. Notable examples include the NIST standard SLH-DSA and its recent variants such as SPHINCS-α and SPHINCS+C. We extend the hypertree structure that underlies the SPHINCS+ framework by allowing trees of different heights to appear on different layers, and we plug generalized hash-based one-time signatures with chains of different lengths into the hypertree. We give a reduction showing how the security proof for the SPHINCS+ framework extends to these structural generalizations. These generalizations lead to an enlarged design space, opening up the possibility for finer-grained trade-offs. We perform a systematic exploration of the parameter space for the generalized structure guided by a thorough theoretical cost analysis that minimizes the number of variables to be enumerated in the searching process. As a result, we identify many parameter sets superior to state-of-the-art stateless hash-based signature schemes in terms of signature size, signing or verification efficiency. In particular, we provide some parameter settings not only enjoying smaller signature size, but also more efficient in signing and verification. The improvement can be significant if we do not pursue optimizing all performance metrics simultaneously. One of our 128-bit secure constructions intended to balance all metrics with size and verification speed as priorities is 9.8% smaller than SPHINCS+C-128s (27.6% smaller than SPHINCS+-128s, 18.3% smaller than SPHINCS-α-128s, and 22.5% smaller than SPHINCS+FP-128s). Further size reduction is possible with a greater sacrifice in speed. Moreover, we apply our technique to schemes supporting less than 264 signatures. We provide implementations and benchmark results for representative parameter sets.