Paper 2026/2502

Shorter Hash-Based Signatures via Guarded Sharing in a DAG Model

Abstract

Stateless hash-based signatures are among the most important post-quantum signature schemes. Although they have been standardized by NIST, they still have large signatures. Within these constructions, the few-time signature component is receiving increasing attention. Recent work has introduced new techniques, including rejection sampling, forced pruning, bucket thinning, and hash chains. In this work, we continue to improve few-time signatures with a new technique, guarded sharing. Our construction moves beyond the previous tree-based model to a DAG-based signature. By combining guarded sharing with bucket thinning, hash chains, and rejection sampling, we obtain a new signature scheme called BGS-CC. Our construction further improves on the state-of-the-art few-time signature BPORS-C+BFP. Most notably, for 128-bit security and a small use quota of $Q=2^{24}$, it yields complete signatures of 2,228 bytes. To our knowledge, this is the first SPHINCS-based stateless signature to be shorter than the 2,420-byte signatures of the standardized module-lattice scheme ML-DSA-44.