open question to the community related to KEMs based on structured lattices

[tillich]

On Wed, May 19, 2021 at 6:27 AM 'Moody, Dustin (Fed)' via pqc-forum
<pqc-...@list.nist.gov> wrote:
>
> IPR issues have been an explicit evaluation criteria since the beginning of the PQC standardization process. Our efforts in this area are ongoing; we are aware of the issues.  It is certainly a complex situation.

(..)

> We would appreciate any feedback from the community on this issue, including the size of role that patents/IPR issues should play in our final selection process.

Dustin et al,

In addition to algorithms themselves, the problems can also arise from obvious *use cases* being patented or tainted by patent applications. Consider US20190319796A1:

"Low latency post-quantum signature verification for fast secure-boot."
S. Ghosh et al, Intel. https://patents.google.com/patent/US20190319796A1/

This application seems to have been filed while the Hash-Based Signature (HBS) standardization process was already ongoing. It mainly talks about using XMSS in one of the most obvious use cases of HBS. Regardless of its merits, I am now hesitant to recommend XMSS as a solution to customers wanting quantum-resilient firmware security, despite it being both a NIST and an IETF standard (well, at least to some degree, informational RFC, etc).

Yes, I am aware of the prior art, but still -- it's there, I have no desire of being targeted by Intel lawyers, and there are other options. SP 800-208 describes not only XMSS(^MT), but LMS, HSS too, and all of these were approved last October. This may one of the main reasons why LMS/HSS seems like a preferred choice (for this particular use case) in the industry. As an example, RFC 9019 ("A Firmware Update Architecture for Internet of Things") only mentions LMS/HSS.

NIST has other standards and technical reports discussing firmware updates (e.g. SP 800-193), but those do not include very specific algorithm guidance. If 800-193, FIPS 140-3 IG, or some other place said "you can use XMSS for digitally signing firmware updates!" I'd certainly be relieved.

- Since none of the US20190319796A1 inventors are XMSS designers I assume that the patent application didn't need to be disclosed during the standardization process (SP 800-208 itself has a section about patent disclosures).

- On the other hand, the designers of LMS/HSS have prior art specifically in this use case, and I have no reason to believe that they have secret IP related to LMS/HSS that they didn't disclose to either NIST and IETF (RFC 8554).

I think this goes as an example of why it may be preferable to standardize multiple options "of almost the same thing" if similar security assurance is there for all of those options. Convergence to one of those options may happen for reasons unrelated to security, but at least the options are there.

Personal opinions only, not a lawyer, etc.

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@pqshield.com> PQShield, Oxford UK.

--
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/8005dddd-7744-4e04-994b-23af990fe496n%40list.nist.gov.

[Guilbon Joffrey]

Dear forum,

It looks like the displayed message here is an attachement of the mail (the first one). We received on the mailing another mail (you can verify it, 10 nov. 2021 5:13pm) which I would like to paste here for clarity reasons. Also, can anyone explain why the first attachement is displayed instead of the original mail? On top of that, the preview of the post through the web UI shows the beginning of the original mail.
Below the original mail:

"Dear forum,

NIST has stated on multiple occasions its preference to select at most
one KEM among {Kyber, NTRU, SABER}. After discussing this matter with
several colleagues, we think it is worth considering the possibility of
having several structured lattices KEM standardized instead of one.

The decision to be made now will impact a primitive that will be heavily
deployed and used in the coming decades. There is a huge responsibility
involved here if we do not standardize the best solution in the long run.

There is a patent issue (true or potential, it does not matter) for
Kyber and SABER which is unlikely to be solved by the end of this year.
This may impact the process and lead to reject schemes irrespective of
their scientific merits. Also, as previously mentioned on this forum
(see attached messages), there might be other IP issues we are not yet
aware of. Moreover, there is a fair chance that these patent issues will
be resolved if given enough time.

Therefore, our open question to the community is

"would not it be good to standardize several solutions?"

Giving both time and options without compromising the competition
timeline. This could allow a soft landing towards the best solution(s)
for the various platforms and applications. Besides, structured
lattice-based KEMs allow compact implementation, mitigating the 'burden
on implementors' argument.

Nicolas Sendrier & Jean-Pierre Tillich"

Thanks,
Joffrey

[Guilbon Joffrey]

By the way, I agree with the multiple standardisation approach. It won't cause harm and can prevent difficult situations. What would have happened if NIST had standardized only binary elliptic curves to standardize "only one elliptic curve solution" ?  

If IPR issues reduce the "three cyclic lattice finalists" approach to one without technical merits consideration, one may consider that this standardization round somehow has been a failure.

Thanks,
Joffrey

[D. J. Bernstein]

Guilbon Joffrey writes:
> If IPR issues reduce the "three cyclic lattice finalists" approach to one
> without technical merits consideration, one may consider that this
> standardization round somehow has been a failure.

Can you please elaborate on what you see this as failing to accomplish,
and how that's connected to NIST's job in NISTPQC?

I see the following in the call for submissions:

NIST has observed that royalty-free availability of cryptosystems and
implementations has facilitated adoption of cryptographic standards
in the past. For that reason, NIST believes it is critical that this
process leads to cryptographic standards that can be freely
implemented in security technologies and products.

Having NIST standardize Kyber, kicking the can down the road for each
company to learn later that Kyber is subject to multiple patent threats,
would thus appear to be abandoning something that NIST labeled as a
"critical" feature of the NISTPQC process.

---Dan