Quantum Robust Hash Based Signatures

0
21
Hash based Signatures

Invented by Merkle in the 1970s, hash-based digital signatures have ever since taken its place as a mainstay for many, and have become the leading component in the world of cryptography. Although Leslie Lamport was well-known discoverers behind hash based signatures for single messages. It’s only major drawback is the fact that anyone hash-based public key could only generate a limited amount of signatures to be signed by paired private keys had initially pegged its usage, but now it has become an indispensable tool for security against quantum computer attacks.

creating a Lamport hash

Merkle Signature Scheme (MSS)

There have been many newer improvements in the last decade over the original hash-based scheme which Merkle had pitched in the late 1970’s. So it will be worth taking note of his scheme first. The basic idea on which it has been built is that of Lamport’s OTS (and variants) – a one-time signature – in which, only one message will be signed by a unique key pair.

Merkle Signature Scheme

using the nodes on the authentication path – and if this root value matches the public key’s information, the signature is verified and accepted.

Extended Merkle Signature Scheme (XMSS)

XMSS, and XMSSMT, its multi-tree variant, improves on some fronts over the original MSS – such as collision resistance, whereas the latter allows better key-signature generation times, but with a caveat that the signatures are larger.

XMSS utilizes WOTS (Winternitz OTS) – a plus point for which is that of verifying a signature a public key is computed and compared to the given one. Its application in MSS implies that the MSS signature dispenses with the prerequisite for a pkOTS,I containment – alternately, pkOTS,I is computed by the verification from the OTS signature itself, and then this OTS public key is used to compute the root value. If the computed root value matches the public key counterpart, it validates the authenticity for the OTS key pair, and thus validates the OTS signature.

The size of the signature, which was S ≈ 2n2+nlog2N in the basic MSS is thereby reduced to roughly n2+nlog2N. This also affects changes in the runtime, in accordance with the size (w ∈ N). Signatures decrease in size logarithmically, while runtime grows sub-linear in w (by a factor of w/log2w).

Additionally, the vital requirement for a collision-resistant hash function is no longer a prerequisite in XMSS. In essence, the inputs to the hash function before each computation instance is masked with bitmasks. The second-preimage resistance that XMSS uses remains intact even in the cases even where practical collision attacks are exhibited with MD5 and SHA1.

Merkle Signature Scheme

To explain XMSSMT ‘s key generation time improvement, it is a trade-off for signature size, which is a slight increment by a factor of d, i.e. O(dd√N) instead of O(N), where d layers of XMSS key pairs are used in the certification tree of XMSS key pairs. In its multi-tree structure, the top layer signs the root nodes of the key pair immediately below it – and this same order repeats in the case for the key pairs for this layer, which are in turn used to sign the public key below it, and so on. The lowest layer’s key pair, in the ultimate instance, signs the messages, i.e. the leaves of a tree are used to sign the root of the tree below it. This means that the structure allows for a generation of key pairs that can be used for a large, practically unlimited number of times (N = 250).

Instead of applying a collision-resistant hash function as the basic MSS, therefore, another binary hash tree is used to compress the WOTS public key – and this tree, called the L tree, has usage of the bitmask.
Here is a sample public key vector generation algorithm (pk), where σ = signature input and M= message input.

1. bitsn [l]pk;
2. unsigned int csum = 0;
3. unsigned int[l] msg;
4. unsigned intl3=ceil(log2l1(w−1));
5. Append (mmod log2w) 0 bits toM;
6. for int i= 0; i < l1; i+ +do
7. | msg[i] =coef(M,i,log2w);
8. end
9. for int i= 0; i < l1; i+ +do
10. csum +=w−1−msg[i];
11. end
12. Convert csum to a bitsl3 and append (l3mod log2w) 0 bits;
13. for int i= 0; i < l2; i+ +do
14. msg [i+l1] =coef(csum,i,log2w);
15. end
16. forinti= 0; i < l; i+ +do
17. pk[i]=chain(σ[i], msg[i], w-1-msg[i],bm);
18. end
19. return pk

Application

Digital signatures have a gigantic field of application in network security – data comparisons, password authentication, message integrity checking or non-repudiation. The basic skeletal MSS might have initially had space constraints and was somewhat lacking in performance, but XMSS, as already illustrated, is up to speed with the day’s pace, and can as well save up on space notably.

The post-quantum based signature modules and systems are subject to further research (lattice-based schemes and its offshoots), while the hash-based signatures grounding on XMSS have been established as the market standard over the last decade, and with good reason. Other schemes take for granted an innate intractability mechanism to generate the signature, the quantum hash-based signatures are self-reliant as it uses the hash function itself to secure the data, and the hash functions are even interchangeable to some extent without affecting the core XMSS model.
This is the best time to opt for hash-based signatures over other methods, because with SPHINCS, and its introduction of HORST, the key sizes are much more realistic, and this eliminates a major drawback of hash-based signature systems.

The traditional number-theoretic digital signatures that use either prime number factorization in elliptic curve methods (e.g. Rivest – Shamir – Adleman or RSA algorithm) have not scaled very well with age. Today, they are susceptible to quantum computers, which can crack them rather easily. The quantum hash-based digital signatures can protect our messages in this regard – from things like Shor’s algorithm, to exemplify, and therefore are a godsend.

LEAVE A REPLY

Please enter your comment!
Please enter your name here