Security comes up a lot in our conversations with enterprise customers. And for good reason: one of the most significant applications of quantum computing is its theoretical ability to crack the encryption schemes that secure most of the world’s sensitive information.
This will have enormous consequences: every trade secret, classified document, customer dataset, financial or medical record, private email, iMessage and more currently protected by encryption could be exposed. Critical military, communications and financial systems could also be hacked by adversaries to wreak havoc and inflict trillions of dollars of damage.
Given the magnitude of the threat, we believe it is imperative that we accelerate efforts to develop and implement post-quantum cryptography (PQC) schemes that can withstand quantum attacks. Critically, we cannot wait until the day when quantum computers are powerful enough to break existing encryption schemes, because as we will show below, that day could come much sooner than is typically expected.
In this blog post, I’ll share our answers to some of the most common security-related questions we get from customers. Read on to learn more about the security risk posed by quantum computing, when it will be a problem, and what you can do to protect your sensitive data.
For decades, a small handful of cryptographic schemes have been used to encrypt all our sensitive data, with RSA being the most widely used. Most of these schemes are based on the difficulty of finding the prime factors of large integers or equivalent mathematical problems. There is no known classical algorithm that can solve this problem efficiently. In fact, it would take the world’s fastest classical supercomputer 590 million years to crack a 2048-bit RSA encryption key. For a long time, this seemed reliably safe.
That changed in 1994 with the seminal publication of Shor’s algorithm, named after its creator Peter Shor. Researchers proved that, given access to a large enough fault-tolerant quantum computer (FTQC), it would be possible for Shor’s algorithm to factor a 2048-bit integer in just 8 hours — thus compromising RSA and any other encryption schemes relying on factorization.
To mitigate this risk, researchers have started developing post-quantum cryptographic algorithms: classical cryptographic algorithms designed to be resistant to attacks by quantum computers. These algorithms are not based on integer factorization, but on other mathematical problems that are not known to be efficiently solvable by a quantum computer.
However, it will take a long time and significant financial resources to adapt all currently encrypted systems to use post-quantum cryptography, and it is expected that some systems may not be able to make this transition at all. The World Economic Forum predicts that over 20 billion digital devices around the world will need to be upgraded or replaced globally to incorporate PQC, and estimates suggest it could take over ten years to make this transition.
For this reason, in 2016 the US National Institute of Standards and Technology (NIST) initiated a standardization process to assess the suitability of candidate algorithms for post-quantum cryptography. NIST previously defined the cryptographic standards now in widespread use by organizations, including the US government. The new standardization process will assess both the security and the practicality of implementing potential PQC schemes.
At the conclusion of this assessment, expected between 2022 and 2024, NIST will define new PQC algorithms as standards to replace the encryption algorithms currently in use. Lawmakers are already taking action to ensure these standards will be implemented promptly. The Quantum Computing Cybersecurity Preparedness Act, introduced in April 2022, would ensure federal agencies implement the new NIST standards for PQC. The Department of Homeland Security has also released its own road map for adopting PQC.
Sooner than you think. The conventional view is that we don’t need to worry until we have a quantum computer powerful enough to run Shor’s algorithm, which may not be for another 10-20 years. Shor’s algorithm is believed to require tens of millions of qubits. For perspective, IBM’s industry leading Condor computer, slated for release in 2023, will have just 1,121 qubits.
In 2020, more than half of expert respondents predicted that there was at least a 50% probability that a significant quantum threat to public key encryption would emerge within the next 15 years.
But there’s good reason to believe that “Q-Day” (the term for when quantum computers will be able to meaningfully compromise RSA and other common encryption schemes) will come much sooner than the large-scale FTQCs that can run Shor’s algorithm. The reality is that Shor’s is not the only threat to encryption, nor is it the most pressing. Heuristic algorithms, leveraging the noisy, near-term quantum devices available today together with classical computers, could break encryption much sooner. If quantum hardware roadmaps are accurate, a quantum cryptographic threat in the form of a heuristic algorithm could plausibly arrive by 2030.
One example of a heuristic algorithm is Variational Quantum Factoring (VQF). In 2018, Zapata research showed that VQF could factor 6-digit numbers using the quantum hardware available at the time. Extrapolating this research into regimes with larger keys showed it was possible to factor a 2048-bit RSA number with only 6,000 high-quality physical qubits, significantly accelerating the dawn of Q-Day. Additional heuristic algorithms have since been invented, and concerningly, an algorithm proposed in one recent paper may even compromise a family of post-quantum algorithms currently being considered by NIST as potential new standards.
This underlines a hole in NIST’s approach. NIST is currently considering only encryption algorithms that rely on mathematical problems for which there are no known classical or quantum algorithms that are provably efficient at solving them. Since heuristic algorithms usually don’t have theoretically rigorous proofs of their efficiency, they are explicitly excluded from NIST’s consideration. However, they could still compromise the security of post-quantum cryptographic methods.
The first step would be to identify your organization’s most sensitive data so it can be prioritized for re-encryption. You will also need to survey and catalogue your organization’s entire digital infrastructure to assess what cryptographic algorithms and protocols are currently in use in every instance. Given the scale, this task cannot be done manually and will require months of work, even with some degree of automation. And that does not even begin the process of re-encrypting everything with PQC.
It’s too early to say whether the new NIST standards will be reliable or which PQC scheme will be the best option. The threats will continue to evolve, whether it’s new heuristic algorithms or mathematically provable algorithms like Shor’s. The bottom line is that when there’s a new standard, hackers will look for ways to exploit it.
That’s why when you’re planning your organization’s migration to new cryptographic systems, you need to prioritize flexibility and agility. You’re inevitably going to need to invest millions of dollars and years of work into the migration, the last thing you want is for a new algorithm to come out that can break your new encryption and leave you vulnerable again. You’re going to want to do it right the first time so you don’t have to do it again. That means investing in security platforms that give you the flexibility to easily swap encryption schemes in and out, and even layer encryption schemes on top of each other.
Any sensitive data should be re-encrypted with PQC schemes once reliable options are available. However, anything that has already been intercepted and stored by hackers or adversaries is a lost cause and may one day be decrypted using quantum computers. Decades of encrypted data is currently vulnerable to these “store now; decrypt later” (SNDL) attacks.
Inevitably, this means we’re all going to need to change our passwords once they can be securely encrypted with reliable PQC schemes. However, it won’t be possible to save secure information, such as customer data or trade secrets, from quantum decryption if it has already been exfiltrated. The bottom line is that the dawn of quantum decryption algorithms will be massively disruptive and will lead to rampant leaks and extortion attempts. An entire generation of secrets will come to light.
That said, it is impossible to know what encrypted data or communication has already been intercepted and saved. The best practice will be to assume any sensitive data has not yet been intercepted and to proactively re-encrypt it with PQC accordingly.
Yes. Having access to a quantum computer that can break classical encryption would be valuable both as a defensive deterrent and as a counterattack against hackers. It could also be used as a solution to ransomware, wherein attackers encrypt your data until a ransom is paid. Quantum computing could decrypt the attackers’ encryption and neutralize the ransomware attack. However, we are still several years away from the day when quantum computers can break classical encryption, so in the near-term it is better to focus on adopting PQC schemes to protect your sensitive information from future quantum attacks.
What is Zapata doing to support post-quantum encryption?
Zapata is directing significant resources towards quantifying the security threat posed by quantum computers and assessing the resources required to break existing encryption schemes. We believe hackers will not wait until the arrival of FTQCs that can run Shor’s algorithm, and will look to exploit whatever near-term classical, quantum, or quantum-inspired algorithm can break encryption first. For that reason, we will continue to research potential heuristic algorithms, such as VQF, and evaluate their potential to crack both existing encryption schemes and proposed post-quantum schemes. You can think of this as equivalent to the penetration testing used by many organizations to identify their security vulnerabilities.
Since the greatest near-term threat — heuristic algorithms — do not have mathematical proofs (aka theoretical guarantees) of their efficiency, we are also performing benchmarking tests to precisely quantify the classical and quantum resources these algorithms will need to break encryption. Zapata’s quantum software platform, Orquestra®, is well suited for running large-scale benchmarks on a wide variety of quantum devices. That’s what it does best today.
In fact, earlier this year Zapata received an award from the Defense Advanced Research Projects Agency (DARPA) to use Orquestra to benchmark quantum computing at both the algorithmic and the application level. The multi-year, multi-million-dollar award will help fund the creation of software tools to make hardware-specific resource estimates for software running on quantum computers, which could include heuristic algorithms and other quantum security threats. This work will help us to better predict when our existing encryption schemes may be compromised.
Perhaps most importantly, we want to provide our customers with the confidence that their workflows running on Orquestra will be secure from quantum cryptographic threats. As part of this, we are pursuing partnerships with vendors offering quantum security solutions and integrating them into Orquestra. This work will help us to better predict when our existing encryption schemes may be compromised.
One of the greatest advantages of Orquestra is its modularity. We typically talk about this in the context of swapping in and out hardware backends and software components, but it can also be used to swap in and out different PQC schemes as the threat landscape evolves. Given the scale of the investment required to migrate to PQC, the last thing you want is to be locked into a cryptographic system that could be vulnerable in the future. We are designing Orquestra to give our customers the flexibility to quickly adapt to future threats.
To learn more about quantum cybersecurity considerations and what your organization can do now to prepare, contact us.
