International Association
for Cryptologic Research

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-$\alpha$ 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. While these structural generalizations do not affect the original security proof for the SPHINCS+ framework as long as the encoding function employed by the underlying one-time signature is injective and incomparable, they lead to 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 constructions with 128-bit security is 8.1% smaller than SPHINCS+C-128s (26.2% smaller than SPHINCS+-128s and 16.7% smaller than SPHINCS-$\alpha$-128s). At the same time, it is faster in verification but slower in signing than SPHINCS+C-128s. Further size reduction is possible with a greater sacrifice in speed. We provide implementations and benchmark results for representative parameter sets.