The Current State Of Post-Quantum Cryptography

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.

https://www.flickr.com/photos/ibm_research_zurich/40786969122

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.

4. The quantum-secure algorithms are more secure against both quantum and classical attacks, and in some cases, they are more efficient and flexible as well.

So, what are the quantum-secure replacement algorithms? They fall into two categories: quantum cryptography and post-quantum cryptography.

Quantum Cryptography

Quantum cryptography is cryptography that runs on quantum computers and is secure against classical and quantum attacks. This form of cryptography is provably secure based on the laws of quantum physics. This means that while quantum computers are the problem (i.e. used to break cryptography), they are also a potential solution (i.e. used to ‘make’ cryptography). However, there are downsides with using quantum cryptography, especially when compared with classic public key cryptography. Quantum cryptography requires parties to have access to a quantum computer, and it can be costly, impractical, and inefficient. Quantum cryptography is currently being developed and used already, however, it is unlikely that it will replace all our current cryptographic use cases, especially in the near future [See What is quantum cryptography? ..].

Post-Quantum Cryptography

Post-quantum cryptography is quantum-resistant cryptography that runs on our current computers. Essentially, post-quantum cryptography is just like our current public key cryptography, but based on harder mathematics. It’s important to make this distinction because many use the term ‘post-quantum’ when they mean ‘quantum,’ and vice-versa. The difference is that quantum cryptography uses a quantum computer, and post-quantum cryptography does not. Post-quantum cryptography is not provably secure the way quantum cryptography, however, there are security proofs that show that breaking a scheme is at least as hard as solving a well-known very hard problem (often NP-Hard). It is also important to note we do not have similar security proofs for our current public key cryptography. Additionally, it is unlikely that quantum computers will appear in our wristwatches, smartphones, or laptops any time soon. That is, in a quantum world, classical computation will not disappear, but coexist, motivating the demand for quantum-secure cryptography that runs on our current computers (i.e. post-quantum cryptography).

NIST Competition

The National Institute of Standards and Technology (NIST) is currently holding a competition to determine the new post-quantum public key cryptography standards [See NIST PQC], and cryptosystems are being evaluated and eliminated.

Before we describe the post-quantum algorithms, let’s review the two primary uses of public key cryptography: KEM/Encryption and Digital Signatures. Public key encryption ensures confidentiality. Suppose one party (Alice) wants to send another party (Bob) a secret message. Alice encrypts her message with Bob’s public key, creating an unintelligible ciphertext, which she sends to Bob. Bob decrypts the ciphertext to uncover the original message. Note that the communication is unidirectional or ‘asymmetric’; Alice cannot decrypt messages from Bob since she does not possess the private key. Since public key encryption is asymmetric and generally slower than symmetric encryption schemes like AES, public key encryption is primarily used to establish a shared secret key among parties. That is, the secret message sent from Alice to Bob is a secret key, and this secret key is then used to efficiently encrypt and decrypt data using symmetric encryption. Note that the same quantum threat does not apply to symmetric cryptography; AES [See Stubbs] can maintain the same level of security against quantum computers by doubling the key size. However, Alice and Bob cannot skip the public key encryption step because they need a method of establishing their shared key, called a Key Establishment Mechanism (KEM).

Digital signatures verify integrity and authenticity. Alice creates a signature for her message with a private key, and sends the message and signature to Bob. Bob verifies the signature using a public key to ensure that the message was not altered in transit and that his message does in fact come from Alice.

The goal of the NIST Post-Quantum Cryptography competition is to standardize at least one KEM/Encryption scheme and Digital Signature scheme. The competition began with 69 proper submissions in December 2017. As of July 22, 2020, the competition entered the third round with 7 finalist algorithms (4 KEM/Encryption and 3 Signature) and 8 alternatives (5 KEM/Encryption and 3 Signature). The remaining have varying strengths and weaknesses, such as security, key size, and efficiency. The underlying math problems vary but are all much more difficult to solve than our current cryptography.

Lattice-Based Cryptography

The leading class of problems use lattices, with 5 of the 7 finalists using lattice-based cryptography. The two remaining non-lattice schemes are not suited for all applications, so it is highly probable that the new standard will include