Quantum Robust Hash-based Signatures
Quantum Robust Hash-based Signatures
Public key methods provide us with ways of both authenticating the sender, and the integrity of the method. Unfortunately most of the methods which are used to create these signatures, such as with prime number factorization (as with RSA) and in elliptic curve methods, will be cracked with quantum computers. This article outlines some of the hash-based signature methods which could be used as a basis for hash-based signatures.
Introduction
Many of the problems we see on the Internet relate to the lack of trust within transactions. The emails you receive and the Web sites that you visit often have very little trust built into them. For trust we examine the email address of the sender, but anyone can fake that address. So increasingly we create digital signatures, and where we sign our messages with a private key. In this way, we can check for authentication, integrity and non-repudiation.
With this Alice creates a key-pair: a public key and a private key. She then takes a hash of the message, and encrypts this hash with her private key (this is her signature), and passes the message and the signature to Bob. Bob then reads the message and takes a hash of it. He then decrypts Alice’s signature with her public and checks the hashes. If they match, he knows that she signed it, and that it has not been changed along the way:
Currently, we often use RSA, DSA and ECDSA to sign our messages. These are based on the difficulty of finding out the factors of a number and on the processing of discrete logarithms. At the current time these methods are computationally hard problems, but with quantum computers, they become much easier. This was shown by Peter Shor who illustrated that it was possible to crack them in polynomial time.
Of all the methods that are being proposed, the hash-based methods look as if they have a good chance of success of creating quantum robust signatures. Lattice- and code-based methods are being researched, but the usage of hashing methods is already well defined and could provide the best alternative to the existing methods. Hashing methods, too, often bring other advantages, such as forward security, which means that a key which is cracked will not reveal all the previous keys.
Lamport Signature
Sometime soon we perhaps need to wean ourselves of our existing public key methods, and look to techniques that are more challenging for quantum computers. With the implementation of Shor’s alorigthm [here] on quantum computers, we will see our RSA and Elliptic Curve methods being replaced by methods which are quantum robust. One method is the Lamport signature method and which was created by Leslie B. Lamport in 1979. At the current time it is thought to be a quantum robust technique for signing messages. When we sign a message we take its hash and then encrypt with our private key. The public key is then used to prove it, and will prove that we signed it with our private key. The Lamport signature uses 512 random hashes for the private key, and which are split into Set A and Set B. The public key is the hash of each of these values. The size of the private key is 16KB (2×256×256 bits) and the public key size is also 16 KB (512 hashes with each of 256 bits).
The basic method of creating a Lamport hash signature is:
- We create two data sets with 256 random 256-bit numbers (Set A and Set B). These are the private key (512 values).
- Next we take the hash of each of the random numbers. This will give 512 hashes and will be the public key.
- We then hash the message using SHA-256, and then test each bit of the hash (0 … 255). If it is a 0, we use the ith number in Set A, else we use the ith number from Set B.
- The signature is then 256 random numbers (taken from either Set A or Set B) and the public key is the 512 hashes (of Set A and Set B).
This process is illustrated below:
We can use the Lamport method for one-time signing, but, in its core format, we would need a new public key for each signing. The major problem with Lamport is thus that we can only sign once with each public key. We can overcome this, though, by creating a hash tree which is a merger of many public keys into single root.
A sample run which just shows the first few private key and the first public keys:
==== Private key (keep secret) =====
Priv[0][0] (SetA): 6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556c
Priv[0][1] (SetB): 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Priv[1][0] (SetA): 19f0f71e913ca999a23e152edfe2ca3a94f9869ba973651a4b2cea3915e36721
Priv[1][1] (SetB): 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Priv[2][0] (SetA): 15ef65eda3ee872f56c150a5eeecff8abd0457408357f2126d5d97b58fc3f24e
Priv[2][1] (SetB): 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Priv[3][0] (SetA): 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
Priv[3][1] (SetB): e9dcbdd63d53a1cfc4c23ccd55ce008d5a71e31803ed05e78b174a0cbaf43887
==== Public key (show everyone)=====
Pub[0][0]: 7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9
Pub[0][1]: 4bc371f8b242fa479a20f5b6b15d36c2f07f7379f788ea36111ebfaa331190a3
Pub[1][0]: 663cda4de0bf16a4650d651fc9cb7680039838d0ccb59c4300411db06d2e4c20
Pub[1][1]: 1a853fde7387761b4ea22fed06fd5a1446c45b4be9a9d14f26e33d845dd9005f
==== Message to sign ===============
Message: The quick brown fox jumps over the lazy dog
SHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]: 4b1012fc5669b45672e4ab4b659a6202dd56646371a258429ccc91cdbcf09619
Sign[1]: 04b05e62cc5201cafc2db9577570bf7d28c77e923610ad74a1377d64a993097e
Sign[2]: 8b5e7513075ce3fbea71fbec9b7a1d43d049af613aa79c6f89c7671ab8921073
Sign[3]: 1c408e62f4c44d73a2fff722e6d6115bc614439fff02e410b127c8beeaa94346
The signature test is True
In this case we take the random number, and then convert it to a string. So the SHA-256 signature of “6f74f11f20953dc91af94e15b7df9ae00ef0ab55eb08900db03ebdf06d59556c” is 7f2c9414db83444c586c83ceb29333c550bedfd760a4c9a22549d9b4f03e9ba9. If can be seen that the hash of message (“The quick brown fox jumps over the lazy dog”) has a hex D value at the start, which is 1101 in binary, and we see we take from SetB [0], SetB [1], SetA [2] and SetB [3].
A demonstration is given here.
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.
This is illustrated below:
A sample run which just shows the first few private key and the first public keys:
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.
Merkle signatures
The roots of hash-based methods is Merkle trees, and which are a way of hashing used in many applications, including with Bitcoin, Ethereum, Git distribution systems, No SQL, and P2P file transfer. With a Merkle tree we take our data elements, and then hash them, and take pairs of these hashes to create a new hash, and so we build a hierarchical tree. At the top of the tree is the root element (in this case Hash1234):
In this way, we can use the tree to see if we have matching data on systems. On a P2P network, we can transfer a file by splitting it into data segments and then distributing these segments across the network. A trusted source will have the complete Merkle tree for rebuilding the file, and a client can thus rebuild from the Merkle tree and determine the parts of the file which are still missing (or are in error). Once transferred, the root hash (and all the other hashes) will then match. In its core method, the Merkle Signature Scheme (MSS) has serious performance and memory issues, but enhanced methods such as XMSS create the hash table with much less of a performance hit.
The methods present for W-OTS and Lamport only provide for 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):
In the following we have a message of “hello” and which has a SHA-256 hash of “2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824”.
We first produce four sets of key pairs (and which can only be used once each). For each set of key-pairs we have 32 256-bit random numbers, and the public key is 32 256-bit versions of the private key, and that have been hashed 256 times.
We then take the message and hash it with SHA-256. Next we take each 8-bit value in the hash (N), and then hash 256-N times using SHA-256. These values become the signature.
To verify the receiver takes the hash of the message, and takes the SHA-256 hash. Next they will take each 8-bit value of the received signature, and then hash it by the value of the byte in the hash of the message. The results should be the corresponding value in the public key.
The Merkle root defines the top level hash, and where the authentication of the hash for the corresponding key pair is also given.
Message: hello
Hash(message): 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
=== Calculate four signatures with 32 key pairs each ===
Private key [0][0]: 4db81f526b64d69b58a6a1cf9578dc9e04eac297414e9fe63a85df2ccef11a6a
Private key [0][1]: 673d627b7badf7461257d3e65bd557bda0da24e6485d97e86cf92d784bbbcdc6
....
Private key [0][31]: 5d4b71021c9d90ec95822037004d994e15bee4587fc08cf33d1877cc8c5fe153
....
Public key [0][0]: 336196ed0c22d4cff3218c9000e24c70a0bfec5e0ca318afe4899a16ccc755c6
Public key [0][1]: fa0a9ce753520bb142dc97c10fc313e09b6f5f83639d9bfb2beabd78785276e0
....
Public key [0][31]: a5912d99be04e9af0fdc6e2b2903788d7023c6ddae69a7b409e07e57465e246b
=== Determine Merkle Root ====
Merkle root: 3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf
=== Create signature ====
Signature [0]: 9e82faf05429db2854001abf42ea38eec1cd6cbf1b76292cc1bc8ef82ca61216
....
Signature [31]: aaaf98ff8576a19ac758b765a5eb75d42286bf548188e5778a294f09f78aa42a
=== Verify signature ====
Verified MSS: True
Merkle path: [('161b01f3c986543bda6a9a49bde5820f7ba5324cdfd5ea4535d897fed750309c', '47dfb8b70b1a7e8227dca2b226410d818104f4af45352f5334f4230436903c4c'), ('b344637c77e539df5d5396b354bbc2c3d202d6b2fd4ce8175338ae42035ec1a6', '61eddc1359167727065c94a0427b8d18811a791fae7db2b5103dc3b20b1a3cf5'), ['3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf']]
Verify root True
A demonstration of this method is given here.
Hash to Obtain Random Subset (HORS)
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.
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.
SPHINCS
SPHINCS is a stateless hash-based signature scheme, which is quantum robust. It was proposed by Bernstein et al. in 2015 [paper]. SPHINCS+ 256 has a public key size of 1kB, a private key size of 1kB, and a signature of 41 kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor.
It uses WOTS and HORST for hash-based trees. The code uses a number of parameters:
- n — length of hash in WOTS / HORST (in bits)
- m — length of message hash (in bits)
- h — height of the hyper-tree
- d — layers of the hyper-tree
- w — Winternitz parameter used for WOTS signature
- tau — layers in the HORST tree (2^tau is no. of secret-key elements)
- k — number of revealed secret-key elements per HORST signature
In the example we use: n=256, m=512, h=2, d=1, w=4, tau=8, k=64.
The hashing method used of some of the operations is BLAKE, and Cha-cha is used to generate a random number.
A demonstration of this method is given here.
Conclusions
There you go, a quantum robust future for cybersecurity.