> 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.
_______________________________________________
TLS mailing list -- [email protected]
To unsubscribe send an email to [email protected]
