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.
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.
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.