Preparing for Q-Day using Vernam, Miller and Shamir

As experiments with quantum computing progress, the security of the Internet is at risk. Whenever we click “pay” with our credit card, use a password to sign into any account or simply send information around the Internet, we are relying on security based on the assumption that there is no easy way of finding the factors of large near-prime numbers. “Q-Day” is the time when a machine is invented that can crack this mathematical challenge and render today’s security obsolete.

This is why the whole technology community is watching the development of quantum computing with excitement and unease in equal measure. Back in 2014, I argued that there are limits to a universal quantum computer (see The Quantum Computer Dream) but it is very likely that an analogue machine using quantum principles can realise Shor’s Algorithm an as yet unscaled approach to solving the factorial problem for large numbers.

The good news is that scientists aren’t waiting. The very same quantum principles that power quantum computing experiments enable quantum communication technology that is already emerging from labs around the world. Rather than relying on encrypting messages, the technique can tell if any bits of information have been intercepted by a third party. As elegant as this solution is, it requires new infrastructure across our global Internet that will come with an enormous price tag.

You do have to wonder whether we should pause for a moment and look at the back catalogue of ideas. You don’t have to go much further than look at two old inventions to have a potential, cheap, solution that could be applied on Q-Day plus one. The first is a patented encryption invention that has been mathematically proven to be unbreakable but depends on a cumbersomely large key. The second is an approach that avoids the need to ever have a shared key between message sender and receiver.

In 1917 Gilbert Vernam (on behalf of AT&T) patented an approach to encryption using a one-time pad, although it appears that the same technique was independently described as early as 1882 by Frank Miller. A one-time pad involves a genuinely random key of the same length as the message to be encrypted. Each character in the message is combined with the corresponding character in the key. If the key is truly random, the same length as the message and secretly shared with the recipient there is no way for the message to be decrypted by any third party.

On its own, the one-time pad method would be difficult to implement over today’s Internet. However, in 1980 Adi Shamir proposed the “three-pass protocol”. In this approach, the original message is encrypted using the sender’s key, sent to the receiver who further encrypts the message with their own key and returns it to the sender. The sender then reverses out the original key and retransmits the message. The receiver is then left with a message that has been encrypted with their own key which they can easily remove returning the unencrypted message. At no time has sender or receiver needed the other’s key.

The combination of the Vernam/Miller one-time pad and the Shamir three-pass protocol is as powerful as a potential quantum internet at a fraction of the cost. To realise this technology every endpoint will need the addition of technology to generate genuinely random numbers to create the one-time pads. Today’s computers generate pseudo random numbers which do not meet the high bar of a genuinely random one-time pad key. Quantum technology could come to the rescue here with several techniques already available ranging from entanglement to quantum tunnelling likely to prove to be the analogue technology that can scale for today’s multi-billion device digital world.

Q-Day will, however, introduce another problem, regardless of whether expensive quantum encryption or a more cost effective Vernam, Miller and Shamir approach is adopted. Over the Internet, the receiver needs to be confident of the identity of the sender. This problem is solved today using “public key” signatures which rely on the same technology we use to encrypt messages but won’t work post Q-Day.

Identity could be assured in the future by signatures authenticated by trusted third party servers. Working like domain name servers today, these servers would generate one-time identity keys and broker identity confirmation across the Internet. Solving this problem ahead of Q-Day will require Internet governance bodies to agree on common, or at least interoperable, standards.

We live in an era of constant disruption. Q-Day is no different to other changes we need to navigate but I can’t help wondering if we are letting periods of ample, including ample capital, blind us to solutions that might be simpler, faster, and superior.