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

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).
• Take each of the values (hi) and use as a look-up to the public key value.

If Bob creates the public key and the private key, then he creates the message, and then adds the hash-based signatures. He then shows Alice the message and the message, and his public key. Bob then shows that he has the associated private key for this public. He cannot use this key pair again, so will produce a new key pair for the next signature.

The following illustrates a simple example:

A sample run with “hello” is:

Byte values: 146 197 23 16 145 157 113 185 118 42 75 188 42 64 65 93 
Private key: [36, 140, 153, 156, 175, 202, 73, 171, 214, 161, 0, 56, 19, 26, 121, 135, 207, 109, 89, 97, 152, 171, 207, 131, 122, 89, 256, 199, 49, 146, 234, 60, 243, 182, 45, 179, 166, 228, 44, 144, 140, 154, 2, 98, 5, 133, 139, 43, 73, 156, 143, 72, 189, 98, 219, 172, 169, 205, 47, 86, 86, 172, 114, 147, 58, 189, 224, 122, 54, 70, 196, 82, 239, 221, 87, 127, 77, 200, 115, 193, 103, 171, 52, 256, 149, 55, 85, 150, 248, 132, 202, 200, 56, 236, 95, 1, 31, 139, 255, 253, 233, 90, 113, 24, 232, 98, 160, 95, 185, 130, 211, 185, 147, 83, 5, 66, 56, 205, 12, 199, 148, 148, 204, 135, 214, 123, 122, 196, 209, 94, 42, 121, 123, 26, 17, 2, 61, 23, 172, 70, 76, 225, 164, 176, 159, 146, 231, 138, 18, 175, 238, 34, 33, 210, 213, 93, 36, 91, 250, 91, 202, 105, 254, 140, 209, 65, 48, 141, 198, 232, 211, 148, 38, 11, 178, 254, 212, 229, 30, 145, 19, 234, 250, 95, 164, 105, 161, 207, 141, 46, 72, 47, 31, 5, 187, 159, 68, 123, 91, 195, 125, 197, 189, 65, 176, 35, 84, 114, 138, 141, 116, 51, 155, 157, 195, 237, 211, 51, 99, 68, 220, 76, 34, 126, 189, 251, 189, 17, 256, 49, 131, 72, 62, 237, 59, 105, 211, 133, 223, 239, 198, 110, 193, 37, 178, 227, 65, 158, 29, 194, 87, 89, 206, 173, 253, 232]

Public key: 
['19c', '138', 'b3e', '1c9', '821', '854', 'd2d', 'a4a', 'ca4', 'bd4', 'cfc', '9f6', '1f0', '4e7', '4c5', '7f1', '69a', '272', '764', 'e2e', '37a', 'a4a', '69a', '1af', 'a0a', '764', 'f71', '84d', 'f45', 'a5e', '289', '072', 'cb7', '4c5', '6c8', '8f5', '7e7', '74d', 'f71', '0a0', '138', '1d7', 'c81', 'ed3', 'e4d', '9fc', 'e00', '17e', 'd2d', '1c9', '903', '32b', 'a25', 'ed3', 'c0e', '1ff', '363', 'eae', '67c', '93d', '93d', '1ff', '5fd', '8d5', '66f', 'a25', '13f', 'a0a', 'a68', '7cb', '084', '977', '555', '060', 'c7e', 'ec5', '28d', '364', '2b4', 'bd6', '697', 'a4a', '9a1', 'f71', 'f22', 'b53', '3ef', '7ef', '621', '65d', '854', '364', '9f6', '011', '812', 'c4c', 'c16', 'e00', 'fe1', 'c24', 'e16', '861', '732', '1ff', 'be8', 'ed3', 'b73', '812', 'eec', '9b8', 'eb1', 'eec', '8d5', 'fe9', 'e4d', '329', '9f6', 'eae', 'c20', '84d', '47d', '47d', '274', '7f1', 'ca4', '202', 'a0a', '084', 'b1d', 'f4b', 'a1d', '4c5', '202', '4e7', '70e', 'c81', '7f3', '376', '1ff', '7cb', 'fbd', 'd1c', 'fa7', '38a', '140', 'a5e', '9b0', '013', '6f4', '821', 'ac1', 'e36', '182', '6f3', '979', '98d', '19c', '542', '6c9', '542', '854', '65b', 'c52', '138', 'b1d', 'fc4', '642', '0f2', '0e6', 'be8', 'eb1', '47d', 'a57', '651', '8f8', 'c52', '153', '57a', '341', '2b2', '1f0', '289', '6c9', '812', 'fa7', '65b', 'bd4', '69a', '0f2', 'd9d', '32b', '67c', 'c16', 'e4d', '31f', '140', 'a3f', '202', '542', '033', '3de', '85d', 'a25', 'fc4', '38a', '1c3', '68d', '5fd', '013', '0f2', 'c45', '283', '2a7', '6c4', '033', '539', 'eb1', '283', 'ac6', 'a3f', 'ec8', 'fbd', 'e36', '069', 'a25', '19f', 'a25', '70e', 'f71', 'f45', '1af', '32b', '44f', '539', '093', '65b', 'eb1', '9fc', '115', '555', '0e6', '5f9', 'bd6', 'a5b', '8f8', '705', 'fc4', '064', '6ea', 'a59', 'c7e', '764', '7ea', 'f7e', 'c24', 'be8']

Signature: ['32b', '7f1', '4c5', '5fd', '9b0', '364', 'f71', 'ed3', '1f0', 'b3e', '084', 'd1c', 'b3e', '67c', 'd9d', 'eb1']

A demonstration of this method is defined here.

Signing

HORS is a one-time signature. In order to sign many messages, we can use the Merkel signature scheme (MSS). With we take a hash of the keys and build these as the leaves of the tree. The root of the tree is then the public key — the verification key. We then just use the private key of the OTS method to create the signature. The sender also sends the authentication path, which is the neighbouring nodes within the path which leads to the root of the tree. At the receiver end, they can then rebuild the tree using the verification key (which can be received a digital certificate) and the authentication path. For we move onto another key pair and where the index of the key part is revealed.

In the following example we have our root as the public key, and then want to sign with Key3. We then show the authentication path which takes us to the root (as defined in the bold arrows):