What is Quantum Computing?

The 1965 Nobel prize in physics was awarded jointly to Sin-Itiro Tomonaga, Julian Schwinger, and Richard Feynman. Their work in ‘quantum electrodynamics’ was an important scientific contribution the world, but, still to this day, their research describes phenomena that are strange and counter-intuitive to the ways in which we understand the world. Those phenomena, such as superposition and entanglement, make up the basis of quantum computing. Computers that perform quantum computations using these phenomena are known as ‘quantum computers.’

A traditional computer has two states: on and off, which is why we call them binary computers and often refer to ones and zeros that represent those as on and off states. A quantum computer uses a third state known as a superposition, which gives a quantum computer a powerful unique capability. Quantum superposition is a principle where a quantum system can exist in multiple states until it is measured. That unique capability enables a quantum computer to perform integer factorization very quickly, which is where the intersection between quantum computing and cybersecurity takes place.

Traditional binary computing’s basic unit is the bit, which expresses the two states of on and off.  In contrast, quantum computing’s basic unit is the qubit. You may have read recent headlines about ‘quantum supremacy’ which is another way of saying that someone may have achieved a quantum computing capability with the most stable qubits. 

The quantum apocalypse

Currently, cryptographic algorithms are based on factorization. RSA and Elliptic Curve Cryptography (ECC) algorithms are difficult to solve using traditional binary computers because the computer is forced to work through an incomprehensibly long list of probabilities. A traditional binary computer solves that mathematical problem slowly, whereas a quantum computer with an efficient algorithm can solve that problem much more quickly. Maybe a million times faster!  That efficient algorithm, known as ‘Shor’s Algorithm,’ when coupled with a quantum computer with enough stable qubits will theoretically be able to break current cryptographic algorithms such as RSA and Elliptic Curve (ECC).

The point at which quantum computing achieves enough stable qubits to break current cryptographic algorithms is what has been called the ‘Z Date’ by Michela Mosca, a researcher at the University of Waterloo. It is important to note that the timeline of quantum computing advancement is seemingly linear, despite the grand announcements of quantum supremacy by competitors, which is why we don’t have to worry about cryptographic algorithms being rendered unsafe in the short term. But the time we have, which is likely within the 6-10 year timeframe, has to be used carefully.

Quantum computing is not applicable to all computing problems. It should be noted that not all current cryptographic primitives are under threat by quantum computers.  Hashing algorithms such as SHA-2 are not as vulnerable to quantum computing as RSA and ECC due to the fact that quantum superposition does not offer a speed advantage in solving the mathematical problem posed by SHA-2. Interestingly, the solutions being proposed for quantum-safe cryptography are based on traditional computing capabilities. 

As a result, we will be living in a world where quantum and classic binary computing will co-exist together, and both will be used where they are both most applicable. Democratization of quantum computing will likely be achieved in the same way that massively scalable classic computing was achieved, which is via the cloud.

What is being done?

Quantum resistant cryptographic algorithms have been proposed and are currently undergoing a selection process by NIST, a federal agency that supports the development of standards. Quantum resistance comes from choosing a mathematical approach that is difficult for both traditional and quantum computers. Current cryptographic algorithms such as RSA and Elliptic Curve (ECC) are based on algebraic problems, whereas quantum-resistant algorithms are based on solving entirely different problems. As an example, lattice-based cryptography is based on a geometric approach rather than algebraic, rendering a quantum computer’s special properties less effective. 

Good cryptography requires a tough problem to solve. Lattice-based cryptography is tough for both classical and quantum computers to solve, making it a good candidate to be the basis of approach for a post-quantum cryptographic algorithm.

NIST plans to release the initial standard for quantum-resistant cryptography in 2022. 

What can businesses do now to prepare for this upcoming cybersecurity challenge?

Education is an important first step. Even before NIST has completed their selection process, it is important to take inventory of systems that are under threat. Vendors of IoT devices such as healthcare devices, automobiles, and systems going into critical infrastructure, which will be in the field beyond the 10-year timeframe, should be among the first businesses to get involved. 

What should be obvious is that we will have PKI systems that will live well beyond the quantum apocalypse and will require eventual replacement, but complete replacement will not be possible for many systems. How will we achieve cryptographic agility for systems that will bridge the current period into a post-quantum world?

Quantum-safe certificates are x.509 based PKI certificates where the keypair is generated with a quantum-resistant algorithm. In the future, we will likely be living in a world where both traditional and post-quantum algorithms will be used at the same time because it will be difficult to rip and replace all of the PKI infrastructure in existence. Hybrid certificates will have both traditional and quantum-safe keys and signatures, which will help to bridge the gap between systems that have been designed to take advantage of the new algorithms, and those that cannot.

For companies worrying today about the threat of quantum cyber security, Hybrid certificates provide an effective way to use both standard encryption and security algorithms as well as quantum safe algorithms.

The industry must get hands-on experience with the new post-quantum algorithms and test the issuance and usage of x509 based quantum-safe certificates. Sectigo has announced the release of ‘Sectigo Quantum Labs’ which combines a web resource meant to provide education on this subject, as well as a toolkit that enables the user to experiment with quantum resistant algorithms and issue hybrid certificates.

The call to arms has already begun. It’s time to plan and prepare.