Improved constant-sum encodings for hash-based signatures

The Winternitz one-time signature scheme is one of the cornerstones of hash-based signatures. Cruz, Kaji, and Yatani (CKY) propose to use a constant-sum encoding function with this scheme to obtain signature verification at lower and predictable costs in exchange for increased costs of key generation and signature verification. We give a novel description of this scheme called Wots-cs that greatly reduces the costs associated with key and signature generation, as well as signature verification. We achieve this by introducing new deterministic constant-sum encoding algorithms that accept larger sets of parameters than the original proposal. In addition, we provide a security proof of our scheme that relies on weaker assumptions than the CKY variant, reducing signature sizes by $$50\%$$ . Finally, we compare our work with Wots+ for parameters with the same signature size, and experiment with Xmss to discuss the impact of the encoding and possible applications.