W-OTS’s The Problem? Sleepwalking Into a Broken World of Trust

Like it or not, we face a severe risk to our digital world on the advent of quantum computers, as these will be able to crack most of our…
Photo by Alexandra Gorn on Unsplash

Quantum Robust: Winternitz one time signature scheme (W-OTS)

Like it or not, we face a severe risk to our digital world on the advent of quantum computers, as these will be able to crack most of our public key methods. Almost in an instance, the RSA modulus (N) will be factorized into its prime number parts (p and q), and all the messages encrypted with it or signed by it, will be cracked. With ECC (Elliptic Curve Cryptography), the private keys will be reveal from the public keys. And even John Napier’s logarithms will fall in the wake of quantum computers.

And so we now see a move toward the creation of quantum robust signatures, and which will still provide a challenge to quantum computers. Everything we have put on the blockchain, for instance, could be cracked, and where the signatures could be reversed back to determine the private key of the signer, and then for all their cryptocurrency to be transferred. Organisations such as IOTA and R3 are making plans for this, and integrate post-quantum cryptography methods. For IOTA it is the Winternitz one time signature (W-OTS) method, and for R3 Corda it is Blockchained Post-Quantum Signatures (BPQS) method. In this article we will look at W-OTS.

Winternitz one time signature scheme (W-OTS)

The W-OTS method was proposed by Robert Winternitz of the Stanford Mathematics Department. It uses relatively small key and signatures sizes, and is thought to be quantum robust. Overall it generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n). The signature is then derived from the signature.

The method is:

  • Initially we create 32 256-bit random numbers. These 32 values will be our private key.
  • We then hash each of these values 256 times. These 32 values will be our public key.
  • We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 … N32).
  • For the signature we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
  • To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.

This is illustrated below:

A sample run which just shows the first few private key and the first public keys [here]:

Hashing number:	256
==== Private key (keep secret) =====
Priv[0]:  bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]:  20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]:  625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]:  ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]:  ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]:  d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]:  45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]:  184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]:  a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]:  60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]:  8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]:  9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]:	e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]:	59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]:	72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is  True

A demonstration of the method is given here.

Conclusions

You know sometimes we just like using things that are simple. ECC is a great example, and where ECDSA produces short signature with short public keys. But, a storm is coming, and we need to plan for it. WOTS is one method which produces a fairly short signature as we can use a hash function with shorter outputs.