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.
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 lattice-based schemes, one of the 3 KEM/Encryption (Kyber, NTRU, or SABER) and one of the 2 Signature (Dilithium or FALCON) schemes.
What is a lattice? A lattice is a set of integer linear combinations of vectors, or slightly more intuitively, we can think of it as an n-dimensional grid. Lattice-based cryptography uses NP-hard lattice problems such as the Shortest Vector Problem (SVP) and Learning with Errors (LWE) problem. All of the lattice finalist schemes use structured lattices, meaning they have additional mathematical structure (e.g. ring or module).
2D Lattice A lattice is intuitively an n-dimensional grid. This depicts a 2D lattice, and the red arrows b1 and b2 represent a basis for the lattice. A basis of an n-dimensional lattice is a set n vectors such that any other lattice vector can be generated by adding (multiples) of vectors in this set. Many lattice problems are easy to solve if the basis given is ‘nice’ (vectors are short and nearly perpendicular) but hard if the basis is ‘bad’. https://texample.net/tikz/examples/lattice-points/
CRYSTALS is a cryptographic algorithm based on Module Learning with Errors (MLWE), a problem where you solve a system of noisy linear equations with a module structure. CRYSTALS includes both a signature primitive Dilithium and a KEM primitive Kyber. This scheme has flexible security parameters, allowing you to increase or decrease security levels easily and without reimplementation, and has a strong balance of fast computations and small key, signature, and ciphertext sizes, for overall great performance.
NTRU is a KEM primitive based off the Shortest Vector Problem (SVP), in which you find the shortest vector on a lattice. The original NTRU scheme was the first lattice-based encryption scheme. Although NTRU is less efficient than other lattice schemes, the scheme inspires confidence because it has been widely analyzed over longer period than newer schemes.
SABER is a KEM primitive based on the presumed hardness Module Learning with Rounding (MLWR), which is similar to MLWE except using rounding instead of noise. SABER has excellent performance and is a promising candidate.
FALCON is signature primitive based on the Shortest Integer Solution (SIS) problem. It has tight security proofs, and the smallest public key and signatures sizes of all signature schemes. Key generation is slower but signing and verification are fast, giving it overall great performance.
Code-Based Cryptography
Code-based cryptography has 1 KEM/Encryption algorithm finalist in the NIST competition. Code-based cryptography relies on error correcting codes. Error-correcting codes are commonly used to correct errors in classical computation, and were proposed for cryptographic use in 1979 by McEliece, but did not receive attention because of the large key sizes and complexity, especially compared to RSA (developed in 1977). With the increase of computational power and new threat of quantum computation, code-based cryptography has received more attention recently for KEM/Encryption schemes.
Classic McEliece, which uses a binary Goppa code. A message is encrypted as a codeword with errors, and is decrypted by removing the errors with the private key, decoding map. The scheme is similar to the original proposed in 1979 with some security and efficiency improvements. It has the largest key sizes but the smallest ciphertexts of remaining KEM schemes. The hardness is well-known and studied for over 40 years with only slight improvements, inspiring confidence in the scheme. Although the scheme is not a good fit in general due to the large key sizes, it will likely be standardized for use with certain applications requiring small ciphertexts.
Multivariate Cryptography
Multivariate cryptography is based on equations in multiple variables, and is relatively easy to understand. The public key is a composition of three functions, and the private key is knowing these functions, which allows you to invert this function.
RAINBOW is a multivariate signature scheme with very fast signing and verification and short signatures. RAINBOW has large key sizes, making it impractical general use, but for certain applications that do not send keys often, the scheme offers the fastest signing and verification of post-quantum schemes.
Other Forms of Post-Quantum Cryptography
It is important to note that there are other alternative schemes, and among them are two additional categories of post-quantum cryptography. Hash-based cryptography uses hashes, Merkle trees, and zero knowledge proofs, and has 2 signature scheme alternatives. Isogeny-based cryptography is newer and uses abstract mathematics. An isogeny is a structure-preserving maps between elliptic curves. Isogeny-based cryptography is based on harder path-finding problems. Isogeny-based cryptography has an alternative KEM/encryption algorithm.
Start Preparing Now
The takeaway: should we start thinking about (post)-quantum cryptography now? Yes. Although NIST has not chosen a single scheme as the winner yet, the competition has been greatly narrowed down and the new standards should be available in 2022-2024. Currently, organizations can ask and answer the following questions:
Who will lead the implementation of new cryptographic technology?
Where and how is our current public-key cryptography currently implemented? For each use case, what are the security and efficiency requirements?
Which scheme(s) will we implement?
How can we increase our cryptographic agility? That is, how can we make our systems capable of adapting quickly to security threats and adopting new or modified cryptographic algorithms smoothly? This is an important preparation step in transitioning to post-quantum cryptography.
Should we be proactive in adopting new cryptographic technology and calling for solutions from partners and vendors?
Organizations can begin testing out the different schemes in their environments and planning the adoption of the new standards.
About the author: Emily Stamm is the COO and cofounder of CyberSecurity NonProfit (CSNP) and a cryptography research engineer at Allstate. She graduated from Vassar College in 2018 with a degree in mathematics where she published research papers in number theory. Emily enjoys public speaking on topics in mathematics, cryptography, and quantum computing. Instagram @crypto.emily
References
· Classic McEliece https://classic.mceliece.org/
· CRYSTALS https://pq-crystals.org/
· NTRU https://ntru.org/
· FALCON https://falcon-sign.info/
· NIST Post-Quantum Cryptography Competition https://csrc.nist.gov/Projects/Post-Quantum-Cryptography & https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
· Ding, Jintai, and Schmidt, Dieter “Rainbow, a New Multivariable Polynomial Signature Scheme” https://link.springer.com/chapter/10.1007/11496137_12
· Galbraith, Steven “Mathematics of Public Key Cryptography” https://www.math.auckland.ac.nz/~sgal018/crypto -book/main.pdf
· Jozsa, Richard “Quantum factoring, discrete logarithms and the hidden subgroup problem” https://arxiv.org/pdf/quant-ph/0012084.pdf
· Korolov, Maria, DougDrinkwater “What is quantum cryptography? It’s no silver bullet, but could improve security” https://www.csoonline.com/article/3235970/what-is-quantum-cryptography-it-s-no-silver-bullet-but-could-improve-security.html
· Micciancio, Daniele, & Regev, Oded ‘Lattice-based Cryptography’ https://cims.nyu.edu/~regev/papers/pqc.pdf
· Stubbs, Rob “ Quantum Computing and its Impact on Cryptography” https://www.cryptomathic.com/news-events/blog/quantum-computing-and-its-impact-on-cryptography
· Takagi, Tsuyoshi, Morozov, Kirill ‘Mathematics of Post-Quantum Cryptography’ https://www.springer.com/gp/book/9784431550150
· Wikipedia “Shor’s Algorithm” https://en.wikipedia.org/wiki/Shor%27s_algorithm
Thank you to Neil Smyth for his helpful feedback and suggestions.