[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Jon Callas]

> On Feb 20, 2025, at 18:19, Bill Stewart <billstewart at pobox.com> wrote:
> 
> On 2/20/2025 12:19 PM, Jon Callas wrote:
>> I have a follow-up and addendum to my missive of last night.
>> I went over to Google and typed in "factor 2323" --
> DDG offered me "23x101" and a bunch of websites that said things like "1,23,101".
> Then there's the old "physicist, mathematician, engineer" joke with
> "2's prime, 3's prime, 5's prime, 7's prime, 9's prime, 11'ss prime..."
> 
> But more seriously, a few months ago there was something in the press about a Chinese group using D-Wave to crack some kind of crypto;
> did that turn out to be bogus?

D-Wave is a quantum annealing machine, so it doesn't run Shor's Algorithm. As I remember the paper, they also were doing "special form" integers, though I don't know what special form. As I remember, they can do factoring with the machine, but there's no especial advantage they have yet over classical computers.

There are plenty of ways that cryptanalysts could get our attention. Remember when Wang threw our understanding of hash functions into the bin by just noting two strings that hashed to the same value. Somewhat analogously to this, a number of years ago, someone in the forum for TI programmable calculators casually noted that two numbers multiplied together were some other number, and the product just happened to be the 512-bit RSA signing key for the calculator ROM. The cryptanalyst did it conventionally, yet actually factoring something is pretty indisputable. That's pretty much Peter's point. I distilled it down to easy mode, make it be interactive. If someone said, "I have a quantum computer, and here's a 2048-bit TLS retired certificate and isn't it interesting that it factors to P and Q," we'd all say, "why yes, that is indeed interesting, please tell me more. I'm all ears."

	Jon