Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

12434 views
Skip to first unread message

Moody, Dustin (Fed)

unread,
Jul 5, 2022, 11:32:17 AMJul 5
to pqc-forum

Announcement

 

After careful consideration during the 3rd Round of the NIST PQC Standardization Process, NIST has identified four candidate algorithms for standardization. The primary algorithms NIST recommends be implemented for most use cases are CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures).  In addition, the signature schemes Falcon and SPHINCS+ will also be standardized.

 

Algorithms to be Standardized


 

Public-Key Encryption/KEMs

CRYSTALS-KYBER

 

Digital Signatures

CRYSTALS-Dilithium

Falcon

SPHINCS+


 

 

CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures) were both selected for their strong security and excellent performance, and NIST expects them to work well in most applications. Falcon will also be standardized by NIST since there may be use cases for which CRYSTALS-Dilithium signatures are too large. Additionally, SPHINCS+ will be standardized to avoid only relying on the security of lattices for signatures. NIST asks for public feedback on a version of SPHINCS+ with a lower number of maximum signatures.

 

Additionally, the following candidate KEM algorithms will advance to the fourth round:

 

4th Round Candidates


 

Public-Key Encryption/KEMs

BIKE

Classic McEliece

HQC

SIKE

 


 

Both BIKE and HQC are based on structured codes, and either would be suitable as a general-purpose KEM that is not based on lattices. NIST expects to select at most one of these two candidates for standardization at the conclusion of the fourth round. SIKE remains an attractive candidate for standardization because of its small key and ciphertext sizes and will continue to study it in the fourth round. Classic McEliece was a finalist but is not being standardized by NIST at this time.  Although Classic McEliece is widely regarded as secure, NIST does not anticipate it being widely used due to its large public key size. NIST may choose to standardize Classic McEliece at the end of the fourth round.

 

For the algorithms moving on to the fourth round, NIST will allow the submission teams to provide updated specifications and implementations (“tweaks”). The deadline for these tweaks will be October 1, 2022. Any submission team that feels that they may not meet the deadline should contact NIST as soon as possible. NIST will review the proposed modifications and publish the accepted submissions shortly afterwards. As a general guideline, NIST expects any modifications to be relatively minor. The fourth round will proceed similarly to the previous rounds. More detailed information and guidance will be provided in another message.

 

A detailed description of the decision process and rationale for selection will be included in NIST Interagency or Internal Report (NISTIR) 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, which will soon be available at https://csrc.nist.gov/publications and on the NIST post-quantum webpage https://nist.gov/pqcrypto. Questions may be directed to pqc-co...@nist.gov.

 

NIST will create new draft standards for the algorithms to be standardized and will coordinate with the submission teams to ensure that the standards comply with the specifications. As part of the drafting process, NIST will seek input on specific parameter sets to include, particularly for security category 1. When finished, the standards will be posted for public comment. After the close of the comment period, NIST will revise the draft standards as appropriate based on the feedback received. A final review, approval, and promulgation process will then follow.

 

NIST will hold a 4th NIST PQC Standardization Conference on November 29 – December 1, 2022. The conference details have not yet been finalized. The preliminary Call for Papers will be posted, both on the pqc-forum and the NIST PQC webpage http://nist.gov/pqcrypto.

NIST also plans to issue a new Call for Proposals for public-key (quantum-resistant) digital signature algorithms by the end of summer 2022. NIST is primarily looking to diversify its signature portfolio, so signature schemes that are not based on structured lattices are of greatest interest. NIST would like submissions for signature schemes that have short signatures and fast verification (e.g., UOV). Submissions in response to this call will be due by June 1, 2023. Submitters are encouraged to communicate with NIST ahead of time. NIST will decide which (if any) of the submitted signature algorithms to accept and will initiate a new process for evaluation. NIST expects this process to be much smaller in scope than the current PQC process. The signature schemes accepted to this process will need to be thoroughly analyzed, which will similarly take several years. 

 

NIST would like to thank the community and all of the submission teams for their efforts in this standardization process and hopes that the teams whose schemes were not selected to advance will continue to participate by evaluating and analyzing the remaining cryptosystems alongside the cryptographic community at large. These combined efforts are crucial to the development of NIST’s future post-quantum public-key standards.

 

 

The NIST PQC team

 

Deirdre Connolly

unread,
Jul 5, 2022, 11:45:04 AMJul 5
to Moody, Dustin (Fed), pqc-forum
Congratulations and thank you to the NIST team and all the submitters! 🎇

--
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/SA1PR09MB866933A15C3568FC510B4B68E5819%40SA1PR09MB8669.namprd09.prod.outlook.com.

Doge Protocol

unread,
Jul 5, 2022, 12:27:15 PMJul 5
to pqc-forum, dustin...@nist.gov
Thanks NIST team!

>>>NIST would like submissions for signature schemes that have short signatures and fast verification (e.g., UOV).

On this, will having shorter public keys also be a pre-requisite for submissions or only shorter signatures is a pre-req?

Yesterday there was a paper posted that improves on Falcon signature size. Would this and similar improvements in the future also be considered eligible for submission?

Moody, Dustin (Fed)

unread,
Jul 5, 2022, 1:34:31 PMJul 5
to pqc-forum

Guidelines for submitting tweaks for Fourth Round Candidates

Deadline: October 1, 2022

 

Candidate teams must meet the same submission requirements and minimum acceptability criteria stated in the original Call for Proposals. Submissions must be submitted to NIST at pqc-sub...@nist.gov by October 1, 2022. Submissions should include a cover sheet, algorithm specifications (and other supporting documentation), and optical/digital media (e.g., implementations, known-answer test files, etc.) as described in Section 2 of the original Call For Proposals. In addition, NIST requires a short document outlining the modifications introduced in the new submission. This document should be included in the supporting documentation folder of the submission (see Section 2.C.4 of the CFP). NIST will review the proposed changes to determine whether they meet the submission requirements and minimum acceptability requirements, as well as whether they significantly affect the design of the algorithm and require a major reevaluation. As a general guideline, NIST expects any modifications to be relatively minor. It would be helpful if submission teams provided NIST with a summary of their expected changes prior to the deadline. If the deadline will pose a problem for any submission team, they should contact NIST in advance.

 

NIST does NOT need new signed IP statements unless new submission team members have

been added or the status of intellectual property for the submission has changed. If either of

these cases apply, NIST will need new signed IP statements (see Section 2.D of the CFP). These

statements must be actual hard copies – not digital scans – and must be provided to NIST by the 4th NIST PQC Standardization Conference (December 1, 2022).

 

NIST is aware that some submission packages may be large in size. The email system for pqc-submi...@nist.gov can only accept files up to 25MB. For larger files, candidate teams may upload submission packages at a location of their choosing and send NIST the download link. If that option is not suitable, NIST has a file transfer system that can be used (please email pqc-co...@nist.gov for more details). NIST will review the submitted packages as quickly as possible and post the candidate submission packages that are complete and proper on www.nist.gov/pqcrypto. Teams are encouraged to submit early. General questions may be asked on the pqc-forum. For more specific questions, please email pqc-co...@nist.gov.

 

The NIST PQC team

--

Moody, Dustin (Fed)

unread,
Jul 5, 2022, 1:34:56 PMJul 5
to pqc-forum

During PQC Standardization, the United States Department of Commerce’s National Institute of Standards and Technology (NIST) has worked on selecting a cryptographic key encapsulation algorithm that would protect information from attacks by classical and quantum computers.  In furtherance of NIST’s PQC Standardization efforts, NIST and Dr. Jintai Ding announce intentions to enter into a patent license agreement, wherein a patent owned by Dr. Ding’s Ohio-based company, Algo Consulting, would be licensed to NIST.  As a result of this patent license agreement, implementers and end users of NIST’s PQC standard, which will be based on the selected cryptographic key encapsulation algorithm, will not need a separate license from Algo Consulting, Inc.  This will promote the timely and widespread adoption of NIST’s PQC standard, a shared goal of NIST and Dr. Ding.

 

NIST appreciates Dr. Ding’s efforts and cooperation and will announce its selection of the cryptographic key encapsulation algorithm as soon as reasonably possible.

 

The NIST PQC team

Dr. Jintai Ding, owner Algo Consulting, Inc.

 

 

From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Tuesday, July 5, 2022 11:32 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

Announcement

--

Moody, Dustin (Fed)

unread,
Jul 5, 2022, 1:35:29 PMJul 5
to pqc-forum

Call for Papers for the 4th NIST PQC Standardization Conference

Location: Virtual

November 29 – December 1, 2022

Submission deadline:  September 15, 2022

(Conference without proceedings)

 

NIST plans to hold the 4th NIST PQC Standardization Conference from November 29 to December 1, 2022.  The purpose of the conference is to discuss various aspects of the candidate algorithms and to obtain valuable feedback for informing decisions on standardization. NIST will invite the submission teams for both the selected algorithms, as well as the algorithms advancing to the fourth round, to give an update on their algorithms.

 

In addition, NIST is soliciting research and discussion papers, surveys, presentations, case

studies, panel proposals, and participation from all interested parties, including researchers,

system architects, implementors, vendors, and users. NIST will post the accepted papers and

presentations on the conference website after the conference; however, no formal proceedings

will be published. NIST encourages the submission of presentations and reports on preliminary

work that participants plan to publish elsewhere.

 

Topics for submissions should include but are not limited to:

 

  • Classical and quantum cryptanalysis of the algorithms, including cryptanalysis of weakened or toy versions
  • Analysis of relative performance or resource requirements for some or all of the algorithms
  • Assessments of classical and quantum security strengths of the algorithms
  • Systemization of knowledge relevant to the NIST PQC standardization process
  • Substantial improvements in the implementation of algorithms
  • Improved analysis or proofs of properties of finalists/candidates, even when this does not lead to any attack
  • Proposed criteria to be used for selecting algorithms for standardization
  • Impacts to existing applications and protocols (e.g., changes needed to accommodate specific algorithms)
  • Steps or strategies for organizations to prepare for the coming transition

 

 

Submissions should be provided electronically, in PDF, for standard US letter-size paper (8.5 x

11 inches). Submitted papers must not exceed 20 pages, excluding references and appendices

(single space, with 1-inch margins using a 10 pt or larger font). Proposals for panels should be

no longer than five pages and should include possible panelists and an indication of which

panelists have confirmed their participation.

 

Please submit the following information to pqc...@nist.gov:

 

  • Name, affiliation, email, phone number (optional), postal address (optional) for the primary submitter
  • First name, last name, and affiliation of each co-submitter
  • Finished paper, presentation, or panel proposal in PDF format as an attachment

 

All submissions will be acknowledged.

 

General information about the conference, including registration information, will be available at the conference website: http://www.nist.gov/pqcrypto.

 

 

From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Tuesday, July 5, 2022 11:32 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

Announcement

--

Moody, Dustin (Fed)

unread,
Jul 5, 2022, 1:36:32 PMJul 5
to pqc-forum

Sorry for so many messages! 

 

Here’s the link to the official NIST announcement.  Please share:

 

https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

 

 

Here’s the link to NISTIR 8413:  Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, which explains the rationale behind the decisions.

 

https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf

 

Dustin

 

 

From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Tuesday, July 5, 2022 11:32 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

Announcement

--

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


To view this discussion on the web visit

ToTheMars ABC

unread,
Jul 5, 2022, 1:50:26 PMJul 5
to pqc-forum, dustin...@nist.gov
Can someone tell me why there is no rainbow signature in the list? Isn't it a 3rd round finalist?

Gustavo Banegas

unread,
Jul 5, 2022, 1:54:17 PMJul 5
to ToTheMars ABC, pqc-forum, dustin...@nist.gov
Well,
As Dustin pointed in the first email, there is a report that details all the choices. It includes why some of the schemes were not selected. For Rainbow, please read page 51.

All the best,
Gustavo
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

D. J. Bernstein

unread,
Jul 5, 2022, 4:04:16 PMJul 5
to pqc-...@list.nist.gov
'Moody, Dustin (Fed)' via pqc-forum writes:
> NIST and Dr. Jintai Ding announce intentions to enter into a patent
> license agreement

Great. Is there a specific schedule for the completion of this
agreement?

[ implementors and end users ]
> will not need a separate license

That's good to hear. But will the agreement have limitations and poison
pills similar to the "grant" that NIST previously obtained from ISARA
(https://web.archive.org/web/20201101181903/https://www.isara.com/nist-grant.html)?

In any case, congratulations to Dr. Ding and the rest of the Kyber team
regarding Kyber's selection for standardization!

---D. J. Bernstein

P.S. Also, regarding signatures, congratulations to the Dilithium and
Falcon teams! And, since I'm just one of a huge number of members of the
SPHINCS+ team, maybe I'm allowed to congratulate SPHINCS+ too.
signature.asc

Moody, Dustin (Fed)

unread,
Jul 6, 2022, 12:24:45 PMJul 6
to pqc-forum
From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Tuesday, July 5, 2022 1:36 PM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] RE: Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized
 

Scott Fluhrer (sfluhrer)

unread,
Jul 6, 2022, 1:14:29 PMJul 6
to Moody, Dustin (Fed), pqc-forum

Can we get the text of the actual license agreement between NIST and CNRS/University of Limoges?

John Mattsson

unread,
Jul 6, 2022, 2:01:26 PMJul 6
to pqc-forum

Hi,

 

Do anybody know if we can expect an update of the CNSA suite in a few days or will it take months? That is another very important announcement. The NSA PQC FAQ states:

 

"The intention is to update CNSA to remove quantum-vulnerable algorithms and replace them with a subset of the quantum-resistant algorithms selected by NIST at the end of the third round of the NIST post-quantum effort"

 

https://www.nsa.gov/Cybersecurity/Post-Quantum-Cybersecurity-Resources/

 

Suite B was very influencial. The algorithms, modes, and parameters chosen for CNSA will likely have a big influence on enterprises and various industries.

 

Cheers,

John Preuß Mattsson

EL HASSANE LAAJI

unread,
Jul 6, 2022, 2:17:50 PMJul 6
to pqc-forum
Hi.
Congratulations to the teams whose schemes were selected.
I ask if the NTRU scheme (Public-Key Encryption/KEMs), will die???
Best regards.

--
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.

Mike Ounsworth

unread,
Jul 6, 2022, 2:24:49 PMJul 6
to John Mattsson, pqc-forum

I assume that the standards need to be written before they can be adopted into the CNSA Suite?

 

---

Mike Ounsworth

 

From: 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov>

Sent: July 6, 2022 1:01 PM
To: pqc-forum <pqc-...@list.nist.gov>

Subject: [EXTERNAL] [pqc-forum] Re: Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.


--

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

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

Q R

unread,
Jul 6, 2022, 2:37:02 PMJul 6
to John Mattsson, pqc-forum
That is an excellent question.

I cannot imagine how anyone can implement these without having the
final standards from NIST.

It does not seem like a good approach to just say - go use the
algorithms as-is because it seems like there is a lot of work yet to
be done with finalizing parameters, making algorithms more human
readable, providing guidance on how to use alg and security levels,
etc.

The current NSA guidance ups key sizes to help protect against Q-Day
and Y2Q and NIST also added support for hybrid shared keys, pre-shared
keys and ITU added hybrid certificates.

As I currently understand it, teams should be
- creating a data inventory with sensitivity
- creating a crypto inventory with details
- determining is a hybrid method is needed to protect against the
store-now / decrypt later attack
- figuring out ways to add crypto agility from internal, open-source
and commercial products
- doing the NIST guidance on preparing for PQC transition
- experimenting with things like Open Quantum Safe and its spinoffs
(TLS, SSH, S/MIME...)
- learning how to do optimizations for lattice based methods
- exploring all their use cases for the different devices and how
these algorithms may impact choosing parameters sets and which algs to
use

Bottom line, I know NSA wants to move fast once the standards are
complete, but it does seem immature that that is now.

However, I cannot speak for anyone so take all my comments with a grain of salt.

-Amzoti
> --
> 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/HE1PR0701MB3050DE85057A661E22566FB989809%40HE1PR0701MB3050.eurprd07.prod.outlook.com.
>

Blumenthal, Uri - 0553 - MITLL

unread,
Jul 6, 2022, 3:00:30 PMJul 6
to Mike Ounsworth, John Mattsson, pqc-forum

I assume that the standards need to be written before they can be adopted into the CNSA Suite?

 

This is my assumption as well.

 

Now we know what algorithms will be standardized – but not the exact parameter sets, format of the bits-on-the-wire, etc. And the upcoming standards will have to undergo public discussion first.

 

Thanks

 

 

From: 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov>
Sent: July 6, 2022 1:01 PM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] [pqc-forum] Re: Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.


Hi,

 

Do anybody know if we can expect an update of the CNSA suite in a few days or will it take months? That is another very important announcement. The NSA PQC FAQ states:

 

"The intention is to update CNSA to remove quantum-vulnerable algorithms and replace them with a subset of the quantum-resistant algorithms selected by NIST at the end of the third round of the NIST post-quantum effort"

 

https://www.nsa.gov/Cybersecurity/Post-Quantum-Cybersecurity-Resources/

 

Suite B was very influencial. The algorithms, modes, and parameters chosen for CNSA will likely have a big influence on enterprises and various industries.

 

Cheers,

John Preuß Mattsson

--
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/HE1PR0701MB3050DE85057A661E22566FB989809%40HE1PR0701MB3050.eurprd07.prod.outlook.com.

Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

--

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.

Stanger, Adrian D

unread,
Jul 6, 2022, 3:11:39 PMJul 6
to pqc-forum

NSA does not currently have a set date for release of "CNSA 2.0.” We hope to have an update soon, after we have completed our review of NIST's report and worked through internal reviews. It will probably take longer than days, hopefully less than months.

 

Cheers,

 

Adrian

Stanger, Adrian D

unread,
Jul 6, 2022, 3:14:15 PMJul 6
to pqc-forum

Forgot to include—

 

This will be guidance only for now.

Daniel Apon

unread,
Jul 6, 2022, 3:43:32 PMJul 6
to Blumenthal, Uri - 0553 - MITLL, Mike Ounsworth, John Mattsson, pqc-forum
From my end: Uri appears exactly right

--Daniel

Blumenthal, Uri - 0553 - MITLL

unread,
Jul 6, 2022, 4:28:48 PMJul 6
to Dan Brown, pqc-forum

Ideally – no tweaks would be necessary. In practice, however, we can’t know (yet).

 

And the standard would have to spell out all the details, so that one could (re-)create an interoperable implementation from scratch.

 

-- 

V/R,

Uri

 

 

From: Dan Brown <dani...@blackberry.com>
Date: Wednesday, July 6, 2022 at 16:09
To: Daniel Apon <dapon....@gmail.com>, Uri Blumenthal <u...@ll.mit.edu>
Cc: Mike Ounsworth <Mike.Ou...@entrust.com>, John Mattsson <john.m...@ericsson.com>, pqc-forum <pqc-...@list.nist.gov>
Subject: RE: [pqc-forum] RE: Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

The submitted specifications already included parameters, and the reference implementation included bits-on-the-wire formats implied by the api.h files. 

Small changes in cryptography can mean big changes in security. So, ideally, no more changes will be needed.

​​​​​

Dan

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Daniel Apon
Sent: Wednesday, July 6, 2022 3:43 PM
To: Blumenthal, Uri - 0553 - MITLL <u...@ll.mit.edu>
Cc: Mike Ounsworth <Mike.Ou...@entrust.com>; John Mattsson <john.m...@ericsson.com>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] RE: Announcement: The End of the 3rd Round - the First PQC Algorithms to be Standardized

 

CAUTION - This email is from an external source. Please be cautious with links and attachments. (go/taginfo)

 


This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

Moody, Dustin (Fed)

unread,
Jul 7, 2022, 1:55:57 PMJul 7
to Doge Protocol, pqc-forum

As stated in our announcement yesterday:  "NIST also plans to issue a new Call for Proposals for public-key (quantum-resistant) digital signature algorithms by the end of summer 2022. NIST is primarily looking to diversify its signature portfolio, so signature schemes that are not based on structured lattices are of greatest interest. NIST would like submissions for signature schemes that have short signatures and fast verification. Submissions in response to this call will be due by June 1, 2023. Submitters are encouraged to communicate with NIST ahead of time. NIST will decide which (if any) of the submitted signature algorithms to accept and will initiate a new process for evaluation. NIST expects this process to be much smaller in scope than the current PQC process. The signature schemes accepted to this process will need to be thoroughly analyzed, which will similarly take several years." 

We’re willing to look at any (including lattice-based) signature scheme, but we will only move them forward in the “on-ramp” standardization process if they align with the stated priorities above.  For lattice-based signatures, they would also need to substantially improve over what we already selected.  NIST will consider the submissions on a case by case basis. You can look for more detailed information when the new call for signatures is released.   

Dustin Moody

NIST

Scott Fluhrer (sfluhrer)

unread,
Jul 15, 2022, 2:55:15 PMJul 15
to Moody, Dustin (Fed), pqc-forum, Jonathan Felten (jfelten)

Let me be more explicit.

 

I have not talked to the Cisco execs; I cannot imagine that they would approve the use of Kyber without an assessment of the Cisco liability (and associated licensing fees, if any).

 

I have not talked to the Cisco lawyers; I cannot imagine that they would be willing to give any such assurance without an examination of the licenses (and an examination of the press releases would not be sufficient).

 

Hence, until we get the text of the licenses (both the one signed with CNRS and the one to be signed with Algo Consulting), Cisco cannot use Kyber.  If continues to be true, we will need to seek an alternative solution.

Daniel Apon

unread,
Jul 15, 2022, 3:12:51 PMJul 15
to Scott Fluhrer (sfluhrer), Moody, Dustin (Fed), pqc-forum, Jonathan Felten (jfelten)
This connects to another pressing issue, for which there is not yet a concrete recommendation from NIST, at least as far as I'm aware:

When does NIST recommend that an interested organization should begin their actual migration to post-quantum cryptography deployment based on the July 5th, 2022 announcement?
(Of course, prior to such a "go" date, many practical, preliminary steps can be completed in preparation for the migration date. But that aside..)

As this issue arises in context: Scott says that Cisco cannot use Kyber until Cisco receives the text of the licenses (CNRS/Algo) -- and presumably has sufficient, interluding time for Cisco lawyers to examine the text of the licenses.

1) At which point in time does NIST intend for (for example) Cisco -- or any other organization -- to begin migration to Kyber (or Dilithium/Falcon/SPHINCS+)?
2) At which point in time will the text of the licenses (CNRS/Algo) be posted publicly?

Speaking in my personal capacity in my role at MITRE (having not spoken with MITRE execs or MITRE lawyers either),
--Daniel

Daniel Apon

unread,
Jul 15, 2022, 3:17:10 PMJul 15
to Scott Fluhrer (sfluhrer), Moody, Dustin (Fed), pqc-forum, Jonathan Felten (jfelten)
The particularly relevant question I'm also asking about is when NIST will go from algorithm specification selection to parameterization / tweak finalization for the selected algorithms.

The obvious date is the release of the full standards documents in ~2024 (ETA).
Will there be a safe fixed point in parameterization/tweaks for early-adopters/deployers prior to the standards documentation release in ~2024?

Cheers

D. J. Bernstein

unread,
Jul 15, 2022, 11:32:49 PMJul 15
to pqc-...@list.nist.gov
'Scott Fluhrer (sfluhrer)' via pqc-forum writes:
> If continues to be true, we will need to seek an alternative solution.

NIST's new report already points to a solution (see page 18):

If the agreements are not executed by the end of 2022, NIST may
consider selecting NTRU instead of KYBER. NTRU was proposed in 1996,
and U.S. patents were dedicated to the public in 2007.

(I have no idea how whoever reviewed this could have imagined that
"2007" was correct. If NTRU had been patent-free in 2007 then why didn't
people try rolling it out in response to the Snowden revelations? In
fact, the main NTRU patent expired in 2017, and the company didn't give
up on the patent until earlier in 2017.)

The same report says NIST is confident in NTRU's security:

One of the difficult choices NIST faced was deciding between KYBER,
NTRU, and Saber. All three were selected as finalists and were very
comparable to each other. NIST is confident in the security that each
provides.

Regarding performance, the report says

A significant factor in the decision to choose KYBER over NTRU was
NTRU's performance (particularly key generation), which was not quite
as efficient as that of KYBER

but also admits how insignificant this "significant factor" is in the
real world:

Most applications would be able to use any of them without
significant performance penalties.

So NIST could have simply selected the patent-free option back in 2021.
What happened instead was NIST delaying for half a year working on
patent buyouts for Kyber. Many wheels in the deployment ecosystem were
waiting for NIST, and were slowed down by half a year as a result. This
translates directly into half a year of user data given to attackers.

There's nothing in the report considering the security damage caused by
this delay, let alone explaining how this damage is outweighed by the
small advantages that the report attributes to Kyber.

Maybe the patent-buyout details will be published next week. Maybe we'll
see that the details are adequate, unlike the poison-pill "grant" that
NIST negotiated with ISARA:

https://web.archive.org/web/20201101181903/https://www.isara.com/nist-grant.html

And maybe NIST will release an analysis convincingly explaining why we
shouldn't be worried about the patents that NIST hasn't said anything
about so far, such as CN107566121A.

Or maybe NIST simply doesn't grasp the magnitude of the problem here.
NIST's report briefly says that "an evaluation factor is whether a
patent might hinder adoption", but this is a remarkable retreat from the
call for submissions, which used the word "critical":

NIST believes it is critical that this process leads to cryptographic
standards that can be freely implemented in security technologies and
products.

Figuring out what patents are out there, and what's safe from those
patents given the complications of patent law, takes tons of work and
should have been emphasized from the beginning of NISTPQC. Instead NIST
discouraged public patent analysis, instead deciding to handle patents
behind the scenes as an afterthought. This mistake has already created
half a year of delay.

This looks like a great opportunity for agile tech companies to get
ahead of the game by rolling out NTRU. The business case is clear, with
ample cover provided by NIST's report:

* We can act now to help protect users against quantum computers.
There's broad awareness of the quantum threat, and users will
appreciate hearing that we're taking action.

* NIST selected Kyber and seems to have some patent agreements for
Kyber, but many companies are stalled waiting to see whether those
agreements really deal with the full scale of the patent problem.
Main scenarios to consider are "yes", "no", and "still won't be
sure by 2023".

* Meanwhile NIST's report says NTRU is patent-free, says NIST is
"confident in the security" of NTRU, and says most applications can
use NTRU "without significant performance penalties".

* NIST's report even says "If the agreements are not executed by the
end of 2022, NIST may consider selecting NTRU instead of KYBER."
The report is _not_ saying that there's something wrong with NTRU.

* NIST's report says that some small performance advantages of Kyber
over NTRU were a "significant factor" in NIST's decision to choose
Kyber. Those performance advantages are irrelevant to us, and NIST
calls other Kyber advantages "marginal". We care much more about
issues that are barely covered in NIST's report, such as deployment
timelines and patents.

* We can go ahead with rolling out NTRU right now, while running
experiments with Kyber in parallel to make sure we can easily swap
in Kyber later if that turns out to be the right thing to do.

I'm concerned about various risks here that were downplayed or ignored
in NIST's report. In particular, the NTRU submission is _not_ exactly
the 1996 version of NTRU, so it _could_ be covered by patents that
haven't come to public attention (even if the risks are lower than for
Kyber); also, one should _not_ be confident in the security of any of
these systems. The analysis in https://ntruprime.cr.yp.to/warnings.html
indicates that Streamlined NTRU Prime (as in sntrup761, now used by
default in OpenSSH) has somewhat lower patent risks and somewhat lower
security risks than the NTRU submission. However, from the perspective
of users whose data is being intercepted and recorded by large-scale
attackers right now, it's hard to imagine how any of these risks are
comparable to the damage caused by further delay.

---D. J. Bernstein
signature.asc

Daniel Apon

unread,
Jul 16, 2022, 12:28:56 AMJul 16
to pqc-forum
"in response to the Snowden revelations"

Thanks, Dad.

Perhaps you could explain to the Public why you're so aggressively targeting, in public, your PhD student's submission with political nonsense?

--
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.

EL HASSANE LAAJI

unread,
Jul 16, 2022, 6:55:53 PMJul 16
to pqc-...@list.nist.gov
Hi
> One of the difficult choices NIST faced was deciding between KYBER,
  >NTRU, and Saber. All three were selected as finalists and were very
  >comparable to each other. NIST is confident in the security that each
 >  provides.

> Regarding performance, the report says

 >  A significant factor in the decision to choose KYBER over NTRU was
 >  NTRU's performance (particularly key generation), which was not quite
 >  as efficient as that of KYBER


I think it is possible to increase NTRU's performance.

I create a release of NTRU-HPS, but defined in the ring of the form "Rq=Zq[X]/(X^n+1)", that uses NTT algorithm combined with our Fast Modular Multiplication Algorithm (FMMA) (inspired by NewHope method). We obtained drastic results as shown in the table:

6.2          Performance benchmarking of NTRUrobust, Saber, and Kyber

                In this subsection, we present the performance results of our NTRUrobust release compared to the FairSaber and Kyber1024 releases of SABER and KYBER post-quantum KEM schemes, which their parameter sets meet the category 5 security Levels.

with parameters {n=1024, q=65537, p=2}

 

Table 2: Performance benchmarking between NTRUrobust,  FireSaber, and Kyber1024 releases. The result values are given in milliseconds (ms):

Keys Gen (ms)

Encap (ms)

Decap (ms)

Kyber1024

0.46

0.63

0.63

FireSaber

2,51

3.12

3.43

NTRUrobust

1,25

0.47

0,62

 

 NB: We note that all implementations are performed on a PC-TOSHIBA with an Intel(R) Core(TM) i7-2630QM CPU, 2 GHz processor, RAM  8 GO, under environment Windows 7-32 bits and  Dev-C++ 4.9.9.2.

Best regards.

--
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.

Brian Hagen

unread,
Jul 16, 2022, 7:29:39 PMJul 16
to pqc-...@list.nist.gov
"D. J. Bernstein" <d...@cr.yp.to> writes:
> NIST's new report already points to a solution (see page 18):
>
> If the agreements are not executed by the end of 2022, NIST may
> consider selecting NTRU instead of KYBER. NTRU was proposed in 1996,
> and U.S. patents were dedicated to the public in 2007.
>
> (I have no idea how whoever reviewed this could have imagined that
> "2007" was correct. If NTRU had been patent-free in 2007 then why didn't
> people try rolling it out in response to the Snowden revelations? In
> fact, the main NTRU patent expired in 2017, and the company didn't give
> up on the patent until earlier in 2017.
 
What about US7929688B2 and US7773746B2? You've previously said that US7929688B2 is "a potential problem for the 2005 NTRU parameter sets, Streamlined NTRU Prime, the HRSS NTRU KEM, etc."
 
-b

D. J. Bernstein

unread,
Jul 16, 2022, 9:32:08 PMJul 16
to pqc-...@list.nist.gov
Brian Hagen writes:
> What about US7929688B2 and US7773746B2? You've previously said that US7929688B2
> is "a potential problem for the 2005 NTRU parameter sets, Streamlined NTRU
> Prime, the HRSS NTRU KEM, etc."

Yes, https://cr.yp.to/patents/us/7929688.html says that the patent
"might be stretched to cover similar formulas to eliminate decryption
failures in other variants of NTRU, so it's a potential problem" etc.
(Similar comments apply to 7773746.)

"Stretched" is alluding to how patent coverage is expanded via court
procedures, such as _Markman_ hearings and the doctrine of equivalents.
Patent novices think it's enough to say that a patent doesn't literally
apply to any of the proposals at hand; in reality, land mines _can_ blow
up even when you don't step directly on them.

Fortunately, there's prior art directly on point. The same page goes on
to review two papers from the prior art that already eliminated
decryption failures in the original NTRU system:

* One paper is the Crypto 2000 Jaulmes--Joux paper. The only weakness
here is that this paper doesn't explicitly justify the statement
"For appropriate parameter choices, we can ensure that all
coefficients of the polynomial ... lie between −q/2 and q/2". One
would thus have to explain to a judge that anyone of ordinary skill
in the art would have understood how to do this; realistically,
this means convincing the judge that _the judge_ would have
understood how to do this from the information available.

* The other paper is the original 1996 NTRU conference handout, which
has a section "NTRU with 0% decoding failure", and doesn't have the
above weakness. At least in the U.S., conference handouts count as
prior art.

Would Panasonic be able to come up with an interpretation of words of
the patent claims to avoid covering the prior art? Conceivably. Would it
then be able to argue that (e.g.) Google's deployment of ntruhrss701 is
performing substantially the same function in substantially the same way
with substantially the same result?

I don't see how. But this example illustrates that a proper analysis of
patent risks is _much_ more complicated than "NTRU was proposed in 1996,
and U.S. patents were dedicated to the public". As I wrote in my
previous message:

Figuring out what patents are out there, and what's safe from those
patents given the complications of patent law, takes tons of work and
should have been emphasized from the beginning of NISTPQC. ...

I'm concerned about various risks here that were downplayed or
ignored in NIST's report. In particular, the NTRU submission is _not_
exactly the 1996 version of NTRU, so it _could_ be covered by patents
that haven't come to public attention (even if the risks are lower
than for Kyber); also, one should _not_ be confident in the security
of any of these systems.

---D. J. Bernstein
signature.asc

Christopher J Peikert

unread,
Jul 22, 2022, 2:29:09 PMJul 22
to pqc-forum
On Fri, Jul 15, 2022 at 11:32 PM D. J. Bernstein <d...@cr.yp.to> wrote:
The analysis in https://ntruprime.cr.yp.to/warnings.html
indicates that Streamlined NTRU Prime (as in sntrup761, now used by
default in OpenSSH) has somewhat lower patent risks and somewhat lower
security risks than the NTRU submission.

This analysis is sorely lacking in both respects (security and patents).

On security risks:

A proper risk evaluation should account for the amount of scrutiny that has been devoted to a system's mathematical structures and associated problems. Those that have received little scrutiny should be considered risky. See, e.g., what happened to Rainbow -- which was proposed in 2005 -- once it finally underwent sustained analysis in recent years.

NTRU Prime's security relies *entirely* on a rather new structure -- namely, deterministic "small rounding" errors -- that has seen very little public cryptanalytic effort. (See this thread for details.) By contrast, the NTRU submission relies on long-scrutinized "random noise" for its errors. In this respect, NTRU "classic" is less risky.

The above-linked page omits (small) rounding from the risk analysis, shown under "Known attack avenues not ruled out by theorems." The authors might say that this is because rounding is not a *known* attack avenue. But that's only because nobody seems to have seriously tried much. That's no reason to omit it from the risk evaluation -- indeed, it's a source of risk.

On patent risks:

I can't see what justifies the claim that Streamlined NTRU Prime (SNTRUP) "has somewhat lower patent risks" than the NTRU submission. The above-linked table claims no risk to either of them from two known patents, so any difference would have to lie elsewhere. Where?

If anything, the argument that NTRU LPRime, Kyber, and SABER are at risk from patent 9246675 could *also* be applied to SNTRUP -- but not to the NTRU submission.

In essence, the argument is this: the patent covers ciphertext-compression-by-rounding (which SNTRUP uses), and the "doctrine of equivalents" broadens the patent's claims to any underlying "noisy agreement" mechanism known at the time of the patent (LWE, its Ring/Module variants, etc.).

Well, the prior art teaches how to interchange LWE-style and NTRU-style noisy agreement, which SNTRUP uses. See, e.g., this Eurocrypt'11 paper and the January 2012 talk about this STOC 2012 paper ("On-the-Fly Multiparty Computation...")

So, *if* the above argument really puts those other proposals at risk from the patent, then Streamlined NTRU Prime is at risk too. By contrast, the NTRU submission doesn't use rounding-based compression, so the argument doesn't apply to it.

Now, to be absolutely clear: the above argument is deeply flawed, and should not lead us to believe that *any* of the above-named NISTPQC submissions are at real risk from the patent. (The fact that NIST is licensing the patent reduces the risk even further -- at least for the NIST-selected algorithms.)

This is because the patent describes a different method of compression -- not the "drop some bits" rounding used by NISTPQC schemes, which comes from abundant prior art. Courts have repeatedly ruled that the doctrine of equivalents cannot be used to "ensnare" prior art; see, e.g., this review.

Here is some of the prior art that describes "drop some bits" compression for a variety of (Ring/Module-)LWE encryption schemes and other applications; there is likely even more out there:
  • Section 4.2 of this: "it is possible to improve their efficiency (without sacrificing correctness) by discretizing the LWE distribution more ‘coarsely’ using a relatively small modulus q'...";
  • this: "'derandomization' of LWE: deterministic [rounding] errors. Also gives more practical ... encryption";
  • this: "the underlying intuition is that Z_p can 'approximate' Z_q by simple scaling, up to a small error..." and "As a nice byproduct of this technique, the ciphertexts ... become very short";
  • this, explicitly for Ring/Module-LWE (called GLWE therein): "The transformation from c to c' involves simply scaling by (p/q) and rounding..."
Sincerely yours in cryptography,
Chris

D. J. Bernstein

unread,
Jul 22, 2022, 7:12:09 PMJul 22
to pqc-...@list.nist.gov
Christopher J Peikert writes:
> This analysis is sorely lacking in both respects (security and patents).

The specific pieces alleged to be missing are, in fact, in Sections 3.5,
3.6, 3.18, and 5.3 of a paper giving details of the analysis. That paper
is linked from the top of https://ntruprime.cr.yp.to/warnings.html.

For example, regarding "I can't see what justifies the claim that
Streamlined NTRU Prime (SNTRUP) 'has somewhat lower patent risks' than
the NTRU submission":

* Section 3.18 of the paper says "Instability also contributes to
general patent risks" and explains why.

* The corresponding instability lines of the comparison table show
that ntruhrss, ntruhps, and sntrup all changed in 2019.04, but that
sntrup's PKE goes all the way back to 2016.05---the only changes
to sntrup after that were at the CCA layer---while ntruhrss and
ntruhps changed their PKE much more recently.

To be clear, the risks of unknown patents covering, e.g., Google's
ntruhrss deployment aren't anywhere near the risks incurred by Kyber,
which is even less stable (one has to review patents all the way through
October 2020) and starting from major components patented in 2010 and
2012. Maybe NIST has succeeded in buying out those two patents, but
what's being done about the systemic problem? Two landmines disarmed
(hopefully), but Kyber is still stuck in the middle of a minefield!

It's important to avoid underestimating the number of post-quantum
patents out there, the costs of analyzing patent applicability, and the
real-world damage that comes from botching the handling of patents. It
seems that NIST delayed everything by (at least) half a year working on
those two patent buyouts. https://blog.cr.yp.to/20220129-plagiarism.html
reviews the evidence that patents were a major contributor to years of
delay in post-quantum rollout before that.

---D. J. Bernstein
signature.asc

John Mattsson

unread,
Jul 24, 2022, 8:13:53 AMJul 24
to pqc-...@list.nist.gov

I have talked to our lawyers many times. What they say is that public discussion on specific alleged patents typically benefits the patent holder.

 

Cheers,

John

Billy Brumley

unread,
Jul 24, 2022, 12:38:29 PMJul 24
to pqc-...@list.nist.gov
> I have talked to our lawyers many times. What they say is that public discussion on specific alleged patents typically benefits the patent holder.

There is a lot of truth to this, and Dan even writes it down in his
blog post he linked https://blog.cr.yp.to/20220129-plagiarism.html
(which I don't encourage anyone to read who thinks they might be at
risk for infringing on PQC-related IP)

> Actually, because intentional patent infringement is subjected to triple damages under patent law, the lawyers at big companies try to avoid sending email that could end up making any subsequent infringement sound intentional.

Despite what Dan wrote, it's not just the lawyers. When part of your
(engineering or academic) job is protecting IP by internally filing
Invention Disclosures (IDFs), companies / employers actively
discourage you from searching for prior art for exactly those reasons.
In fact they encourage you to file IDFs for any of your ideas: Why
would the company seek a patent, if they knew it was covered already?
This provides a paper trail to later argue against the amplified
damages of intentional patent infringement, if needed. (Especially
because, in the industry case, the IDF and any subsequent patent is
commonly just a cover-your-ass strategy, since you've already
implemented / deployed the idea in question.)

For those reasons, I agree with John's company's lawyers.

Cheers,

BBB

Christopher J Peikert

unread,
Jul 24, 2022, 10:53:43 PMJul 24
to pqc-forum
(Breaking this out into its own thread, the topic being the following statement from this message:

"The analysis in https://ntruprime.cr.yp.to/warnings.html indicates that Streamlined NTRU Prime (as in sntrup761, now used by default in OpenSSH) has somewhat lower patent risks and somewhat lower security risks than the NTRU submission."

I replied with a critique of that analysis, on both security and patents. I'm now responding to a reply to that message.)

On Fri, Jul 22, 2022 at 7:12 PM D. J. Bernstein <d...@cr.yp.to> wrote:
Christopher J Peikert writes:
> This analysis is sorely lacking in both respects (security and patents).

The specific pieces alleged to be missing are, in fact, in Sections 3.5,
3.6, 3.18, and 5.3 of a paper giving details of the analysis. That paper
is linked from the top of https://ntruprime.cr.yp.to/warnings.html.

As I said: this analysis is sorely lacking. It does not substantiate the claim that Streamlined NTRU Prime (SNTRUP) is superior to the NTRU submission on security and patent risks. Mainly, this is because it omits or unjustifiably dismisses the significant ways in which SNTRUP has *higher* risks. But it also invites specious conclusions of SNTRUP's superiority on certain risks, where a closer look shows that NTRU is clearly better off.

(In my view, the omitted and dismissed risks outweigh the ones for which SNTRUP *might* really be superior, but that's a matter of judgement.)

The rest of this message gives an expanded critique of the analysis, focusing mostly on the cited sections, along with a much more thorough investigation of the NTRU-vs-SNTRUP comparison.

Summary on security risks:
  • Section 3.5 does not account for the larger risk (very little scrutiny) of SNTRUP’s small-rounding errors, versus NTRU’s (long-scrutinized) random errors. Instead, it implicitly but unjustifiably treats them as having indistinguishable risk.
  • On other security risks, none of the other three cited sections shows that SNTRUP is superior. Two sections fail to show any advantage in either direction. And for the third section (on stability), a proper evaluation favors NTRU, owing to its overall much-older design and substantial advantage in scrutiny.
Summary on patent risks:
  • The claimed larger risk of NTRU vs SNTRUP is based entirely on a crude comparison of their underlying PKEs' publication dates, and the hypothetical of a relevant patent being filed in the interim. (NB: the table assigns a date to NTRU that looks wrong by ~21 months, about 60% of the claimed gap.)
  • Merely comparing most-recent-publication dates is of very little value in assessing actual risks. Looking at the substance of the PKEs:
    • NTRU's is identical to the original 1998 NTRU proposal, except for two small tweaks whose ideas date back to 2006 or earlier (in related contexts).
    • SNTRUP's uses a technique that was first proposed in 2011.
    • So, NTRU's window of vulnerability to patents is *extremely* narrow, if not fully closed, while SNTRUP's window is larger.
  • Moreover, the analysis omits that for a *known* patent, *its own* (dubious) argument about the risks to other proposals would also apply to SNTRUP, but not to NTRU.
Details on security risks:

Section 3.5 describes the criteria for “known attack avenue,” and says why (small) rounding doesn’t currently qualify as one. This is not responsive to what I wrote about rounding, which did not even dispute this categorization.

What I wrote is that the lack of a known attack avenue does *not* justify omitting small-rounding from the risk evaluation, because so little effort has been put into finding such an avenue.

Indeed, SNTRUP's security relies *entirely* on small rounding. This is a rather new structure that has received very little public scrutiny, and therefore represents a significant amount of uncertainty/risk. I don't know of any dispute about these points from anyone. (If there is, I would like to know.)

Section 3.6 is about implementation risks, and explains why they are *not* included in the risk table. In short: assessment alone is a major unresolved research question, and the targets are moving. It doesn’t mention NTRU at all. I don’t see how this sheds any light on the comparison with SNTRUP.

Section 5.3 concerns proofs and their (in)applicability; there’s no contribution to the NTRU-vs-SNTRUP comparison here either.

Section 3.18 addresses both security and patent risks of "(PKE) instability." For security, the motivation for stability is the need for scrutiny. In this respect, NTRU clearly has the advantage: it is much older and has seen vastly more scrutiny than SNTRUP. (See below for details of their PKEs and the timing.)

Details on patent risks (Sections 3.17 and 3.18):
 
For example, regarding "I can't see what justifies the claim that
Streamlined NTRU Prime (SNTRUP) 'has somewhat lower patent risks' than
the NTRU submission":

   * Section 3.18 of the paper says "Instability also contributes to
     general patent risks" and explains why.

   * The corresponding instability lines of the comparison table show
     that ntruhrss, ntruhps, and sntrup all changed in 2019.04, but that
     sntrup's PKE goes all the way back to 2016.05---the only changes
     to sntrup after that were at the CCA layer---while ntruhrss and
     ntruhps changed their PKE much more recently.

Ok, so the extent of the claimed NTRU-vs-SNTRUP risk difference is: the publication dates of their underlying PKEs (2019.04 vs 2016.05, supposedly), and the hypothetical of a patent filed during that gap which would cover some part of the later PKE, while still avoiding the prior art.

Again: this analysis is sorely lacking, to say the least.

Firstly, it does not consider the actual designs of the PKEs, nor the prior art and its dates, nor the nature of the changes (if any) relative to the prior art. Let's look at those now.

The very first paragraph of the 2019 NTRU submission says "Modulo a few small changes introduced by [HRSS'17], the correct DPKE that we describe here is obtained by applying the [NTRU] preprint's transformations for determinism and correctness to the PPKE from ANTS'98."

If that’s true, then NTRU’s PKE design should be dated no later than HRSS's publication date of 2017.07, not 2019.04. That's a ~21 month difference, or about 60% of the gap stated in the risks table.

More importantly, HRSS’s small changes consist entirely of:
  1. The obvious, old, and widely used idea of sampling small coefficients independently (instead of with fixed weight), and
  2. A key-generation tweak that makes f*h a multiple of (x-1), for security and simplicity reasons. This also is an old idea: e.g., Peikert-Rosen’06 uses the same kind of trick for similar reasons (in a different context), and it likely appears in other old works too.
In sum, this leaves an *extremely* narrow window, if any, for a hypothetical patent that somehow covers HRSS’s small tweaks, while also avoiding all