Paper 2025/889

At the Top of the Hypercube -- Better Size-Time Tradeoffs for Hash-Based Signatures

Dmitry Khovratovich, Ethereum Foundation
Mikhail Kudinov, Eindhoven University of Technology
Benedikt Wagner, Ethereum Foundation
Abstract

Hash-based signatures have been studied for decades and have recently gained renewed attention due to their post-quantum security. At the core of the most prominent hash-based signature schemes, XMSS and SPHINCS+, lies a one-time signature scheme based on hash chains due to Winternitz. In this scheme, messages are encoded into vectors of positions (i.e., vertices in a hypercube) in the hash chains, and the signature contains the respective chain elements. The encoding process is crucial for the efficiency and security of this construction. In particular, it determines a tradeoff between signature size and computational costs. Researchers have been trying to improve this size-time tradeoff curve for decades, but all improvements have been arguably marginal. In this work, we revisit the encoding process with the goal of minimizing verification costs and signature sizes. As our first result, we present a novel lower bound for the verification cost given a fixed signature size. Our lower bound is the first to directly apply to general encodings including randomized, non-uniform, and non-injective ones. Then, we present new encodings and prove their security. Inspired by our lower bound, these encodings follow a counterintuitive approach: we map messages non-uniformly into the top layers of a much bigger hypercube than needed but the encoding itself has (hard to find) collisions. With this, we get a 20 % to 40 % improvement in the verification cost of the signature while keeping the same security level and the same size. Our constructions can be directly plugged into any signature scheme based on hash chains, which includes SPHINCS+ and XMSS.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2025
Keywords
Hash-based signaturesOne-time signaturesPost-quantumWinternitzincomparable encodingslower bounds
Contact author(s)
dmitry khovratovich @ ethereum org
mishel kudinov @ gmail com
benedikt wagner @ ethereum org
History
2025-06-04: revised
2025-05-19: received
See all versions
Short URL
https://ia.cr/2025/889
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/889,
      author = {Dmitry Khovratovich and Mikhail Kudinov and Benedikt Wagner},
      title = {At the Top of the Hypercube -- Better Size-Time Tradeoffs for Hash-Based Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/889},
      year = {2025},
      url = {https://eprint.iacr.org/2025/889}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.