[TLS] Re: WG Adoption Call for Post-Quantum Hybrid ECDHE-MLKEM KeyAgreement for TLSv1.3

["D. J. Bernstein" <[e-mail]>]

Alicja Kario writes:
> NIST has selected HQC for standardisation this week... No idea about
> its patent situation

Interesting question.

My tracking page lists HQC as being claimed by GAM. People have mostly
heard about GAM as a lattice patent, but the patent is actually broader
and originates in code-based cryptography. As confirmation,

    https://web.archive.org/web/20250314182134/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/final-ip-statements/HQC-Statements-Round4.pdf

claims applicability of U.S. patent 9094189 and French patent 10/51190.

However, that document also has a FRAND-RF commitment triggered by NIST
standardization. Of course FRAND-RF can have poison pills, but

    https://web.archive.org/web/20221130033932/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/selected-algos-2022/nist-pqc-license-summary-and-excerpts.pdf

doesn't report any poison pills, and at a cursory glance it seems to
exempt not just Kyber but also HQC from the GAM patent.

Maybe I'm missing something---NIST's latest report mentions just the
future-FRAND-RF commitment without mentioning the existing license---but
maybe the NIST patent negotiators back in 2022 did something right.

On the other hand, this patent minefield is bigger than the GAM patent.
The same license has different terms regarding patent 9246675, clearly
allowing _only_ unmodified ML-KEM. As far as I can tell, even another
version of Kyber (the 2017 version, the 2019 version, the 2020 version,
or a future patched version) wouldn't be within this 9246675 license;
merely being similar, like HQC, is definitely not enough to trigger the
license.

The question, then, is whether HQC is covered by 9246675. As always, the
doctrine of equivalents says that patents cover not just what's
literally claimed but also anything that's doing "substantially" the
same thing, so a patent lawyer will pull out endless literature on
similarities between HQC and the patent. NIST's report even feeds into
this by saying that HQC is "similar in structure" to LPR, ML-KEM, etc.

An HQC user targeted by 9246675 wins if the court doesn't accept the
doctrine-of-equivalents argument. Otherwise I think there's some chance
of success of an ensnarement defense. The way this works is that the
court challenges the patent holder to retroactively expand the patent
claims, and then the court will ask whether the expanded "hypothetical"
claims (1) would also have been patentable and (2) literally cover HQC.
It's not immediately obvious to me that the patent holder will be able
to get past this. On the other hand, the patent holder has carte blanche
to engage in retroactive creative writing, so thinking through all the
possibilities in advance is labor-intensive.

This analysis then has to be repeated for other patents in the same
minefield, such as the Zhao patent that claims Kyber coverage. HQC was
modified in October 2024, so any patent filed before then might apply.
Patent applications typically aren't public until 18 months later.

---D. J. Bernstein