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

Kaiyi Zhang; Hongrui Cui; Yu Yu

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

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Hash-Based Signature Post-Quantum Cryptography SPHINCS+
Contact author(s): kzoacn @ sjtu edu cn
rickfreeman @ sjtu edu cn
yuyu @ yuyu hk
History: 2023-06-08: revised; 2022-01-18: received; See all versions
Short URL: https://ia.cr/2022/059
License: CC BY

BibTeX

@misc{cryptoeprint:2022/059,
      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{https://eprint.iacr.org/2022/059}},
      url = {https://eprint.iacr.org/2022/059}
}