Novel One Time Signatures (NOTS): A Compact Post-Quantum Digital Signature Scheme

The future of the hash based digital signature schemes appears to be very bright in the upcoming quantum era because of the quantum threats to the number theory based digital signature schemes. The Shor’s algorithm is available to allow a sufficiently powerful quantum computer to break the building blocks of the number theory based signature schemes in a polynomial time. The hash based signature schemes being quite efficient and provably secure can fill in the gap effectively. However, a draw back of the hash based signature schemes is the larger key and signature sizes which can prove a barrier in their adoption by the space critical applications, like the blockchain. A hash based signature scheme is constructed using a one time signature (OTS) scheme. The underlying OTS scheme plays an important role in determining key and signature sizes of a hash based signature scheme. In this article, we have proposed a novel OTS scheme with minimized key and signature sizes as compared to all of the existing OTS schemes. Our proposed OTS scheme offers an 88% reduction in both key and signature sizes as compared to the popular Winternitz OTS scheme. Furthermore, our proposed OTS scheme offers an 84% and an 86% reductions in the signature and the key sizes respectively as compared to an existing compact variant of the WOTS scheme, i.e. WOTS+.