The Current State Of Post-Quantum Cryptography
Author Emily Stamm
Public Key Cryptography
Public key cryptography is vital for online security. When two or more parties want to communicate, public key cryptography ensures that the information is confidential and accurate, and that the correct parties are communicating. Most of the time, cryptography is working behind the scenes, and we do not even realize that it is happening, let alone which type of cryptography we are using. When you visit a HTTPS website using Safari or Google Chrome, click on the lock > Certificate > Details, and scroll down to ‘Public Key Info’ to view what algorithms are protecting your connection to this site, likely RSA or Elliptic Curve.
Each public key scheme relies on the hardness of an underlying mathematical problem. If a person or computer can efficiently solve this problem, they can break the cryptography. Not every hard math problem is suitable for cryptographic use; the key characteristic is that the problem must be hard to solve in one direction, but easy in the opposite direction. For instance, it is easy to multiply two large primes together, but factoring a large number into two primes is very difficult.
Our current public key cryptography is based on problems involving factoring (RSA), discrete logs (Diffie-Hellman), and elliptic curves (ECC). While these seem like different problems, they are actually all instances of a general problem called the abelian hidden subgroup problem [See Jozsa]. This problem is difficult to solve, with the best classical algorithms having (sub)exponential complexity. It would take trillions of years to break our current public key cryptography with even the most powerful current computer, assuming the cryptography is correctly implemented.
The Quantum Threat
Our current public key cryptography has sufficed for decades, but the recent development of quantum computers poses a threat. Quantum computers are based on quantum physics rather than classical physics. In classical computing, the basic unit of information is a bit, where the value 0 or 1 may represent two distinct voltage levels. In quantum computing, this unit is a qubit, where the value, a combination of 0 and 1, may represent an electron spin or photon polarization. Quantum computers take advantage of quantum phenomenon that allow them to solve certain problems much more efficiently. In particular, Shor’s algorithm [See Wikipedia] and related quantum algorithms solve the abelian hidden subgroup problem in polynomial time. Thus, once a sufficiently powerful quantum computer is developed, it will break our current public key cryptography, and increasing the key size will not suffice.
IBM quantum computer An IBM Q cryostat used to keep IBM’s 50-qubit quantum computer cold in the IBM Q lab in Yorktown Heights, New York.
Though currently a quantum computer that can break public key cryptography does not exist, there are many reasons that organizations are already looking into quantum-secure cryptography, including the following.
1. It is difficult to estimate when quantum computation will reach the point of breaking our cryptography. This is a new form of science and technology with companies, governments, and academia trying different approaches, and estimates range from ten to thirty years until quantum computers can break our cryptography. However, we need to have our quantum-secure cryptography chosen, implemented, and tested, before anyone develops a quantum computer.
2. Transitioning cryptosystems can take many years. This aspect is often overlooked, but transitioning any technology, especially in a large organization, is an arduous process, and can take a decade. Even a simple update of an algorithm or key size can be time-consuming. It can require new infrastructure, education for developers, redesign of older applications, and new cryptographic standards.
3. Adversaries are currently storing our encrypted data and communication in preparation, making this a pertinent risk to cybersecurity today. Some data may not be as relevant in ten to thirty years, but most data will, such as PII/PHI. We need to prioritize stronger encryption of long-term sensitive data.