The security world has fallen head over heals for Elliptic Curve Cryptography (ECC) methods, and ECDSA (Elliptic Curve Digital Signature Algorithm) is becoming the standard in creating keys and to sign for transactions. For exchange key it is ECDH (Elliptic Curve Diffie Hellman) that often creates our secure connections.
But quantum computers have both ECC and RSA is their sights. But what’s at risk? Well a core risk is around keys used in ECDSA and the signatures added to the blockchain, including within Ethereum and Bitcoin. With this they use the ECDSA method to create the keys for the wallet and to sign for transactions.
With ECDSA, we create a random 256-bit private key, and then can easily derive our public key. It is then extremely difficult to find the random value which generated the given public key:
The private key is used to sign for transactions, and the public key proves that a given private key has been used. But with Shor’s algorithm we are able to reverse back the private key for any public address, and thus take over control of a person’s wallet.
As an alternative we can use hash-based signature, and which are used by IOTA. They are simpler from ECDSA, but are also quantum robust. For IOTA the method used is the Winternitz one time signature scheme (W-OTS). As it is only used once, we should not sign for a transaction with the same details (and this could be easily spoofed).
Winternitz one time signature scheme (W-OTS)
W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. 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.