Hash to Obtain Random Subset (HORS) is a 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.
Quantum Robust: Hash to Obtain Random Subset (HORS)MethodIf 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:
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: PresentationThe following is an outline of the method [slides] CodeThe following is a very simple abstraction of the method (and where the public key values are truncated to four characters). In this case I have simply used the MD5 hash signature to produce a 128-bit hash signature of the value (but could easily use SHA-1, SHA-256 or any other hashing function): import random import sys nvals=256 max=256 message = "hello" if (len(sys.argv)>1): message=int(sys.argv[1]) def get_private(): priv = [] for x in range(nvals): priv.append(random.randint(0,max)) return priv def int_to_bytes(value): result = bytearray() for i in range(0, len(value)//2): str = value[2*i:2*i+2] result.append(int(str,16)) result.reverse() return result def hashthem(priv): pub = [] for x in priv: m = hashlib.md5() m.update(str(x).encode()) pub.append(m.hexdigest()[:4]) return pub def getsig(val,priv,pub): sig =[] for x in val: sig.append(pub[priv[x]]) return sig import hashlib m = hashlib.md5() m.update(message.encode()) msg = int_to_bytes(m.hexdigest()) print("Byte values:", end=' ') for i in range(len(msg)): print(msg[i], end=' ') print() print() priv = get_private() print("Private key") print(priv) print() public = hashthem(priv) print("Public key") print(public) print() print("Signature") sig = getsig(msg,priv,public) print(sig) 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'] |