The quantum sea change: Navigating the impacts for cryptography

Professionals in cybersecurity and cryptography (and even non-IT executives) are hearing about the coming threat from quantum computing. It’s reaching the mainstream business consciousness.

A December 2018 report from Deloitte notes “It is expected that 2019 or 2020 will see the first-ever proven example of quantum supremacy, sometimes known as quantum superiority: a case where a quantum computer will be able to perform a certain task that no classical (traditional transistor-based digital) computer can solve in a practical amount of time or using a practical amount of resources.” The report also notes quantum computing will take many years to supplant traditional computing, but it promises to have a transformative effect.

Quantum computing leverages the ability of subatomic particles to exist in more than one state at a time. This results in faster operations and less energy usage than classical computers. The term classical computers refers to computing platforms as we know them today: laptops, smartphones, or tablets are all classical computing devices. On these devices, a bit stores a single piece of information in one of two states: either a 1 or 0.

Quantum computers use something called quantum bits – or qubits. Qubits are kind of like bits in that there are 0 or a 1 states; however, they are also not like bits at all because the state of a qubit can also be a superposition of both possible states. That is, maybe it’s a 1, or maybe it’s a 0, or maybe it’s both at the same time.

Qubits can store much more information than a classical bit, and a quantum computer can perform certain operations much faster than a classical computer. In 2015, Google and NASA installed a D-Wave Two computer and found that it was 100 million times faster than a conventional computer. That level of speed and efficiency has uncomfortable effects on the current cryptographic landscape, or cryptoscape. And its implications are much worse for public key (asymmetric) cryptography than for symmetric cryptography and hashing.

With quantum computing, mathematical problems such as discrete logarithms and integer factorization are exponentially faster. This matters because integer factorization and discrete logarithms are the (at least for now) hard (i.e., expensive and time-consuming) problems that provide security for certain types of cryptographic protocols. Say these problems become easy, meaning fast and cheap. Public key encryption, key establishment and key exchange protocols (e.g., TLS), trust in digital signatures, and the authenticity provided by digital certificates would all be catastrophically impacted. The systems that enable national security, the economy, distributed commerce, and secure and trustworthy communications, would become obsolete – overnight.

This state of affairs is known as “the coming cryptopocalypse.” The good news is that quantum algorithms achieve only modest efficiency gains for problems like searching, collision finding and evaluation of Boolean functions. So, while symmetric encryption algorithms (e.g., AES) and cryptographic hash functions (e.g., SHA-2, SHA-3) are not going to be completely obsolete, the cryptography community must still adapt.

The right response with symmetric encryption is to increase the key size for the symmetric algorithms; e.g., moving from 256-bit keys to 512-bit or larger keys. For cryptographic hash functions, it’s to increase the size of the output string: e.g., moving from 512 bits to 768 or 1,024, or more. This is consistent with Grover’s algorithm which provides a speed increase for quantum search algorithms over conventional search algorithms.

For current forms of asymmetric encryption the prospects are bleaker. This is vitally important because this type of encryption underlies nearly every online activity. An international community is developing “Post-Quantum Cryptography (PQC)” in response. There are algorithm families proposed as post-quantum cryptographic primitives, including lattice-based, code-based, and multivariate polynomial cryptography, hash-based signatures, and isogenies on super singular elliptic curves.

Industry needs to roll out security mechanisms that recognize the impending cryptopocalypse. Tools that use symmetric cryptography should use the protocols in novel ways that guarantee key space extension, regardless of the algorithms used. Ensuring asymmetric cryptography means incorporating promising candidates from the PQC competition into current products in a modular composable way so that even if the first PQC algorithms used aren’t standardized, they can be quickly replaced and existing products upgraded.

There are also efforts to exploit quantum computing properties to create more secure cryptography. Quantum cryptography leverages Heisenberg’s Uncertainty Principle and the No-Cloning Theorem. Meaning we can’t examine a quantum system without changing it, and we can’t record characteristics of the system before examining it. Just by observing a quantum system, we change it. The No-Cloning Theorem states that it’s impossible to create a copy of an arbitrary, unknown quantum state.

Such a situation makes unobserved eavesdropping impossible due to detectable impacts. This provides assurance that communication over a quantum-protected channel is private. One well-developed application of quantum cryptography is Quantum Key Distribution (QKD). QKD uses quantum communication to establish a shared secret key between Alice and Bob, without Eve (the eavesdropper) being able to eavesdrop. QKD’s security is described as unconditional, meaning it can be proven without imposing any restrictions on the abilities of the attacker.

Quantum computing presents both risks and opportunities. It’s an evolutionary, existential threat to some forms of current cryptography, but solutions are available and ready for implementation. And on the other side it provides the potential for practically achievable unconditional security and privacy.