Quantum Computing & Cryptography
Encryption Killer & Savior
“God does not play dice with the universe” Albert Einstein
“Einstein, stop telling God what to do!” Niels Bohr
In previous blogs, where I advocated the benefits of encryption at multiple layers to protect data from interception, I claimed that using modern techniques like AES-256 (Advanced Encryption Standard with a 256-bit key) renders the encrypted data unbreakable for all practical purposes. It would require over 100 years of computing to discover the encryption key, by which time no one cares.
I then read that by using quantum computing it is feasible to reduce this time to a matter of hours! So, I think to myself - whoa! When did centuries become hours? What’s going on here? Is encryption, a bedrock of modern cyber security really threatened? And if so, what can we do about it? I did some research and you, dear reader, are the beneficiary of my findings below.
All encryption is based on substitution, from simple schemes we did as kids (substitute A with D, B with E, etc.) to complex non-repeating patterns based on a long numerical key. Modern encryption systems construct these keys using a combination of private and public keys with mathematical one-way functions. These are functions that are easy to compute in one direction, but extremely time consuming to reverse. Think about multiplying two prime numbers, say 113 and 157 representing the public and private keys. You can obtain the result, 17741, instantly. But let’s say someone gave you 17741 and asked you to find the prime factors. This would take a while longer. When we construct these keys with long numerical sequences it can indeed take conventional computers over 100 years to reverse.
Why so long? Conventional computers are based on “bits”. They use silicon logic gates to assume precisely two states: 0 or 1. So, even though state-of-the-art computers can have billions of binary gates, each stage of algorithms (relying on bit-based computing) can only produce a 0 or a 1. No matter how many gates are provided or how fast they are exercised, this is a fundamental limitation.
On the other hand, quantum computers use “qubits” (quantum bits). These are implemented with properties of elementary particles, like electrons, that have an up or down spin, or photons that have vertical or horizontal polarization. What makes qubits different is that, due to the weirdness of quantum physics, qubits can simultaneously assume multiple states of up/down spin, or vertical/horizontal polarization, until they are actually measured in a specific state. In fact, n qubits can store or process the same amount of information as 2n conventional bits. This quantum property is called superposition, and it is employed in quantum computers to perform classes of algorithms that benefit from massive parallelism, including factoring very large numbers.
So, the reality is – yes - quantum computing can, in fact, defeat current encryption methods. But there is no reason for immediate alarm, for two reasons:
- First, quantum computing is still in its infancy. It requires sophisticated and delicate machinery, far more suited for a lab and experimentation than a computer room and commercial applications. It will not be used anytime soon to break into your encrypted system.
- Second, even as quantum computing matures to commercial availability (and over time it will), quantum principles can also be used to implement “quantum cryptography” (also called quantum encryption), which, in theory, is unbreakable even with infinite computing power.
Quantum cryptography relies on quantum randomness (also known as Heisenberg's uncertainty principle) to establish a key; not on mathematical equations. A typical procedure relies on the person initiating a message sending a series of individual photons through a series of randomly-selected vertical or horizontal polarization filters (one photon per filter, creating qubits) to the message receiver. The receiver detects each photon through his or her own random filters. The sender and receiver communicate openly about the filter sequences but not about the results, either 0’s or 1’s, which are only known to them, and use this as the basis to establish an encryption key. Tapping into the photon stream and listening to the coordinating conversation cannot benefit anyone because they don’t know the random manipulations that were used to establish the key. Moreover, the very act of tapping the photon stream changes the results statistically so that the sender and receiver know they are being monitored. Better yet, it is possible to make the key as long as the message being encrypted, implementing an encryption technique known as a one-time pad, which is, in fact, totally unbreakable, because every encoded symbol is random. There is no pattern.
A form of Schrodinger’s equation, which underlies quantum mechanics
Like quantum computing, quantum cryptography is also in its infancy. It has been demonstrated for a sender-receiver pair 200km apart, but has many technical challenges to overcome until it can be used commercially, particularly over long distances.
In summary, while we will continue to use and benefit from bit-based encryption methods for the foreseeable future, in another generation, this could all shift to the world of quantum qubits. In the meanwhile you can enjoy optical encryption today.