Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS

Kaiyi Zhang; Hongrui Cui; Yu Yu

Paper 2023/850

Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS

Kaiyi Zhang

, Shanghai Jiao Tong University

Hongrui Cui, Shanghai Jiao Tong University

Yu Yu

, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute

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 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 the best of 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 signing time and signature size.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in CRYPTO 2023
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-07: approved; 2023-06-06: received; See all versions
Short URL: https://ia.cr/2023/850
License: CC BY

BibTeX

@misc{cryptoeprint:2023/850,
      author = {Kaiyi Zhang and Hongrui Cui and Yu Yu},
      title = {Revisiting the Constant-sum Winternitz One-time Signature with Applications to {SPHINCS}+ and {XMSS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/850},
      year = {2023},
      url = {https://eprint.iacr.org/2023/850}
}