Towards A Quantum World: Hash to Obtain Random Subset (HORS)

Sometime soon we will have to ween ourselves on many of your public key encryption methods. On the Ethereum infrastructure, we sign for transactions using an elliptic curve based private key. Unfortunately elliptic curves will be crackable by quantum computers, so we must thus find method which still allow us to define signatures. One way is to create a hash-based method with public and private keys to prove the signature.

Hash to Obtain Random Subset (HORS) is one such quantum robust hashed-based one-time signature. With this we create a series of integers for our private keys and organise into an indexable form. Then we hash them to a sequence of public key values. Next we segment the hash of the message into a series of n-bit integer values. The signature is then achieved through a look-up of the value in the public key list.

If we assume that we are going to segment the hash into 8-bit values and for a 128-bit hash (using MD5), the method is then:

• Create 256 random values. These are our private key values (priv0…priv255).
• Hash each of the private key values to produce a list of our public key values pub. These will be indexed.
• Hash the message (M) for a 128-bit hash (h), and which will produce 16 8-bit values (hi).