Paper 2022/059

SPHINCS-$\alpha$: A Compact Stateless Hash-Based Signature Scheme

Kaiyi Zhang, Shanghai Jiao Tong University
Hongrui Cui, Shanghai Jiao Tong University
Yu Yu, Shanghai Jiao Tong University

Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. Nevertheless, a major drawback that makes it less favorable to deploy in practice is the (relatively) large size of the signatures, and long signing and verification time. In this paper, we introduce SPHINCS-$\alpha$, a stateless hash-based signature scheme, which benefits from a twofold improvement. First, we provide an improved Winternitz one-time signature with an efficient size-optimal encoding, which might be of independent interest. Second, we give a variant of the few-time signature scheme, FORC, by applying the Winternitz method. Plugging the two improved components into the framework of the state-of-the-art (stateless) hash-based SPHINCS$^+$, with carefully chosen parameter choices, yields a certain degree of performance improvement. In particular, under the ``small'' series parameter set aiming for compact signatures, our scheme reduces signature size and signing time by 8-11% and 3-15% respectively, compared to SPHINCS$^+$ at all security levels. For the ``fast'' series that prioritizes computation time, our scheme exhibits a better performance in general. E.g., when instantiating the simple tweakable hash function with SHA-256, our scheme reduces the signing and verification time by 7-10% and up to 10% respectively, while keeping roughly the same signature size. The security proofs/estimates follow the framework of SPHINCS$^+$. To facilitate a fair comparison, we give the implementation of SPHINCS-$\alpha$ by adapting that of SPHINCS$^+$, and we provide a theoretical estimate in the number of hash function calls.

Note: This paper is subsumed by eprint 2023/850

Available format(s)
Public-key cryptography
Publication info
Hash-Based SignaturePost-Quantum CryptographySPHINCS+
Contact author(s)
kzoacn @ sjtu edu cn
rickfreeman @ sjtu edu cn
yuyu @ yuyu hk
2023-06-08: revised
2022-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaiyi Zhang and Hongrui Cui and Yu Yu},
      title = {SPHINCS-$\alpha$: A Compact Stateless Hash-Based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2022/059},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.