Photo by Chunlea Ju on Unsplash

One Public Key and Thousands of Private Keys

Prof Bill Buchanan OBE

--

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:

--

--

Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.