MSS/LMS solution

The hash-based signature scheme starts with the one-time signature scheme (OTS), which means that each key pair in a signature scheme cannot be used to sign multiple messages. Currently the most effective OTS program is the Winternitz program (WOTS). The core idea of WOTS is to iteratively apply functions to secret inputs, and the number of iterations depends on the information to be signed.

The Merkle signature scheme (MSS) is applicable to any cryptographic hash function and any one-time signature scheme. MSS uses a Merkle tree to connect N = 2H OTS public keys together, where H is the height of the tree. The root of the Merkle tree is used as the public key of the MSS. The algorithm used to calculate the Merkle root is called Tree hash, see Algorithm 8.

In order to generate the signature of the message M, it is necessary to select the key of the next unused OTS public key and generate the OTS signature. The MSS signature includes the OTS signature, the OTS public key and the verification path used to prove the existence of the OTS public key in the Merkle tree. To verify the signature, first check the validity of the OTS signature to the OTS public key, and then verify that the OTS public key is a valid leaf of the Merkle tree with a verification path.