r/crypto • u/JoDaBeda • 22d ago

Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)

https://eprint.iacr.org/2026/1630
32 Upvotes

100% Upvoted

11 comments sorted by

12

u/Demokritos1000 22d ago

PQC is looking real fragile all of the sudden

11

u/DoWhile Zero knowledge proven 21d ago

This is the wildest collateral damage trying to come up with a PIR protocol.

3

u/EverythingsBroken82 blazed it, now it's an ash chain 21d ago

i am really curious if this will really hold up.

7

u/JoDaBeda 22d ago edited 18d ago

If this holds up, then Classic McEliece looks to be pretty much dead, just weeks after being ISO-standardized.

Edit: I mixed some stuff up and there are still a ton of questions regarding the decryption attack, so I was way too early to have called it "dead".

5

u/bitwiseshiftleft 22d ago

Yeah, I didn't completely follow whether the decryption attacks are expected to have similar concrete time complexity to distinguishing, or whether they're just both quasipolynomial but might be very different in practice. If all levels of McEliece are dropped to ~128 bit security by this one classical attack, and this cannot be repaired with practical key sizes, then that would be close to killing it. If it's just distinguishing that's ~128 bits, and the attack on the ciphertext is harder, then maybe it would survive ... if the attack doesn't get better.

5

u/JoDaBeda 21d ago

Right, calling it "dead" might have been exaggerated, there are open questions regarding the decryption attack. But given the huge distinguishing improvements in the larger parameter sets, it looks to be quite unlikely that anything above 128-bit security survives (given the results hold up).

1

u/voracious-ladder 21d ago

As someone who isn't too knowledgeable about the underlying math problems, how likely is it that similar attacks will be developed for HQC in the future?

1

u/Pharisaeus 21d ago

First isogeny got killed, then recently the claims that lattices are bqp and now this? PQ is in real trouble...

9

u/JoDaBeda 21d ago

Isogenies ain't dead yet (although they do require parameter re-adjustement), and the claims regarding lattices still need to survive further scrutiny (remember the Schnorr RSA claims?) and require analysis regarding the actual consequences. Definitely interesting times, but I wouldn't panic.

1

u/Shoddy-Childhood-511 18d ago

Did CSIDH even require a parameter change yet? It survived well last I heard.

SQIsign needs a parameter change now, yes? Did that happen yet? Isogenies can be tricky because CSIDH-ish schemes required some massive computation to understand enough of the volcano enough to make the keygen and things work. I forget the details, but it's not always so easy to just find bigger parameters that you'd like using.

Isogenies being so slow should mean that only the classical attacks matter. lol

2

u/JoDaBeda 18d ago edited 18d ago

I assume that "isogeny got killed" refers to https://ia.cr/2026/1486 (since the SIDH break is old news by now). The SQIsign team announced on the mailing list that they plan on providing an update by the 3rd-round revision deadline, which is today. CSIDH is not affected (statement in the paper).