A recent research paper from China claims to have used just 372 qubits to break RSA-2048, the popular cryptographic schema many companies and the planet rely upon for digital security. Of course, such announcements have created a flurry of interest as scientists scramble to understand and digest the implications of the work and whether or not it is a reliable result. This is of concern since IBM has already released a Quantum Computer sporting 433 qubits, and the number of qubits available is increasing, and soon over 1,000 can be expected.
The paper claims … well, it’s hard to pin down what it claims, but it’s certainly given many people the impression that there’s been a decisive advance on how to factor huge integers, and thereby break the RSA cryptosystem, using a near-term quantum computer. Not by using Shor’s Algorithm, mind you, but by using the deceptively similarly named Schnorr’s Algorithm. The latter is a classical algorithm based on lattices, which the authors then “enhance” using the heuristic quantum optimization method called QAOA.
Scott Aaronson on “Factoring integers with sublinear resources on a superconducting quantum processor”
Breaking RSA encryption or NOT?
The paper: “Factoring integers with sublinear resources on a superconducting quantum processor” suggests that applying a factoring algorithm, in conjunction with a quantum approximate optimization algorithm (QAOA), can break asymmetric RSA-2048 encryption using a non-fault tolerant quantum computer. Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, hackers need millions of physical qubits, far beyond current technical capabilities, although we are close to 1,000th of that at 1,000 qubits. In the work, they report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). Whether this result can be tested on given hardware is not known at this time, but it could only be a small matter of time before researchers attempt to implement the result.
All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many. Having said that, this actually isn’t the first time I’ve encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor’s algorithm, should somehow “rub off” onto quantum optimization heuristics that embody none of the actual insights of Shor’s algorithm, as if by sympathetic magic. Since this idea needs a name, I’d hereby like to propose Cargo Cult Quantum Factoring.
Scott Aaronson on “Factoring integers with sublinear resources on a superconducting quantum processor”
Security and Quantum Experts Weigh in
The work builds upon an earlier paper that relies on a factoring algorithm by Claus Schnorr (not a typo of the famous Peter Schor of Shor’s algorithm fame). The new work claims that previous limitations of work with smaller moduli can be overcome (meaning it can break larger numbers). Bruce Schneider a well-known security expert, thinks that if the paper from the 24 Chinese scientists can overcome previous limitations of restrictions to smaller moduli, it might work. But they haven’t tested it with larger moduli, and if dependent on the Schnorr technique, which doesn’t scale, then the algorithm is expected to fail.
Scott Aaronson, a well now complexity theorist, author and blogger, says he’s seen this all before with these claims over the last 25 years. In a nutshell, Aaronson is dismissive of the claim, which should be reassuring for many since Scott Aaronson is one of the foremost thinkers on complexity theory which deals with whether quantum algorithms can run faster than classical equivalents.
Companies with secure technology
Despite the flurry of activity and some concern from the likes of Bruce Schneider, there appears to be a growing movement that the paper is not, in fact, to be taken all that seriously. That shouldn’t prevent each security paper like this from being taken seriously since, potentially, the majority of the world’s security protocols could be at risk. Companies like Qrypt and also keen to make it known that their protocols can be more secure against quantum attacks. For those who want to learn more about Shor’s algorithm, we have provided a link here.
Traditionally, users are at the mercy of the encryption algorithm they use point to point; when this falls, they lose the encryption keys and all their data security. Qrypt’s technique is complementary and achieves much stronger privacy, making cracking communications harder, both technically and practically. This makes Qrypt the only available technology that could protect against advancements like those described in the paper – when it turns out to be the real thing.
Chris Schnabel, VP PRODUCT QRYPT
