Paper 2022/059

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

Kaiyi Zhang, Hongrui Cui, and Yu Yu

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Hash-Based SignaturePost-Quantum CryptographySPHINCS+
Contact author(s)
yuyu @ yuyu hk
History
2022-01-18: received
Short URL
https://ia.cr/2022/059
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.