The National Institute of Science and Technology (NIST) says that public-key encryption, digital signatures, and secure key exchange “are the heart and blood” of digital identity and trust. These support numerous online applications and services critical to our economy, safety, and way of life.
Public-key cryptography performs two essential functions:
- Establishment of an agreed, shared cryptographic key to secure online communications.
- Implementation of digital signatures to validate the identity of communicating parties, building, thus, trust over an open network.
The strength of today’s cryptographic algorithms relies on the difficulty of solving the mathematical problems of integer factorization and calculating discrete logarithms. These problems have been extensively studied for decades, and when properly configured, provide long-term security against traditional computers.
The quantum threat to cryptography
However, researchers have demonstrated that large, general-purpose quantum computers can exploit the quantum mechanical phenomena. Meaning, they will solve mathematical problems computationally infeasible for today’s conventional computers.
When large-scale quantum computers become mainstream, many of the existing public-key cryptographic algorithms will become obsolete. Broken cryptography can result in unauthorized access to sensitive information, lack of control over connected devices, and potentially overthrowing the global status quo.
In contrast with public-key encryption, the good news is that quantum computers do not significantly impact the security of symmetric cryptography. Existing symmetric algorithms - such as AES - can continue to be used with suitable key sizes. The following table, taken from NIST IR 8105 “Report on Post-Quantum Cryptography,” summarizes the impact of quantum computing on public-key and symmetric cryptography.
What is quantum-safe cryptography?
NIST defines the goal of quantum-safe cryptography as the development of “cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks.”
In 2017, NIST launched a competition to design, analyze and choose a set of quantum-safe algorithms for public-key cryptography. The contest is known as the Post Quantum Cryptography (PQC) Standardization Challenge. The contest states that selected quantum-safe public-key cryptography standards will specify an additional digital signature, public-key encryption, and key-establishment algorithms to augment the following publications and standards:
- FIPS 186-4, “Digital Signature Standard (DSS)”
- NIST SP 800-56A Revision 3, “Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography.”
- NIST SP 800-56B Revision 2, “Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization.”
The quantum-safe competition intends to develop cryptographic algorithms that will protect sensitive information even after the advent of quantum computers. In July 2020, NIST announced candidates for the third round of submissions based on lattices, codes, multivariate polynomials, and hash-based signatures.
- Lattice-based cryptography is the foundation of applications such as fully homomorphic encryption, code obfuscation, and attribute-based encryption. Lattice-based cryptography relies on solving lattice problems in linear algebra, which are more complex and time-consuming than factoring prime numbers.
- Code-based cryptography is based on the McEliece cryptosystem, first proposed in 1978, and has not been broken since.
- Multivariate polynomial cryptography relies on the difficulty of solving systems of multivariate polynomials over finite fields and has been proved to be a successful approach to digital signatures.
- Hash-based signatures are developed using hash functions and leveraging pseudorandom hashing strong enough to resist sophisticated attacks.
What quantum-safe cryptography is not
Quantum-safe encryption is implemented mostly the same way current public-key cryptography is implemented. However, there will not be a “one-size-fits-all” algorithm, like RSA or ECC.
Why? Because post-quantum algorithms are based on different areas of mathematics and have distinct properties, features, and advantages.
For this reason, there is a large variation in performance characteristics between different algorithms. Some algorithms will be more suited to some use-cases than others. Let’s also consider the ever-expanding requirements for cryptography, including the proliferation of constrained connected IoT devices. It will seem unlikely there will be a single algorithm suitable for all applications.
Another reason for developing algorithms from multiple areas of mathematics is resilience. If someone finds a vulnerability in one algorithm, it will not threaten the whole post-quantum cryptography ecosystem. Developers can even use a combination of algorithms to create stronger public-keys using hybrid cryptographic approaches.
Why it is essential to prioritize crypto-agility
What should organizations do until quantum-safe cryptographic algorithms are standardized? The answer is crypto-agility.
The UK’s National Cyber Security Centre (NCSC) states that:
“Organizations that manage their own cryptographic infrastructure should factor quantum-safe transition into their long-term plans and conduct investigatory work to identify which of their systems will be high priority for transition.”
At the same time, the European Telecommunications Standards Institute (ETSI) has developed a report that detail steps organizations should take to enable a smooth migration to a quantum-safe cryptographic state.
“What we lay out in the migration report is getting the role of cryptography and the depth of its integration in a business better understood. We need to increase cryptography awareness so that people send out encrypted data keeping in mind that it may be commercially sensitive years later when attacks are possible. This helps counter harvesting attacks,” says Scott Cadzow, the Rapporteur of the Technical Report in the ETSI QSC group.
There are many approaches to deploying post-quantum cryptography while ensuring crypto-agility. For example, enhanced X.509 digital certificates simultaneously contain two sets of public-keys and signatures, traditional and quantum-safe. These enhanced certificates are compliant with industry standards and enable enterprises to gradually transition their infrastructures and systems to a quantum-safe state while maintaining backward compatibility with legacy systems.
The goal is to reap the benefits of quantum-safe technology without compromising data and system security. The NIST National Cybersecurity Center of Excellence (NCCoE) recommends several practices “to ease the migration from the current set of public-key cryptographic algorithms to replacement algorithms that are resistant to quantum computer-based attacks.”
A proactive approach to planning and preparing for the post-quantum era is needed to establish and enforce crypto-agile solutions. Teams must be ready to mitigate the threat of quantum computers and safeguard their sensitive corporate data and encryption keys and algorithms.