eprint.iacr.orgpaper

CUTS: Chained Uniform-sum Tree Signatures

The paper analyses stateful hash-based signatures whose key is a tree of hash chains, and asks what a second signature from the same one-time key reveals after state loss or rollback. It proves that the values derivable from several signatures are exactly the union of those from each signature alone. It also bounds forgery after b signatures in the classical random-oracle model by a combinatorial coverage exponent λ_b, including when the signer grinds a counter. It then introduces CUTS, a scheme on one binary tree whose chain positions sum to a fixed value S and whose signature size and verification cost do not depend on tree height. One parameter set has 1,424-byte signatures and λ_2 ≥ 128.6. A counter variant, CUTS+C, gives a proven grinding gain.