Please revert to original title: Factoring integers with sublinear resources on a superconducting quantum processor
From the paper:
> We proceed by estimating the quantum resources required to factor RSA-2048. We find that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 even in the simplest 1D-chain system. Such a scale of quantum resources is most likely to be achieved on NISQ devices in the near future.
They aren't "claiming to break 2048-bit encryption". They are claiming to have an algorithm that could break 2048 bit encryption given (currently unobtainable) quantum computers.
"Researchers using novel techniques break 48-bit encryption and assert that the same techniques could be used on not-available hardware to break 2048-bit encryption" just doesn't hit the same.
EDIT: Not-yet-extant changed to not-available as IBM Osprey has >372 qbits.
This paper is claiming to make quantum factoring thousands of times cheaper than previously estimated (maybe even hundreds of thousands of times, depending on if error correction is needed). I think it's wrong, but if it was correct it would have major implications for how fast quantum-safe cryptosystems had to be rolled out. Like, "a machine capable of running this could conceivably exist next year, instead of next decade" level of change in expectation. It would hit pretty damn hard.
I didn't intend to downplay the impact of such a development, only to highlight my skepticism regarding their claims (and the title provided in the post).
Bruce Schneier sums it up better than I could:
"One of the issues with the algorithm is that it relies on a recent factoring paper by Claus Schnorr. It’s a controversial paper; and despite the “this destroys the RSA cryptosystem” claim in the abstract, it does nothing of the sort. Schnorr’s algorithm works well with smaller moduli—around the same order as ones the Chinese group has tested—but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that’s what’s behind Grimes’s comment) but don’t give any details—and they haven’t tested it with larger moduli."
Scott Aaronson says "All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many."
5 comments
[ 3.2 ms ] story [ 24.3 ms ] threadIn fact, I'm pretty sure that Scott Aaronson's response has already been discussed here? https://scottaaronson.blog/?p=6957 (Yup: 1 month ago, around the time the referenced paper came out: https://news.ycombinator.com/item?id=34260124)
From the paper:
> We proceed by estimating the quantum resources required to factor RSA-2048. We find that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 even in the simplest 1D-chain system. Such a scale of quantum resources is most likely to be achieved on NISQ devices in the near future.
They aren't "claiming to break 2048-bit encryption". They are claiming to have an algorithm that could break 2048 bit encryption given (currently unobtainable) quantum computers.
EDIT: Not-yet-extant changed to not-available as IBM Osprey has >372 qbits.
Bruce Schneier sums it up better than I could:
"One of the issues with the algorithm is that it relies on a recent factoring paper by Claus Schnorr. It’s a controversial paper; and despite the “this destroys the RSA cryptosystem” claim in the abstract, it does nothing of the sort. Schnorr’s algorithm works well with smaller moduli—around the same order as ones the Chinese group has tested—but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that’s what’s behind Grimes’s comment) but don’t give any details—and they haven’t tested it with larger moduli."
Scott Aaronson says "All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many."
https://www.schneier.com/blog/archives/2023/01/breaking-rsa-...
https://scottaaronson.blog/?p=6957