Patent update

[D. J. Bernstein]

In 2017, on behalf of an undeclared client, a British law firm named
Keltie (declared consultants include two NCSC cryptographers, presumably
from GCHQ; and Dr. Peikert) filed an opposition to the European version
of patent 9094189. See https://ntruprime.cr.yp.to/faq.html for
background on patents 9094189 and 9246675.

Keltie's opposition was rejected. Keltie appealed. The appeal board
issued a preliminary assessment a few weeks ago, not in the direction
Keltie wanted. A hearing was still scheduled, but Keltie withdrew the
appeal a few days ago (20 October). See the latest documents here:

https://register.epo.org/application?number=EP11712927&lng=en&tab=doclist

The idea that one can avoid these patents by minor tweaks---changing
rings to modules, for example, or changing noise to rounding---is
divorced from the reality of how patent law works:

https://tile.loc.gov/storage-services/service/ll/usrep/usrep535/usrep535722/usrep535722.pdf

I propose that NIST issue a statement

* saying that consideration of standardization within NISTPQC of the
structured LPR variants (Kyber, SABER, and the NTRU LPRime option
within NTRU Prime) has been rescheduled for 2033, when both patents
9094189 and 9246675 have expired; and

* saying that putting this on a faster schedule will require those
patents and their international versions to be fully abandoned.

I propose that the statement be issued now, not delayed until NIST's
next report. Delaying the inevitable is counterproductive for people
trying to convince the patent holders to disarm their landmines.

---Dan

[Markku-Juhani O. Saarinen]

Hi All,

I fully trust that NISTPQC does exactly what it set out to do in 2016 and selects post-quantum cryptography algorithms primarily based on their technical and security merits (while of course also considering the advice from their own legal professionals.) This is what the security industry, other U.S. government departments, various military branches, international standardization bodies, etc expects it to do.

While it is good for a professional cryptographer to have basic knowledge about patents, in my view the commercial and legal professions are better qualified to assess their importance and business impact. It would be very unfortunate is if potential patent issues would affect our technical evaluation or recommendations. So we should keep these issues separate.

regardless, here's my 2 pennies on these patents...

There are more ways to resolve patent conflicts than "full abandonment" or waiting for an expiration date, as proposed below. The semiconductor industry (which occupies most of my time nowadays) certainly wouldn't be able to function if it thought about patents and intellectual property like that. The mere existence of a patent is rarely an immovable blocker, at least if you don't try to negotiate a solution first.

It is very difficult to speculate on this particular case: It wouldn't be wise for the patent owners to comment on their plans and intentions, so I don't know those. I'd assume that they would at least try to reach some kind of licensing agreement if their patent is found to be a "threat". While legal challenges are public, commercial and licensing negotiations always happen behind closed doors. So we don't know.

Cheers,

-Markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20211025092915.1309641.qmail%40cr.yp.to.

[Greg Maxwell]

On Mon, Oct 25, 2021 at 7:32 PM Markku-Juhani O. Saarinen
<mjos....@gmail.com> wrote:
> There are more ways to resolve patent conflicts than "full abandonment" or waiting for an expiration date, as proposed below. The semiconductor industry (which occupies most of my time nowadays) certainly wouldn't be able to function if it thought about patents and intellectual property like that.

This approach has been attempted in the past with cryptography and it
resulted in widespread non-adoption and a lot of traffic going
unencrypted that otherwise would have been. When you produce a good
with effectively zero marginal cost-- such as a web-browser-- the cost
of *any* patent licensing is considerable. And even those parties who
have room for some royalties still need to operate with those who do
not.

I think this is even more likely to be the case for PQC because the
threat of quantum attacks are more conjectural and users have the
option of just continuing to use their mature non-PQC cryptosystems
which are good enough unless/until practical large quantum computers
are developed. To the extent that PQ crypto is a useful hedge to
protect confidentiality decades into the future-- it's the end user
that takes on that risk, not the application developer.

If NIST standardizes an approach that the industry treats as
encumbered and fails to also standardize a viable alternative which
the industry treats as unencumbered it will cause considerable harm to
the world when parties don't deploy the encumbered thing (due to
costs) and don't deploy a non-encumbered alternative (non-standard)
and as a result leave traffic with long term exposure that could have
been prevented.

Why do you believe this process is unable to weigh IPR risks but
totally able to weigh performance tradeoffs? If anything that is
backwards: New processors are constantly coming out and new software
optimizations are constantly being developed but new systems of law
are not so common. Performance being discussed in the comparison is
only applicable to the specific devices being discussed, use a
different part and you will get different results. Application
tolerances for performance also differ significantly. The reality is
that all metrics are inherently somewhat subjective or unclear.

And in terms of adoptability, I believe for widespread adoption being
extremely clear of IP encumbrances is significantly more important
than the performance differences among any of the lattice finalists
and alternates.

[Markku-Juhani O. Saarinen]

On Mon, Oct 25, 2021 at 8:52 PM Greg Maxwell <gmax...@gmail.com> wrote:

On Mon, Oct 25, 2021 at 7:32 PM Markku-Juhani O. Saarinen
<mjos....@gmail.com> wrote:
> There are more ways to resolve patent conflicts than "full abandonment" or waiting for an expiration date, as proposed below. The semiconductor industry (which occupies most of my time nowadays) certainly wouldn't be able to function if it thought about patents and intellectual property like that.

 

Hi Greg,

The semiconductor industry worries about cost a lot. I was trying to hint at the direction of the potential one-off licensing negotiations. I 100% agree that a license fee per unit would lead to non-adoption. I mean, it wouldn't fly at the IETF, so it wouldn't fly anywhere.

I wanted to avoid speculation, but here we are: USG has already expressed interest in fast lattice-based cryptography, basically stating that they want to use it. The patent holders would be fools if they at least didn't try to negotiate some kind of deal if they think that they have half a case. They have the precedent in the Elliptic Curve patents to think of course. I'd wait for it to play out rather than abandon the entire project for 10 years and exit the building.

If it doesn't go the way we wish and those algorithms will have license fees, I agree that the industry will adopt other algorithms.

Why do you believe this process is unable to weigh IPR risks but
totally able to weigh performance tradeoffs?  If anything that is
backwards:  New processors are constantly coming out and new software
optimizations are constantly being developed but new systems of law
are not so common.

I think you make a lot of good points, but on this I completely disagree.

I personally design components for computer systems. I have basically a schoolbook approach to this -- modern computer architecture and hardware design is quantitative in nature. We measure every component, such as a cryptographic algorithm, and only via that method the resulting whole can have good overall performance, battery life, etc. Any new processor coming out is more powerful precisely because of this process; every component -- from the process node and cell libraries upwards via EDA tools to CPU designs themselves -- everything -- is slightly improved. A cryptographic algorithm is just another component of a computer system and gets no special privilege in relation to it. Note that its area or power budget doesn't grow unless there are good reasons for it.If there are multiple options, we will try to select the best one for the task (which is typically also cheapest, total costs considered).

The reality is that all metrics are inherently somewhat subjective or unclear.

One could also throw one's hands up and say "it is impossible to design instruction set architectures because no single ISA is going to fulfill all programming tasks in an optimal way -- it is all subjective and unclear." The latter part of the argument is true, but the first one is not; it is not impossible to design instruction set architectures that are generally useful, that make good compromises, and responds to future developments well. Endless quantitative analysis is required to reach suitable compromises. The evolution of modern cryptographic algorithms follows similar principles and it is closely informed by quantitative analysis. We're much past the RSA type "equation inventions" -- concrete algorithms are engineered and designed rather than invented; this is especially visible in the more mature fields of lattice-based cryptography and symmetric cryptography, where a lot of things can be done for performance.

I think we should select cryptographic algorithms that have quantitatively good overall performance, in addition to having no compromises in security. These things are not unknowable. The legal system and the decisions of patent holders are more arbitrary and unpredictable in my opinion.

Cheers,

- markku