Lamport Signatures for a Post-Quantum Computing World

Towards a More Trusted Quantum Computing World

Lamport Signatures for a Post-Quantum Computing World

Towards a More Trusted Quantum Computing World

Remember the time there was the “Intel Inside” logo on computers, well, quite soon, there may be stickers that advertise “Post-quantum robust”. These stickers will identify that the software used will not be broken by the advent of quantum computers. Like it or not, all of our existing signatures on our blockchains will be broken and along with most of our digital signed software, thus applications such as Corda and IOTA are planning for a post-quantum world, while many others are just sleep walking into a world of broken trust.

Introduction

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.

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 [here]:

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 “6f74f11f20953dc91af94e15…0db03ebdf06d59556c” is 7f2c9414db83444c586c…49d9b4f03e9ba9. 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.

Conclusions

The Lamport OTS is fast, but the key sizes and signatures are relatively large. So what’s the problem with Lamport? Well, it is a one time use, and where we can only use our public key once. But, in Bitcoin, we could sign with our current public key, and then add our next one. The great advantage, though, of ECDSA is that the public key is only 33 bytes long and the signature is 73 bytes, whereas with a Lamport Signature the public key is 16 KB (512 versions of 256 bits), and the signatures is 8KB (256 versions of 256 bits).

But … EDCSA uses Elliptic Curve Cryptography, and which will be cracked easily by quantum computers, so our small public keys and signatures may be a thing of the past. So applications, such as IOTA and Corda, have already identified the risk, and replaced RSA and ECC methods with post-quantum techniques. IOTA integrates the Winternitz one time signature scheme (W-OTS) and which produces an efficient key size and a compressed signature, and Corda uses Blockchained Post-Quantum Signatures (BPQS) [Link].