Paper 2022/059
SPHINCS-$\alpha$: A Compact Stateless Hash-Based Signature Scheme
Abstract
Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. As a core building block of hash-based signatures, the efficiency of one-time signature (OTS) largely dominates that of hash-based signatures. The WOTS$^{+}$ signature scheme (Africacrypt 2013) is the current state-of-the-art OTS adopted by the signature schemes standardized by NIST---XMSS, LMS, and SPHINCS$^+$. A natural question is whether there is (and how much) room left for improving one-time signatures (and thus standard hash-based signatures). In this paper, we show that the WOTS$^{+}$ one-time signature, when adopting the constant-sum encoding scheme (Bos and Chaum, Crypto 1992), is size-optimal not only under Winternitz's OTS framework, but also among all tree-based OTS designs. Moreover, we point out a flaw in the DAG-based OTS design previously shown to be size-optimal at Asiacrypt 1996, which makes the constant-sum WOTS$^{+}$ the most size-efficient OTS to our knowledge. Finally, we evaluate the performance of constant-sum WOTS$^{+}$ integrated into the SPHINCS$^+$ (CCS 2019) and XMSS (PQC 2011) signature schemes, which exhibit certain degrees of improvement in both sign time and signature size.
Note: This paper is subsumed by eprint 2023/850
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CRYPTO 2023
- Keywords
- Hash-Based SignaturePost-Quantum CryptographySPHINCS+
- Contact author(s)
-
kzoacn @ sjtu edu cn
rickfreeman @ sjtu edu cn
yuyu @ yuyu hk - History
- 2025-03-03: last of 2 revisions
- 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},
url = {https://eprint.iacr.org/2022/059}
}
