A Hash based digital signature utilizes a one-time signature (OTS) as the signature’s main building block, and converts it to a many-times scheme, in order to sign a greater number of signatures. Within the context of known constructions, the size and cost of each signature rise as the number of needed digital signatures grows. When real world applications are considered, a considerably large number of signatures are needed, and these signatures can occasionally get quite large. As such, it is inarguably clear that post-quantum signatures relying on hashes require more computation resources, as well as larger sizes, when compared to classical signatures.
What are hash based schemes?
One-time signatures (OTS) represent the main building blocks of hash based schemes, and are only useful to successfully sign a single message per key. An OTS is then converted to a many-times schemes, which are useful in signing a limitless number of messages. Along both, the difficulty of signature breakage declines to the hash function breaking problems they are made of.
In previously designed many-times constructions, the size and cost of each and every signature surges as the number of needed signatures rises; whenever a key is used to sign a large number of signatures, e.g. a million signatures, these signatures will be much larger and more costly than other signatures signed by a key that only signs a small number of signatures, e.g. ten. Within the context of applications, a very large number of signatures is required, which can be relatively impractical.
A recently published paper introduced a unique construction that challenged that idea. The author of the paper proved that it is feasible to design a many-times signatures scheme, which is far more efficient than OTSs, that represent its basic building blocks. He studied the process of signature generation on top of a blockchain e.g. bitcoin. The suggested scheme allows using a limitless number of signatures. Signatures’ sizes are constant and are similar to those of the OTS. The cost of verification is similar to the cost of verification within the OTS in the beginning, yet it declines as each newly formed signature becomes more efficient, as the number of signatures within the system grows.