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

[[e-mail]]

I support publication of this document, and am replying to this particular message to clear up significant misconceptions I’ve seen (both here and elsewhere).

Unfortunately, it appears that there are very few people on this mailing list familiar with lattice-based cryptography (there are more who are familiar with ML-KEM, but if the deluge of recent emails is anything to go by, there are not nearly enough who fall into that camp either…). I myself am a lattice-based cryptographer, though one who works on Fully Homomorphic Encryption mainly. So more on the theoretical side (and with hardness assumptions even less solid than those of ML-KEM).

So let’s first talk a brief history of the field

1. The initial (post-hoc defined this way) lattice-based scheme was due to Merkle and Hellman, namely their “knapsack” cryptosystem in 78. This was broken by Shamir in 84. I call this a post-hoc lattice-based scheme as it heavily inspired later work in the field (Micciancio’s early 2000s papers often mentioned knapsacks built from cyclic lattices etc).

2. in the 90s, further (post-hoc defined this way) lattice-based schemes were defined. Of them, only NTRUcrypt is still plausibly fine. Lattice-based systems had significant issues, in particular there were no secure lattice-based signatures.

3. In 2005, Regev introduced LWE, and defined a simple (e.g. IND-CPA) encryption scheme based on it. It has had no real issues for >= 20 years.

4. Algebraic structure in lattices dates back to NTRU in the ~90s. Outside of NTRU, it first appeared in ~2001 in what we would now call the R-SIS problem, due to Micciancio. This was broken (due to using cyclic lattices)

5. Algebraically structured lattices using quotients by power of two cyclotomic polynomials (“negacyclic lattices”) have been used since ~2009 I think. RLWE and RSIS have had no significant issues since then. The only “real” issues are
5a. the attacks on the sPIP problem over these lattices. This is a different problem. We would not want to use schemes that use this problem.
5b. There are better quantum attacks, not against RLWE, but against other “rank one” lattice problems. See the line of work starting with Biasse and Song, 2016. out of an abundance of caution (and for parameter flexibility reasons) this encouraged people to use rank > 1 lattices. Those better quantum attacks have not been generalized to impact any “standard” lattice problems (RLWE or MLWE over power of two cyclotomics) in the ~10 years since that paper came out.

This is to say that all of the “exciting breaks” of lattice-based cryptosystems people fear with a new form of cryptography HAVE happened. Most happened in the previous millennium though. SOTA attacks against LWE (and its algebraically structured variants) have been “stable” in the sense that they take 2^{cn} time for a constant c (and have exponential memory costs as well iirc) for close to 2 decades. Over time the constant c has mildly decreased, but it has now been stable for nearly a decade.

None of the above is controversial at all. Any lattice-based cryptographer could tell you the same story. They mostly don’t bother because dealing with Bernstein’s attempts to obfuscate the above (very clear) story is exhausting. We can already see this in this mailing list, where many people have responded to Bernstein’s call to interrupt this process despite knowing very little about the field.

Concerns about implementation quality are valid. Even here, lattice-based schemes are much easier to implement than RSA/ECC schemes. It’s mostly arithmetic of word-sized modular integers. This doesn’t mean everything is trivial, but it does make the huge amounts of concern claimed by non-experts quite puzzling. I’ve seen some people point towards the “glue code” to create the hybrid as being plausibly its own source of implementation issues. Any code has possible implementation issues. Perhaps that means no new cryptographic code should be written, and we should dissolve this working group. Or, maybe we deal with that as best as we can.

Best,

Mark


> On Jul 1, 2026, at 5:32 AM, Stephan Neuhaus <[e-mail]> wrote:
> 
> I do not support the publication of this document.
> 
> I remember well that security standards get broken: when they have been well-reviewed, but especially when they're new. Bugs show up in the math, but also in implementations. Lattice cryptography seems to me to be a very active field of research, when quite fundamental results (and bugs!) are still being discovered, both in the math and in the implementations. From a risk-management perspective alone, I believe that it's too risky to standardise, even as "informational", a mode of encryption that relies only on these new methods.
> 
> Cheers
> 
> Stephan
> 
> PS: Full disclosure: I have just joined the TLS mailing list, mainly to say just this. I also have no standing in the cryptographic community, except that I have published a paper last year together with Peter Gutmann of this parish, about how all of the published quantum factorisation records are bogus [1]. What kind of standing this gives me, if any, is anybody's guess.
> 
> [1] https://eprint.iacr.org/2025/1237
> 
> _______________________________________________
> TLS mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]