A new paper by Daniel Simon might indicate lattice based crypto (ML-KEM etc) breaks with quantum computers

The paper in question:

The author also developed Simon’s algorithm that inspired the Shor’s algorithm. The paper hasn’t been peer-reviewed yet.

There’s some analysis by Marin Ivenzic Simon Claims Polynomial-Time DCP Quantum Algorithm

Also a Reddit thread.

2 Likes

On the bright side, this is sure to result in a top tier blog post from djb.

1 Like

You have an error there, translation maybe?

I mean, it does not change the fact that a system is indeed secure by definition, if nothing exists yet, or is not reasonably hypothetical to be assumed to exist at some point, so these claims are valid.

At least that is how I see it.

Anyway, if I understand it correctly, this seems pretty theoretical for now.

1 Like

I did make the relevant word non-italic, as you would in italic text. :wink:

I meant the system exists, but it is secure if no threat to it exists or is reasonably expected.

But yeah, that might be subjective, which I indicated by saying that is at least how I see it.

1 Like

Sorry if I am being blunt, but is every system insecure in your opinion, even if there is no possibility to crack it until that point?

I feel that is what you imply here.

I’d argue that the claim of security is valid if no flaws are found or are even hypothesized.

Yes you’ve successfully defined the basis of all modern cryptography: Computational hardness assumption - Wikipedia

Single assumption bet is the best you can get. Ideally protocols, modes of operations etc are proven to be secure if the underlying structures are secure, and thus, ideally, security of system will reduce to the computational hardness assumptions of the underlying primitives.

Some assumptions will turn out to be wrong and quantum computers can solve some problems efficiently so it’s natural some harness assumptions will not hold, especially because the field is young and there’s not too many humans working on something this advanced.

Nobody’s saying “trust us” here. What wins as the standard is what nobody knows how to break. Trust increases with time but single big break can change the course of what’s trustworthy, overnight. If Simon’s new method works, it represents biggest advancement in cryptanalysis since 1994.

McEliece has resisted cryptanalysis the longest, but even that doesn’t have a proof of security. There is no provably secure cryptography outside information theoretical security, and that world doesn’t have public key cryptography outside quantum key distribution, which is practical impossibility, and still requires pre-shared key for basis orientation authentication.

1 Like

I see your argument, but I would question how it would qualify as vulnerable if a tool or concept to attack it does not exist.

I’m not saying the concerns raised in this paper are invalid, I question the assumption of declaring something insecure if there were not even hypothetical means proving it otherwise. Again, in general, I mean.

Is it wrong to compare that to software vulnerabilities and Zero-days? Currently it is considered “secure”, but what if an attacker breaks that and doesn’t announce that to the world?

It’s debatable, I get it. Some might consider this a secure solution. I am still not convinced. What I mean is that the proof might not be discovered yet. And the question is if it’s mathematically possible to do that (or is there a proof that it’s undeniably impossible).
I’m not a mathematician, so I wouldn’t know. Though it would be nice if it could be explained to a total bufoon of an idiot (me).

The commonality is that attacker might know of a weakness that the defender doesn’t. So no it’s not wrong, but I’d be careful about drawing too many analogies between the two. Cryptography generally isn’t full of implementation bugs at library level, even if there’s an occasional weakness.

The notion that any standard is weak is an invitation to attempt security through obscurity, by using something that might evade attacker’s attention. But it’s also evading most of public cryptanalysis meaning if it’s easily broken, you’ll probably never know. That’s why the standard is a better bet. It gets the attention, like we’ve just seen here.

1 Like

(General request) Can we keep this thread on topic please?

1 Like

You made a good point. However, I’ll stick with the unknown, and you know exactly what I’m talking about. That topic in Marin Ivenzic’s article has revealed some very important information, and if you talk about it openly within the industry involved, they’ll delete your posts.

You understand these issues, and it’s worth reading up on them.

It’s great to find people like you.

I really, really don’t.

The industry experts are who wrote the paper, who will peer review the paper over the coming weeks, and who have already brought out the paper on social media. But no they probably won’t have time for non cryptographers’ takes so it you try to interfere they might delete what they consider spam. You want to participate, you’ll have to prove you belong first with peer reviewed research, connections and having something that contributes to the discussion rather than trowing vague accusations about industry-wide collusion.

I struggle to even make sense of what these experts are saying here. Domain expertise is ridiculously narrow thing. Whatever you’re implying makes no sense to me.

1 Like