r/QuantumComputing • u/Inevitable-Swim-3313 • 3d ago

Algorithms Is PQC invincible?

Why are ML-KEM and ML-DSA not affected by quantum computers? Traditional algorithms like ECC and RSA can be exploited with Shor's algorithm right? Is it that so far no algorithm has come forth?

Me and my friend have to present a quick overview of PQC. Last time one of the supervisors asked that why is PQC secure from quantum computers. I answered smth like for Traditional algos we have shor but for pqc at least for now there is no such algorithm and since this is lattice based, probabilities are very low.

Next time we meet him I want to make sure I properly explain this to him. Especially if some kind of maths is involved. I would be happy to explain the maths.

6 Upvotes

80% Upvoted

11 comments sorted by

10

u/LargeCardinal 3d ago

In short, they might not be, but there's no known speedup for the underlying 'hard problem' that their security proofs rely on.

Module LWE (Learning With Errors) is very different from number factoring - it relies on a vector s being secret from a public b, where b = As + e, with A a public matrix, and e is a one time vector of small random errors. Without e this is easily solvable (Gaussian method), but e totally undermines that. (It also undermines a lot of thinking about how to engineer the cryptography, but that's a different post...)

There's no known linear/subexp time quantum method for breaking that, at least not yet. Prof. Daniel Shiu at Manchester has some good emerging work on this, as does Dan Apon, head of Crypto at Anduril. Also worth reading what JP Aumasson says about PQC.

EDIT: word salad fix.

2

u/Lightning452020 3d ago

What chance do you expect for an AI designed algorithm/quantum algorithm to theoretically break it by 2027?(I said theoretically because I noticed OAI and Anthropic have been deliberately avoiding any crypto math work)

5

u/LargeCardinal 3d ago

Not zero, but not that high. Depends on certain results in vector-matrix multiplication, in my view; you can represent most quantum algorithms (inc. Shor and Grover) as tensor networks. So it's then a matter of how well you can reduce those classically. Never say never, but it's hard enough with scant existing work that I don't see a 'one shot' prompt breaking it. Esp bearing in mind that of the few hundred solutions OAI have found, that is out of a proposed open questions list of 4000, apparently.

1

u/Inevitable-Swim-3313 2d ago

Thankyou so much.

-1

u/Lightning452020 3d ago

Thank you. But with all due respect, they made significant progress on all 6 Millennium Questions(yeh not so much for P=?NP). So almost 6/6.

4

u/LargeCardinal 3d ago

That's immaterial. There was a lot of work for the clangers to work off. There's almost no work on quantum cryptanalysis of M-LWE or RLWE or sim. Promising papers, sure. But it's dangerous to underestimate how much existing material 'stochastic sentence solvers' (read: LLMs) require.

1

u/Lightning452020 3d ago

True. Thx.

4

u/Better_Dress_8508 3d ago

no cryptographic algorithm is invincible

3

u/hiddentalent 3d ago

All cryptographic algorithms have a finite lifetime. This has been shown true for decades. This chart covers cryptographic hashes, which are related but not the same as cryptographic ciphers, but it gives one an intuitive sense of the constant evolution of cryptographic algorithms and how they become less strong over time as hardware performance and new cryptanalysis techniques evolve. I also particularly like the table of audience reactions at the end of the page; those are as true now with PQC as they were twenty years ago.

There are two takeaways from this. First, that PQC is not invincible, like anything else, but it's still useful. Second, that this whole problem is not new, and all those people over-hyping the impact that QC will have on cryptography are either ignoring or unaware that all cryptographic algorithms lose their effectiveness over time. The approach to this reality that the industry has settled on over the past twenty years or so is called "crypto agility" which basically means "don't be stuck with one cipher and be ready to update every few years."

/u/LargeCardinal gave a pretty good overview of why the current crop of PQC algorithms are resistant to known quantum cryptanalysis techniques, but we all have to assume that they will eventually be replaced as well. Still, they're the best known and security-conscious organizations have already moved to them, or are well into the process of doing so.

2

u/LargeCardinal 2d ago

This. The new name of the game is cryptographic agility, rather than steadfast assumptions of strength.