JVG Algorithm: Why This Quantum RSA Cracking Claim Doesn’t Work
The quantum computing landscape is, to put it mildly, a breeding ground for hype. So when claims emerge of a breakthrough that dramatically accelerates the timeline for breaking modern encryption, skepticism is warranted. Recently, a novel algorithm dubbed “JVG” (after its authors, Jesse, Victor, and Gharabaghi) has been circulating, with some reports suggesting it could allow RSA-2048 encryption to be cracked using as few as 5,000 qubits. This sparked a flurry of concern, but a closer look reveals the algorithm relies on a fundamental flaw and is, in the words of Scott Aaronson, “crap.”
The Core Problem: Exponential Scaling
The JVG algorithm attempts to improve upon Shor’s algorithm, the well-established quantum algorithm for factoring large numbers. Shor’s algorithm, while theoretically capable of breaking RSA and ECC encryption, requires a substantial quantum computer – estimated at around one million qubits – to become practical. This timeline has given the industry breathing room to transition to post-quantum cryptography (PQC), standards for encryption designed to resist attacks from both classical and quantum computers. NIST has already recommended several PQC algorithms, and adoption is underway, though perhaps not as quickly as some security experts would like.
The JVG algorithm’s proposed innovation centers around a key step in Shor’s algorithm: computing xr mod N in a superposition over all possible values of ‘r’. The JVG approach suggests pre-computing all these values on a classical computer and then loading them into the quantum state. However, this seemingly clever shortcut runs into a brick wall: the number of possible ‘r’ values grows exponentially with the size of the number being factored. As Scott Aaronson succinctly puts it, In other words you’re trading one computationally intractable problem for another – moving from a problem scaling with n2 time to one scaling with 2n time. Essentially, the pre-computation and loading process itself becomes exponentially difficult, negating any potential gains.
This isn’t a novel observation. As noted in a discussion on Hacker News and further detailed by Postquantum.com , the fundamental issue is the exponential scaling inherent in the approach. The algorithm might appear to work for particularly small numbers, but it quickly becomes impractical as the size of the number increases to levels relevant for real-world encryption.
Why the Alarm Didn’t Stick
Several red flags should have immediately raised suspicion about the JVG algorithm’s claims. First, the research was published on Preprints.org, a repository that, while legitimate, doesn’t have the same rigorous peer-review process as established platforms like arXiv , ECCC , or IACR . Scott Aaronson points out that he’s seen “pretty much only crap” on preprint repositories other than these three.
Second, the claims were amplified by clickbait news sites, but largely ignored by reputable science and technology news outlets. Even publications known for covering quantum computing with enthusiasm remained silent, a strong indicator that the claims weren’t holding up to scrutiny. A quick Google search confirms this pattern, with results dominated by sensationalized articles rather than in-depth analysis.
Implications for Post-Quantum Cryptography
While the JVG algorithm itself appears to be a dead end, the episode serves as a reminder of the ongoing urgency surrounding the transition to post-quantum cryptography. The threat from quantum computers is real, even if the timeline remains uncertain. The “harvest now, decrypt later” attack – where adversaries are currently collecting encrypted data with the intention of decrypting it once quantum computers become powerful enough – is a significant concern.
The NIST PQC standardization process is a crucial step in mitigating this risk. Several PQC algorithms have been selected for standardization, and their implementation in widely used protocols like TLS and messaging apps is underway. However, adoption hasn’t been universal. Signal and iMessage have been early adopters, but popular platforms like WhatsApp and Telegram still lack end-to-end encryption using PQC standards.
The JVG algorithm, despite its flaws, underscores the need for continued vigilance and accelerated adoption of PQC. It’s a stark reminder that the cryptographic landscape is constantly evolving, and relying on outdated encryption methods is a growing risk.
The Importance of Scrutiny
The swift dismissal of the JVG algorithm by the quantum computing community highlights the importance of rigorous scrutiny in scientific research. The fact that the claims were met with silence rather than debate speaks volumes. As Scott Aaronson notes, the lack of discussion on relevant forums and in research circles was a clear indication that the algorithm wasn’t a genuine breakthrough.
In a field as complex and rapidly evolving as quantum computing, it’s easy for misinformation and hype to spread. The JVG episode serves as a cautionary tale, emphasizing the need for critical thinking, careful evaluation of evidence, and a healthy dose of skepticism.
What comes next is a return to the methodical work of implementing and refining PQC standards. The focus should be on practical deployment, ongoing research into the security of PQC algorithms, and continued monitoring of advancements in quantum computing technology. The threat is real, but it’s a threat that can be addressed through careful planning, diligent research, and a commitment to robust cryptographic security.