Analyst(s): Dr. Bob Sutor, Krista Case
Publication Date: August 14, 2024
The News: After years of development by quantum, cryptography, and cybersecurity experts worldwide, the US National Institute of Standards and Technology has finalized three new standards for post-quantum cryptography (PQC) based on work by IBM employees. Experts believe these standards prescribe encryption methods that will not be breakable eventually by quantum computers.
Quantum in Context: IBM Key to New NIST Post-Quantum Crypto Standards
Analyst Take: For all the potential of quantum computing to solve problems intractable with today’s classical systems, there has been a shadow hanging over the field since the 1990s. In cryptography, decryption schemes are protected by having authorized people or systems having the keys to unlock encrypted data. These can only be broken by solving some very hard computational problems. In the case of RSA and several other methods, those hard problems involve factoring specific very large numbers into smaller prime numbers.
Peter Shor’s 1995 quantum algorithm shows how to factor numbers almost exponentially faster than any known classical method. However, today’s quantum computers are nowhere near powerful enough to perform these calculations. Nevertheless, we must protect ourselves in the future. The new NIST standards are an excellent start to providing that insurance against quantum computers undoing data encryption. The decades-long strength of IBM’s Research division and its scientific expertise were critical for providing the core algorithms in the standards.
The work to protect our data against quantum attacks is not complete, and NIST should continue to lead the way in developing standards. This is not the time for sovereign or other international efforts to compete. Continued global cooperation and pooling of cryptographic and cybersecurity expertise is critical.
What’s the Cybersecurity Problem? Q2K? Quantum Crypto Apocalypse?
Suppose I tell you that I have a great way to protect data that you and I exchange. It involves keys for encrypting and decrypting the information. I will give you the key you need, but someone else can only figure out the keys if they can factor a number, in particular, a positive integer. This number will have exactly two prime factors, where a prime only has 1 and itself as factors. For example, 5 is prime because 1 times 5 is the only way to break down 5 multiplicatively into positive integers, where we count 5 times 1 as the same factorization.
Are you ready? The two primes related to our scheme are 3 and 7, with the product 21. Only if someone could possibly factor 21 can they break our encryption.
OK, maybe that’s not a good choice. How about 1,114,957? That looks big. Its prime factors are 857 and 1301. It would take an algorithm on your smartphone well less than a second to factor that. That won’t work.
We need to go larger, but even those numbers can be easy to factor. Consider
4,065,611,775,352,152,373,972,797,075,670,416,
710,103,878,906,323,797,634,290,517,698,787,
563,831,961,701,377,171,181,093,217,455,781,
996,250,152,587,890,625.
It has 118 digits. It is simple to factor because it is 3 multiplied by itself 100 times, then multiplied by 5 multiplied by itself 100 times. In other words, 3100 5100.
However, other large numbers are exceptionally hard to factor. Some products of two large primes could take years, decades, or centuries to factor by known classical methods on supercomputers. These would be much better choices for our encryption scheme than the values above.
RSA is one such encryption scheme. We should be set if we use large products of certain primes, right?
In 1995, mathematician Peter Shor developed an algorithm to factor numbers almost exponentially faster than the classical methods we have. Here, we are using “exponentially” in the mathematical sense. Suppose it takes you 1,000 or 103 seconds to accomplish a task. An exponentially faster approach could do the same job in approximately 3 seconds, where 3 is the exponent of 10. A year has 31,536,000 seconds. If the task took that long to finish, an exponentially faster algorithm would only take about 8 seconds. That’s a fantastic improvement.
When Shor discovered his algorithm, we did not have quantum computers. Researchers developed the first quantum computers in the late 1990s, but today’s machines are still not powerful enough to implement Shor’s algorithm for very big numbers. (Note that there is a lot of hype, questionable research, and excellent but unimplemented research in this area.) Many assert that quantum computers will eventually be able to factor the large numbers used in standards such as RSA. We’ll have to wait to see, but we must prepare for the possibility.
The new standards from NIST are a response to that need. Not only do experts believe they are likely uncrackable by quantum computers, but they are better than current classical algorithms. There is no reason not to move to them as part of your cybersecurity infrastructure. Start now! If you used pre-standardized versions of the specifications, get yourself on the official versions. Vendors are rushing to support them. See, for example, what IBM is doing with its Quantum SafeTM technology to discover, inventory, and remediate potential vulnerabilities.
The NIST PQC Standards Development Process
In May 2016, IBM put the first quantum computer on the cloud. Although it was only five qubits, it surprised people that systems only previously available to researchers might be generally available. The formerly abstract idea of Shor’s algorithm and its possible use for breaking encryption took on greater urgency.
Three months later, NIST posted its “Post-Quantum Cryptography: Proposed Requirements and Evaluation Criteria.” By December, after public comments, it understood what it was looking for and published “Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms.” The announcement stated
It is intended that the new public-key cryptography standards will specify one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are capable of protecting sensitive government information well into the foreseeable future, including after the advent of quantum computers.
Note that the posting only refers to protecting government information, not data used by everyone. However, many businesses and individuals work with governments, so the new standards would apply to them. More generally, there was no need to have separate specifications for the public and private sectors, so the standard-setting activity quickly grew into a broad and international effort.
There were many candidate submissions, and the standards team winnowed the collection to semi-finalists and finalists over the eight years. There were surprises along the way, such as when IBM scientist Ward Beullens discovered in 2022 that the “Rainbow” finalist could be broken classically on a laptop over a weekend. The NIST Computer Security Research Center provides the history and documentation of the standards effort.
The three new official standards are:
- FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM) – based on CRYSTALS-Kyber specification
- FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA) – based on CRYSTALS-Dilithium specification
- FIPS 205: Stateless Hash-Based Digital Signature Standard (SLH-DSA) – based on the SPHINCS± specification
For media culture completeness, Dilithium is the fictional element used in Star TrekTM to control matter–antimatter reactions for propulsion, and Kyber is a crystal in Star WarsTM to power light sabers.
You might wonder why there was a rush to develop these standards when we do not have quantum computers capable of breaking today’s encryption methods. First, this effort shows that it took nearly a decade to finalize the first standards, so we should not have waited for the problem to exist and then find a solution.
Second, there is the “harvest now, decrypt later” problem, where bad actors steal confidential, encrypted information today with the hope of gaining access to it later. Say that it takes us 15 years to develop a quantum computer that is powerful enough to exploit cryptographic vulnerability. This still presents the potential for the disclosure of state and military secrets, which must remain confidential for many decades, for example, or personal healthcare or financial information that could still have sensitive implications decades later.
IBM’s Role in Drafting the Standards
IBM Research Zurich scientists Vadim Lyubashevsky and Gregor Seiler developed the original CRYSTALS-Kyber and CRYSTALS-Dilithium specifications with other collaborators. Ward Beullens, co-developer of SPHINCS+, is now an IBM employee. The “hard problem” for CRYSTALS-Kyber is Learning with Errors (LWE), and for CRYSTALS-Dilithium, it is LWE and short integer solutions.
In addition to its work on quantum computing, IBM has demonstrated through its standardization contributions that it looks at the complete picture of a quantum future in the data center and on-premises. To better understand its views on what will happen in the industry and across its products and solutions, see the IBM Quantum Safe Roadmap. It demonstrates successful technology transfer from its global Research division to its cybersecurity business.
Do We Need More PQC Standards?
Are these new standards guaranteed to prevent any future quantum attacks? Unfortunately not, but experts believe we cannot eventually break these standardized encryption schemes with large and powerful enough quantum computers. Belief is not proof, however. Some clever persons may someday discover a new quantum algorithm that renders the encrypted data vulnerable. In fact, there is no proof that someone can’t find a classical algorithm to factor numbers much more efficiently than other known classical methods. Pierre de Fermat formulated his “Last Theorem” around 1637, but it wasn’t until 1994 that Princeton Professor of Mathematics Andrew Wiles demonstrated a proof. We waited 357 years for that. So, who is to say we won’t get a superior classical factoring algorithm?
We must move away from encryption protocols that are associated with factorization. Furthermore, crypto-agility requires a cybersecurity architecture that allows us to shift between encryption schemes. Moving to the new standards will be easier for those who are crypto-agile today. Security vendors such as DigiCert provide guidance on becoming crypto-agile. Research must continue to find new quantum-resistant protocols. If some hackers find an attack on the current ones or an expert discovers a defect, we must have alternatives to deploy.
In 2022, NIST issued a call for additional PQC digital signature standards candidates. By July 2023, they had received 40 specifications that met all the submission requirements.
We believe that NIST should be the sole organization that develops and standardizes any new encryption schemes impervious to future quantum attacks. Global cooperation and expertise are necessary, and there is no need for more local specifications. Let’s consider these and any future PQC standards to be planet-wide and not used only by any single country, region, or alliance.
Where You Can Learn More
Bob Sutor’s quantum computing book Dancing with Qubits, Second Edition: From qubits to algorithms, embark on the quantum computing journey shaping our future explains the cryptographic and quantum-algorithmic aspects related to the need for PQC in detail:
- Section 1.6: “What about cryptography?”
- Section 10.2: “Factoring”
- Section 10.7: “Shor’s Factoring Algorithm”
Key Takeaway
After years of development, we finally have official cryptography standards that should be able to protect our data from quantum cybersecurity attacks. IBM provided key algorithms and worked with the international community to develop and test the proposals. We have no ironclad guarantees that future classical or quantum algorithms will not be able to crack these encryption protocols. So we must remain diligent, adopt the latest standards, and continue the work to create new standards based on different approaches.
For additional details, see the “IBM-Developed Algorithms Announced as World’s First Post-Quantum Cryptography Standards” press release.
Disclosure: The Futurum Group is a research and advisory firm that engages or has engaged in research, analysis, and advisory services with many technology companies, including those mentioned in this article. Bob Sutor is a former employee of IBM and has an equity position in the company. The author has no equity position in any other company mentioned in this article.
Analysis and opinions expressed herein are specific to the analyst individually and data and other information that might have been provided for validation, not those of The Futurum Group as a whole.
Other Insights from The Futurum Group:
Quantum in Context: A Qubit Primer
IBM Think 2023: IBM Charts the Course to Quantum Safe Computing
NIST Releases First Draft Standards for Post-Quantum Cryptography
Author Information
Dr. Bob Sutor is a Consulting Analyst for Futurum and an expert in quantum technologies with 40+ years of experience. He is an accomplished author of the quantum computing book Dancing with Qubits, Second Edition. Bob is dedicated to evolving quantum to help solve society's critical computational problems. For Futurum, he helps clients understand sophisticated technologies and how to make the best use of them for success in their organizations and industries.
He’s the author of a book about quantum computing called Dancing with Qubits, which was published in 2019, with the Second Edition released in March 2024. He is also the author of the 2021 book Dancing with Python, an introduction to Python coding for classical and quantum computing. Areas in which he’s worked: quantum computing, AI, blockchain, mathematics and mathematical software, Linux, open source, standards management, product management and marketing, computer algebra, and web standards.
With a focus on data security, protection, and management, Krista has a particular focus on how these strategies play out in multi-cloud environments. She brings approximately 15 years of experience providing research and advisory services and creating thought leadership content. Her vantage point spans technology and vendor portfolio developments; customer buying behavior trends; and vendor ecosystems, go-to-market positioning, and business models. Her work has appeared in major publications including eWeek, TechTarget and The Register.
Prior to joining The Futurum Group, Krista led the data protection practice for Evaluator Group and the data center practice of analyst firm Technology Business Research. She also created articles, product analyses, and blogs on all things storage and data protection and management for analyst firm Storage Switzerland and led market intelligence initiatives for media company TechTarget.
