[TLS] Re: WG Last Call: draft-ietf-tls-mlkem-08 (Ends 2026-07-08)

[Yaakov Stein <[e-mail]>]

> That said, I do not believe the risk of ML-KEM (and ML-DSA) to be severe:
> there is no known cryptanalysis currently exploiting rank >=2 module structure at these parameters that performs better than generic lattice reduction.
> Module-LWE also has a (granted, an asymptotic) worst-case-to-average-case reduction - something neither RSA nor ECDLP had.

At last, a reasoned argument for believing Kyber is strong.  In fact two arguments.
However ...

1. First argument (in my own words): “Module‑LWE has more structure than LWE but less than Ring‑LWE,
     and no attack exploiting this residual structure has been demonstrated that is any better than using LLL on SVP ignoring structure."

That is a good argument, but the crux is "no attack has been demosntrated" is not the same as "no attack will be found"
and certainly not the same as "no attack exists".
Modular LWE (k>1) is a compromise between efficient but insecure Ring based (k=1) LWE, and complex but more secure LWE over the integers.
We can't yet be sure that this compromise is as secure as it seems.

2. Second argument (n my words): "Even if I can break an average case RSA or ECDLP (e.g., using a CRQC)
    there might be worst cases that I can't break (e.g., Shor keeps trying over and over).
    But for LWE, solving an average case reduces to solving any general (including worst case) SVP problem."

This is a more interesting argument. However ...
Who cares if there are very special worst cases for RSA/ECDLP unless we have ways of finding them and using only them?

and

I assume your argument for LWE goes like this:
        breaking ML-KEM   implies   solving general module LWE   implies   solving worst‑case SIVP problems
I don't really buy the first part, because it is bad even if I can only break 90% of the ML-KEM instances, but I'll let that go.

The second part seems to follow from constructing a noisy representation of a SIVP problem, solving it, and then returning to the original problem.
But there are some assumptions here, including the asymptotic one you mention, the vector to modular transformation,
but also (once again) who said I need to solve worst cases? If I can break average modular LWE that is still a major threat.
And, of course, we shouldn’t neglect an undiscovered structural weakness in the particular ML-KEM methods
(several problems were uncovered during the NIST rounds and fixed, but can we be sure all attack avenues were found?).

Maybe all of this is stupid and it will all turn out perfectly secure.
I truly hope that this is the case.

All I am saying is that if there is a cheap second lock that protects us until we can be sure,
then why not use it?????

Y(J)S


This message is intended only for the designated recipient(s). It may contain confidential or proprietary information. If you are not the designated recipient, you may not review, copy or distribute this message. If you have mistakenly received this message, please notify the sender by a reply e-mail and delete this message. Thank you.