Are adiabatic quantum computers (like D-Wave) a threat?

[ch862]

Hello everyone

In the last two weeks, there were rumors on the internet that Chinese researcher have broken RSA and AES (see e.g. here https://www.tomshardware.com/tech-industry/quantum-computing/chinese-scientists-use-quantum-computers-to-crack-military-grade-encryption-quantum-attack-poses-a-real-and-substantial-threat-to-rsa-and-aes).

As described on Natto Thoughts (https://nattothoughts.substack.com/p/chinas-quantum-tunneling-breakthrough) there are two relevant papers one for RSA and one for SPN ciphers.

# RSA (paper: Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage (http://cjc.ict.ac.cn/online/onlinepaper/wc-202458160402.pdf))

In my view, the claims in the news are obviously highly exaggerated. The original paper , seems to report on the successful factorization of a 50 bit number with D-Waves QPU advantage (https://www.dwavesys.com/solutions-and-products/systems/), what is far from breaking real world RSA.

 As the paper is only available in Chinese, I have not been able to understand it entirely and I have the following questions:

• What is the complexity of the attack?
• Does the approach presented scale?

In addition I would like to ask, whether NIST is taking the danger of factoring using adiabatic quantum computers into account in their considerations and why, respectively why not.

I am fully aware that the transition to the proposed PQG algorithms completely mitigates this attack. Nevertheless I would like to understand it in more details.

# SPN (paper: Research on Quantum Computing for Practical SPN Structure Symmetric Ciphers Attacks Using the D-Wave Advantage (no link))

Here it becomes more mysterious. It seems like the research have successfully (?) attacked some SPN ciphers, but not AES. I have not been able to find the original paper.

• Does someone has seen the original paper?
• What are exactly the claimed results?
• If the summary on Natto Thoughts is correct, will there be a need for new symmetric ciphers?
• What are NIST's views on this issue?
  

Any hints, remarks, and pointers to relevant literature are welcome.

Thanks a lot and best regards.

Chi Hanh

[gard...@gmail.com]

For my part, I continue to monitor progress in factoring larger numbers on the D-Wave hardware.  Just as I also watch the progress of QAOA and other techniques.  No one is going to defeat commonly used RSA keys in the next few years using these approaches, but they may become viable in the future.  My understanding is that these techniques are more viable than Shor's algorithm in noisy quantum systems.  

I haven't looked at the SPN/AES aspect.  My only comment is that I would like to see another general purpose symmetric cipher certified so we can have some diversity.  Perhaps Ascon will be allowed for uses beyond light-weight crypto?

[Sam Jaques]

Scott Aaronson sums up this line of research nicely here: https://scottaaronson.blog/?p=6957. Mosca and Verschoor also published about this question here: https://www.nature.com/articles/s41598-022-11687-7.

In short: the quantum annealers work by first translating factoring (a highly structured problem) into some sort of satisfiability problem (a highly unstructured problem) and then apply a generic SAT-solving quantum device to the factoring instance.

Will this work? If so, one of two things happens:
1) It works for factoring, but not much else. This seems highly implausible: you've thrown away all of the structure! As Aaronson says: "the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor’s algorithm, should somehow “rub off” onto quantum optimization heuristics that embody none of the actual insights of Shor’s algorithm, as if by sympathetic magic. Since this idea needs a name, I’d hereby like to propose Cargo Cult Quantum Factoring".

2) It works for factoring and also every other class of problems that fit into a SAT solver, i.e., all NP problems. That would be a huge result, but do we really think that's true? I don't. There's no good theory saying it should be true. Sure, they throw around ideas like "quantum tunnelling" to justify why a quantum annealer might be better than classical, and these are probably true in some sense, but probably not true in the sense that quantum annealers are going to solve generic NP problems in polynomial time.

Even more broadly, there's lots of techniques one might use to solve cryptographically relevant problems which cannot be proven to work, but cannot be proven to fail: quantum annealing, machine learning, slime moulds (https://pmc.ncbi.nlm.nih.gov/articles/PMC9838547/). Even accounting for cryptographic paranoia, I think the burden of proof is on the person proposing an esoteric computational model: if I factor a few numbers with a slime mould, shouldn't I also give some sort of evidence that my moulds are scaling well enough to factor cryptographically relevant numbers, before we get concerned? Why should a quantum annealer be different? If we give credence to every vaguely plausible problem-solving algorithm, there we can't rely on cryptography at all, because, as in point (1), there's no reason to believe it should stop at factoring! All the post-quantum schemes and all symmetric crypto would be similarly vulnerable. In fact, this RSA paper also uses Schnorr's lattice-based factoring technique (just like the paper Aaronson criticizes). So in fact they've already reduced factoring to the closest vector problem and then solved that. If this really worked, lattice crypto is gone too!

(similarly, I see no reason to believe that the version I can't access, tackling SPN-based ciphers, would not also extend to any block cipher).

Maybe you think this paper does provide some evidence that the technique scales effectively because they're factored 50 bit numbers. As with all quantum factoring papers, you need to look very carefully for how much of the problem they've compiled away: since we can easily factor numbers of this size classically, it's too easy to make a classical computer do a lot of the hard pre-processing and post-processing and give the quantum computer a trivial intermediate task (see the classic "Pretending to factor very large numbers on a quantum computer" https://arxiv.org/abs/1301.7007). In this case (with the caveat that I can't read Mandarin), the table at the end seems to give away the magic: electronically translating the column headers, one of them says "logical qubits", and the 50-bit number was "factored" by 10 "logical qubits". Checking earlier tables seems to corroborate this: they compiled the problem down to solving CVP in a 10-dimensional lattice, and then they solved that. Wow.

(I also have no idea what they mean by "logical qubits" since D-wave is not a general purpose quantum computer so they're not doing any standard quantum error correction; another column translates to "physical qubits" and only states 16. Probably the text I can't read explains it, but I stand by my conclusion that they only tackled a 10-dimensional lattice).

Given that D-wave advertises thousands of qubits on that machine, I have to wonder why this team wouldn't factor a slightly bigger number, which should easily fit on the available hardware? My guess: it doesn't work.

[gard...@gmail.com]

Hi Sam,

there is a more recent post on  Scott Aaronson's blog here: https://scottaaronson.blog/?p=8375

While he doesn't believe there is any speedup to QAOA, the idea of quantum computers being beneficial for optimization tasks is "back in business" due to a newer DQI algorithm

[Xavier Bonnetain]

Hi all,

Thanks Sam for your message, I agree with your comments.

I wanted to add a few comments on the symmetric part. While I do not have access to the paper, I can tell that "being an SPN" doesn't give much info on the security of a cipher, and there is no clear structured problem that one may conceivably solve to break a family of ciphers at once, contrary to, say, structured lattices, or using a specific family of codes.

Now, from the elements I have, the claim seems to be some attacks against *reduced-round* PRESENT, GIFT-64 and RECTANGLE that build upon integral distinguishers. Assuming this claim holds:

 - This does not demonstrate a quantum advantage, as the attack is already known, applicable classically, and not applicable to the full version of the ciphers

 - This provides exactly 0 insight on AES

Since the standardization of AES, new ciphers seek to be faster than AES, to tackle a specific use case, or to provide a better/more modern API. Not to be more secure, because despite being probably the most studied block cipher for decades, AES is still fine, and this new paper does not appear to change that.

Regards,

Xavier

---

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/95c5da71-e454-4221-890e-59681693a4fbn%40list.nist.gov.

[Andre Le]

Xavier, All,

In the same vein, has anyone seen this recent paper (https://arxiv.org/pdf/2409.07501) ?

They claim to be able to model a full round AES-128 with "just" over 21k variables.

Different from the above paper since they do not look for integral distinguishers but they also target the use of quantum annealers to attack AES.

Andre

[Oscar Smith]

This is essentially useless since quantum computer don't have significant advantages over classical ones for generalized optimization problems.

[Daniel Apon]

If this were a true old-school Internet message forum, like from the '90s or early 2000's, I'd be able to upvote Oscar Smith's comment.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/412d72c0-c82a-4821-b057-9bb30e893806n%40list.nist.gov.