Living in a Post-Quantum Cryptography World

The slow yet steady development of quantum computers has brought major security fears to the forefront of the cryptocurrency sector as well as many other industries.

This article explains the problem, its origin, mechanisms, and implications as well as the steps that are being taken to remedy the threat that quantum computers pose.

What Is Post-Quantum Cryptography?

Post-quantum cryptography refers to the study of cryptographic algorithms that are considered able to withstand an attack by quantum computers. These cryptographic algorithms are usually public-key algorithms and are sometimes called quantum-proof, quantum-safe, or quantum-resistant algorithms.

Quantum proof cryptography has become a significant issue for the cryptography sector as computer scientists continue to work on developing quantum computers. These types of machines make use of the quantum states of subatomic particles to store information. In quantum computers, calculations are based on the behavior of particles at the atomic and sub-atomic level, hence the name quantum.

In theory, quantum computers should be able to handle a much higher number of instructions per second than previous machines. The exponential increase in the millions of instructions per second (MIPS) is due to the fact that data in a quantum computer exists in more than one state. This is contrary to regular computers, such as a typical PC, which are binary.

Because data in quantum computers is not binary, the machine can “think” different “thoughts” at the same time. The simultaneous exploration of different end states from the same set of particles, variables, or data allows quantum computers to offer much faster processing capabilities. Data in quantum computers is denoted in Qubits, which are similar to standard bits, except that they can take on more than one value, sometimes many, simultaneously.

Due to their processing speed, quantum computers represent a risk for many cryptography-based applications. However, researchers suggest that it is still tricky for quantum computers to behave correctly for extended periods. This is because the machines are quick to abandon quantum computing and go back to functioning like ordinary computers in the event of the slightest disturbances. Examples of these disturbances include electrical discharges, stray electromagnetic fields, or even physical movement.

Robert Schoelkopf, a Yale professor and founder of a company called Quantum Circuits, explains the promise and challenge of creating functional quantum computers. Schoelkopf says:

“If you had 50 or 100 qubits and they really worked well enough, and were fully error-corrected—you could do unfathomable calculations that can’t be replicated on any classical machine, now or ever. The flip side to quantum computing is that there are exponential ways for it to go wrong.”

For these reasons, many consider quantum computers to be far from ready and a theoretical threat at this point. However, technology giant IBM has developed a quantum computer. IBM’s machine is a 20-qubit machine, with in-house computer scientists working on upgrading it to a 50 qubit capability.

An Emerging Threat

In 2014, following Snowden’s leak of a substantial amount of classified materials, it became public knowledge that the NSA was working on a developing a quantum computer. The project was called “Penetrating Hard Targets” and was allocated a $79.7 million budget. The highly classified program is thought to be running out of a facility in College Park, Maryland. While somewhat worrying, the comparatively small budget set aside as well as the fact that the project was likely in its initial stages, resulted in lower levels of concern sector-wide.

However, in the following year, the NSA refueled these worries. The agency published an updated set of guidelines, urging agencies as well as private contractors, who work with them to begin the transition towards quantum resistant cryptography. The surveillance authority stated:

“Our ultimate goal is to provide cost-effective security against a potential quantum computer. We are working with partners across the USG, vendors, and standards bodies to ensure there is a clear plan for getting a new suite of algorithms that are developed in an open and transparent manner that will form the foundation of our next Suite of cryptographic algorithms.”

The statement set off alarms across the cryptography world as people began to wonder whether the NSA had managed to stabilize Qubits and successfully create a quantum computer. Also, others speculated that the NSA had not managed to develop a quantum computer but had knowledge of a functional one.

One major risk that quantum computers pose is Shor’s algorithm. Shor’s algorithm is named after its creator, a mathematician called Peter Shor. The algorithm was created in 1994 and is a quantum algorithm that allows users to find the prime integers of a number (N) in polynomial time. The relative ease at which Shor’s algorithm can be used to detect the prime factors of vast numbers is part of what makes quantum computers such a threat to cryptography and, in turn, the cryptocurrency industry

.@aantonop on quantum computing threat to Bitcoin.Source: https://t.co/sgGd6ObLPP pic.twitter.com/aXixeXavx4 — Panama Crypto (@Panama_TJ) September 19, 2018

Using Shor’s algorithm, quantum computers can wreak havoc on all public key systems currently in use. This is because if one has prior knowledge of one fact concerning an integer, such as a public key, then one can decipher the prime factorization. Much of the Internet uses RSA, a type of public-key cryptosystem, to securely transmit data. RSA stands for Rivest–Shamir–Adleman, after the scientists who created it. The cryptosystem consists of two components, the public key and the decryption key which is hidden from the public.

Using the public key and Shor’s algorithm, quantum computers are theoretically able to break RSA encryption. Additionally, quantum computing is also thought to be ready to tackle other types of mathematical problems that classical computers require significant resources to break. Conventional computers are unable to crack many of the algorithms in use today because they would require large amounts of power to do so. The amount of energy needed to achieve this end is unfeasible and negates any of the risk posed by classical computers.

On the other hand, quantum computers can crack public key encryption in much less time as well as compute discrete logarithm mod primes and discrete logs over elliptic curves. Quantum computing poses a risk to the cryptocurrency industry because the machines can be used to break the digital signatures utilized to ascertain transactions in digital currencies. The implication of this is immense as it can allow double spends, theft, forgeries and can likely result in the downfall of the affected cryptocurrency.

While many speculate on the future of digital currencies in the event of functioning quantum computers, Israeli cryptographer Adi Shamir, the “S” in the RSA algorithm, is of a more optimistic opinion. Speaking at the 2017 RSA conference, Shamir said:

“I wouldn’t lose too much sleep over quantum computers. Quantum computers are not at the top of my list of worries. I think there is a higher chance that RSA could be broken by a mathematical attack.”

Quantum computing is not just a concern for the computer science world. Giving the keynote speech at the 2017 RSA conference, U.S. Rep. Michael McCaul, R-Texas revealed that the U.S. was working on creating policies that could help it maintain security despite the advent of quantum computers. McCaul, who also serves as the chairman of the House Homeland Security Committee and a co-chair of the Cybersecurity Caucus, is leading the charge of lawmakers calling for substantial increases in the funding and research allocated to the field.

The Republican representatives said that he wants the United States to lead a coalition of like-minded nations to explore what security changes and defenses will be required for the quantum future, confirming that the security concerns had reached the upper echelons of power.

Waiting on NIST Guidance

In December 2016, NIST launched a post-quantum crypto project designed to identify quantum-resistant public-key cryptographic algorithms. The National Institute of Standards and Technology (NIST) is a non-regulatory agency of the United States Department of Commerce whose mission is to promote innovation and industrial competitiveness through science and innovation.

NIST provides industry standards concerning a number of technological innovations including cryptography. Using the submissions received in the post-quantum crypto project, NIST plans to issue guidance in a few years regarding how to proceed in a reality where quantum computers exist.

However, this process is expected to take a long time. Sufficiently testing algorithms requires adequate peer review which can be time-consuming in and of itself. This procedure is a part of what makes modern public key infrastructure so robust. Shamir explains:

“Remember, we are celebrating this year the 40th anniversary of the RSA algorithm; it was invented in 1977. Should we switch now, as a cautionary step, to a quantum-resistant algorithm? If someone would come up with something that is both quantum-resistant and better than our current algorithms, we win.”

Post-Quantum Algorithms

As described previously, post-quantum cryptography is the study of cryptosystems which can be computed on a classical computer but remain secure even when running on a quantum computer. NIST is currently in the process of reviewing the submissions contributed towards the efforts of standardizing post-quantum cryptography. NIST explains:

“The goal of post-quantum cryptography (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks.”

While the submissions are myriad, there are a few that are quite promising. The proposals with the greatest promise are those whose cryptosystems are based on lattices, isogenies, hash functions, and codes.

Lattices are complex mathematical structures which can obscure data. In and of themselves, lattices are not quantum-proof. However, they can be used to create quantum resistant cryptosystems. Lattices posses strong security reductions, are capable of key exchanges, digital signatures, as well as more complex features like full homomorphic encryption. The cryptosystems based on lattices in the NIST PQC standard submissions are Kyber and Dilithium.

An isogeny is defined as “a function that transforms one elliptic curve into another in such a way that the group structure of the first curve is reflected in the second.” The Supersingular Isogeny Diffie-Hellman (SIDH) scheme looks to be a promising lead for isogeny-based quantum-proof computing where the secret keys are a chain of isogenies, and public keys are curves. While isogeny-based cryptography has tiny key sizes compared to other post-quantum schemes, it is the slowest of all the other proposed QP techniques. Moreover, they support perfect forward secrecy, which cannot be said of the other proposals.

Codes in this context refer to error correcting codes. Initially created by a duo of scientists, codes have become a mainstay in modern computing. When utilizing codes, it is computationally challenging to decipher any data without knowing the linear code upon which it is based. The McEliece public key cryptosystem is the most promising cryptosystem that uses codes.

Currently, McEliece systems utilize Goppa Codes to encrypt data, but research is now underway to use another class of codes, called “quasi-cyclic moderate density parity-check codes.” This iteration will help reduce the large key size that currently exists within the McEliece cryptosystem.

Hash functions are any functions that can be used to reduce data of arbitrary size to data of a fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. In cryptosystems which use hash-based signatures, a private key can only be used once because the signature is exposed as a component of the private key. This requires ample space to store all the data. While it is not possible to create a public key encryption scheme out of hashes, SPHINCS is a QP proposal which employs hash-based signatures.

These four types of cryptosystems have been on the receiving end of a significant amount of attention, but are yet to be approved by NIST. Many consider ring lattice-based cryptography to be the most promising path to QP cryptography, but it has been tested for a shorter amount of time in comparison to its peers. As a result, much of the consensus is that the McEliece cryptosystem, when used with the battle-tested Goppa Codes, is the best bet to a quantum-proof future.