A clipping technique for shorter hash-based signatures

• Amos Y. C. L. Zheng
• Leonardo T. D. Ferraz
• Marcos A. Simplicio Jr.

Resumo

Hash-based signature schemes are a class of post-quantum algorithms that usually consist of hash-trees built upon One-Time Signature (OTS) solutions. These schemes have small key sizes, efficient processing and are simple to implement, while their security properties rely basically on the pre-image or collision resistance of the their underlying hash function. Despite such advantages, however, they have relatively large signature sizes compared to traditional signature algorithms. One way of tackling this issue is to reduce the sizes of their underlying OTS algorithms. In this article, we describe a probabilistic technique that, with negligible processing overhead, allows such reductions. Namely, up to 12.5% average size reduction can be achieved depending on the signature's parameters.