On Post-Quantum Algorithms
Disclaimer
This is supposed to be a collection of patents that have been mentioned to possibly afect the current post-quantum standardization candidates from the NIST challenge and the migration to post-quantum secure algorithms and schemes. This list is maintained by computer scientists without any legal background and shall only be used for informational purposes. To identify if some patents to apply to certain algorithms or use-cases, a separate legal analysis by experts should be carried out.
U.S.- and European Patent from „CNRS“
The France-based “Centre National de la Recherche Scientifique” holds patents:
- US9094189 (02/2010) “Cryptographic method for communicating confidential information”[1],
- EP2537284 (02/2010) “Cryptographic method for communicating confidential information”[2].
This patent is also often referred to as the “Gaborit&Aguilar-Melchor patent” named after its inventors. The patent holder claims that the patent applies to “one or more proposals” that were submitted to the NIST PQC standardization process[3],[5].
Damien Stehlé and Vadim Lyubashevsky released an analysis followed by the claim that the CNRS patent does not apply to Kyber and SABER[4],[5].
On July 5th, 2022, one day after the announcement of the NIST PQC processes winners, CNRS published a statement titled „License Agreement between the NIST, the CNRS and the University of Limoges: The International Impact of French Research Excellence“. This agreement states, that implementers of said PQC algorithms are not required to obtain a separate license under the CNRS patent family. [31]
U.S. Patents from „Algo Consulting Inc.“ and Inventor Jintai Ding
For the NIST submission Rainbow[6], two patents from the scheme’s creators/inventors exist:
- US7961876 (06/2011) “Method to produce new multivariate public key cryptosystems”[7],
- US7158636 (01/2007) “Multivariate cryptosystem”[8].
However, the patent holder waived any compensation by signing the mandatory intellectual property statement by NIST before submitting Rainbow into the standardization process[9].
At the time of the announcement of the NIST PQC competition winners, Dustin Moody from NIST published the following statement: „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.“ [29]
U.S. Patent from „Onboard Security Inc.“
For the NIST submission Falcon, one patent claims coverage
- US7308097 (12/2022) „Digital signature and authentication method and apparatus“.
Chinese Patents from „Shanghai Hu Min Block Chain Science and Technology Co., Ltd.“
China-based company “Shanghai Hu min block chain science and Technology Co., Ltd” holds patents:
- CN108173643 (11/2016): “Efficient secret key consensus transmission method”[10],
- CN107566121 (11/2016): “A kind of efficient secret common recognition method”[11].
According to the patent holder, Kyber[12] and SABER[13] fall within their AKCN mechanism[14],[15] introduced in 2016. They argue that the “conciliation/reconciliation-mechanisms” of Kyber and AKCN-LWE or SABER and AKCN-MLWE are essentially the same, apart from minor differences. Similarly, this applies to all KEMs based on LWE/MLWE/LWR/MLWR like NewHope[16]. However, Frodo[17], for example, does not fall into this patent, as the mechanism in Frodo is not optimal.
However, the inventor 赵运磊 (Yunlei Zhao) made the following statements on May 12th, 2022:
“With respect to the patents, we ever mentioned in the KCL submission we would like to give up all the patents for using our proposals. We hold the patents only for protection. This position applies to all of our proposals.”[18]
“Finally, we would like to stress again we hold all the patents only for protection against credit (not for economic reasons). We hope the above clarifications could make the situation clearer.”[19]
South Korean and U.S. Patents from „Crypto Lab Inc.“
The South Korea-based company “Crypto Lab Inc.” holds patent:
- KR101905689 (11/2016): “Calculating apparatus for encrypting message by public key and method thereof”[20],
and has a pending application for patent:
- US20200169384 (11/2016): “Calculation device for encryption using public key and encryption method thereof”[21].
These patents are similar but make slightly different claims.
These patents predate the NISTPQC submission deadline. It is unclear if these patents apply to any NIST PQC candidate or if they affect the standardization process in any way[22].
U.S. and European Patents from „Koninklijke Philips NV“
Netherlands-based company “Koninklijke Philips NV” holds patents:
- US11050557 (05/2017): “Key agreement devices and method”[23],
- EP3698515 (10/2017): “Configurable device for lattice-based cryptography”[24].
These patents predate the NISTPQC submission deadline. It is unclear if these patents apply to any NIST PQC candidate or if they affect the standardization process in any way[22].
U.S. Patents from „ISARA Corporation“
The Canada-based company “ISARA Corporation” holds patents:
- US9660978 (08/2016): “Using a Digital Certificate with Multiple Cryptosystems”[25],
- US10425401 (10/2018): “Extensions for Using a Digital Certificate with Multiple Cryptosystems”[26].
They are comprised of 39 and 17 claims respectively. This makes it hard to construct a hybrid PKI which does not violate any of the patents.
As of March 2020, the patent application for US9660978 to the European Patent Office as EP17838243 has been withdrawn[27]. However, the application for US10425401 as EP19878832 is still pending[28].
ISARA Corporation published a statement on their website regarding a potential collision of their patents with the NIST PQC standardizaton process [30].
[1] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=9094189.PN.
[2] https://worldwide.espacenet.com/patent/search/family/042753478/publication/EP2537284B1?q=pn%3DEP2537284B1
[3] https://www.cnrsinnovation.com/?lang=en
[4] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/2Xv0mrF9lVo/m/e0oKQhIIBwAJ
[5] https://eprint.iacr.org/2021/1364.pdf
[6] https://cryptoeng.github.io/pqdb/detail/rainbow
[7] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=7961876.PN.
[8] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=7158636.PN.
[9] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/ip-statements/Rainbow-Statements.pdf
[10] https://patents.google.com/patent/CN108173643B/en
[11] https://patents.google.com/patent/CN107566121A/en
[12] https://cryptoeng.github.io/pqdb/detail/kyber
[13] https://cryptoeng.github.io/pqdb/detail/saber
[14] https://arxiv.org/abs/1611.06150
[15] https://arxiv.org/abs/2109.02893
[16] https://cryptoeng.github.io/pqdb/detail/newhope
[17] https://cryptoeng.github.io/pqdb/detail/frodo
[18] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/aj31YoWWBAAJ
[19] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/7HJShM2dBAAJ
[20] https://patents.google.com/patent/KR101905689B1/en
[21] https://patents.google.com/patent/US20200169384A1/en
[22] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/6Psr4bFHHgk/m/3rDADGcMAQAJ
[23] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=11050557.PN.
[24] https://worldwide.espacenet.com/patent/search/family/063834029/publication/EP3698515B1?q=pn%3DEP3698515B1
[25] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=9660978.PN.
[26] https://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/srchnum.html&r=1&f=G&l=50&d=PALL&s1=10425401.PN.
[27] https://register.epo.org/application?lng=en&number=EP17838243
[28] https://register.epo.org/application?lng=en&number=EP19878832
[29] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/G0DoD7lkGPk/m/hFdKaHp-AgAJ
[30] https://web.archive.org/web/20201101181903/https://www.isara.com/nist-grant.html
[31] https://www.cnrs.fr/en/license-agreement-between-nist-cnrs-and-university-limoges-international-impact-french-research