Abstract
This disclosure relates to the field of digital signatures, and more particularly to stateful hash-based digital signature schemes for applications having restricted message spaces. A digital signature scheme, referred to as SmallMsg-LMS, is disclosed that reduces signature size and computational cost by adapting the one-time signature component of the Leighton-Micali Signature (LMS) [1,2] scheme to messages having a relatively small number of possible values. By adapting the one-time signature component of LMS to a restricted message space and retaining the LMS Merkle-tree framework, the disclosed scheme, SmallMsg-LMS, significantly reduces signature size and computational costs. The smaller the message, the smaller signature size and computational costs.
For a 1-byte message using a Merkle tree height of 15, the Secure Hash Algorithm 256-bit (SHA-256) and a Winternitz parameter of , SmallMsg-LMS signatures are approximately 556 bytes compared to 1,612 bytes in standard LMS, and 4,627 bytes in Module-Lattice-Based-Digital Signature Algorithm-87 (ML-DSA-87) [3], still achieving equivalent security. While a standard LMS signature with the same parameter set requires approximately 4,368 hash computations on average during verification, the small-message LMS variant requires only 271 hash computations on average, representing a reduction of more than 93% in verification workload.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Share Alike 4.0 License.
Recommended Citation
INC, HP, "SmallMsg-LMS: Optimised LMS Signatures for Small Message Spaces", Technical Disclosure Commons, ()
https://www.tdcommons.org/dpubs_series/12991