This is not my area, but I wanted to mention this before speculation got out of control: some quick feedback from colleagues is that the analysis in this paper seems to assume Schnorr's claims from 2021 [0] without detailed supporting evidence that these claims are true for large parameters like the ones needed to factor RSA-2048. But these claims are viewed skeptically, and this paper doesn't provide much evidence to change that.<p>[0] <a href="https://eprint.iacr.org/2021/933" rel="nofollow">https://eprint.iacr.org/2021/933</a>
I want to contrast this paper with Shor's factoring paper [1].<p>One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2].<p>The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by <i>hoping</i> potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA".<p>How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them.<p>Is there somewhere where I can bet money that this doesn't amount to anything?<p>1: <a href="https://arxiv.org/abs/quant-ph/9508027" rel="nofollow">https://arxiv.org/abs/quant-ph/9508027</a><p>2: <a href="https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493" rel="nofollow">https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2...</a><p>3: <a href="https://arxiv.org/abs/2212.12372" rel="nofollow">https://arxiv.org/abs/2212.12372</a>
You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0]<p>If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA.<p>IBM expects to get there by 2025. [1]<p>[0] <a href="https://en.wikipedia.org/wiki/Five-qubit_error_correcting_code" rel="nofollow">https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co...</a><p>[1] <a href="https://www.ibm.com/quantum/roadmap" rel="nofollow">https://www.ibm.com/quantum/roadmap</a>
A note to cast further suspicion on the immediate risk severity:<p>The researchers indicate use of a computer built with superconducting qubits in the abstract, to that, superconducting qubits present barriers such as<p>- limited coherence time due to common atmospheric muon events, and resulting phonons<p>- limited topological connectivity, further increasing needed coherence time.
I'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...
Huge, if true. However, many such claims have surfaced before and turned out to be dudds.<p>For now, I am taking it with a spoon of salt but with an interest of any follow-ups and peer review.
> Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics.<p>Yeah, that alone is impressive. Schneier led a group that wrote Twofish, which was one of the AES finalists before losing Rijndael.
Here's an implementation of Schnorr's algorithm with an attempt to estimate the amount of work needed to factorize big numbers: <a href="https://github.com/lducas/SchnorrGate">https://github.com/lducas/SchnorrGate</a><p>It also contains some links to critique of the Schnorr's algorithm paper. It looks like either much more p_n-smooth integer pairs are needed or the size of the p_n-smooth integers should be much bigger than estimated by original Schnorr's paper. Or both estimations are off.<p>As the paper discussed Schneier relies on the assumptions of the (classic) Schnorr's algorithm, it may also be off in the calculations as well.
> A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA.<p>If a quantum computer can break 2048-bit RSA, what about elliptic curves?
Who was the guy and what was the flawed and retracted paper mentioned in the below quote from Schneier's article?<p>>In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.
I remember that some small countries, running DPI in their up-link were just storing their whole encrypted traffic to - when this day comes - be able to decrypt the traffic and see who was conspiring against the government back in the days and then start the witch hunt. Maybe this day is coming. Maybe its already there for some degree.
I just watch this yesterday about post quantum cryptography.<p><a href="https://youtu.be/_C5dkUiiQnw" rel="nofollow">https://youtu.be/_C5dkUiiQnw</a>
"And there’s the nagging question of why the Chinese government didn’t classify this research"<p>Would like to hear informed thoughts on any state's pros and cons of sharing such obviously weaponizable discoveries.
Even if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
HN discussion for the paper itself: <a href="https://news.ycombinator.com/item?id=34235964" rel="nofollow">https://news.ycombinator.com/item?id=34235964</a>