[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Jon Callas]

[Apologies to anyone who got multiple copies of this, my mail client was apparently glitching.]

> On Feb 24, 2025, at 15:07, Steven Bellovin <smb at cs.columbia.edu> wrote:
> 
> Let me add one other thing (and I've set Reply-To to point to the list, lest my inbox be flooded): a lot of the push for post-quantum algorithms comes from the NSA. At the risk of belaboring the obvious, Your Threat Model is Not Their Threat Model. They have secrets they want to protect for decades, against adversaries who can and will record and retain things. Let me give two examples.
> 
> The first is Project Venona, the NSA effort to decrypt traffic based on Soviet reuse of one-time pads. The bad pads were used 1942-1945, the cryptanalysis started in earnest in 1946, the project ended in 1980, and it wasn't formally declassified until 1995.
> 
> The second is the Friedman collection, released by the NSA in 2015. William Friedman retired from the NSA in 1955; even so, some 3% of the documents were withheld in their entirety, and many others had significant redactions. One I was particularly interested in dated to 1948—and 67 years later, some crucial details were blanked out. (I had assumed that what was redacted was the name of a U.S. cipher machine; Stephen Budiansky later identified it as a Soviet system that Friedman suspected could be cracked.)
> 
> Does anyone want to be that there won't be a powerful quantum computer 65 years hence? I sure don't.

That's an excellent point.

My personal estimate is that a quantum computer that can break RSA 4096 will arrive between 2050 and 2060. I think that the present push for PQC is not unreasonable. NIST wants the transition done by 2035, and if that slides a decade, then it's still in a fine place for 2050.

(A reason I pick that time period is because on the old <https://www.keylength.com/> estimating site -- it's still up, take a look -- is that estimates for when we should stop using RSA 3K to 4K based on extending the Moore's Law graph out indefinitely. Phrased another way, I believe quantum computers will arrive, yet their performance is going to be approximately what we'd have if silicon lithography could somehow make subatomic transistors.)

Moreover, we're going to see the PQ COMSEC stuff arriving long before that -- heck, it's already in trial deployment -- and that directly addresses the issue of collect-now-decrypt-later. That's more reason not to tap the brakes on PQC deployment.

At the same time, though, Peter is right! There are zero NUMS (Nothing Up My Sleeve) quantum breaks on keys of any size. Richard Carback's Quantum Doomsday Clock site is also fine tool for trying to make sense. I have my own very ugly spreadsheet where I can plug in things to make a SWAG at when a relevant quantum computer might arrive, and the available information makes for a capital W and a small S -- low on the "scientific" and big on "wild-ass" in the guessing. We need real data to be able to make good guesses.

This week's NewScientist has as its cover Special Report, "Our Quantum Future: Quantum Computers are finally here. What next?" Kudos to that "finally." Their opening essay is "When to believe the hype" and has a comparison of AI and QC developments and says:

   "Practitioners in both [the AI and quantum computing] fields are certainly 
   guilty of hyping up their wares, but part of the problem for would-be quantum 
   proponents is that the current generation of quantum computers is essentially 
   useless."

There you have it. That's basically what we're saying here -- that the current generation of quantum computers is essentially useless. And we cryptographers know that the difference between science and snake oil is hype. They conclude that essay with the sentence:

   "So, by all means, aim to revolutionise the world — but please, do show your working."

And this also reflects the discussion in this thread. Time and time again, a quantum cryptanalysis paper comes out and we find that they had something up their sleeve.

There are some great articles that issue, like one called "The megaquop machine" about getting to where a quantum computer can do a million quantum operations and it interviews John Preskill of Caltech who says:

   "Those [megaquop calculations for simulating physical systems] will be the 
   most important applications with practical implications for chemistry and 
   material science." 

Real quantum cryptanalysis is, as I understand it (correct me if I'm confused), a teraquop-ish problem (depending on many things for implementing Shor). Assuming there's some sort of exponential growth, akin to Moore's Law, it's not a million times harder to get a teraquop, but we're not going to get a teraquop machine without building a megaquop machine.

So let me give a prediction for 2030ish. Three things will be in place:

(1) We have a megaquop machine that's doing some physical simulations that are useful to industry that needs those.
(2) The PQC migration is mostly done. Most TLS is actively PQC, some other systems like OpenPGP, S/MIME, and full disk encryption are delivered, but we're still not quite there in embedded systems like ATMS and point-of-sale. We understand how we're going to get practical PQC equivalents of unlinkable BBS signatures, zk-proofs, threshold, group and so on. Some is delivered, more is understood, and there are annoying gaps in some of it.
(3) The mainstream discussions of quantum information science are no longer talking about breaking cryptography except as an aside because of the above. We did it. We obviated the need.

	Jon