One Public Key and Thousands of Private Keys

One Public Key and Thousands of Private Keys

We cling onto wet signatures within the Internet era, but sometime soon we need to deprecate them, and their flawed associated methods. Within this COVID-19 period, I still get asked for my wet signature, and then take a GIF of my signature, and the paste it into a document, and produce a PDF of the whole document. Can anyone see the flaw here? Everyone knows that it’s not too difficult to convert a PDF into something else and that anyone can get access to a scanner or camera to reproduce my wet-signature! It is a crazy old system. But we replace it with a system which mimics something that is not my signature on the click of a button (DocuSign), and which is almost as equally untrustworthy but pleases those people who like to see a scribble on a legal document.

When completely eradicated, we will truly enter a trusted digital age. Normally for this, we use public-key encryption and where the sender takes a hash of the data and then encrypts this with their private key. The recipient then proves this by decrypting with the senders public key, and then checking the hash is the same as the message. For many of our existing methods, we create a trap door function, and where someone with special knowledge is able to apply a different key to unlock the data. But, what if the trap door function is not a provable hard problem? Well, this is the fundamental problem with our existing public key methods — ECC and RSA — as they are based on hard problems within our current computer systems, but are not difficult in a world of quantum computers.

So how can we overcome this? One such method is hash-based signing. For this, we could generate thousands of key pairs, and then use one of them at a time. In this way, we could publise all the keys that we want to use. And then reveal the associated private key for each message we send. In the BiBa (Bins and Balls) method we do this and sign the message with two values — a secret value and a discovered value — that end up in the same bin:

But our public key is going to be lengthy, as we now need to all the associated public keys. An improved method is to use many private keys, but have a single public key to prove all of them. For this we turn to the fundamental method used in the blockchain: The Merkle Tree. With this, we create a tree of hashes created from our randomly generated private keys and then create a root hash. This root hash becomes our public key, and to show our private key, we should the branch of the tree that takes us to the private key.

Merkle Trees

With a Merkle Trees, we create a tree of hashes and then create a root hash. We start from the bottom of the tree with the original data, and then concatenate two values together, and make a hash of these. We then move up the tree talking two hashes at a time and hashing them together. Now, we can use this method for our public key encryption. For this, we can create 1,024 private keys that we will use to sign our messages, and then the root of the Merkle Tree will become our public key. There’s no large number multiplication or elliptic curve point adding, just good old — and fast — hashing. So let’s say we have eight secrets (P1, … P8), and then hash P1 and P2 to give P12, and then hash this with P34 to get P1234, and then hash this with P5678 to get a public key hash value:

In this case, I can keep P1, P2 … P8 secret, so that no-one will know these values until I use them. To prove I do know them, I will publish my public key (P12345678), and then will prove that I know P1 by showing the chain that goes from my public key to P1 (P1234, P5678, P12, P34, P1 and P2). I then do not release any information about P3, P4, … P8, and can use these in future signings. When I run out of secrets, I then just create another public key, and a whole lot of secrets (my private keys).

So let’s say we have the names of a few countries: ‘France’, ‘Germany’, ‘Denmark’, ‘Sweden’, ‘UK’, ‘Spain’, and ‘Italy’. We can then hash as [here]:

Input:		 [ 'France', 'Germany', 'Denmark', 'Sweden', 'UK', 'Spain', 'Italy' ]
Root hash:	 65C7C87E2731AE97D0BE89EA3299A544FD28DE6A
Tree depth	 3
Tree levels:	 4
Tree nodes:	 7Level  0
[ '65C7C87E2731AE97D0BE89EA3299A544FD28DE6A' ]Level  1
[ '8D832398ACABF7B669C023174169C8876F9764DC',
  '2BBB8E1E1D16671B763D0C026C9A2BA43FD73381' ]Level  2
[ '0F705D70B6CF6FFE1FE570FC24947767438541FA',
  'A5D0D57347C4BE03B6E91E0176D5E53614AA861E',
  'F8A5C1FC111019BDCD2E6F7877299878F9699640',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]Level  3
[ 'E3772AC4B4DB87B4A8DBFA59EF43CD1A8AD29515',
  '17D53E0E6A68ACDF80B78D4F9D868C8736DB2CEC',
  '89DA124E04DFE1AD9946CD37D91A119E1D028898',
  '72DDD2B619AF6D6A73FEBF80F7FCAD22495498CD',
  '7770D04C7BFB791E7C95959F12D6797BEE87A8D8',
  '20A8DF9B760336178FCA425339EC1C7E542A2463',
  'AD79EF0F076D3A686AB9738925F4DD2C7E69D7D1' ]

The root of the tree is then 65C7C87E2731…299A544FD28DE6A, and we have seven nodes and four levels. We can now draw the Merkle Tree:

The SHA-1 hash of ‘France’ is E3772AC4B4D…43CD1A8AD29515. Notice that because we have an odd number of nodes, the hash for ‘Italy’ is used for the next level. If we create with no hashing method, we can clearly see the structure of the true. In this case, we use ‘1’,’2',’3',’4' and ‘5’ for our data [here]:

var merkle = require('merkle');
Input: [ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]
Type: none
Root hash: 12345
Tree depth 3
Tree levels: 4
Tree nodes: 6
Level 0[ ‘12345’ ]
Level 1[ ‘1234’, ‘5’ ]
Level 2[ ‘12’, ‘34’, ‘5’ ]
Level 3[ ‘1’, ‘2’, ‘3’, ‘4’, ‘5’ ]

The great advantage of using a Merkle Tree is that we can easily check that a value is included in the root hash. In the diagram below, to test that ‘Germany’ (Node 2) is in the tree, we would need only need Node 1, Node 34 and Node 567 in order to generate the root (Node 1234567):

The reason we only need nodes 1, 34 and 567, is that we can regenerate Node 12 and Node 1234 from these values. Bitcoin, for example, uses this method in order to check the validity of a transaction within the block. We can then add our transactions into a Merkle Tree, and produce a root hash. Within the block we can then add the root hash of the previous block and the root hash of the next block, and thus interlock the blocks into a chain:

Merkle signatures scheme (MSS)

The roots of hash-based methods are 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 presented for W-OTS and Lamport only provide for a one-use — or 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 “2cf24dba5fb0a30e26e83b2ac5b9e29e1 — e73043362938b9824”.

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.

Conclusions

Thank you Ralph Merkle!