The Story of VQF: A Near-Term Quantum Threat
The Story of VQF: A Near-Term Quantum Threat
In 2018, we developed an algorithm that made us rethink the timeline for when quantum computers will threaten the world’s cybersecurity.
In 2018, Zapata co-founders Jonny Olson and Yudong Cao developed Variational Quantum Factoring (VQF), an algorithm that could compromise some instances of RSA encryption using noisy intermediate-scale quantum (NISQ) devices in the near term. This is their story.
Since Peter Shor created his eponymous algorithm in 1994, cybersecurity experts have known that quantum computers will one day be able to crack the RSA encryption that protects most of the world’s sensitive data and applications. The consensus is that running Shor’s algorithm would require roughly 14,000 fault-tolerant qubits (or 20,000,000 physical qubits) over 8 hours. Based on that assumption, it will be another decade or two before quantum computers are powerful enough to break RSA encryption.
Our alarming discovery in 2018 showed that the threat from quantum computers could come much sooner — perhaps within the next 5 years, rather than the next 15. Given the astronomical scale of systems protected by RSA, this means organizations can no longer afford to wait to prepare for this threat.
One summer morning in 2018, we were standing around a whiteboard with Eric Anschuetz, an intern at the time from MIT, discussing potential avenues to take our research next. A few years earlier, Zapata founders Alán Aspuru-Guzik and Jhonathan Romero Fontalvo had made waves in the quantum community as part of the team that developed the Variational Quantum Eigensolver (VQE), one of the first NISQ algorithms and a flagship algorithm for quantum chemistry. We wondered if a similar approach would make it possible for NISQ devices to solve the factoring problem that secured RSA.
Over lunch, I (Yudong) had an idea. If we turned the factoring problem into an optimization problem, as others had done before, we could solve it with a recently developed quantum algorithm for optimization. Eric lit up at the idea and got to work on implementing it. By the time the weekend was over, we had a working prototype. A week later, we had filed a patent and written a paper. VQF was born.
At first, the prototype was just running on a laptop using a classical simulator of a small quantum computer, but we later validated it on a real quantum device from IBM. By extrapolating our results, we estimated that with just a little over 6,000 NISQ qubits, VQF could factor a 2048-bit RSA number in a few hours. If the product roadmaps from leading quantum hardware vendors are accurate, that means a NISQ device available in the next 5 years would be able to crack a subset of RSA keys. The threat is much more immediate than many realize.
When we realized the significance of our discovery, we had an ethical dilemma on our hands. We could either keep it to ourselves and keep the quantum cyberthreat timeline as it was — or tell the world. Ultimately, we decided the world needed to know. Considering how quickly we came up with VQF, it was very possible there could be other near-term quantum threats that hadn’t been considered. The world was not ready for these threats, and time was running out to prepare. We had to raise the alarm.
If the product roadmaps from leading quantum hardware vendors are accurate, that means a NISQ device available in the next 5 years would be able to crack a subset of RSA keys.
Unlike Shor’s, VQF is a heuristic algorithm, which means there is empirical but not mathematical proof of its effectiveness. That shouldn’t assure anybody that it isn’t a threat — neural networks are also heuristic algorithms and are widely deployed and extremely effective for applications such as facial recognition, and they are continually improving.
VQF works by mapping the factoring problem underlying the security of RSA onto a combinatorial optimization problem. Whereas Shor’s algorithm requires error correction — something only found on future quantum computers — to perform, VQF harnesses existing technology, using a combination of classical and quantum resources. Pre-processing is done on the classical computer before employing the Quantum Approximate Optimization Algorithm (QAOA). By doing most of the problem-solving classically, we can dramatically reduce the qubits required. This will be the case with most near-term quantum applications, in fact.
It should be noted that VQF won’t be able to factor every 2048-bit RSA encryption key — unlike Shor’s algorithm. Rather, its outcome is unpredictable; we don’t know which keys that VQF will factor and which it won’t.
But how much risk are you willing to accept? When the stakes are as high as national security, the power grid, or the privacy of your customers, any risk is unacceptable. Whether VQF or other heuristic algorithms can break your encryption or not, it’s worth assessing your vulnerability in case they can.
The National Institue of Standards and Technology (NIST) has been preparing for Shor’s algorithm for a long time, developing new post-quantum cryptography (PQC) standards that are supposed to be safe from attacks using Shor’s algorithm. However, there is no guarantee that these new standards will be safe from heuristic algorithms like VQF. In fact, one recent paper proposed a heuristic algorithm that may even compromise a family of cryptographic algorithms currently under consideration for NISQ’s new standards.
If we could come up with VQF over a weekend, a dedicated group of malicious actors with the right motivation could just as easily devise a similar heuristic threat.
We are rapidly approaching a world where encryption — and by extension cybersecurity, privacy, and confidentiality — is no longer guaranteed. If we could come up with VQF over a weekend, a dedicated group of malicious actors with the right motivation could just as easily devise a similar heuristic threat. If you follow NIST’s guidance of migrating to PQC over the next 10-15 years, you will still be vulnerable to VQF and other heuristic algorithms.
Even if you assume that the powerful quantum computers needed to run VQF, Shor’s or other decryption algorithms won’t be available for the next decade, you still can’t afford to wait. As you read this, hackers are exfiltrating encrypted data with the aim of decrypting it later with sufficiently powerful quantum computers. You have to assume your encrypted data will one day come to light — how will you deal with that? Now is the time to start preparing.
So, what can you do as an organization to prepare when there is no way to trust any cryptography standard in the long run? The key is to develop a posture of crypto-agility. Crypto-agility refers to the ability to rapidly deploy new encryption protocols in response to a changing threat landscape. If you’re going to invest millions of dollars in migrating your sensitive systems to PQC, you’re going to want to plan for crypto-agility from the start — or be prepared to invest millions in doing PQC migration twice.
As a first step to crypto-agility, you will want to create an inventory of the cryptography used to secure all your sensitive data and applications. From there, it will be easier to perform penetration testing of these assets using VQF and other heuristic algorithms, and to update the cryptography as necessary.
Zapata is supporting our customers’ transition to PQC in three areas: assessment, testing, and verification.
We are focused on helping customers and security vendors assess the risk profile of their security postures, particularly their vulnerabilities to near-term threats from heuristic algorithms running on NISQ devices. As part of this, we research and identify other heuristic algorithms like VQF that could also pose a threat, and analyze how vulnerable existing security algorithms, standards and implementations are to these heuristic algorithms. As a result, our customers will be able to select the most appropriate PQC algorithms to adopt and develop a sound roadmap to mitigate near-term quantum security risks.
The next area where we provide support is in penetration testing. This involves applying VQF and any other heuristic algorithms we may discover to understand what it takes to break our customers’ encryption. This will allow us to identify encryption that may be vulnerable to near-term attacks and give our customers the chance to proactively update their encryption.
Resource estimation is a key part of the testing. Using our Orquestra® platform, we can benchmark these algorithms on various hardware backends to estimate the time and compute resources — both quantum and classical — required for these algorithms to work, helping our customers to understand when these algorithms could be a problem.
We provide a detailed quantum security rating for customers’ security implementation, giving them visibility into how effectively their implementation can resist near-term quantum threats and how long they can remain effective. This will be followed by ongoing monitoring for new vulnerabilities as quantum computers mature and the threat landscape evolves.
We are currently applying this approach to assess the threats posed by near-term hybrid heuristic algorithms with our customers. If you’d like to work with us to assess your organization’s vulnerability to near-term attacks, get in touch today.
