目次

NIST IR 8309 日本語訳

英語タイトル : Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process
日本語タイトル : NIST 耐量子暗号標準化プロセス第 2 ラウンドの状況報告
公開日 : 2020-07-22
原文URL : https://csrc.nist.gov/pubs/ir/8309/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 320 / 320 ブロック

[要約] NIST IR 8309 は、NIST が公開された競技会形式のプロセスにより進めている耐量子暗号(PQC)の公開鍵暗号アルゴリズムの標準化について、第 2 ラウンドの状況を報告するものです。このプロセスは 2017年に 69 のアルゴリズム候補で始まり、NIST は 26 のアルゴリズムを第 2 ラウンドに進めるものとして選定しました。報告書は、第 2 ラウンドの候補について、一般からのフィードバックと内部レビューに基づく評価と選定のプロセスを説明し、26 のアルゴリズム候補を要約したうえで、第 3 ラウンドに進むものを示します。第 3 ラウンドの公開鍵暗号化および鍵確立のファイナリストは Classic McEliece、CRYSTALS-KYBER、NTRU、SABER で、デジタル署名のファイナリストは CRYSTALS-DILITHIUM、FALCON、Rainbow であり、8 つの代替候補も第 3 ラウンドに進みます。

NISTIR 8309

NISTIR 8309

Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process

NIST 耐量子暗号標準化プロセス第 2 ラウンドの状況報告

Gorjan Alagic Jacob Alperin-Sheriff Daniel Apon David Cooper Quynh Dang John Kelsey Yi-Kai Liu Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Daniel Smith-Tone

Gorjan Alagic Jacob Alperin-Sheriff Daniel Apon David Cooper Quynh Dang John Kelsey Yi-Kai Liu Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Daniel Smith-Tone

This publication is available free of charge from:

本刊行物は次の場所から無料で入手できます:

https://doi.org/10.6028/NIST.IR.8309

https://doi.org/10.6028/NIST.IR.8309

NISTIR 8309

NISTIR 8309

Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process

NIST 耐量子暗号標準化プロセス第 2 ラウンドの状況報告

Gorjan Alagic Jacob Alperin-Sheriff* Daniel Apon David Cooper Quynh Dang John Kelsey Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Daniel Smith-Tone Computer Security Division Information Technology Laboratory

Gorjan Alagic Jacob Alperin-Sheriff* Daniel Apon David Cooper Quynh Dang John Kelsey Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Daniel Smith-Tone Computer Security Division Information Technology Laboratory

Yi-Kai Liu Applied and Computational Mathematics Division Information Technology Laboratory

Yi-Kai Liu Applied and Computational Mathematics Division Information Technology Laboratory

*Former employee; all work for this publication was done while at NIST

*元職員。本刊行物のすべての作業は NIST 在職中に行われました

This publication is available free of charge from:

本刊行物は次の場所から無料で入手できます:

https://doi.org/10.6028/NIST.IR.8309

https://doi.org/10.6028/NIST.IR.8309

July 2020

2020 年 7 月

U.S. Department of Commerce Wilbur L. Ross, Jr., Secretary

米国商務省 Wilbur L. Ross, Jr. 長官

National Institute of Standards and Technology

National Institute of Standards and Technology

Walter Copan, NIST Director and Under Secretary of Commerce for Standards and Technology

Walter Copan、NIST 所長兼商務次官(標準・技術担当)

National Institute of Standards and Technology Interagency or Internal Report 8309 39 pages (July 2020)

National Institute of Standards and Technology Interagency or Internal Report 8309 39 ページ(2020 年 7 月)

This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8309

本刊行物は次の場所から無料で入手できます: https://doi.org/10.6028/NIST.IR.8309

Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by NIST, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.

本文書では、実験の手順や概念を適切に説明するために、特定の商業的な事業体、機器、または資材を明示している場合があります。このような明示は、NIST による推奨や是認を意図するものではなく、また、それらの事業体、資材、または機器が目的に照らして必ずしも最良であることを意図するものでもありません。

There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, federal agencies may wish to closely follow the development of these new publications by NIST.

本刊行物には、NIST が法令で定められた責務に従って現在策定中のほかの刊行物への言及が含まれる場合があります。本刊行物の情報(概念や方法論を含む)は、そうした関連刊行物の完成前であっても、連邦機関が利用してもよいです。したがって、各刊行物が完成するまでは、現行の要件、ガイドライン、および手順が存在する場合には、それらが引き続き有効です。計画および移行のため、連邦機関は、NIST によるこれらの新しい刊行物の策定状況を注意深く追うことを検討してもよいです。

Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. Many NIST cybersecurity publications, other than the ones noted above, are available at https://csrc.nist.gov/publications.

組織は、パブリックコメント期間中にすべてのドラフト刊行物を確認し、NIST にフィードバックを提供することが推奨されています。上記以外にも、NIST の多くのサイバーセキュリティ刊行物が https://csrc.nist.gov/publications で入手できます。

Comments on this publication may be submitted to:

本刊行物に対するコメントの提出先:

National Institute of Standards and Technology Attn: Computer Security Division, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930 Email: pqc-comments@nist.gov

National Institute of Standards and Technology Attn: Computer Security Division, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930 Email: pqc-comments@nist.gov

All comments are subject to release under the Freedom of Information Act (FOIA).

すべてのコメントは、情報自由法(FOIA)に基づく公開の対象となります。

Reports on Computer Systems Technology

コンピュータシステム技術に関する報告書

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in federal information systems.

National Institute of Standards and Technology(NIST)の Information Technology Laboratory(ITL)は、国の測定・標準インフラストラクチャに関する技術的リーダーシップを提供することで、米国経済と公共の福祉を促進しています。ITL は、情報技術の発展と生産的な利用を推進するため、テスト、テスト方法、参照データ、概念実証実装、および技術分析を開発しています。ITL の責務には、連邦情報システムにおける国家安全保障関連以外の情報について、費用対効果の高いセキュリティとプライバシーを実現するための、管理面・運用面・技術面・物理面の標準とガイドラインの策定が含まれます。

Abstract

要旨

The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify one or more additional digital signatures, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

National Institute of Standards and Technology は、公開された競技会形式のプロセスにより、1 つ以上の公開鍵暗号アルゴリズムを選定しているところです。新しい公開鍵暗号標準では、Federal Information Processing Standard(FIPS)186-4『Digital Signature Standard (DSS)』、NIST Special Publication(SP)800-56A Revision 3『Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography』、および SP 800-56B Revision 2『Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography』を補完するものとして、1 つ以上の追加のデジタル署名、公開鍵暗号化、および鍵確立のアルゴリズムが規定されます。これらのアルゴリズムは、量子コンピューターの出現後を含め、予見できる将来にわたって機微な情報を保護できるものとなることが意図されています。

The NIST Post-Quantum Cryptography Standardization Process began in 2017 with 69 candidate algorithms that met both the minimum acceptance criteria and submission requirements. The first round lasted until January 2019, during which candidate algorithms were evaluated based on their security, performance, and other characteristics. NIST selected 26 algorithms to advance to the second round for more analysis. This report describes the evaluation and selection process, based on public feedback and internal review, of the second-round candidates. The report summarizes the 26 second-round candidate algorithms and identifies those selected to move forward to the third round of the competition. The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER. The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow. These finalists will be considered for standardization at the end of the third round. In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+. These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round. NIST hopes that the announcement of these finalists and additional candidates will serve to focus the cryptographic community’s attention during the next round.

NIST 耐量子暗号標準化プロセスは、最低限の受理基準と提出要件の両方を満たした 69 のアルゴリズム候補をもって、2017 年に始まりました。第 1 ラウンドは 2019 年 1 月まで続き、その間、候補アルゴリズムは安全性、性能、およびその他の特性に基づいて評価されました。NIST は、さらなる分析のため、26 のアルゴリズムを第 2 ラウンドに進めるものとして選定しました。本報告書は、第 2 ラウンドの候補について、一般からのフィードバックと内部レビューに基づく評価と選定のプロセスを説明します。また、第 2 ラウンドの 26 のアルゴリズム候補を要約し、競技会の第 3 ラウンドに進むものとして選ばれたものを示します。第 3 ラウンドの公開鍵暗号化および鍵確立アルゴリズムのファイナリストは、Classic McEliece、CRYSTALS-KYBER、NTRU、および SABER です。デジタル署名のファイナリストは、CRYSTALS-DILITHIUM、FALCON、および Rainbow です。これらのファイナリストは、第 3 ラウンドの終了時に標準化の対象として検討されます。加えて、8 つの代替候補アルゴリズム(BIKE、FrodoKEM、HQC、NTRU Prime、SIKE、GeMSS、Picnic、および SPHINCS+)も第 3 ラウンドに進みます。これらの追加候補も標準化の対象として引き続き検討されますが、第 3 ラウンドの終了時に標準化される可能性は低いです。NIST は、これらのファイナリストと追加候補の発表が、次のラウンドの間、暗号コミュニティの注意を集中させる助けとなることを期待しています。

Keywords

キーワード

cryptography; digital signatures; key-establishment mechanism (KEM); post-quantum cryptography; public-key encryption; quantum resistant; quantum safe.

暗号技術、デジタル署名、鍵確立メカニズム(KEM)、耐量子暗号、公開鍵暗号化、量子耐性、量子安全。

Supplemental Content

補足コンテンツ

The NIST Post-Quantum Cryptography Standardization Process webpage is available at:

NIST 耐量子暗号標準化プロセスのウェブページは、次の場所にあります:

https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization

https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization

Acknowledgments

謝辞

NIST would like to thank all of the candidate submission teams who developed, designed, and analyzed post-quantum public-key algorithms and prepared detailed submission packages describing their algorithms.

NIST は、耐量子公開鍵アルゴリズムを開発・設計・分析し、アルゴリズムを詳細に記述した提出パッケージを用意した、すべての候補提出チームに感謝します。

NIST is also grateful for the efforts of those in the cryptographic community who provided security, implementation, and performance analyses of the candidate algorithms during the first and second rounds. NIST would not be able to select new post-quantum public-key algorithms for standardization without the combined efforts of these individuals and the algorithm submitters.

NIST はまた、第 1 ラウンドおよび第 2 ラウンドの間に候補アルゴリズムの安全性・実装・性能の分析を提供した暗号コミュニティの方々の尽力にも感謝します。こうした方々とアルゴリズム提出者の協力がなければ、NIST は標準化のための新しい耐量子公開鍵アルゴリズムを選定できません。

The authors of this report are also appreciative of the efforts by other members of NIST’s Post-Quantum Cryptography team who reviewed candidate algorithms, analyses, and public comments; performed testing; provided technical and administrative support; and participated in numerous meetings to discuss the selection of the second-round candidates. They are Larry Bassham, Lily Chen, Thinh Dang, Morris Dworkin, Sara Kerman, and Andrew Regenscheid.

本報告書の著者は、候補アルゴリズム、分析、およびパブリックコメントをレビューし、テストを実施し、技術面・事務面の支援を提供し、第 2 ラウンドの候補の選定を議論する数多くの会議に参加した、NIST の耐量子暗号チームのほかのメンバーの尽力にも感謝します。それらのメンバーは、Larry Bassham、Lily Chen、Thinh Dang、Morris Dworkin、Sara Kerman、Andrew Regenscheid です。

Table of Contents

目次

1 Introduction

1 はじめに

In recent years, there has been steady progress in building quantum computers. If large-scale quantum computers are realized, they would threaten the security of many commonly-used public-key cryptosystems. Key-establishment schemes and digital signatures based on factoring, discrete logarithms, and elliptic curve cryptography will be the most severely affected. (Symmetric cryptographic primitives, such as block ciphers and hash functions, will only be mildly affected.) In response, there has been intense research into post-quantum cryptography. This science is the study of cryptosystems that would be secure against adversaries who have both quantum and classical computers and that can be deployed without drastic changes to existing communication networks and protocols.

近年、量子コンピューターの構築は着実に進展しています。大規模な量子コンピューターが実現すれば、広く使われている多くの公開鍵暗号システムの安全性が脅かされることになります。素因数分解、離散対数、および楕円曲線暗号に基づく鍵確立方式とデジタル署名が、最も深刻な影響を受けます。(ブロック暗号やハッシュ関数などの共通鍵暗号プリミティブへの影響は、軽微にとどまります。)これを受けて、耐量子暗号の研究が活発に行われています。この科学は、量子コンピューターと古典コンピューターの両方を持つ攻撃者に対して安全であり、かつ既存の通信ネットワークやプロトコルに大幅な変更を加えずに展開できる暗号システムを研究するものです。

Motivated by these considerations, the National Institute of Standards and Technology (NIST) is in the process of selecting public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify one or more additional algorithms for digital signatures, public-key encryption, and key-establishment. The new standards will augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS) [1], as well as Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography [2], and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography [3]. It is intended that these algorithms will be capable of protecting sensitive U.S. Government information well into the foreseeable future, including after the advent of quantum computers. The competition-like process will be referred to as the NIST Post-Quantum Cryptography (PQC) Standardization Process hereafter in this document.

こうした考慮から、National Institute of Standards and Technology(NIST)は、公開された競技会形式のプロセスにより、公開鍵暗号アルゴリズムを選定しているところです。新しい公開鍵暗号標準では、デジタル署名、公開鍵暗号化、および鍵確立のための 1 つ以上の追加のアルゴリズムが規定されます。新しい標準は、Federal Information Processing Standard(FIPS)186-4、Digital Signature Standard (DSS) [1]、Special Publication(SP)800-56A Revision 3、Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography [2]、および SP 800-56B Revision 2、Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography [3] を補完するものです。これらのアルゴリズムは、量子コンピューターの出現後を含め、予見できる将来にわたって米国政府の機微な情報を保護できるものとなることが意図されています。この競技会形式のプロセスを、本文書では以後、NIST 耐量子暗号(PQC)標準化プロセスと呼びます。

The NIST PQC Standardization Process began in December 2016, when NIST issued a public call for submissions of post-quantum public-key cryptographic algorithms [4]. A total of 82 candidates were submitted by the November 2017 deadline. In December 2017, NIST announced that 69 of these candidates met both the submission requirements and the minimum acceptability criteria and were accepted into the first round of the standardization process. Submission packages for the first-round candidates were posted online at https://www.nist.gov/pqcrypto for public review and comment.

NIST PQC 標準化プロセスは、2016 年 12 月に NIST が耐量子公開鍵暗号アルゴリズムの提出を一般に募った [4] ことで始まりました。2017 年 11 月の締め切りまでに、合計 82 の候補が提出されました。2017 年 12 月、NIST は、これらのうち 69 の候補が提出要件と最低限の受理可能性基準の両方を満たしており、標準化プロセスの第 1 ラウンドに受理されたことを発表しました。第 1 ラウンドの候補の提出パッケージは、一般によるレビューとコメントのために https://www.nist.gov/pqcrypto でオンライン公開されました。

In January 2019, based on public feedback and internal reviews of the candidates, NIST selected 26 algorithms to move on to the second round of the standardization process [5]. These algorithms were viewed as the most promising candidates for eventual standardization. During the second round, these candidates were subjected to more detailed analysis by NIST and the broader cryptographic community. This analysis included more thorough checking of the theoretical and empirical evidence used to justify the security of these cryptosystems, more careful benchmarking of the performance of these algorithms using optimized implementations on a variety of hardware platforms and under realistic conditions, and consideration of other factors that could aid or hinder the practical deployment of these cryptosystems.

2019 年 1 月、NIST は、一般からのフィードバックと候補の内部レビューに基づき、26 のアルゴリズムを標準化プロセスの第 2 ラウンドに進めるものとして選定しました [5]。これらのアルゴリズムは、最終的な標準化に向けて最も有望な候補とみなされたものです。第 2 ラウンドの間、これらの候補は NIST とより広い暗号コミュニティによって、より詳細な分析を受けました。この分析には、これらの暗号システムの安全性を裏付ける理論的・経験的な証拠のより徹底した確認、さまざまなハードウェアプラットフォーム上で、現実的な条件の下で最適化された実装を用いた、これらのアルゴリズムの性能のより慎重なベンチマーク、およびこれらの暗号システムの実用的な展開を助けうる、あるいは妨げうるその他の要因の検討が含まれていました。

The second round began on January 30, 2019, and continued until July 22, 2020. The Second NIST PQC Standardization Conference was held in Santa Barbara, CA on August 22-24, 2019, co-located with the CRYPTO 2019 conference. Each submission team was invited to present an update on their candidate algorithm. In addition, several researchers presented work that was relevant to the PQC standardization process. NIST also held an open discussion session to gather input from attendees. As in the first round, NIST received much feedback from the cryptographic community.

第 2 ラウンドは 2019 年 1 月 30 日に始まり、2020 年 7 月 22 日まで続きました。2019 年 8 月 22 日から 24 日にかけて、CRYPTO 2019 カンファレンスとの併催で、第 2 回 NIST PQC 標準化カンファレンスがカリフォルニア州サンタバーバラで開催されました。各提出チームは、自らの候補アルゴリズムの最新状況を発表するよう招かれました。加えて、PQC 標準化プロセスに関連する研究を数名の研究者が発表しました。NIST は、参加者の意見を集めるための公開討論セッションも開きました。第 1 ラウンドと同様に、NIST は暗号コミュニティから多くのフィードバックを受け取りました。

After careful deliberation and analysis, NIST has selected seven finalists and eight alternates to move on to the third round. NIST intends to select a small number of the finalists for standardization at the end of the third round. In addition, NIST expects to standardize a small number of the alternate candidates (most likely at a later date).

慎重な検討と分析を経て、NIST は 7 つのファイナリストと 8 つの代替候補を第 3 ラウンドに進めるものとして選定しました。NIST は、第 3 ラウンドの終了時に、ファイナリストのうちごく少数を標準化の対象として選定する予定です。加えて NIST は、代替候補のうちごく少数も(おそらくは後の時期に)標準化することを見込んでいます。

Below is a timeline of major events with respect to the NIST PQC Standardization Process to date.

以下は、これまでの NIST PQC 標準化プロセスに関する主要な出来事の年表です。

Table 1: NIST PQC Standardization Process Timeline

表 1: NIST PQC 標準化プロセスの年表

April 2-3, 2015Workshop on Cybersecurity in a Post-Quantum World, NIST, Gaithersburg, MD
February 24, 2016PQC Standardization: Announcement and outline of NIST’s Call for Submissions presentation given at PQCrypto 2016 [5]
April 28, 2016NISTIR 8105, Report on Post-Quantum Cryptography, released [6]
December 20, 2016Federal Register Notice – Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms [7]
November 30, 2017Submission Deadline for NIST PQC Standardization Process
December 20, 2017First-round candidates announced. The public comment period on the first-round candidates began.
April 11-13, 2018First NIST PQC Standardization Conference, Ft. Lauderdale, FL [8]
January 30, 2019Second-round candidates announced. NISTIR 8240, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process [9], released. The public comment period on the second-round candidates began.
April 1, 2019Deadline for updated submission packages for the second round
August 22-24, 2019Second NIST PQC Standardization Conference, Santa Barbara, CA
April 15, 2020NIST invited comments from submitters and the community to inform its decision-making process for the selection of third-round candidates.
July 22, 2020Third round finalists and alternate candidates announced. The public comment period on the third round began. NISTIR 8309, Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process, released.
2015 年 4 月 2 日〜3 日量子計算時代におけるサイバーセキュリティに関するワークショップ、NIST、メリーランド州ゲイザースバーグ
2016 年 2 月 24 日PQC 標準化:PQCrypto 2016 で行われた NIST の提出募集に関する発表および概要のプレゼンテーション [5]
2016 年 4 月 28 日NISTIR 8105、Report on Post-Quantum Cryptography を公開 [6]
2016 年 12 月 20 日連邦官報告示 ― 公開鍵耐量子暗号アルゴリズムの候補推薦募集の発表 [7]
2017 年 11 月 30 日NIST PQC 標準化プロセスの提出期限
2017 年 12 月 20 日第 1 ラウンドの候補を発表。第 1 ラウンドの候補に対するパブリックコメント期間が開始。
2018 年 4 月 11 日〜13 日第 1 回 NIST PQC 標準化会議、フロリダ州フォートローダーデール [8]
2019 年 1 月 30 日第 2 ラウンドの候補を発表。NISTIR 8240、Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process [9] を公開。第 2 ラウンドの候補に対するパブリックコメント期間が開始。
2019 年 4 月 1 日第 2 ラウンド用の更新版提出パッケージの期限
2019 年 8 月 22 日〜24 日第 2 回 NIST PQC 標準化会議、カリフォルニア州サンタバーバラ
2020 年 4 月 15 日NIST は、第 3 ラウンドの候補を選定する意思決定プロセスに資するため、提出者とコミュニティからのコメントを募りました。
2020 年 7 月 22 日第 3 ラウンドのファイナリストと代替候補を発表。第 3 ラウンドに対するパブリックコメント期間が開始。NISTIR 8309、Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process を公開。

1.1 Purpose and Organization of this Document

1.1 本文書の目的と構成

The purpose of this document is to report on the second round of the NIST PQC Standardization Process. The report is organized as follows.

本文書の目的は、NIST PQC 標準化プロセスの第 2 ラウンドについて報告することです。本報告書の構成は次のとおりです。

Section 2 enumerates the candidates that were included in the second round. A description of the evaluation criteria and selection process used to ultimately select the third-round finalists and alternate candidates is then provided. The third-round finalists and alternates are named.

第 2 節では、第 2 ラウンドに含まれた候補を列挙します。続いて、第 3 ラウンドのファイナリストと代替候補を最終的に選定するために用いた評価基準と選定プロセスを説明し、第 3 ラウンドのファイナリストと代替候補を挙げます。

Section 3 summarizes each of the second-round candidates. For each candidate, there is a brief description of the algorithm and its strengths, as well as characteristics that might be disadvantageous. This report presents reasons why candidate algorithms were selected or not selected for the third round.

第 3 節では、第 2 ラウンドの各候補を要約します。各候補について、アルゴリズムとその長所、および不利になりうる特性を簡潔に説明します。本報告書は、候補アルゴリズムが第 3 ラウンドに選ばれた理由、または選ばれなかった理由を示します。

Section 4 describes the next steps in the NIST PQC Standardization Process and the evaluation process for selecting algorithms that will be standardized.

第 4 節では、NIST PQC 標準化プロセスにおける次のステップと、標準化するアルゴリズムを選定するための評価プロセスを説明します。

2 Evaluation Criteria and the Selection Process

2 評価基準と選定プロセス

2.1 Acceptance of the Second-Round Candidates

2.1 第 2 ラウンド候補の受理

NIST selected 26 candidate algorithms for the second round. Of the 26 candidates, 17 were key-establishment mechanisms (KEMs) or public-key encryption schemes, while nine were digital signatures. Submission teams were allowed to make minor modifications and re-submit their packages, which had to meet the same requirements as the original submissions. Four of the candidates were mergers of first-round algorithms: LEDAcrypt (merged from LEDAkem and LEDApkc), NTRU (merged from NTRUEncrypt and NTRU-HRSS-KEM), ROLLO (merged from LAKE, LOCKER, and Ouroboros-R), and Round5 (merged from Hila5 and Round2). The complete updated specifications were posted on www.nist.gov/pqcrypto on April 10, 2019, for public review.

NIST は、第 2 ラウンドに進める候補アルゴリズムとして 26 を選定しました。26 の候補のうち、17 が鍵確立メカニズム(KEM)または公開鍵暗号化方式であり、9 がデジタル署名でした。提出チームは、軽微な修正を加えてパッケージを再提出することが認められましたが、そのパッケージは元の提出と同じ要件を満たす必要がありました。候補のうち 4 つは、第 1 ラウンドのアルゴリズムの統合でした。LEDAcrypt(LEDAkem と LEDApkc の統合)、NTRU(NTRUEncrypt と NTRU-HRSS-KEM の統合)、ROLLO(LAKE、LOCKER、および Ouroboros-R の統合)、Round5(Hila5 と Round2 の統合)です。更新された仕様の全体は、一般によるレビューのため、2019 年 4 月 10 日に www.nist.gov/pqcrypto で公開されました。

Table 2: Second-Round Candidates

表 2: 第 2 ラウンドの候補

BIKELEDAcryptRainbow
Classic McElieceLUOVROLLO
CRYSTALS-DILITHIUMMQDSSRound5
CRYSTALS-KYBERNewHopeRQC
FALCONNTRUSABER
FrodoKEMNTRU PrimeSIKE
GeMSSNTS-KEMSPHINCS+
HQCPicnicThree Bears
LACqTESLA
BIKELEDAcryptRainbow
Classic McElieceLUOVROLLO
CRYSTALS-DILITHIUMMQDSSRound5
CRYSTALS-KYBERNewHopeRQC
FALCONNTRUSABER
FrodoKEMNTRU PrimeSIKE
GeMSSNTS-KEMSPHINCS+
HQCPicnicThree Bears
LACqTESLA

2.2 Evaluation Criteria

2.2 評価基準

NIST’s Call for Proposals [10] identified three broad aspects of the evaluation criteria that would be used to compare candidate algorithms throughout the NIST PQC Standardization Process: 1) security, 2) cost and performance, and 3) algorithm and implementation characteristics. These criteria are described below, along with a discussion of how they impacted the second-round candidate evaluations.

NIST の Call for Proposals [10] は、NIST PQC 標準化プロセスを通じて候補アルゴリズムの比較に用いる評価基準の大きな観点を 3 つ示していました。1) 安全性、2) コストと性能、3) アルゴリズムと実装の特性です。これらの基準を以下に説明し、あわせて、それらが第 2 ラウンド候補の評価にどのように影響したかを論じます。

2.2.1 Security
2.2.1 安全性

As was the case for the past Advanced Encryption Standard (AES) and Secure Hash Algorithm 3 (SHA-3) competitions, security is the most important factor when evaluating the candidate post-quantum algorithms. NIST’s current public-key standards are used in a wide variety of applications, including internet protocols like TLS, SSH, IKE, IPsec, and DNSSEC, as well as for certificates, software code signing, and secure bootloaders. New standards are needed to provide security for all of these applications.

過去の Advanced Encryption Standard(AES)や Secure Hash Algorithm 3(SHA-3)の競技会の場合と同様に、耐量子アルゴリズムの候補を評価する際には、安全性が最も重要な要素です。NIST の現行の公開鍵標準は、TLS、SSH、IKE、IPsec、DNSSEC などのインターネットプロトコルのほか、証明書、ソフトウェアのコード署名、セキュアブートローダーなど、幅広い用途で使われています。これらすべての用途の安全性を確保するには、新しい標準が必要です。

For the purpose of quantifying the security of candidate algorithms, NIST gave three possible security definitions—two for encryption and one for signatures. NIST also designated five security strength categories for classifying the computational complexity of attacks that violate the security definitions (see [10]).

候補アルゴリズムの安全性を定量化するため、NIST は 3 つの安全性の定義(暗号化に 2 つ、署名に 1 つ)を示しました。また NIST は、これらの安全性の定義を破る攻撃の計算量を分類するために、5 つの安全強度カテゴリーを指定しました([10] を参照)。

For general-use encryption and key-establishment schemes, the Call for Proposals [10] asked for “semantically secure” schemes with respect to adaptive chosen ciphertext attack (equivalently IND-CCA2 security1). For ephemeral use cases, NIST also accepted algorithms that provided semantic security with respect to chosen plaintext attack (IND-CPA security) since IND-CCA2 security is not required in strictly ephemeral use cases, and attempting to meet the more stringent requirements of IND-CCA2 security may incur significant performance penalties for some schemes. Digital signature schemes were required to provide existentially unforgeable signatures with respect to an adaptive chosen message attack (EUF-CMA security). Submitters were encouraged but not required to provide proofs of security in relevant models.

汎用の暗号化方式と鍵確立方式については、Call for Proposals [10] は、適応的選択暗号文攻撃に対して「意味的に安全」(同等に IND-CCA2 安全性1)な方式を求めていました。一時的な(ephemeral)用途については、NIST は、選択平文攻撃に対する意味的安全性(IND-CPA 安全性)を提供するアルゴリズムも受理しました。これは、厳密に一時的な用途では IND-CCA2 安全性が必要でなく、また一部の方式では、より厳格な IND-CCA2 安全性の要件を満たそうとすると、大きな性能上の不利益が生じる場合があるためです。デジタル署名方式には、適応的選択メッセージ攻撃に対して存在的に偽造不可能な署名(EUF-CMA 安全性)を提供することが求められました。提出者には、関連するモデルでの安全性の証明を提供することが推奨されましたが、必須ではありませんでした。

The five security strength categories defined in [10] were based on the computational resources required to perform certain brute force attacks against the existing NIST standards for AES and SHA in a variety of different models of the cost of computation, both classical and quantum. Submitters were asked to provide a preliminary classification of all proposed parameter sets according to these definitions. While category 1, 2, and 3 parameters were (and continue to be) the most important targets for NIST’s evaluation, NIST nevertheless strongly encourages the submitters to provide at least one parameter set that meets category 5. Most of the candidate algorithms have already done this; a few have not.

[10] で定義された 5 つの安全強度カテゴリーは、古典および量子のさまざまな計算コストのモデルにおいて、AES と SHA に関する既存の NIST 標準に対して特定の総当たり攻撃を行うために必要な計算資源に基づいていました。提出者は、提案するすべてのパラメーターセットについて、これらの定義に従った暫定的な分類を提供するよう求められました。カテゴリー 1、2、3 のパラメーターは、NIST の評価にとって最も重要な対象でした(現在もそうです)が、それでも NIST は、提出者がカテゴリー 5 を満たすパラメーターセットを少なくとも 1 つ提供することを強く推奨しています。候補アルゴリズムの大半は既にそうしていますが、していないものも少数あります。

NIST also mentioned other desirable security properties, such as perfect forward secrecy, resistance to side-channel and multi-key attacks, and resistance to misuse, all of which continue to be of interest. In addition, NIST required submission packages to summarize known cryptanalytic attacks on the scheme and complexity estimates for these attacks.

NIST は、完全前方秘匿性、サイドチャネル攻撃やマルチキー攻撃への耐性、誤用への耐性など、そのほかの有用な安全性の特性にも言及しました。これらはいずれも引き続き関心の対象です。加えて NIST は、提出パッケージに、その方式に対する既知の暗号解読攻撃の要約と、それらの攻撃の計算量の見積もりを含めることを求めました。

During the first and second rounds of the NIST standardization process, a number of cryptanalytic results dramatically reduced the security of some submitted schemes and undermined NIST’s confidence in the maturity of others. These results were the basis for many of NIST’s decisions thus far in the process.

NIST 標準化プロセスの第 1 ラウンドと第 2 ラウンドの間に、いくつかの暗号解読の成果が、提出された一部の方式の安全性を劇的に低下させ、ほかの方式の成熟度に対する NIST の信頼を損ねました。これらの成果は、プロセスのこれまでの NIST の多くの決定の根拠となりました。

As NIST moves closer to making standardization decisions, cryptanalysis aiming to precisely measures the security of various submitted parameter sets with respect to known attacks will become even more relevant. This may include, for example, precise quantification of decryption failure rates for CCA parameter sets, quantification of the concrete algorithmic complexity of lattice reduction, and designing and testing countermeasures to advanced side-channel attacks like differential power analysis. It would also be useful for researchers to use techniques from formal verification to ensure the correctness of security proofs. All of this work is important to provide the high degree of confidence necessary for NIST to standardize some of these schemes in the near future.

NIST が標準化の決定に近づくにつれ、既知の攻撃に対する提出済みのさまざまなパラメーターセットの安全性を正確に測定することを目指す暗号解析が、いっそう重要になります。これには、たとえば、CCA パラメーターセットの復号失敗率の正確な定量化、格子簡約の具体的なアルゴリズム計算量の定量化、差分電力解析などの高度なサイドチャネル攻撃への対策の設計とテストが含まれる場合があります。また、研究者が形式検証の手法を用いて、安全性証明の正しさを確認することも有用です。こうした作業はすべて、NIST が近い将来これらの方式の一部を標準化するために必要な高い水準の信頼を得るうえで重要です。

NIST also sees diversity of computational hardness assumptions as an important long-term security goal for its standards. NIST hopes to standardize practically efficient schemes from different families of cryptosystems to reduce the risk that a single breakthrough in cryptanalysis will leave the world without a viable standard for either key-establishment or digital signatures. Nonetheless, NIST does not feel the need to choose these standards all at once but will rather prioritize those schemes which seem closest to being ready for standardization and wide adoption. NIST feels this strategy best serves to balance the desire for diversity with the need for all standards to be thoroughly vetted before they are released.

NIST はまた、計算困難性の仮定の多様性を、標準の長期的な安全性の重要な目標とみなしています。NIST は、暗号解読における単一のブレークスルーによって、鍵確立またはデジタル署名のいずれかについて使用可能な標準が世界から失われるリスクを減らすため、異なる暗号システムのファミリーから、実用上効率的な方式を標準化することを望んでいます。とはいえ NIST は、これらの標準を一度にすべて選ぶ必要はないと考えており、むしろ標準化と広範な採用の準備が最も整っているように見える方式を優先します。NIST は、この戦略が、多様性への要望と、すべての標準が公開前に徹底的に精査される必要性とのバランスを取るのに最も適していると考えています。

1 For the remainder of this document, IND-CCA2 security will simply be referred to as CCA security.
1 本文書の以降では、IND-CCA2 安全性を単に CCA 安全性と呼びます。
2.2.2 Cost and Performance
2.2.2 コストと性能

The original call for proposals [10] identified cost as the second most important criterion when evaluating candidate algorithms. Cost includes the computational efficiency of key generation and public and private key operations, the transmission costs for public keys and signatures or ciphertexts, and the implementation costs in terms of RAM (random-access memory) or gate counts.

当初の call for proposals [10] は、候補アルゴリズムを評価する際に、コストを2 番目に重要な基準として挙げていました。コストには、鍵生成と公開鍵・秘密鍵操作の計算効率、公開鍵と署名または暗号文の伝送コスト、および RAM(ランダムアクセスメモリ)やゲート数で表される実装コストが含まれます。

During the second round of the NIST PQC Standardization Process, more information about the computational efficiency of the algorithms became available. Faster, constant-time implementations on Intel x64 processors were provided for many of the algorithms, as were ARM Cortex-M4 and hardware implementations. These new implementations provided better information not only about the performance of the different algorithms but also about the resources required by implementations (RAM or gate counts). NIST hopes to see more and better data for performance in the third round. This performance data will hopefully include implementations that protect against side-channel attacks, such as timing attacks, power monitoring attacks, fault attacks, etc.

NIST PQC 標準化プロセスの第 2 ラウンドの間に、アルゴリズムの計算効率に関する情報が増えました。多くのアルゴリズムについて、Intel x64 プロセッサー上のより高速な定数時間実装が提供され、ARM Cortex-M4 実装やハードウェア実装も提供されました。これらの新しい実装により、異なるアルゴリズムの性能だけでなく、実装に必要な資源(RAM やゲート数)についても、より良い情報が得られました。NIST は、第 3 ラウンドで、性能に関するより多く、より良いデータが得られることを期待しています。この性能データには、タイミング攻撃、電力監視攻撃、フォールト攻撃などのサイドチャネル攻撃を防御する実装が含まれることが望まれます。

When comparing the overall performance of the algorithms, both computational cost and data transfer cost were considered. For this purpose, the algorithms were generally compared with respect to the two separate categories, leaving open the possibility that different algorithms will eventually be standardized for these two categories of use cases.

アルゴリズムの全体的な性能を比較する際には、計算コストとデータ転送コストの両方を考慮しました。このため、アルゴリズムは一般に、この 2 つの別々のカテゴリーについて比較され、これら 2 つの用途のカテゴリーで、最終的に異なるアルゴリズムが標準化される可能性が残されています。

For general-purpose use, the evaluation of overall performance considered the cost of transferring the public key in addition to the signature or ciphertext during each transaction. For KEMs, algorithms that provided better overall performance when the cost of key generation was taken into account were preferred since many applications use a new KEM key pair for each transaction to provide forward secrecy. For signature algorithms, the cost of key generation was considered less important.

汎用の用途については、全体的な性能の評価で、各トランザクションにおける署名または暗号文に加えて、公開鍵の転送コストも考慮しました。KEM については、多くのアプリケーションが前方秘匿性を提供するためにトランザクションごとに新しい KEM 鍵ペアを使うことから、鍵生成のコストを考慮に入れた場合に全体的な性能がより良いアルゴリズムが好まれました。署名アルゴリズムについては、鍵生成のコストはそれほど重要でないと考えました。

For special-purpose uses, the performance requirements can be somewhat different, and different algorithms may be preferable. For example, a few of the candidate algorithms are computationally efficient and have very small signatures or ciphertexts but very large public keys. While these algorithms may not provide the best overall performance when the public key needs to be sent for each connection, there are applications for which the public key is distributed in advance (e.g., as part of the software package) so that the cost of transmitting the public key is not part of the transaction cost. Algorithms with large public keys may work well with these applications even if they do not provide the best performance for other applications.

特殊な用途では、性能要件がいくらか異なる場合があり、異なるアルゴリズムが望ましい場合があります。たとえば、候補アルゴリズムの少数は、計算効率が高く、署名や暗号文が非常に小さい一方で、公開鍵が非常に大きくなります。接続のたびに公開鍵を送る必要がある場合、これらのアルゴリズムは最良の全体的な性能を提供しないかもしれませんが、公開鍵を(たとえばソフトウェアパッケージの一部として)あらかじめ配布しておくアプリケーションもあり、その場合は公開鍵の送信コストがトランザクションコストに含まれません。公開鍵の大きいアルゴリズムは、ほかのアプリケーションでは最良の性能を提供しないとしても、そうしたアプリケーションではうまく機能する可能性があります。

2.2.3 Algorithm and Implementation Characteristics
2.2.3 アルゴリズムと実装の特性

While current implementations of the candidate algorithms tend to run in constant time, there can be subtle issues which can be overlooked (see, for example, [11]). Most implementations do not provide protection against other types of side-channel attacks, such as power analysis. During the third round, NIST hopes to collect more information about the costs of implementing these algorithms in a way that provides resistance to such attacks. Implementations on very constrained devices, such as smart cards, tend to be more vulnerable to such attacks than implementations on general-purpose computers since constrained devices are more likely to be used in environments in which the attacker has unrestricted access to the device. So, in addition to the cost in terms of computation time, the cost of implementing these mitigations in terms of RAM (or gate count) is also very important.

候補アルゴリズムの現在の実装は定数時間で動作する傾向にありますが、見落とされやすい微妙な問題が存在する場合があります(たとえば [11] を参照)。ほとんどの実装は、電力解析など、ほかの種類のサイドチャネル攻撃に対する防御を提供していません。第 3 ラウンドの間、NIST は、そうした攻撃への耐性をもたらす形でこれらのアルゴリズムを実装するコストについて、より多くの情報を集めることを望んでいます。スマートカードのような非常に制約のあるデバイス上の実装は、汎用コンピューター上の実装よりも、そうした攻撃に対して脆弱である傾向があります。これは、制約のあるデバイスが、攻撃者がデバイスに無制限にアクセスできる環境で使われる可能性が高いためです。したがって、計算時間の面でのコストに加えて、これらの緩和策を実装するための RAM(またはゲート数)の面でのコストも非常に重要です。

In addition, NIST has examined the potential performance impact of candidate algorithms in existing widely used protocols (e.g., TLS, IPSec, and SSH) and certificates. It is clear that some algorithms would cause major performance problems if dropped into those protocols— particularly schemes with very large public keys, ciphertexts, or signatures. Using these algorithms in such widely used protocols would require considerable re-engineering to achieve adequate performance. Other candidate algorithms could be substituted for existing signature and key establishment algorithms with a relatively small performance loss.

加えて NIST は、広く使われている既存のプロトコル(たとえば TLS、IPSec、SSH)や証明書に候補アルゴリズムを組み込んだ場合に生じうる性能への影響を調べました。一部のアルゴリズム、特に公開鍵、暗号文、または署名が非常に大きい方式は、それらのプロトコルにそのまま組み込むと、大きな性能問題を引き起こすことが明らかです。これらのアルゴリズムをそうした広く使われているプロトコルで使うには、十分な性能を達成するためにかなりの再設計が必要になります。そのほかの候補アルゴリズムは、既存の署名アルゴリズムや鍵確立アルゴリズムの代わりに、比較的小さな性能の低下で置き換えることができます。

Several of the candidates made updates during the first and second rounds to improve simplicity. When considering standardization, simple and elegant designs are preferable, as they encourage further analysis and understanding. NIST will continue to pay close attention to how well-analyzed and well-understood candidates are during the third round.

候補のいくつかは、単純さを高めるため、第 1 ラウンドと第 2 ラウンドの間に更新を行いました。標準化を検討する際には、単純で洗練された設計が好まれます。そうした設計は、さらなる分析と理解を促すためです。NIST は、第 3 ラウンドの間も、候補がどの程度よく分析され、よく理解されているかに引き続き細心の注意を払います。

As stated in [10], NIST will consider any factors which might hinder or promote the adoption of an algorithm or implementation, including but not limited to intellectual property covering an algorithm or its implementations and the availability and terms of licenses to interested parties. Considerations involving intellectual property may play a stronger role in the third round as NIST makes decisions regarding standardization. NIST has a clear preference for royalty-free algorithms in order to enable widespread adoption.

[10] に述べられているとおり、NIST は、アルゴリズムまたは実装の採用を妨げうる、あるいは促進しうるあらゆる要因を考慮します。これには、アルゴリズムやその実装に及ぶ知的財産、および関心のある当事者に対するライセンスの提供可能性と条件が含まれますが、これらに限られません。知的財産に関する考慮は、NIST が標準化に関する決定を行う第 3 ラウンドでは、より大きな役割を果たす可能性があります。NIST は、広範な採用を可能にするため、ロイヤルティフリーのアルゴリズムを明確に好みます。

2.3 Selection of the Third-Round Finalists and Alternate Candidates

2.3 第 3 ラウンドのファイナリストと代替候補の選定

As mentioned in Section 2.2.1, a number of cryptanalytic results announced during the second round dramatically reduced the security of some submitted schemes and undermined NIST’s confidence in the maturity of others. These results led to the elimination of some of the candidates from further consideration.

2.2.1 節で述べたとおり、第 2 ラウンドの間に発表されたいくつかの暗号解読の成果が、提出された一部の方式の安全性を劇的に低下させ、ほかの方式の成熟度に対する NIST の信頼を損ねました。これらの成果により、一部の候補はそれ以降の検討から除外されました。

Of the remaining schemes, the second round provided NIST with a number of KEMs that could be standardized in the near future—many with similar designs, based on similar security assumptions, and with comparable performance. NIST is unlikely to standardize two or more very similar KEM algorithms, so some very strong candidates had to be eliminated in this round in order to focus analytical attention on the most promising ones. This was particularly the case for the structured lattice-based KEMs. By contrast, NIST had far fewer candidate signature algorithms to choose from at the end of the second round.

残った方式のうち、第 2 ラウンドは NIST に、近い将来標準化されうる多数の KEM を提供しました。その多くは、設計が似ており、似た安全性の仮定に基づき、性能も同程度でした。NIST が、非常によく似た 2 つ以上の KEM アルゴリズムを標準化する可能性は低いため、最も有望なものに分析の注意を集中させるべく、このラウンドでは、非常に強力な候補の一部を除外せざるを得ませんでした。これは特に、構造化格子ベースの KEM に当てはまりました。対照的に、第 2 ラウンドの終了時に NIST が選べる署名アルゴリズムの候補は、はるかに少数でした。

When choosing between very similar KEM algorithms, cost and performance were significant selection criteria. As noted in Section 2.2.2, when comparing candidates, both data transmission costs and computational efficiency were taken into account. NIST considered benchmarks provided by the community (see, for example, [12, 13, 14, 15, 16]) across multiple platforms when determining computational efficiency.

非常によく似た KEM アルゴリズムの間で選ぶ際には、コストと性能が重要な選定基準でした。2.2.2 節で述べたとおり、候補を比較する際には、データ伝送コストと計算効率の両方を考慮しました。計算効率を判断する際、NIST は、コミュニティから提供された複数のプラットフォームにわたるベンチマーク(たとえば [12, 13, 14, 15, 16] を参照)を考慮しました。

NIST selected 15 of the second-round candidates to move onto the third round of the standardization process. Of the 15 advancing candidates, seven have been selected as finalists and eight as alternate candidates.

NIST は、第 2 ラウンドの候補のうち 15 を、標準化プロセスの第 3 ラウンドに進めるものとして選定しました。進む 15 の候補のうち、7 つがファイナリストとして、8 つが代替候補として選ばれています。

Table 3: Third-Round Finalists

表 3: 第 3 ラウンドのファイナリスト

Public-Key Encryption/KEMsDigital Signatures
Classic McElieceCRYSTALS-DILITHIUM
CRYSTALS-KYBERFALCON
NTRURainbow
SABER
公開鍵暗号化 / KEMデジタル署名
Classic McElieceCRYSTALS-DILITHIUM
CRYSTALS-KYBERFALCON
NTRURainbow
SABER

Table 4: Alternate Candidates

表 4: 代替候補

Public-Key Encryption/KEMsDigital Signatures
BIKEGeMSS
FrodoKEMPicnic
HQCSPHINCS+
NTRU Prime
SIKE
公開鍵暗号化 / KEMデジタル署名
BIKEGeMSS
FrodoKEMPicnic
HQCSPHINCS+
NTRU Prime
SIKE

The set of finalists are algorithms that NIST considers to be the most promising to fit the majority of use cases and most likely to be ready for standardization soon after the end of the third round. As CRYSTALS-KYBER, NTRU, and SABER are all structured lattice schemes, NIST intends to select, at most, one for the standard. The same is true for the signature schemes CRYSTALS-DILITHIUM and FALCON. In NIST’s current view, these structured lattice schemes appear to be the most promising general-purpose algorithms for public-key encryption/KEM and digital signature schemes.

ファイナリストは、大多数のユースケースに適合し、第 3 ラウンド終了後まもなく標準化の準備が整う可能性が最も高いと NIST が考える、最も有望なアルゴリズムです。CRYSTALS-KYBER、NTRU、および SABER はいずれも構造化格子方式であるため、NIST は標準として最大でも 1 つを選定する意向です。署名方式の CRYSTALS-DILITHIUM と FALCON についても同様です。NIST の現時点の見解では、これらの構造化格子方式は、公開鍵暗号化 / KEM およびデジタル署名方式の汎用アルゴリズムとして最も有望であると考えられます。

The alternate candidates are regarded as potential candidates for future standardization, most likely after another round of evaluation. Some of the alternate candidates have worse performance than the finalists but might be selected for standardization based on NIST’s high confidence in their security. Others have acceptable performance but require additional analysis or other work to inspire sufficient confidence in their security for NIST to standardize. In addition, some alternate candidates were selected based either on NIST’s desire for diversity in future post-quantum security standards or on their potential for further improvement. During the third round, the term “finalist” will refer to the first seven algorithms listed above, and the terms “alternate” or “alternate candidate” will be used for the other eight algorithms also advancing.

代替候補は、将来の標準化の潜在的な候補とみなされており、おそらくもう 1 ラウンドの評価を経てからになります。代替候補の一部は、ファイナリストより性能が劣りますが、その安全性に対する NIST の高い信頼に基づいて標準化に選ばれる可能性があります。ほかのものは、許容できる性能を持つものの、NIST が標準化するのに十分な安全性への信頼を得るには、追加の分析やその他の作業が必要です。さらに、一部の代替候補は、将来の耐量子安全性標準における多様性を求める NIST の意向、またはさらなる改善の可能性に基づいて選ばれました。第 3 ラウンドの間、「ファイナリスト」という用語は上に挙げた最初の 7 つのアルゴリズムを指し、「代替」または「代替候補」という用語は、同じく進む残りの 8 つのアルゴリズムに用います。

3 Summary of Second-Round Candidates

3 第 2 ラウンド候補の概要

Each of the second-round candidates is discussed below, including a summary of their advantages and disadvantages. In addition, the discussion provides reasons why a scheme was (or was not) selected to advance to the third round. Some suggestions are included that the submitters of advancing schemes may wish to address for the third round.

以下では、第 2 ラウンドの各候補を、その利点と欠点の要約を含めて論じます。加えて、ある方式が第 3 ラウンドに進むものとして選ばれた(または選ばれなかった)理由を示します。進む方式の提出者が、第 3 ラウンドに向けて対処することを検討するとよい提案も含まれています。

The 17 public-key encryption and key-establishment schemes are discussed first (in Sections 3.1 to 3.17), and the nine digital signature schemes follow (in Sections 3.18 to 3.26). The finalists are presented first, followed by the alternate candidates and then the algorithms not selected to advance to the third round.

17 の公開鍵暗号化および鍵確立方式を最初に論じ(3.1 節から 3.17 節)、続いて 9 つのデジタル署名方式を論じます(3.18 節から 3.26 節)。ファイナリストを最初に示し、次に代替候補、その後に第 3 ラウンドに進むものとして選ばれなかったアルゴリズムを示します。

3.1 Classic McEliece (merger of Classic McEliece and NTS-KEM)

3.1 Classic McEliece(Classic McEliece と NTS-KEM の統合)

Classic McEliece is a code-based KEM based on the 1979 McEliece cryptosystem built from a hidden Goppa code. Classic McEliece includes some modern improvements for efficiency and to provide CCA security. The security of these improvements is reduced to the one-wayness against chosen-plaintext attack (OW-CPA) security of the original construction as proposed in 1979 [17]. The original construction is not based on a particularly natural computational assumption; however, Goppa code McEliece and related cryptosystems have a long history of study.

Classic McEliece は、隠された Goppa 符号から構成される 1979 年の McEliece 暗号システムに基づく、符号ベースの KEM です。Classic McEliece には、効率化と CCA 安全性の提供のための、いくつかの現代的な改良が含まれています。これらの改良の安全性は、1979 年に提案された元の構成の選択平文攻撃に対する一方向性(OW-CPA)安全性に帰着されます [17]。元の構成は、特に自然な計算上の仮定に基づいているわけではありませんが、Goppa 符号 McEliece と関連する暗号システムには、長い研究の歴史があります。

Classic McEliece has a somewhat unusual performance profile—it has a very large public key but the smallest ciphertexts of all competing KEMs. This is not a good fit for general use in internet protocols as they are currently specified, but in some applications, the very small ciphertext size could make Classic McEliece an appealing choice (for example, see [18]).

Classic McEliece の性能の特徴はやや珍しいものです。公開鍵が非常に大きい一方で、競合するすべての KEM の中で暗号文が最小です。これは、現在規定されているインターネットプロトコルでの汎用的な使用には適していませんが、一部のアプリケーションでは、暗号文サイズが非常に小さいことが Classic McEliece を魅力的な選択肢にする可能性があります(たとえば [18] を参照)。

Goppa code McEliece has been a well-known construction for over 40 years with only incremental improvements on attacks. Due to the confidence this fact inspires in the construction, as well as the careful implementation work of the submitters, Classic McEliece has a stable specification−−the only significant change in the second round is the addition of additional parameter sets. As such, NIST selected Classic McEliece as a finalist and believes it could be ready for standardization (should NIST choose to select it) at the end of the third round.

Goppa 符号 McEliece は 40 年以上にわたってよく知られた構成であり、攻撃の改善は漸進的なものにとどまっています。この事実が構成に対して与える信頼と、提出者の入念な実装作業により、Classic McEliece の仕様は安定しており、第 2 ラウンドでの重要な変更は、パラメーターセットの追加のみです。このため、NIST は Classic McEliece をファイナリストとして選定し、(NIST が選定することにした場合には)第 3 ラウンドの終了時に標準化の準備が整う可能性があると考えています。

3.2 CRYSTALS-KYBER

3.2 CRYSTALS-KYBER

CRYSTALS-KYBER is a KEM whose security is based on the presumed hardness of the Module Learning With Errors (MLWE) problem. At its core is Regev’s original idea for public-key encryption from plain LWE [19]. CCA security is achieved with a Fujisaki-Okamoto transform [20, 21] and is supported by a security proof in the quantum random oracle model (QROM). While MLWE is a relatively young problem, no attacks are known against MLWE that do not also apply to the more well-established plain LWE. The module structure of KYBER is over a power-of-two cyclotomic ring, enabling fast computations via the number theoretic transform (NTT). The scheme has excellent all-around performance for most applications. It also enables relatively straightforward adjustment of the performance/security trade-off by varying module rank and noise parameters. In addition, CRYSTALS-KYBER shares a common framework with the CRYSTALS-DILITHIUM signature scheme, which is also a finalist.

CRYSTALS-KYBER は、安全性が Module Learning With Errors(MLWE)問題の困難性の想定に基づく KEM です。その中核にあるのは、素の LWE による公開鍵暗号化という Regev の元のアイデアです [19]。CCA 安全性は Fujisaki-Okamoto 変換 [20, 21] によって達成され、量子ランダムオラクルモデル(QROM)での安全性証明によって裏付けられています。MLWE は比較的新しい問題ですが、より確立された素の LWE にも適用される攻撃以外に、MLWE に対する攻撃は知られていません。KYBER のモジュール構造は 2 のべき乗の円分環上にあり、数論変換(NTT)による高速な計算を可能にしています。この方式は、ほとんどのアプリケーションで全般的に優れた性能を持ちます。また、モジュールのランクとノイズのパラメーターを変えることで、性能と安全性のトレードオフを比較的容易に調整できます。さらに、CRYSTALS-KYBER は、同じくファイナリストである署名方式 CRYSTALS-DILITHIUM と共通の枠組みを共有しています。

For Round 2, KYBER no longer uses the public-key compression that was present in the first-round version. The modulus and noise parameters were also adjusted. Final key derivation now uses SHAKE256 instead of SHA3-256. During the second round, a new fault attack forcing nonce reuse was discovered, affecting several lattice schemes, including KYBER [22]. Recent theoretical work has placed MLWE on stronger footing by providing a very tight reduction from ring LWE to module LWE [23].

第 2 ラウンドでは、KYBER は第 1 ラウンド版にあった公開鍵の圧縮を使用しなくなりました。法とノイズのパラメーターも調整されました。最終的な鍵導出には、SHA3-256 の代わりに SHAKE256 を使うようになりました。第 2 ラウンドの間に、ナンスの再利用を強制する新しいフォールト攻撃が発見され、KYBER を含むいくつかの格子方式に影響を与えました [22]。最近の理論的な研究は、環 LWE からモジュール LWE への非常にタイトな帰着を示すことで、MLWE をより強固な基盤の上に置きました [23]。

Compared to other lattice schemes, KYBER has relatively lower “CoreSVP” [24] security strength when targeting security strength category 1. NIST believes it is important to understand how exactly this CoreSVP security translates into “true” bit security strength for KYBER. KYBER’s performance in side-channel-resistant implementations will be closely considered by NIST in the third round. NIST views CRYTALS-KYBER as one of the most promising KEM schemes to be considered for standardization at the end of the third round.

ほかの格子方式と比べて、KYBER は、安全強度カテゴリー 1 を目標とする場合に、「CoreSVP」 [24] の安全強度が相対的に低くなっています。NIST は、この CoreSVP の安全性が KYBER の「真の」ビット安全強度にどのように対応するかを正確に理解することが重要だと考えています。NIST は、第 3 ラウンドで、KYBER のサイドチャネル耐性のある実装での性能を詳細に検討します。NIST は、CRYSTALS-KYBER を、第 3 ラウンドの終了時に標準化が検討される最も有望な KEM 方式の 1 つとみなしています。

3.3 NTRU

3.3 NTRU

NTRU is a structured lattice-based KEM whose security is based on a different assumption than the Ring-LWE (RLWE) or MLWE-based approach of several of the other lattice-based candidates. Although it lacks a formal worst-case-to-average-case reduction, NTRU has a long and established history and is a very widely analyzed scheme. Versions of NTRU have also been standardized by other organizations [25, 26]. In Round 2, the NTRU submission was the result of a merger of the NTRUEncrypt and NTRU-HRSS-KEM first-round submissions. This variant of NTRU under consideration satisfies perfect correctness and uses an improved CCA transform with a security proof in the QROM. While NTRU is very efficient, it is not quite at the level of the highest-performing lattice schemes. In particular, NTRU has slower key generation than the schemes based on RLWE and MLWE.

NTRU は構造化格子ベースの KEM で、その安全性は、ほかの格子ベース候補のいくつかが採る Ring-LWE(RLWE)や MLWE に基づくアプローチとは異なる仮定に基づいています。最悪ケースから平均ケースへの形式的な帰着はありませんが、NTRU には長く確立された歴史があり、非常に広く分析された方式です。NTRU のバージョンは、ほかの組織によっても標準化されています [25, 26]。第 2 ラウンドの NTRU の提出は、第 1 ラウンドの NTRUEncrypt と NTRU-HRSS-KEM の提出を統合した結果でした。検討対象のこの NTRU の変種は、完全正当性を満たし、QROM での安全性証明を伴う改良された CCA 変換を用います。NTRU は非常に効率的ですが、最高性能の格子方式の水準には達していません。特に、NTRU の鍵生成は、RLWE や MLWE に基づく方式より遅くなっています。

NTRU provided two different cost models for estimating the security of its parameter sets: a local and a non-local model. The non-local model is most similar to the CoreSVP metric used by the other lattice-based submissions, and in this model, the NTRU submission lacks a category 5 parameter set proposal. Likewise, the lowest security parameter set in the NTRU submission (ntruhps2048509) does not meet security category 1, according to the non-local model. NTRU also proposed a more aggressive local model, which assigns higher security to the parameter sets. If NTRU’s parameter sets are treated as targeting the security categories assigned by the local model, then they would have lower CoreSVP complexity than many of the other schemes targeting the same security strength categories. It is important to understand exactly how these various cost metrics translate into “true” bit security strengths.

NTRU は、パラメーターセットの安全性を見積もるために、局所モデルと非局所モデルという 2 つの異なるコストモデルを提供しました。非局所モデルは、ほかの格子ベースの提出が用いる CoreSVP 指標に最も近く、このモデルでは、NTRU の提出にはカテゴリー 5 のパラメーターセットの提案がありません。同様に、NTRU の提出で最も安全性の低いパラメーターセット(ntruhps2048509)は、非局所モデルによればセキュリティカテゴリー 1 を満たしません。NTRU はまた、パラメーターセットにより高い安全性を割り当てる、より積極的な局所モデルも提案しました。NTRU のパラメーターセットを、局所モデルで割り当てられたセキュリティカテゴリーを目標とするものとして扱うと、同じ安全強度カテゴリーを目標とするほかの多くの方式より、CoreSVP の計算量が低くなります。これらのさまざまなコスト指標が「真の」ビット安全強度にどのように対応するかを正確に理解することが重要です。

NIST sees structured lattice-based schemes as very promising. As NTRU is such a scheme but based on a different security assumption than RLWE or MLWE, it provides some diversity to the collection of finalists. While NTRU has a small performance gap in comparison to KYBER and SABER, its longer history was an important factor in NIST’s decision to select NTRU as a finalist. Due to its longer history, NTRU has less risk of unexpected intellectual property claims.

NIST は、構造化格子ベースの方式を非常に有望とみなしています。NTRU はそうした方式でありながら、RLWE や MLWE とは異なる安全性の仮定に基づくため、ファイナリストの集合にある程度の多様性をもたらします。NTRU は KYBER や SABER と比べて性能にわずかな差がありますが、その長い歴史が、NIST が NTRU をファイナリストに選定した重要な要因でした。歴史が長いため、NTRU は想定外の知的財産の主張を受けるリスクがより小さくなっています。

NIST expects that, at most, only one of these candidates—KYBER, SABER, or NTRU—will be standardized at the end of the third round. In the event that new cryptanalytic or intellectual property issues threaten the future of KYBER and SABER, NTRU would be seen as a more appealing finalist.

NIST は、これらの候補(KYBER、SABER、NTRU)のうち、第 3 ラウンドの終了時に標準化されるのは多くても 1 つだけだと見込んでいます。新たな暗号解読や知的財産の問題が KYBER と SABER の将来を脅かす場合には、NTRU がより魅力的なファイナリストとみなされることになります。

3.4 SABER

3.4 SABER

SABER is a KEM whose security is based on the presumed hardness of the Module Learning With Rounding (MLWR) problem, a variant of MLWE where the addition of small error terms is replaced by rounding from one modulus to a smaller, second modulus. CCA security is given by a variant of the Fujisaki-Okamoto transform. While reductions to MLWR from MLWE exist, they are not concretely applicable to SABER, which is a mild concern. It should be noted that reductions exist from MLWE to a shortest vector problem, but they are also not concretely applicable to the MLWE candidates, such as KYBER. On the other hand, the rounding operation and power-of-2 moduli in SABER allow for the efficient optimization of the modular reduction and polynomial multiplication steps. Overall, SABER has excellent performance and would be immediately suitable for general-purpose applications.

SABER は、Module Learning With Rounding(MLWR)問題が困難であるとの想定に安全性が基づく KEM です。MLWR は、小さな誤差項の加算を、ある法からより小さい別の法への丸めに置き換えた MLWE の変種です。CCA 安全性は Fujisaki-Okamoto 変換の変種によって与えられます。MLWE から MLWR への帰着は存在しますが、SABER には具体的に適用できず、これは軽度の懸念事項です。MLWE から最短ベクトル問題への帰着も存在しますが、KYBER などの MLWE 候補にも具体的に適用できないことに留意すべきです。一方、SABER の丸め演算と 2 のべき乗の法により、法簡約と多項式乗算の手順を効率的に最適化できます。全体として、SABER は優れた性能を持ち、汎用アプリケーションにすぐに適しています。

A few minor changes were made in SABER’s specification for the second round. Notably, a small tweak allowed for a successful formal reduction from the security of SABER to Module-LWR.

第 2 ラウンドに向けて、SABER の仕様にはいくつかの軽微な変更が加えられました。特に、小さな調整により、SABER の安全性から Module-LWR への形式的な帰着が成功しました。

NIST currently has no suggestions for changes to the SABER specification but believes that there are many valuable avenues for research in this area. In particular, NIST encourages additional research regarding side-channel analysis and optimization of the non-NTT style of multiplication that is unique to SABER among the lattice candidates, as well as on the concrete differences between the security of MLWE and MLWR for the proposed parameter sets. The performance of side-channel-resistant implementations of SABER will be closely considered by NIST during the third round. As mentioned above, SABER is one of the most promising KEM schemes to be considered for standardization at the end of the third round.

NIST は現時点で SABER の仕様変更について提案を持っていませんが、この分野には価値ある研究の方向が数多くあると考えています。特に NIST は、サイドチャネル解析、および格子候補の中で SABER 特有の NTT 方式でない乗算の最適化について、さらに研究することを奨励します。また、提案されたパラメーターセットにおける MLWE と MLWR の安全性の具体的な違いについても研究を奨励します。NIST は第 3 ラウンド中に、サイドチャネル耐性を備えた SABER 実装の性能を詳細に検討します。上述のとおり、SABER は第 3 ラウンド終了時に標準化が検討される最も有望な KEM 方式の 1 つです。

3.5 BIKE

3.5 BIKE

BIKE is a structured code-based KEM which offers balanced performance for general use, similar to structured lattice-based KEMs but with somewhat slower decapsulation and key generation and somewhat more bandwidth (public-key size plus ciphertext size). This performance profile, which optimizes bandwidth for BIKE, was chosen by the submitters at the end of the second round from three different performance profiles offered in BIKE’s initial second-round submission. A new decoder was also introduced during the second round and is detailed below.

BIKE は、構造化符号ベースの KEM で、汎用の用途に対して、構造化格子ベースの KEM と同様にバランスの取れた性能を提供しますが、脱カプセル化と鍵生成がやや遅く、帯域幅(公開鍵サイズと暗号文サイズの和)がやや大きくなります。BIKE の帯域幅を最適化するこの性能プロファイルは、BIKE の第 2 ラウンド当初の提出で示されていた 3 つの異なる性能プロファイルから、第 2 ラウンドの終了時に提出者が選びました。第 2 ラウンドの間には新しいデコーダーも導入されており、以下で詳しく説明します。

The most significant attacks for both passive key recovery and message recovery for BIKE are based on information-set decoding, and complexity estimates for this family of attacks have been much more stable than for most other classes of attacks. As such, a scheme like BIKE would, if standardized, provide a useful fallback in the case of major cryptanalytic advances against structured lattice schemes.

BIKE に対する、受動的な鍵回復とメッセージ回復の両方について最も重大な攻撃は、情報集合復号に基づいており、この攻撃ファミリーの計算量の見積もりは、ほかのほとんどの種類の攻撃よりはるかに安定しています。このため、BIKE のような方式は、標準化されれば、構造化格子方式に対する大きな暗号解読上の進展があった場合の有用なフォールバックとなるでしょう。

Nonetheless, there remain serious questions about side-channel protections and CCA security that need to be resolved before BIKE can be considered for standardization. BIKE pays a significant performance penalty by targeting CCA security since a very low decapsulation failure rate is required. The decapsulation failure rate is estimated in a heuristic way by using simplified models to extrapolate from experiments [27]. The submitters announced a redesign of the decoder (switching from a backflip decoder to a Black-Gray-Flip [BGF] decoder [28]) and altered their parameters at the end of the second round to better meet their target decapsulation failure rate. As of the end of the second round, however, the submitters were not confident enough to explicitly claim CCA security.

それでも、BIKE が標準化の検討対象となる前に解決しなければならない、サイドチャネル防御と CCA 安全性に関する重大な疑問が残っています。BIKE は CCA 安全性を目標とするため、非常に低い脱カプセル化失敗率が必要となり、大きな性能上の不利益を負っています。脱カプセル化失敗率は、単純化したモデルを用いて実験から外挿する、ヒューリスティックな方法で見積もられています [27]。提出者は、デコーダーの再設計(backflip デコーダーから Black-Gray-Flip [BGF] デコーダー [28] への切り替え)を発表し、第 2 ラウンドの終了時に、目標とする脱カプセル化失敗率をよりよく満たすようパラメーターを変更しました。しかし、第 2 ラウンドの終了時点で、提出者は CCA 安全性を明示的に主張できるほどの確信を持っていませんでした。

Additionally, the BIKE submitters provided a new implementation designed to be constant time and without secret dependent memory access. As both the parameters and the implementation are quite new, both will require vetting by the community, in particular regarding side-channel protections and decapsulation failure rates. Finally, BIKE did not provide category 5 parameters in their most recent update. NIST strongly encourages that such parameters be added.

加えて、BIKE の提出者は、定数時間で、秘密情報に依存したメモリアクセスを伴わないように設計された新しい実装を提供しました。パラメーターも実装もかなり新しいため、特にサイドチャネル防御と脱カプセル化失敗率について、どちらもコミュニティによる精査が必要になります。最後に、BIKE は最新の更新でカテゴリー 5 のパラメーターを提供しませんでした。NIST は、そうしたパラメーターを追加することを強く奨励します。

NIST views BIKE as one of the most promising code-based candidates. As mentioned above, more time will be needed to address the security concerns listed. As such, BIKE was not chosen to be a finalist but will advance to the third round for more study.

NIST は、BIKE を最も有望な符号ベースの候補の 1 つとみなしています。上述のとおり、挙げられた安全性の懸念に対処するにはより多くの時間が必要です。このため、BIKE はファイナリストには選ばれませんでしたが、さらなる研究のために第 3 ラウンドに進みます。

3.6 FrodoKEM

3.6 FrodoKEM

FrodoKEM is a KEM whose security is based on the presumed hardness of the plain LWE problem. Frodo is quite close to Regev’s original LWE public-key encryption construction, together with a Fujisaki-Okamoto transform to reach CCA security, supported by a security proof in the QROM. Among lattice-based schemes, Frodo has the least amount of structure and is thus likely to be less susceptible to algebraic attacks. Plain LWE itself is among the most studied and analyzed cryptographic problems in existence today. The resulting potential security advantages of Frodo are paid for with far worse performance in all metrics than other lattice schemes. However, Frodo still has some performance advantages over other conservative options, particularly in key generation time and public-key size.

FrodoKEM は、安全性が素の LWE 問題の困難性の想定に基づく KEM です。Frodo は、Regev の元の LWE 公開鍵暗号化の構成にかなり近く、CCA 安全性に到達するために Fujisaki-Okamoto 変換を併用し、QROM での安全性証明によって裏付けられています。格子ベースの方式の中で、Frodo は構造が最も少なく、そのため代数的攻撃を受けにくい可能性が高いです。素の LWE 自体は、現在存在する暗号上の問題の中で、最も研究され分析されているものの 1 つです。Frodo にこのように潜在的な安全性上の利点があることの代償は、ほかの格子方式よりすべての指標で大幅に劣る性能です。しかし、Frodo は、ほかの保守的な選択肢と比べると、特に鍵生成時間と公開鍵サイズにおいて、いくつかの性能上の利点を持っています。

The Frodo team added a parameter set for security category 5 during the second round. Certain pseudorandomness expansion procedures were moved to the key generation function, apparently avoiding the aforementioned fault attack of [22]. In addition, the Fujisaki-Okamoto transform was somewhat simplified based on new theory results on QROM security. Also, during the second round, a new theoretical analysis of lattice algorithms “with hints” showed that certain power trace attacks against Frodo are stronger than previously believed [29].

Frodo チームは、第 2 ラウンドの間にセキュリティカテゴリー 5 のパラメーターセットを追加しました。擬似乱数の拡張手順の一部が鍵生成関数に移され、これにより [22] の前述のフォールト攻撃が回避されたようです。加えて、Fujisaki-Okamoto 変換は、QROM 安全性に関する新しい理論的成果に基づいて、いくらか単純化されました。また、第 2 ラウンドの間に、「ヒント付き」の格子アルゴリズムの新しい理論的分析によって、Frodo に対する一部の電力トレース攻撃が、従来考えられていたよりも強力であることが示されました [29]。

Use of FrodoKEM would have a noticeable performance impact on high traffic TLS servers, where each server does decapsulation which requires close to 2 million cycles for the best performing parameter set (FrodoKEM-640-AES) and receives a public key and a ciphertext (around 20,000 bytes in total) for every fresh key exchange.

FrodoKEM を使用すると、トラフィックの多い TLS サーバーでは、性能への顕著な影響が生じるでしょう。そこでは、各サーバーが脱カプセル化を行い、最も性能の良いパラメーターセット(FrodoKEM-640-AES)でも 200 万サイクル近くを要し、新たな鍵交換のたびに公開鍵と暗号文(合計で約 20,000 バイト)を受け取ります。

In NIST’s view, FrodoKEM may be suitable for use cases where the high confidence in the security of unstructured lattice-based schemes is much more important than performance. NIST’s first priority for standardization is a KEM that would have acceptable performance in widely used applications overall. As such, possible standardization for FrodoKEM can likely wait until after the third round. FrodoKEM could also serve as a conservative backup in the case of new cryptanalytic results targeting structured lattices being discovered in the third round. For these reasons, FrodoKEM was not selected as a finalist but is one of the alternate candidates advancing.

NIST の見解では、FrodoKEM は、構造化されていない格子ベースの方式の安全性に対する高い信頼が、性能よりはるかに重要となるユースケースに適している可能性があります。NIST が標準化で最優先するのは、広く使われているアプリケーション全般で許容できる性能を持つ KEM です。このため、FrodoKEM の標準化の可能性は、第 3 ラウンドの後まで待てるでしょう。FrodoKEM は、第 3 ラウンドの間に構造化格子を標的とする新たな暗号解読の成果が発見された場合の、保守的なバックアップにもなりえます。これらの理由から、FrodoKEM はファイナリストには選ばれませんでしたが、進む代替候補の 1 つです。

3.7 HQC

3.7 HQC

HQC is a code-based KEM based on the hardness of the decisional quasi-cyclic syndrome decoding (QCSD) with parity problem. The scheme claims CCA2 security based on a rigorous analysis of its decryption failure rate.

HQC は、パリティ付き準巡回シンドローム復号(QCSD)問題の判定版の困難性に基づく符号ベースの KEM です。この方式は、復号失敗率の厳密な分析に基づく CCA2 安全性を主張しています。

In the second round, a new analysis of the error vector distribution showed that the decryption failure rate was lower than previously believed, allowing reductions in key sizes. The HQC team also presented a new decoder using concatenated Reed-Muller and Reed-Solomon codes, further reducing the size of the public keys. Even with these key size reductions, the resulting public keys and ciphertexts are 1.6-2 and 4-5 times the size of those of BIKE, respectively. Although the bandwidth of HQC exceeds that of BIKE, HQC’s key generation and decapsulation functionalities are much faster than BIKE’s.

第 2 ラウンドでは、誤りベクトルの分布の新しい分析により、復号失敗率が従来考えられていたよりも低いことが示され、鍵サイズを削減できるようになりました。HQC チームはまた、連接した Reed-Muller 符号と Reed-Solomon 符号を用いる新しいデコーダーを提示し、公開鍵のサイズをさらに削減しました。こうした鍵サイズの削減を行っても、得られる公開鍵と暗号文は、BIKE のものの、それぞれ 1.6〜2 倍と 4〜5 倍の大きさです。HQC の帯域幅は BIKE を上回りますが、HQC の鍵生成と脱カプセル化の機能は BIKE よりはるかに高速です。

During the third round, NIST encourages further research into the relationship between the decisional and search versions of the QCSD with parity problems as well as a close analysis of the new parameter sets. The community should also continue to investigate the effects on security produced by the quasi-cyclic code structure.

第 3 ラウンドの間、NIST は、パリティ付き QCSD 問題の判定版と探索版の関係についてのさらなる研究と、新しいパラメーターセットの綿密な分析を奨励します。コミュニティも、準巡回符号の構造が安全性に及ぼす影響の調査を続けるべきです。

While HQC offers strong security assurances and a mature analysis, its performance characteristics are overshadowed by the structured lattice KEM candidates, and it compares unfavorably with BIKE in the bandwidth metric. As a result of these facts, NIST did not select HQC as a finalist for the first round of NIST standards. HQC is advancing as an alternate candidate in the third round due to the thoroughness of its security analysis in comparison to BIKE, the other strong code-based KEM candidate.

HQC は強い安全性の保証と成熟した分析を提供しますが、その性能特性は構造化格子 KEM 候補に見劣りし、帯域幅の指標では BIKE に比べて不利です。これらの事実の結果として、NIST は HQC を、NIST の標準の第 1 弾に向けたファイナリストには選びませんでした。HQC は、もう一方の有力な符号ベース KEM 候補である BIKE と比べて安全性分析が徹底されていることから、第 3 ラウンドでは代替候補として進みます。

3.8 NTRU Prime

3.8 NTRU Prime

NTRU Prime is a collection of two lattice-based KEMs, Streamlined NTRU Prime and NTRU LPRime, which share many design elements but differ in algebraic structure. Streamlined NTRU Prime is an “NTRU-like” KEM with a quotient structure in its public key, and NTRU LPRime is an “RLWE-like” KEM with a product structure in its public key. Streamlined NTRU Prime is secure under an assumption similar to that made for classical NTRU, which is in turn based on a long and established history of resisting cryptanalysis. NTRU LPRime was designed with a structure chosen by analogy to RLWE schemes based on the work of Lyubashevsky, Peikert, and Regev [30].

NTRU Prime は、Streamlined NTRU Prime と NTRU LPRime という 2 つの格子ベース KEM の集まりで、多くの設計要素を共有しますが、代数的構造が異なります。Streamlined NTRU Prime は、公開鍵に商構造を持つ「NTRU 型」の KEM であり、NTRU LPRime は、公開鍵に積構造を持つ「RLWE 型」の KEM です。Streamlined NTRU Prime は、古典的な NTRU に対する仮定と同様の仮定の下で安全であり、その NTRU は、暗号解読に耐えてきた長く確立された歴史に基づいています。NTRU LPRime は、Lyubashevsky、Peikert、Regev の研究 [30] に基づく RLWE 方式との類推で選ばれた構造で設計されました。

Recent work on reduction-based security for lattice cryptography covers NTRU LPRime “in spirit” through the work of Peikert, Regev, and Stephens-Davidowitz [31]. NTRU Prime has no decryption failures and thus is immune to decryption failure boosting attacks. It achieves CCA security through a Fujisaki-Okamoto-type transform. The central distinction between NTRU Prime and other structured lattice KEM proposals is its abandonment of the cyclotomic ring structure in favor of the field \(Z_q[x]/(x^p-x-1)\). This choice is partly motivated by recent progress in quantum algorithms for finding short vectors in principal ideal lattices with a guaranteed short generator.

格子暗号に対する帰着ベースの安全性に関する最近の研究は、Peikert、Regev、Stephens-Davidowitz の研究 [31] を通じて、NTRU LPRime を「趣旨において」カバーしています。NTRU Prime には復号失敗がなく、したがって復号失敗ブースティング攻撃の影響を受けません。CCA 安全性は、Fujisaki-Okamoto 型の変換によって達成されます。NTRU Prime とほかの構造化格子 KEM 提案との中心的な違いは、円分環構造を放棄し、体 \(Z_q[x]/(x^p-x-1)\) を用いている点です。この選択は、短い生成元が保証された単項イデアル格子で短いベクトルを見つける量子アルゴリズムの最近の進展が、動機の一部になっています。

In the second round, two new parameter sets were introduced. NTRUprime’s parameter sets target security strength categories 2, 3, and 4. This results in a narrower range of CoreSVP values than other lattice submissions targeting security strengths 1, 3, and 5. NIST encourages NTRUprime to consider expanding the range of security strengths targeted by including category 5 parameter sets. Additionally, while NTRUprime’s category 2 parameter sets at least have a higher CoreSVP value than most of the lattice schemes targeting category 1, the category 3 and 4 parameter sets are quite aggressive compared to most of the other submissions targeting the same security categories, and whether they actually meet their claimed security categories will need to be determined.

第 2 ラウンドでは、2 つの新しいパラメーターセットが導入されました。NTRUprime のパラメーターセットは、安全強度カテゴリー 2、3、4 を目標としています。その結果、安全強度 1、3、5 を目標とするほかの格子の提出と比べて、CoreSVP の値の範囲が狭くなっています。NIST は、NTRUprime が、カテゴリー 5 のパラメーターセットを含めることで、目標とする安全強度の範囲を広げることを検討するよう奨励します。さらに、NTRUprime のカテゴリー 2 のパラメーターセットは、少なくともカテゴリー 1 を目標とする格子方式の大半より高い CoreSVP 値を持っていますが、カテゴリー 3 と 4 のパラメーターセットは、同じセキュリティカテゴリーを目標とするほかの提出の大半と比べてかなり攻めたものであり、主張されたセキュリティカテゴリーを実際に満たすかどうかを判断する必要があります。

NTRU Prime was advanced to the third round but not as a finalist. Additional motivation for NTRU Prime’s unique choice of algebraic structure could be gained by new progress in algebraic cryptanalysis of cyclotomic structures during the third round, provided that it undermines NIST’s confidence in cyclotomic structures but clearly does not extend to NTRUprime’s choice of \(Z_q[x]/(x^p-x-1)\).

NTRU Prime は、ファイナリストとしてではなく、第 3 ラウンドに進みました。NTRU Prime が代数的構造として独自の選択をしたことの動機は、第 3 ラウンドの間に円分構造の代数的暗号解読で新たな進展があれば、さらに強まる可能性があります。ただし、その進展が円分構造に対する NIST の信頼を損ねる一方で、NTRUprime が選んだ \(Z_q[x]/(x^p-x-1)\) には明らかに及ばないことが条件です。

3.9 SIKE

3.9 SIKE

SIKE is unique among the second-round candidates—it is the only scheme based on isogenies of elliptic curves. One of the main advantages to SIKE is that it has the smallest public key sizes of all of the encryption and KEM schemes, as well as very small ciphertext sizes. As part of their second-round update, the SIKE team introduced a version with even smaller (compressed) keys. The parameters are also easy to scale.

SIKE は第 2 ラウンドの候補の中で唯一のものであり、楕円曲線の同種写像に基づく唯一の方式です。SIKE の主な利点の 1 つは、すべての暗号化方式と KEM 方式の中で公開鍵サイズが最小であり、暗号文サイズも非常に小さいことです。第 2 ラウンドの更新の一環として、SIKE チームは、さらに小さい(圧縮された)鍵を持つバージョンを導入しました。パラメーターも容易にスケールできます。

The status report on the first round [9] noted that the basic security problem upon which SIKE is based is an area where further study would be useful. Towards the end of the first round, a series of papers [32, 33] examined the relevant classical and black-box quantum attacks, resulting in confidence that existing parameter sets were providing more security than previously claimed. As a result, the SIKE team was able to lower the parameter sizes used in their second-round specification. One caveat regarding SIKE’s analysis is that its assignment of security strength categories relies on the assumption that adversaries are limited to no more than \(2^{96}\) bits of memory. While this may perhaps be a reasonable assumption when assigning parameter sets to security strength categories 1 and 2, considerations such as maximum achievable circuit depth suggest that adversaries with more memory should be considered when assigning parameter sets to categories 3 and above. Independent of this particular issue, NIST believes that confidence in the hardness of the SIDH (supersingular isogeny Diffie-Hellman) problem would continue to benefit from more study.

第 1 ラウンドの状況報告 [9] は、SIKE の基礎となる基本的な安全性の問題が、さらなる研究が有用な領域であると指摘していました。第 1 ラウンドの終わり頃に、一連の論文 [32, 33] が、関連する古典攻撃とブラックボックス量子攻撃を検討し、既存のパラメーターセットが従来主張されていたよりも高い安全性を提供しているという確信が得られました。その結果、SIKE チームは、第 2 ラウンドの仕様で用いるパラメーターサイズを小さくすることができました。SIKE の分析に関する留意点の 1 つは、安全強度カテゴリーの割り当てが、攻撃者が \(2^{96}\) ビット以下のメモリに限られるという仮定に依存していることです。この仮定は、パラメーターセットをセキュリティ強度カテゴリー 1 と 2 に割り当てる際には、おそらく妥当かもしれませんが、達成可能な最大の回路深度などの考慮から、カテゴリー 3 以上にパラメーターセットを割り当てる際には、より多くのメモリを持つ攻撃者を考慮すべきであることが示唆されます。この特定の問題とは別に、NIST は、SIDH(supersingular isogeny Diffie-Hellman)問題の困難性に対する信頼は、さらなる研究から引き続き恩恵を受けると考えています。

The main drawback to SIKE is that its performance (measured in clock cycles) is roughly an order of magnitude worse than many of its competitors. Much work has been done to optimize implementations, including the compressed-key version, and it is hoped that such optimizations continue. While some existing techniques for side-channel protection are known for computing multiples of points on elliptic curves, more research is also needed on protecting the isogeny computations.

SIKE の主な欠点は、(クロックサイクルで測った)性能が、競合する多くの方式より概ね一桁劣ることです。圧縮鍵バージョンを含め、実装の最適化に多くの作業が行われており、そうした最適化が続くことが期待されます。楕円曲線上の点の倍数を計算する際のサイドチャネル防御には、既存の手法がいくつか知られていますが、同種写像の計算の保護についても、さらなる研究が必要です。

NIST sees SIKE as a strong candidate for future standardization with continued improvements and accordingly selected SIKE to move into the third round as an alternate candidate. There are applications which would benefit from SIKE’s small key and ciphertext sizes and which may be able to accept the performance impact. Further research in isogeny-based cryptography is encouraged.

NIST は、SIKE を、改良が続けば将来の標準化の有力な候補になるとみなし、それに応じて SIKE を代替候補として第 3 ラウンドに進めるものとして選定しました。SIKE の小さな鍵と暗号文のサイズの恩恵を受け、かつ性能への影響を受け入れられるアプリケーションがあります。同種写像ベースの暗号に関するさらなる研究が奨励されます。

3.10 LAC

3.10 LAC

LAC is a KEM whose security is based on the hardness of the RLWE problem. LAC has an unusual design feature: it uses error-correcting codes to “fix” decryption failures. (This idea also appears in Round5.) This means that LAC can tolerate a higher decryption failure rate, which allows it to use a smaller modulus that leads to improved performance. However, care is needed to ensure that this design does not lead to security vulnerabilities. During the first round of the NIST standardization process, several authors published attacks on LAC that reduced its security to below the required levels [34, 35, 36, 37]. These included chosen-ciphertext attacks that worked by artificially increasing the decryption failure rate and side-channel attacks that exploit non-constant-time implementations of the error-correction procedures in LAC. LAC was subsequently modified to resist these attacks.

LAC は、安全性が RLWE 問題の困難性に基づく KEM です。LAC には珍しい設計上の特徴があり、誤り訂正符号を使って復号失敗を「修正」します。(この考え方は Round5 にも見られます。)これは、LAC がより高い復号失敗率を許容できることを意味し、そのため、より小さい法を使うことができて、性能が向上します。しかし、この設計がセキュリティ上の脆弱性につながらないよう、注意が必要です。NIST 標準化プロセスの第 1 ラウンドの間に、複数の著者が、LAC の安全性を要求水準未満に低下させる攻撃を発表しました [34, 35, 36, 37]。これには、復号失敗率を人為的に引き上げることで機能する選択暗号文攻撃や、LAC の誤り訂正手順の非定数時間実装を悪用するサイドチャネル攻撃が含まれていました。その後、LAC はこれらの攻撃に耐えるよう修正されました。

During the second round, a few more minor security issues were discovered, including another issue involving variable-time implementation of error-correction procedures. These issues were described in the public “official comments” during the first and second rounds of the NIST standardization process [38].

第 2 ラウンドの間には、誤り訂正手順の可変時間実装に関するもう 1 つの問題を含め、さらにいくつかの軽微なセキュリティ上の問題が発見されました。これらの問題は、NIST 標準化プロセスの第 1 ラウンドと第 2 ラウンドの間に、公開の「公式コメント」で説明されました [38]。

NIST is concerned that the cryptanalysis of LAC seems to involve precisely those aspects of LAC’s design, particularly the use of error correction, that distinguish it from most other structured lattice-based schemes. Although LAC has been modified to resist those attacks, NIST believes that further study is needed before it can be confident that there are no remaining vulnerabilities in the LAC design. Thus, despite very good performance numbers, LAC was not selected to move on to the third round.

NIST は、LAC の暗号解読が、LAC の設計の中でも、特に誤り訂正の使用という、ほかの大半の構造化格子ベース方式と LAC を区別する点にまさに関わっているように見えることを懸念しています。LAC はそれらの攻撃に耐えるよう修正されましたが、NIST は、LAC の設計に残存する脆弱性がないと確信できるようになるには、さらなる研究が必要だと考えています。したがって、非常に優れた性能の数値にもかかわらず、LAC は第 3 ラウンドに進むものとしては選定されませんでした。

3.11 LEDAcrypt

3.11 LEDAcrypt

LEDAcrypt includes structured code-based KEM and encryption schemes using a similar construction to BIKE. LEDAcrypt differs from BIKE in a few of its design decisions. In particular, LEDAcrypt designed its parameter sets to have more rigorously bounded decryption failure rates than BIKE. As a result, the parameters targeting CCA security have about 60 % larger bandwidth than BIKE.

LEDAcrypt には、BIKE と同様の構成を用いる、構造化符号ベースの KEM と暗号化方式が含まれます。LEDAcrypt は、設計上の判断のいくつかが BIKE と異なります。特に LEDAcrypt は、BIKE よりも厳密に上界を定めた復号失敗率になるようパラメーターセットを設計しました。その結果、CCA 安全性を目標とするパラメーターでは、帯域幅が BIKE より約 60 % 大きくなります。

In the first- and second-round submissions, the private key of LEDAcrypt had additional product structure relative to BIKE. As with BIKE, the private key consisted of a sparse quasi-cyclic matrix, but in the case of LEDAcrypt, this sparse quasi-cyclic matrix was produced by multiplying two sparser quasi-cyclic matrices. This additional structure enabled an attack [39] during the second round, which primarily consisted of a large class of weak keys where a modified information set decoding results in a much more efficient key recovery attack than assumed by the submission.

第 1 ラウンドと第 2 ラウンドの提出では、LEDAcrypt の秘密鍵は、BIKE と比べて追加の積構造を持っていました。BIKE と同様に、秘密鍵は疎な準巡回行列でしたが、LEDAcrypt の場合、この疎な準巡回行列は、より疎な 2 つの準巡回行列を乗算して生成されていました。この追加の構造により、第 2 ラウンドの間に攻撃 [39] が可能になりました。その攻撃は主に、修正した情報集合復号によって、提出で想定されていたよりはるかに効率的な鍵回復攻撃が可能になる、大きな弱い鍵のクラスから成っていました。

The submitters responded by proposing a countermeasure that made the structure essentially the same as that of BIKE. NIST judged this to be too large a modification to consider the scheme for the third round.

提出者は、構造を BIKE の構造と本質的に同じにする対策を提案して対応しました。NIST は、これは第 3 ラウンドの検討対象とするには大きすぎる修正であると判断しました。

In light of these reasons, NIST did not select LEDAcrypt to continue on.

これらの理由を踏まえ、NIST は LEDAcrypt を先に進めるものとしては選定しませんでした。

3.12 NewHope

3.12 NewHope

NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key sizes as well as fast computations via NTT. CCA security is achieved by a standard flavor of Fujisaki-Okamoto transform and is supported by proofs in the classical and quantum random oracle models. Among all LWE-based lattice submissions, NewHope (and other RLWE schemes) can be viewed as the most structured, with MLWE being an intermediately structured case and plain LWE being the least structured case. As a result of this structure, the scheme has very strong performance for nearly all applications.

NewHope は、RLWE 問題の困難性の想定に基づく KEM です。その中核にあるのは、素の LWE による公開鍵暗号化という Regev の元のアイデアですが、2 のべき乗の円分環構造に特化しており、これにより暗号文と鍵のサイズが小さくなり、NTT による高速な計算が可能になっています。CCA 安全性は Fujisaki-Okamoto 変換の標準的な形態によって達成され、古典および量子ランダムオラクルモデルでの証明によって裏付けられています。LWE ベースのすべての格子の提出の中で、NewHope(およびほかの RLWE 方式)は最も構造化されているとみなせ、MLWE は中間的に構造化されたケース、素の LWE は最も構造化されていないケースにあたります。この構造の結果として、この方式は、ほぼすべてのアプリケーションに対して非常に高い性能を持ちます。

In a technical sense, the security of NewHope is never better than that of KYBER. A recent paper gives a highly parameterizable, essentially linear-time reduction from RLWE to MLWE [23]. If that reduction is specialized to the case of NewHope, one finds the following: the reduction takes RLWE instances and outputs an MLWE instance; it is modulus-preserving; it is “almost” sample-preserving; it is error distribution-preserving; and it translates the ring dimension for RLWE into the product of ring-dimension times module-rank for MLWE. As such, any attack against an underlying MLWE instance implies a substantially similar-cost attack against NewHope’s underlying RLWE instance. There are a few minor caveats. However, NIST does not expect that these issues will substantially change the relative concrete security situation of NewHope and an MLWE scheme (like KYBER) that is indicated by the presence of such a tight and efficient reduction.

技術的な意味では、NewHope の安全性が KYBER の安全性を上回ることはありません。最近の論文は、RLWE から MLWE への、高度にパラメーター化可能で、本質的に線形時間の帰着を示しています [23]。この帰着を NewHope の場合に特化すると、次のことがわかります。この帰着は、RLWE のインスタンスを受け取り、MLWE のインスタンスを出力します。法を保存し、「ほぼ」サンプルを保存し、誤差分布を保存し、RLWE の環次元を、MLWE の環次元とモジュールランクの積に変換します。したがって、基になる MLWE インスタンスに対するどのような攻撃も、NewHope の基になる RLWE インスタンスに対する、実質的に同程度のコストの攻撃を意味します。いくつかの軽微な留意点があります。しかし NIST は、これらの問題が、そうしたタイトで効率的な帰着の存在によって示される、NewHope と(KYBER のような)MLWE 方式との相対的な具体的安全性の状況を、大きく変えるとは見込んでいません。

Further, NIST observed that the CoreSVP strength estimates of NewHope and KYBER are substantially comparable, and KYBER was slightly more efficient in most benchmarks. Specifically because of the relaxation in algebraic structure, KYBER naturally supports a category 3 security strength parameter set, whereas NewHope does not.

さらに NIST は、NewHope と KYBER の CoreSVP 強度の見積もりが実質的に同程度であり、ほとんどのベンチマークで KYBER がわずかに効率的であったことを確認しました。代数的構造が緩和されているために、KYBER は自然にカテゴリー 3 の安全強度のパラメーターセットをサポートしますが、NewHope はサポートしません。

Despite the numerous strengths of the NewHope KEM proposal, NIST developed a slight but clear preference for KYBER and for low-rank MLWE schemes over RLWE schemes for the KEM application setting. Therefore, NIST did not select NewHope to continue into the third round.

NewHope KEM の提案には多くの長所があるものの、NIST は、KEM のアプリケーション設定では、RLWE 方式よりも KYBER と低ランクの MLWE 方式をわずかながら明確に好むようになりました。したがって、NIST は NewHope を第 3 ラウンドに進めるものとしては選定しませんでした。

3.13 NTS-KEM

3.13 NTS-KEM

The NTS-KEM submission merged with Classic McEliece in February 2020. The two specifications were very similar. The merged team elected to adopt the Classic McEliece specification, as well as the name, for their merged submission. NIST appreciates the willingness of the two submission teams to work together.

NTS-KEM の提出は、2020 年 2 月に Classic McEliece と統合されました。2 つの仕様は非常によく似ていました。統合されたチームは、統合後の提出に Classic McEliece の仕様と名称を採用することを選びました。NIST は、2 つの提出チームが協力する意思を示したことに感謝します。

3.14 ROLLO

3.14 ROLLO

At the start of Round 2, ROLLO was comprised of three rank metric code-based KEMs with security based on the rank syndrome decoding (RSD) problem. The first-round report noted that the strength of algebraic attacks against RSD was not well understood and should be explored.

第 2 ラウンドの開始時点で、ROLLO は、安全性がランクシンドローム復号(RSD)問題に基づく、3 つのランク距離符号ベースの KEM で構成されていました。第 1 ラウンドの報告書は、RSD に対する代数的攻撃の強さが十分に理解されておらず、探究すべきであると指摘していました。

Since then, new algebraic attacks have surfaced (see [40, 41]) that model the decoding problem as a system of multivariate equations using equations from the extension field structure to solve. The most recent algebraic attack is more efficient than combinatorial approaches against the parameter sets given in ROLLO, resulting in a near-complete break of all three KEMS. All security levels of ROLLO II and III were reduced to less than 128 bits of security, while the category 5 parameters of ROLLO I were reduced to category 1 security.

それ以降、復号問題を多変数方程式系としてモデル化し、拡大体の構造から得られる方程式を使って解く、新しい代数的攻撃が登場しました([40, 41] を参照)。最も新しい代数的攻撃は、ROLLO で与えられたパラメーターセットに対して組合せ的アプローチより効率的であり、3 つの KEM すべてがほぼ完全に破られる結果となりました。ROLLO II と III のすべての安全性レベルは 128 ビット未満の安全性に低下し、ROLLO I のカテゴリー 5 のパラメーターはカテゴリー 1 の安全性に低下しました。

New parameter sets were proposed, resulting in a new ROLLO I scheme which achieves CPA security and a ROLLO II scheme which achieves CCA security, both with category 1, 3, and 5 security levels. The new ROLLO I public keys and ciphertexts are roughly 50 % larger than before, though they are both still significantly smaller than RQC. Although the new key and ciphertext sizes remain competitive, the security analysis of ROLLO needs more time to mature.

新しいパラメーターセットが提案され、その結果、CPA 安全性を達成する新しい ROLLO I 方式と、CCA 安全性を達成する ROLLO II 方式が得られました。どちらもカテゴリー 1、3、5 の安全性レベルを持ちます。新しい ROLLO I の公開鍵と暗号文は以前より約 50 % 大きくなりましたが、どちらも RQC よりは依然としてかなり小さいです。鍵と暗号文のサイズは引き続き競争力がありますが、ROLLO の安全性分析が成熟するには、より多くの時間が必要です。

NIST did not select ROLLO to advance on in the PQC standardization process. Despite the development of algebraic attacks, NIST believes rank-based cryptography should continue to be researched. The rank metric cryptosystems offer a nice alternative to traditional hamming metric codes with comparable bandwidth.

NIST は、ROLLO を PQC 標準化プロセスで先に進めるものとしては選定しませんでした。代数的攻撃が登場したものの、NIST は、ランクベースの暗号は研究が続けられるべきだと考えています。ランク距離暗号システムは、同程度の帯域幅を持つ従来のハミング距離符号に代わる良い選択肢を提供します。

3.15 Round5

3.15 Round5

Round5 is a lattice-based scheme which offers parameter sets optimized for various use cases. The security is based on the (Ring) Learning With Rounding problems. An error-correcting code XEf is used to correct decryption failures, similar to the technique used by LAC, and CCA security is achieved by applying a Fujisaki-Okamoto transform. The performance of Round5 is impressive, both in bandwidth requirements and processing time. The unified design of Round5 allows it to be instantiated in either a ring or non-ring setting.

Round5 は、さまざまなユースケース向けに最適化されたパラメーターセットを提供する格子ベースの方式です。安全性は (Ring) Learning With Rounding 問題に基づいています。復号失敗を訂正するために誤り訂正符号 XEf が用いられ、これは LAC で使われている手法と似ています。CCA 安全性は Fujisaki-Okamoto 変換を適用することで達成されます。Round5 の性能は、帯域幅要件と処理時間の両面で印象的です。Round5 の統一された設計により、環の設定でも非環の設定でもインスタンス化できます。

The security of Round5 was analyzed more closely during the second round, which led to two minor attacks [42, 43]. As a result, the team made small updates to the proposed parameter sets to protect against these attacks. During the second round, Round5 specified the use of TupleHash and TupleHashXOF to ensure domain separation. Small modifications were also made to further optimize implementations of Round5 and protect against side-channel attacks.

Round5 の安全性は第 2 ラウンドの間にさらに詳しく分析され、2 つの軽微な攻撃 [42, 43] が見つかりました。その結果、チームはこれらの攻撃を防ぐために、提案したパラメーターセットに小さな更新を加えました。第 2 ラウンドの間に、Round5 は、ドメイン分離を確実にするために TupleHash と TupleHashXOF を使用することを規定しました。また、Round5 の実装をさらに最適化し、サイドチャネル攻撃を防御するために、小さな修正も行われました。

Overall, the Round5 specification is significantly more complicated than all of the other second-round candidates. Moreover, the Round5 submission documents did not offer a royalty-free license, and there are competing lattice-based schemes which do. The matrix A in Round5 is deterministically generated from a short seed using three different techniques, parametrized by τ in {0, 1, 2}. NIST only finds confidence in the security of one of the techniques (τ = 0) and notes that there is no proof of security for the other two techniques.

全体として、Round5 の仕様は、第 2 ラウンドのほかのすべての候補よりも著しく複雑です。さらに、Round5 の提出文書はロイヤルティフリーのライセンスを提示しておらず、それを提示している競合の格子ベース方式があります。Round5 の行列 A は、τ ∈ {0, 1, 2} でパラメーター化された 3 つの異なる手法のいずれかにより、短いシードから決定論的に生成されます。NIST が安全性に確信を持てるのは、手法のうち 1 つ(τ = 0)だけであり、ほかの 2 つの手法には安全性の証明がないことに注意しています。

For the reasons listed above, NIST does not view Round5 as more promising than the three lattice-based finalists selected. NIST seeks to focus the attention of the community on a small number of algorithms and so needed to cut the number of structured lattice schemes. Thus, even though Round5 has excellent performance, it was not selected to advance.

上記の理由から、NIST は Round5 を、選定された 3 つの格子ベースのファイナリストより有望とはみなしていません。NIST は、コミュニティの注意を少数のアルゴリズムに集中させることを目指しており、そのため構造化格子方式の数を絞る必要がありました。したがって、Round5 は優れた性能を持つものの、先に進めるものとしては選定されませんでした。

3.16 RQC

3.16 RQC

RQC is a structured rank metric code-based KEM with security based on the RSD problem targeting IND-CCA security. RQC differs from ROLLO in that it uses an LWE-like construction with a public error-correcting code instead of an NTRU style construction. This allows RQC to have a zero decryption failure rate, but it also requires larger ciphertexts than either variant of ROLLO. The first-round report noted that the strength of algebraic attacks against RSD was not well understood and should be explored. Since then, new algebraic attacks have surfaced which model the decoding problem as a system of multivariate equations using equations from the extension field structure to solve [40, 41]. The most recent algebraic attack is more efficient than combinatorial approaches against the parameter sets given in the round 2 specification of RQC, resulting in a near-complete break. All security levels of RQC were reduced to less than 128 bits of security.

RQC は、RSD 問題に基づく安全性を持ち、IND-CCA 安全性を目標とする、構造化ランク距離符号ベースの KEM です。RQC が ROLLO と異なるのは、NTRU 型の構成ではなく、公開された誤り訂正符号を用いる LWE 型の構成を使う点です。これにより RQC は復号失敗率をゼロにできますが、ROLLO のどちらの変種よりも大きな暗号文が必要になります。第 1 ラウンドの報告書は、RSD に対する代数的攻撃の強さが十分に理解されておらず、探究すべきであると指摘していました。それ以降、復号問題を多変数方程式系としてモデル化し、拡大体の構造から得られる方程式を使って解く、新しい代数的攻撃が登場しました [40, 41]。最も新しい代数的攻撃は、RQC の第 2 ラウンド仕様で与えられたパラメーターセットに対して組合せ的アプローチより効率的であり、ほぼ完全に破られる結果となりました。RQC のすべての安全性レベルは 128 ビット未満の安全性に低下しました。

New parameter sets were proposed to provide adequate security against algebraic attacks. These resulted in key and ciphertext sizes that were a little more than double what they were at the beginning of the second round. Although the new key and ciphertext sizes remain competitive (albeit less so than those of ROLLO), the security analysis of RQC needs more time to mature.

代数的攻撃に対して十分な安全性を提供するため、新しいパラメーターセットが提案されました。その結果、鍵と暗号文のサイズは、第 2 ラウンドの開始時点の 2 倍をわずかに上回るものになりました。新しい鍵と暗号文のサイズは(ROLLO のものほどではないにせよ)引き続き競争力がありますが、RQC の安全性分析が成熟するには、より多くの時間が必要です。

NIST did not select RQC to advance on in the PQC standardization process. Despite the development of algebraic attacks, NIST believes rank-based cryptography should continue to be researched. The rank metric cryptosystems offer a nice alternative to traditional hamming metric codes with comparable bandwidth.

NIST は、RQC を PQC 標準化プロセスで先に進める対象としては選定しませんでした。代数的攻撃が登場したものの、NIST は、ランクベース暗号の研究を続けるべきです。ランク距離暗号システムは、同程度の帯域幅を持つ従来のハミング距離符号に代わる良い選択肢を提供します。

3.17 Three Bears

3.17 Three Bears

Three Bears is a KEM whose security is based on the presumed hardness of the Integer Module Learning With Errors (I-MLWE) problem, a new variant of the MLWE problem. It draws its inspiration from [30] and, more explicitly, from KYBER and related improvements to the MLWE-like design paradigm that have been devised over time. Three Bears is one of two examples of candidates that are a non-cyclotomic structured lattice KEM. The chosen polynomial ring underlying the module structure in Three Bears is isomorphic to the integers modulo a generalized Mersenne prime, and elements of the ring are written simply as (large) integers in the provided implementations. The scheme also uses an internal Melas forward error correcting code in all parameter sets. Altogether, this leads to a highly efficient scheme.

Three Bears は、安全性が Integer Module Learning With Errors(I-MLWE)問題の困難性の想定に基づく KEM です。I-MLWE は MLWE 問題の新しい変種です。着想は [30] から得ており、より明示的には、KYBER と、MLWE 型の設計パラダイムに対して時間をかけて考案された関連する改良から得ています。Three Bears は、円分でない構造化格子 KEM である 2 つの候補のうちの 1 つです。Three Bears のモジュール構造の基になる多項式環は、一般化 Mersenne 素数を法とする整数と同型であり、提供された実装では、環の元は単に(大きな)整数として書かれます。この方式はまた、すべてのパラメーターセットで内部に Melas 前方誤り訂正符号を使用します。全体として、これは非常に効率的な方式につながります。

In the second round, the security proof sketch in the submission documentation was updated to a formal proof. In addition, parameters were slightly modified to lower the decryption failure rate, along with a detailed analysis for bounding the rate. A later tweak during the second round made implicit rejection mandatory in the specification.

第 2 ラウンドでは、提出文書にあった安全性証明のスケッチが、形式的な証明に更新されました。加えて、復号失敗率を下げるためにパラメーターがわずかに修正され、その率に上界を与える詳細な分析も行われました。第 2 ラウンドの間の後の調整で、仕様において暗黙的な拒否(implicit rejection)が必須となりました。

NIST notes there is a security reduction which shows the asymptotic security equivalence of the usual notion of RLWE and Integer-RLWE, and this proof appears to carry directly over to the case of MLWE and I-MLWE. However, NIST notes that the I-MLWE hardness assumption was essentially created for the sake of submission to the NIST PQC standards process and has not undergone enough rigorous review by the broader cryptographic research community. While the reduction exists between I-MLWE and MLWE, there is still the possibility of concrete attacks exploiting the I-MLWE structure that are not fully captured by the security reduction, or other new issues that may have not been discovered yet. In a similar vein, it seems that the entire Three Bears submission package appears to have received less attention by third-party researchers than other KEM submissions, particularly other lattice KEM submissions.

NIST は、通常の RLWE の概念と Integer-RLWE の漸近的な安全性の同等性を示す安全性の帰着が存在し、この証明が MLWE と I-MLWE の場合にもそのまま持ち越せるように見えることに注意しています。しかし NIST は、I-MLWE の困難性の仮定が、本質的に NIST PQC 標準化プロセスへの提出のために作られたものであり、より広い暗号研究コミュニティによる十分に厳密なレビューを受けていないことに注意しています。I-MLWE と MLWE の間に帰着が存在するものの、安全性の帰着では完全には捉えきれない、I-MLWE の構造を悪用する具体的な攻撃や、まだ発見されていないその他の新たな問題が存在する可能性は残っています。同様に、Three Bears の提出パッケージ全体が、ほかの KEM の提出、特にほかの格子 KEM の提出に比べて、第三者の研究者から受けた注目が少ないように見えます。

While NIST believes the technical and scientific merits of Three Bears are significant, this is not a substitute for a sufficient threshold of broader community attention. NIST therefore chose not to keep Three Bears under consideration for standardization, as there are other options which have comparable security and performance.

NIST は、Three Bears の技術的・科学的な価値は大きいと考えていますが、それは、より広いコミュニティによる十分な水準の注目に代わるものではありません。そのため NIST は、同程度の安全性と性能を持つ別の選択肢があることから、Three Bears を標準化の検討対象として残さないことを選びました。

3.18 CRYSTALS-DILITHIUM

3.18 CRYSTALS-DILITHIUM

CRYSTALS-DILITHIUM was one of three lattice-based signature schemes in the second round. The security of DILITHIUM relies on the hardness of the MLWE and module short integer solutions problems (MSIS) and follows the Fiat-Shamir with aborts technique [44]. DILITHIUM uses the same modulus and ring for all parameter sets and samples via the uniform distribution, which results in a simpler implementation than its main competitor, FALCON.

CRYSTALS-DILITHIUM は、第 2 ラウンドにあった 3 つの格子ベース署名方式の 1 つでした。DILITHIUM の安全性は、MLWE とモジュール短整数解問題(MSIS)の困難性に依存しており、Fiat-Shamir with aborts の手法 [44] に従っています。DILITHIUM はすべてのパラメーターセットで同じ法と環を使い、一様分布でサンプリングするため、主な競合である FALCON よりも実装が単純になります。

Overall, DILITHIUM has strong, balanced performance in terms of key and signature sizes and in the efficiency of the key generation, signing, and verification algorithms. DILITHIUM performs well in real-world experiments.

全体として、DILITHIUM は、鍵と署名のサイズ、および鍵生成・署名・検証アルゴリズムの効率の面で、強力でバランスの取れた性能を持ちます。DILITHIUM は実世界の実験でも良好な性能を示します。

For the second round, DILITHIUM added the option to generate a signature non-deterministically and added an implementation based on using AES rather than SHAKE to illustrate the future benefits of hardware instructions. In addition, new research on security in the QROM was published [45], which applies to DILITHIUM.

第 2 ラウンドに向けて、DILITHIUM は署名を非決定的に生成するオプションを追加し、ハードウェア命令の将来的な利点を示すために、SHAKE ではなく AES を使う実装を追加しました。加えて、DILITHIUM に当てはまる、QROM での安全性に関する新しい研究が公表されました [45]。

NIST encourages the DILITHIUM team to add a category 5 parameter set. More study is also needed on understanding the concrete security, as DILITHIUM has the lowest CoreSVP security strength parameter set of any of the lattice schemes still in the process. NIST selected DILITHIUM as a finalist and expects that either DILITHIUM or FALCON will be standardized as the primary post-quantum signature scheme at the conclusion of the third round.

NIST は、DILITHIUM チームがカテゴリー 5 のパラメーターセットを追加することを奨励します。DILITHIUM は、プロセスに残っている格子方式の中で CoreSVP 安全強度が最も低いパラメーターセットを持つため、具体的な安全性の理解についても、さらなる研究が必要です。NIST は DILITHIUM をファイナリストとして選定し、第 3 ラウンドの終了時に、DILITHIUM または FALCON のいずれかが主要な耐量子署名方式として標準化されると見込んでいます。

3.19 FALCON

3.19 FALCON

FALCON is a lattice-based signature scheme utilizing the “hash and sign” paradigm. Security is based on the hardness of the SIS (short integer solution) problem over NTRU lattices, and security proofs are given in both the random oracle model (ROM) and QROM with tight reductions. FALCON is more complex to implement than DILITHIUM, requiring tree data structures, extensive floating-point operations, and random sampling from several discrete Gaussian distributions.

FALCON は、「hash and sign」パラダイムを利用する格子ベースの署名方式です。安全性は NTRU 格子上の SIS(短整数解)問題の困難性に基づいており、ランダムオラクルモデル(ROM)と QROM の両方で、タイトな帰着を伴う安全性証明が与えられています。FALCON の実装は DILITHIUM より複雑で、木のデータ構造、広範な浮動小数点演算、およびいくつかの離散ガウス分布からのランダムサンプリングが必要です。

One of the advantages of FALCON is that it offers the smallest bandwidth (public key size and signature size) of all of the second-round digital signature schemes. FALCON is also efficient in signing and verifying, although key generation is slower. FALCON can easily be put into existing protocols and applications and offers very good overall performance.

FALCON の利点の 1 つは、第 2 ラウンドのすべてのデジタル署名方式の中で、帯域幅(公開鍵サイズと署名サイズ)が最小であることです。FALCON は署名と検証も効率的ですが、鍵生成は遅くなっています。FALCON は既存のプロトコルやアプリケーションに容易に組み込むことができ、全体として非常に良好な性能を提供します。

At the beginning of the second round, FALCON removed their category 3 parameter sets, which simplified their specification and implementation because they used a different modulus and ring choice. The other major update during the second round was a constant-time implementation released shortly after NIST’s 2nd PQC Standardization Conference.

第 2 ラウンドの開始時に、FALCON はカテゴリー 3 のパラメーターセットを削除しました。これらは異なる法と環の選択を使っていたため、削除により仕様と実装が単純になりました。第 2 ラウンドのもう 1 つの主要な更新は、NIST の 2nd PQC 標準化カンファレンスの直後に公開された定数時間実装でした。

During the third round, NIST encourages more scrutiny of FALCON’s implementation to determine whether the use of floating-point arithmetic makes implementation errors more likely than other schemes or provides an avenue for side-channel attacks. In addition, it would be helpful to have test vectors for the sampler, perhaps by making it deterministic for a random seed, so that implementations can be verified using known answer tests (KATs). As with several other candidates, FALCON’s category 1 parameters have relatively low CoreSVP security strength, and so further study is needed.

第 3 ラウンドの間、NIST は、浮動小数点演算の使用が、ほかの方式よりも実装エラーを起こしやすくしていないか、あるいはサイドチャネル攻撃の経路になっていないかを判断するため、FALCON の実装へのさらなる精査を奨励します。加えて、サンプラーについて、おそらくランダムなシードに対して決定的にすることで、テストベクトルがあれば、既知解テスト(KAT)で実装を検証できるため有用です。ほかのいくつかの候補と同様に、FALCON のカテゴリー 1 のパラメーターは CoreSVP 安全強度が比較的低く、さらなる研究が必要です。

FALCON was selected as a third-round finalist. As stated above, NIST expects that either DILITHIUM or FALCON will be standardized as the primary post-quantum signature scheme at the conclusion of the third round.

FALCON は、第 3 ラウンドのファイナリストとして選定されました。上述のとおり、NIST は、第 3 ラウンドの終了時に、DILITHIUM または FALCON のいずれかが主要な耐量子署名方式として標準化されると見込んでいます。

3.20 Rainbow

3.20 Rainbow

Rainbow is a multivariate signature scheme with a layered construction based on the Unbalanced Oil-Vinegar (UOV) signature scheme. The additional structure imposed by the Rainbow layers exposes the scheme to a larger array of cryptanalytic techniques but improves the scheme’s efficiency. Rainbow offers fast signing and verifying and very short signatures but has very large public keys.

Rainbow は、Unbalanced Oil-Vinegar(UOV)署名方式に基づく、層状の構成を持つ多変数署名方式です。Rainbow の層によって課される追加の構造は、方式をより多くの暗号解読手法にさらすことになりますが、方式の効率を向上させます。Rainbow は、高速な署名と検証、および非常に短い署名を提供しますが、公開鍵は非常に大きくなります。

The selection of Rainbow increases the diversity of the finalist signature schemes; however, due to the very large key size, Rainbow is not suitable as a general-purpose signature algorithm to replace algorithms that currently appear in FIPS 186-4. In particular, the large public keys make certificate chains extremely large. There are applications, however, which do not need to send keys very often. For such applications, Rainbow offers small and fast signatures. The only other advancing candidate signature with a similar performance profile, GeMSS, has substantially larger keys and appears to be difficult to implement on very low-end devices. For these reasons, Rainbow was selected as a finalist.

Rainbow の選定により、ファイナリストの署名方式の多様性が高まります。しかし、鍵サイズが非常に大きいため、Rainbow は、現在 FIPS 186-4 に記載されているアルゴリズムに置き換わる汎用の署名アルゴリズムには適していません。特に、公開鍵が大きいと、証明書チェーンが極端に大きくなります。しかし、鍵を頻繁に送る必要のないアプリケーションもあります。そうしたアプリケーションに対して、Rainbow は小さく高速な署名を提供します。同様の性能プロファイルを持つ、ほかに選定された候補署名である GeMSS は、鍵が大幅に大きく、非常に低機能のデバイスでは実装が困難であるように見えます。これらの理由から、Rainbow はファイナリストとして選定されました。

NIST researchers noted a gap between performance and theoretical complexity for a few attack avenues relevant to the Rainbow scheme. During the second round, some tighter theoretical analyses of (as well as new algorithms for) these well-known attacks have been published [41, 46]. In particular, [46] shows that a parameter tweak is necessary for all parameter sets to achieve the claimed levels of security. Still, with a more conservative parameter selection, it should be possible to meet the claimed security levels with minimal performance cost.

NIST の研究者は、Rainbow 方式に関連するいくつかの攻撃経路について、性能と理論的計算量の間にギャップがあることを指摘しました。第 2 ラウンドの間に、これらのよく知られた攻撃について、より厳密な理論分析(および新しいアルゴリズム)が公表されました [41, 46]。特に [46] は、主張された水準の安全性を達成するには、すべてのパラメーターセットでパラメーターの調整が必要であることを示しています。それでも、より保守的なパラメーターを選択すれば、性能コストを最小限に抑えて、主張された安全性の水準を満たすことができるはずです。

Before Rainbow can be ready for standardization, its parameters must be adjusted to ensure that it meets its claimed security targets. In addition, NIST prefers algorithms with royalty-free licensing in order to encourage widespread adoption.

Rainbow の標準化の準備が整うには、主張された安全性目標を満たすことを確実にするために、パラメーターを調整しなければなりません。加えて、NIST は、広範な採用を促進するため、ロイヤルティフリーのライセンスのアルゴリズムを好みます。

3.21 GeMSS

3.21 GeMSS

GeMSS is a multivariate signature scheme constructed using the “big field” paradigm. GeMSS is based on the HFEv- construction originating in the late 1990s. The scheme utilizes a Fiestel-Patarin construction to bootstrap EUF-CMA security from the assumed universal unforgeability of the HFEv- primitive.

GeMSS は、「ビッグフィールド」パラダイムを用いて構築された多変数署名方式です。GeMSS は、1990 年代後半に始まった HFEv- 構成に基づいています。この方式は、Fiestel-Patarin 構成を利用して、HFEv- プリミティブの仮定された汎用的偽造不可能性から EUF-CMA 安全性をブートストラップします。

GeMSS offers the smallest signatures of any digital signature candidate, supports a reasonably fast verification algorithm, and rests on a stable and well-studied mathematical problem. The drawbacks of the scheme include extremely large public keys, difficulty implementing the algorithm on low-end devices, and signing times ranging from slow to very slow. With these performance security characteristics, GeMSS seems to be a good and appropriate tool for applications in which offline signing and no transmission of the public key are acceptable and expected. GeMSS’s large public keys may not work in many implementations of TLS and SSH without some implementation updates.

GeMSS は、デジタル署名候補の中で最も小さい署名を提供し、そこそこ高速な検証アルゴリズムをサポートし、安定してよく研究された数学的問題に基づいています。この方式の欠点には、公開鍵が極めて大きいこと、低機能のデバイスへのアルゴリズムの実装が困難であること、署名時間が遅いものから非常に遅いものまであることが含まれます。これらの性能と安全性の特性から、GeMSS は、オフラインでの署名と公開鍵を送信しないことが許容され、かつ想定されるアプリケーションにとって、適切で良いツールであると思われます。GeMSS の大きな公開鍵は、実装の更新なしには、TLS や SSH の多くの実装では機能しない可能性があります。

The second-round inclusion of the RedGeMSS and BlueGeMSS parameter sets offers additional flexibility in the performance properties over the initial submission package and appropriately addresses the concerns raised in [9]. It is possible that there may yet be additional trade-offs to further improve performance. In particular, the consideration of the number of bit operations involved in a hash collision attack may warrant a reevaluation of the number of iterations required in the Fiestel-Patarin transformation. As with Rainbow, ROLLO, and RQC, the complexity of some key recovery attacks against GeMSS was affected by recent progress on algebraic methods for solving MinRank [41]. However, this research did not contradict the claimed security of any of GeMSS’s proposed parameter sets.

第 2 ラウンドでの RedGeMSS と BlueGeMSS のパラメーターセットの追加により、当初の提出パッケージに比べて性能特性に柔軟性が加わり、[9] で提起された懸念に適切に対処しています。性能をさらに改善する追加のトレードオフがまだ存在する可能性があります。特に、ハッシュ衝突攻撃に関わるビット演算数の検討により、Fiestel-Patarin 変換に必要な反復回数の再評価が必要になるかもしれません。Rainbow、ROLLO、RQC と同様に、GeMSS に対する一部の鍵回復攻撃の計算量は、MinRank を解く代数的手法における最近の進展の影響を受けました [41]。しかし、この研究は、GeMSS の提案されたパラメーターセットのいずれについても、主張された安全性に反するものではありませんでした。

GeMSS competes most closely with Rainbow, another multivariate signature scheme with large keys and small signatures. GeMSS has much bigger public keys and much slower signing in exchange for slightly smaller signatures; Rainbow’s performance profile is more appealing for most applications, and GeMSS appears to be difficult to implement on low-end devices. GeMSS is also based on a different security assumption. NIST sees GeMSS as an option for standardization if developments during the third round show Rainbow to be unacceptable for standardization. For these reasons, GeMSS was chosen as an alternative candidate.

GeMSS は、同じく鍵が大きく署名が小さい多変数署名方式である Rainbow と最も直接的に競合します。GeMSS は、署名がわずかに小さい代わりに、公開鍵がはるかに大きく、署名がはるかに遅くなります。ほとんどのアプリケーションにとっては Rainbow の性能プロファイルのほうが魅力的であり、GeMSS は低機能のデバイスでは実装が困難であるように見えます。GeMSS は、異なる安全性の仮定にも基づいています。NIST は、第 3 ラウンドの間の進展により Rainbow が標準化に適さないことが示された場合には、GeMSS を標準化の選択肢とみなしています。これらの理由から、GeMSS は代替候補として選ばれました。

3.22 Picnic

3.22 Picnic

Picnic is a signature scheme that uses no number-theoretic or structured hardness assumptions. The security of Picnic depends on a random oracle assumption on the underlying hash function and on the security of the LowMC block cipher [47] against an adversary given a single plaintext/ciphertext pair. A Picnic signature is a non-interactive zero-knowledge proof of knowledge of the secret key. The message being signed is incorporated (via hashing) into the challenges of the proof of knowledge in such a way that only the holder of the secret key can produce the proof. The length of the signature depends on the multiplicative complexity of the encryption scheme and the specific technique to construct a zero-knowledge proof of knowledge (from the field of secure multi-party computation [48]). Picnic has small public key size, large signatures, and slow signing and verifying. Additionally, it appears that a straightforward implementation would have significant side-channel issues [49]. The second-round submission included analyses in the QROM model for each variant of PICNIC.

Picnic は、数論的な、あるいは構造化された困難性の仮定を一切用いない署名方式です。Picnic の安全性は、基になるハッシュ関数に関するランダムオラクルの仮定と、単一の平文と暗号文のペアを与えられた攻撃者に対する LowMC ブロック暗号 [47] の安全性に依存します。Picnic の署名は、秘密鍵の知識の非対話型ゼロ知識証明です。署名されるメッセージは、秘密鍵の保持者だけが証明を生成できるように、(ハッシュ化を通じて)知識証明のチャレンジに組み込まれます。署名の長さは、暗号化方式の乗法的複雑さと、(セキュアマルチパーティ計算 [48] の分野から得られた)ゼロ知識の知識証明を構成する具体的な手法に依存します。Picnic は、公開鍵サイズが小さく、署名が大きく、署名と検証が遅くなっています。加えて、単純な実装には重大なサイドチャネルの問題があるように見えます [49]。第 2 ラウンドの提出には、PICNIC の各変種に対する QROM モデルでの分析が含まれていました。

Picnic is a highly modular design. The cryptographic primitives—a hash function and block cipher—could be instantiated in different ways. The submitted design uses LowMC, a block cipher designed to have low multiplicative complexity. LowMC has not been studied as much as AES and hence needs much more analysis before it can be standardized by NIST. However, the security requirements for the underlying block cipher in Picnic are much less stringent than the general security requirements of a block cipher—only a single plaintext/ciphertext pair is ever revealed, and an attacker needs to find a key that maps that plaintext to that ciphertext in order to forge Picnic signatures. Variants of Picnic based on AES have been proposed [50], but these lead to much larger signatures.

Picnic は、高度にモジュール化された設計です。暗号プリミティブ(ハッシュ関数とブロック暗号)は、さまざまな方法でインスタンス化できます。提出された設計は、乗法的複雑さが低くなるよう設計されたブロック暗号である LowMC を使用しています。LowMC は AES ほど研究されておらず、NIST によって標準化される前に、はるかに多くの分析が必要です。しかし、Picnic の基になるブロック暗号に対する安全性要件は、ブロック暗号の一般的な安全性要件よりはるかに緩やかです。明らかになるのは単一の平文と暗号文のペアだけであり、攻撃者が Picnic の署名を偽造するには、その平文をその暗号文に写す鍵を見つける必要があります。AES に基づく Picnic の変種も提案されています [50] が、署名がはるかに大きくなります。

The approach to designing a signature scheme used in Picnic is quite new, and the design is evolving rapidly. Changes to the parameters and underlying proof of knowledge made during the second round improved performance significantly while fixing attacks discovered in the first round. NIST sees Picnic as an algorithm that is not yet mature enough to be standardized but which has the potential to improve a great deal in both performance and confidence in its security in the near future. NIST also sees Picnic’s reliance on only assumptions about symmetric primitives as an advantage in case the need arises for an extremely conservative signature standard in the future. For this reason, Picnic was not selected as a finalist but was included as an alternate candidate.

Picnic で用いられている署名方式の設計アプローチは非常に新しく、設計は急速に進化しています。第 2 ラウンドの間に行われたパラメーターおよび基になる知識証明の変更は、第 1 ラウンドで発見された攻撃を修正しつつ、性能を大幅に改善しました。NIST は Picnic を、標準化するにはまだ十分に成熟していないものの、近い将来、性能と安全性への信頼の両方が大きく向上する可能性があるアルゴリズムとみなしています。NIST はまた、Picnic が共通鍵プリミティブに関する仮定のみに依拠していることを、将来、極めて保守的な署名標準が必要になった場合の利点とみなしています。この理由から、Picnic はファイナリストには選ばれませんでしたが、代替候補に含まれました。

3.23 SPHINCS+

3.23 SPHINCS+

SPHINCS+ is a stateless hash-based signature scheme. Its security is based entirely on assumptions about the security of the underlying hash function. There is a proof of security for all variants of SPHINCS+ in the random oracle model. There is also a standard-model proof for the robust variants based on plausible but nonstandard assumptions regarding a tweakable hash function constructed from the underlying hash. This proof assumes that the tweakable hash functions have post-quantum single function, multi-target collision resistance for distinct tweaks and post-quantum single function, multi-target decisional second-preimage resistance for distinct tweaks. Hash-based signatures are a very old technology dating back to the dawn of public key cryptography, so they have seen many decades of analysis. In general, SPHINCS+ is probably the least likely of any post-quantum signature candidate to be broken cryptanalytically. On the other hand, the design of SPHINCS+ makes it especially vulnerable to fault attacks [51, 52] and, to a lesser extent, side-channel attacks.

SPHINCS+ は、ステートレスなハッシュベースの署名方式です。その安全性は、基になるハッシュ関数の安全性に関する仮定のみに基づいています。ランダムオラクルモデルでは、SPHINCS+ のすべての変種について安全性の証明があります。また、基になるハッシュから構成される tweak 可能なハッシュ関数に関する、もっともらしいが非標準の仮定に基づく、頑健な変種の標準モデルでの証明もあります。この証明は、tweak 可能なハッシュ関数が、異なる tweak に対する耐量子の単一関数・マルチターゲット衝突耐性と、異なる tweak に対する耐量子の単一関数・マルチターゲット選択第二原像耐性を持つと仮定しています。ハッシュベースの署名は、公開鍵暗号の黎明期にまでさかのぼる非常に古い技術であり、数十年にわたる分析を経ています。一般に、SPHINCS+ は、耐量子署名の候補の中で、暗号解読によって破られる可能性が最も低いものでしょう。一方で、SPHINCS+ の設計は、フォールト攻撃 [51, 52] に特に脆弱であり、程度は低いもののサイドチャネル攻撃にも脆弱です。

SPHINCS+ is a mature design with a thorough and clear specification. SPHINCS+ provides very solid assurance of its security claims, but this comes at a substantial cost in performance—it is slower, and its signatures are considerably larger than most other signature schemes. For example, for category 1 security, the shortest available SPHINCS+ signatures are four times the size of Dilithium signatures and require more than a thousand times the computation to produce. By contrast, SPHINCS+ public keys are very small—down to 32 bytes for category 1 security.

SPHINCS+ は、徹底した明確な仕様を持つ、成熟した設計です。SPHINCS+ はその安全性の主張に対して非常に堅固な保証を提供しますが、その代償として性能が大きく犠牲になっています。ほかのほとんどの署名方式より遅く、署名もかなり大きくなります。たとえば、カテゴリー 1 の安全性では、利用可能な最短の SPHINCS+ 署名は Dilithium の署名の 4 倍の大きさで、生成に 1,000 倍を超える計算を必要とします。対照的に、SPHINCS+ の公開鍵は、カテゴリー 1 の安全性で 32 バイトまで小さく、非常に小さいです。

SPHINCS+ is defined with many different parameter sets offering different trade-offs between speed and signature size at security categories 1, 3, and 5. SPHINCS+ also added “simple” variants in round two, which provide improved speed for signing and verifying at the cost of security being proven only in the random oracle model. Some parameter sets require the use of a non-standard algorithm (Haraka [53]); if SPHINCS+ is eventually chosen as a standard, NIST does not foresee standardizing those parameter sets. The performance profile of SPHINCS+ means that dropping it into existing systems which now use RSA or ECDSA signatures would not work well; extensive re-engineering would likely be necessary. It is difficult to imagine TLS with SPHINCS+ as the signature algorithm providing acceptable performance. Both the speed and size of signatures would be unacceptable.

SPHINCS+ は、セキュリティカテゴリー 1、3、5 で、速度と署名サイズの間に異なるトレードオフを提供する、多くの異なるパラメーターセットで定義されています。SPHINCS+ は第 2 ラウンドで「simple」変種も追加しました。これらは署名と検証の速度を改善しますが、その代償として、安全性がランダムオラクルモデルでのみ証明されます。一部のパラメーターセットは、非標準のアルゴリズム(Haraka [53])の使用を必要とします。SPHINCS+ が最終的に標準として選ばれたとしても、NIST はそれらのパラメーターセットを標準化することを想定していません。SPHINCS+ の性能プロファイルは、現在 RSA や ECDSA の署名を使っている既存のシステムにそのまま組み込んでもうまく機能せず、大規模な再設計が必要になるであろうことを意味します。署名アルゴリズムとして SPHINCS+ を使う TLS が、許容できる性能を提供することは想像しにくいです。署名の速度とサイズの両方が許容できないものになるでしょう。

NIST sees SPHINCS+ as an extremely conservative choice for standardization. If NIST’s confidence in better performing signature algorithms is shaken by new analysis , SPHINCS+ could provide an immediately available algorithm for standardization at the end of the third round. Further, if NIST sees the need for an additional signature algorithm for applications that need very high security and can tolerate larger and slower signatures, NIST may decide to standardize SPHINCS+ in the future.

NIST は、SPHINCS+ を標準化にとって極めて保守的な選択肢とみなしています。性能の良い署名アルゴリズムに対する NIST の信頼が、新たな分析によって揺らいだ場合には、SPHINCS+ が、第 3 ラウンドの終了時に標準化のためにすぐに利用できるアルゴリズムとなりえます。さらに、非常に高い安全性を必要とし、より大きく遅い署名を許容できるアプリケーション向けに、追加の署名アルゴリズムが必要だと NIST が判断した場合には、NIST は将来 SPHINCS+ を標準化することを決定するかもしれません。

3.24 LUOV

3.24 LUOV

LUOV is a multivariate signature scheme of the “small field” variety. LUOV is based on the UOV signature scheme that has remained secure and unchanged for over twenty years. The L in the name stands for “Lifted” and specifies the main innovation of the design. The keys of LUOV are far smaller than UOV keys with the same parameters because the coefficients of the keys of LUOV are depressed into a subfield.

LUOV は、「スモールフィールド」の種類の多変数署名方式です。LUOV は、20 年以上にわたって安全であり続け、変更もされていない UOV 署名方式に基づいています。名前の L は「Lifted」を表し、設計の主要な革新を示しています。LUOV の鍵の係数は部分体に落とし込まれているため、同じパラメーターの UOV の鍵よりもはるかに小さくなります。

During the second round, it was shown that the lifting modification is generically weak for sufficiently underdefined systems due to a new type of differential attack (see [54]). The second-round parameter sets of LUOV were significantly affected by this approach, undermining confidence in this methodology for any sufficiently underdefined polynomial system.

第 2 ラウンドの間に、新しい種類の差分攻撃により、リフティングの修正が、十分に劣決定な系に対しては一般的に脆弱であることが示されました([54] を参照)。LUOV の第 2 ラウンドのパラメーターセットはこのアプローチによって大きな影響を受け、十分に劣決定な多項式系に対するこの手法への信頼が損なわれました。

NIST did not select LUOV to advance to the third round. The development of the aforementioned attacks shows that the lifting innovation is too new to be incorporated into a standard at this time; however, there is room for growth in this area. The attack of [54] relies on the lifting degree as well as the imbalance in the number of polynomials and unknowns in the key. LUOV has already inspired the application of field lifting for other schemes [55], and while it is premature to either trust or discard the lifting construction, NIST believes there is value in the development of the science in this direction.

NIST は、LUOV を第 3 ラウンドに進めるものとしては選定しませんでした。上記の攻撃の登場は、リフティングという革新が、現時点で標準に取り入れるには新しすぎることを示していますが、この分野には成長の余地があります。[54] の攻撃は、リフティングの次数と、鍵における多項式の数と未知数の数の不均衡に依存しています。LUOV は既に、ほかの方式 [55] に対する体のリフティングの適用を促しており、リフティングの構成を信頼するのも破棄するのも時期尚早ですが、NIST は、この方向での科学の発展には価値があると考えています。

3.25 MQDSS

3.25 MQDSS

MQDSS is a multivariate digital signature scheme constructed via a Fiat-Shamir transform on a provably secure 5-pass identification scheme based on the multivariate quadratic (MQ) problem. Due to its construction, MQDSS is more directly comparable in structure and performance to symmetric-based signature schemes than other multivariate candidates.

MQDSS は、多変数二次(MQ)問題に基づく、証明可能安全な 5 パス識別方式に対する Fiat-Shamir 変換によって構成された、多変数デジタル署名方式です。その構成のため、MQDSS は、ほかの多変数候補よりも、共通鍵ベースの署名方式に構造と性能の面でより直接的に比較できます。

During the second round, MQDSS suffered a forgery attack [56] that undermined the security claims for the submitted parameters. While the attack did not invalidate the proof of security for MQDSS, the practical effect of the attack is that 40 % more rounds and 50 % larger keys are required.

第 2 ラウンドの間に、MQDSS は偽造攻撃 [56] を受け、提出されたパラメーターに対する安全性の主張が損なわれました。この攻撃は MQDSS の安全性の証明を無効にするものではありませんでしたが、攻撃の実際上の影響として、ラウンド数が 40 % 多く、鍵が 50 % 大きく必要となります。

Even before the attack, MQDSS seemed to offer performance comparable but inferior to the most similar round 2 candidates, Picnic and SPHINCS+. The performance impact of the attack, however, renders MQDSS uncompetitive with Picnic and SPHINCS+. For this reason, MQDSS was not selected for inclusion among the round 3 candidates.

攻撃を受ける前から、MQDSS は、最も類似した第 2 ラウンド候補である Picnic や SPHINCS+ に、同程度ではあるが劣る性能を提供するように見えました。しかし、攻撃による性能への影響により、MQDSS は Picnic や SPHINCS+ に対して競争力を失いました。この理由から、MQDSS は第 3 ラウンドの候補に含めるものとしては選定されませんでした。

3.26 qTESLA

3.26 qTESLA

qTESLA is a digital signature scheme based on structured lattice assumptions. The public keys in qTESLA consist of LWE samples within a ring, and signing is done using hash functions and the “Fiat-Shamir with aborts” technique referred to above. The second-round version of qTESLA that was submitted to NIST specified 12 different parameter sets (q-TESLA-*, q-TESLA-*-s, and q-TESLA-p-*). After questions were raised about the security arguments in the specification [57], the authors retracted 10 of the parameter sets and kept the remaining two (q-TESLA-p-I and q-TESLA-p-III).

qTESLA は、構造化格子の仮定に基づくデジタル署名方式です。qTESLA の公開鍵は環内の LWE サンプルで構成され、署名は、ハッシュ関数と上述の「Fiat-Shamir with aborts」手法を用いて行われます。NIST に提出された qTESLA の第 2 ラウンド版は、12 の異なるパラメーターセット(q-TESLA-*、q-TESLA-*-s、q-TESLA-p-*)を規定していました。仕様にある安全性の議論について疑問が提起された [57] 後、著者は 10 のパラメーターセットを撤回し、残りの 2 つ(q-TESLA-p-I と q-TESLA-p-III)を維持しました。

Although there is a benefit to having a diversity of design among lattice-based candidates, the performance of the remaining parameter sets of qTESLA is not strong enough to remain competitive. In particular, the public key sizes of q-TESLA-p-I and q-TESLA-p-III are about 15 to 20 times as large as those of FALCON and CRYSTALS-DILITHIUM, and the signature sizes are larger as well. In comparing cycle counts required for signing and verifying, qTESLA is roughly 2 to 5 times slower than FALCON and CRYSTALS-DILITHIUM. For these reasons, qTESLA is not advancing to the third round.

格子ベースの候補の間で設計の多様性があることには利点がありますが、qTESLA の残りのパラメーターセットの性能は、競争力を維持するのに十分なほど強力ではありません。特に、q-TESLA-p-I と q-TESLA-p-III の公開鍵サイズは FALCON や CRYSTALS-DILITHIUM のものの約 15〜20 倍であり、署名サイズも大きくなっています。署名と検証に必要なサイクル数を比較すると、qTESLA は FALCON や CRYSTALS-DILITHIUM よりおよそ 2〜5 倍遅くなっています。これらの理由から、qTESLA は第 3 ラウンドに進みません。

4 Conclusion

4 結論

The internal and external cryptanalysis, performance benchmarks, studies, and experiments involving the second-round candidates led NIST to the selection of seven third-round finalists and eight alternate candidates. The announcement of these schemes marks the beginning of the third round of the NIST PQC Standardization Process. This decision was difficult as several eliminated schemes are based on novel ideas or research areas which are still worthy of continued study.

第 2 ラウンドの候補に関する内部および外部の暗号解読、性能ベンチマーク、研究、実験により、NIST は 7 つの第 3 ラウンドのファイナリストと 8 つの代替候補を選定するに至りました。これらの方式の発表は、NIST PQC 標準化プロセスの第 3 ラウンドの開始を意味します。除外された方式のいくつかは、引き続き研究する価値のある新しいアイデアや研究分野に基づいているため、この決定は困難なものでした。

As CRYSTALS-KYBER, NTRU, and SABER are all structured lattice schemes, NIST intends to select, at most, one of these finalists to be standardized. The same is true for the finalist signature schemes CRYSTALS-DILITHIUM and FALCON. In NIST’s current view, these structured lattice schemes appear to be the most promising general-purpose algorithms for public-key encryption/KEM and digital signature schemes. Nonetheless, NIST believes it is prudent to continue to study schemes that are not based on structured lattices as a hedge against unexpected progress in cryptanalysis. This is particularly true for digital signature schemes where the best schemes that are not based on structured lattices have a substantial performance penalty for general-purpose use.

CRYSTALS-KYBER、NTRU、および SABER はいずれも構造化格子方式であるため、NIST は、これらのファイナリストのうち、標準化するものを最大でも 1 つ選定する意向です。ファイナリストの署名方式である CRYSTALS-DILITHIUM と FALCON についても同様です。NIST の現時点の見解では、これらの構造化格子方式は、公開鍵暗号化 / KEM とデジタル署名方式の汎用アルゴリズムとして最も有望であるように見えます。それでも NIST は、暗号解読における予想外の進展へのヘッジとして、構造化格子に基づかない方式の研究を続けることが賢明だと考えています。これは特にデジタル署名方式に当てはまり、構造化格子に基づかない最良の方式は、汎用の用途では性能上の不利益が大きくなります。

For the eight alternate candidate algorithms advancing to the third round, NIST notes that these algorithms still may potentially be standardized; although that most likely will not occur at the end of the third round. NIST expects to have a fourth round of evaluation for some of the candidates on this track.

第 3 ラウンドに進む 8 つの代替候補アルゴリズムについて、NIST は、これらのアルゴリズムも標準化される可能性があると述べています。ただし、第 3 ラウンドの終了時に標準化されることはまずありません。NIST は、このトラックの候補の一部について、第 4 ラウンドの評価を行うことを見込んでいます。

If new results emerge during the third round which undermine NIST’s confidence in some of the finalists, NIST may extend the timeline, or make changes to the process. If NIST has less serious concerns specific to a particular finalist and sees the need to continue evaluating it, NIST may instead defer the decision about standardization for the affected finalist until the fourth round.

ファイナリストの一部に対する NIST の信頼を損なう新たな成果が第 3 ラウンドの間に出てきた場合、NIST はスケジュールを延長するか、プロセスに変更を加えることがあります。特定のファイナリストに固有の、それほど深刻でない懸念があり、評価を継続する必要があると NIST が判断する場合には、NIST は代わりに、影響を受けるファイナリストの標準化に関する決定を第 4 ラウンドまで延期することがあります。

The third round is expected to last 12-18 months. Submission modifications should be submitted to NIST by October 1, 2020, in a complete submission package as defined in [33]. It would be helpful if submission teams provided NIST with a summary of their expected changes by August 10, 2020. As a general guideline, NIST expects that any modifications to the seven finalists should be relatively minor while allowing more latitude to the eight additional candidate algorithms. Note, however, that larger changes may signal that an algorithm is not mature enough for standardization at this time. More detailed instructions will be provided.

第 3 ラウンドは 12 か月から 18 か月続くと見込まれています。提出内容の修正は、[33] で定義された完全な提出パッケージとして、2020 年 10 月 1 日までに NIST に提出すべきです。提出チームが、予定している変更の要約を 2020 年 8 月 10 日までに NIST に提供すると有用です。一般的な指針として、NIST は、7 つのファイナリストに対する修正は比較的軽微であるべきだと見込んでおり、8 つの追加候補アルゴリズムにはより大きな自由度を認めます。ただし、より大きな変更は、そのアルゴリズムが現時点で標準化するには成熟していないことを示す場合があることに注意してください。より詳細な指示は追って提供されます。

The efforts of the cryptographic community have been invaluable in analyzing and implementing schemes throughout this process. NIST hopes that with only seven finalists and eight alternate candidates, the public review period will include more work on side-channel resistant implementations, performance data in internet protocols, and performance data for hardware implementations in addition to more rigorous cryptanalytical study. NIST is grateful to the community for all of the research, support, and analysis provided.

暗号コミュニティの尽力は、このプロセスを通じて、方式の分析と実装において非常に貴重なものでした。NIST は、ファイナリストが 7 つ、代替候補が 8 つだけになることで、パブリックレビュー期間に、より厳密な暗号解読研究に加えて、サイドチャネル耐性のある実装、インターネットプロトコルでの性能データ、ハードウェア実装の性能データに関するより多くの作業が含まれることを期待しています。NIST は、コミュニティが提供したすべての研究、支援、分析に感謝します。

NIST plans to host a Third NIST PQC Standardization Conference in the spring or summer of 2021. More details will be provided at a later date. NIST expects to select a small number of candidates for standardization by early 2022. To achieve this goal, the third round will serve as a final round for the first phase of standardization, though some schemes will remain under consideration for future standards.

NIST は、2021 年の春または夏に、第 3 回 NIST PQC 標準化カンファレンスを開催する予定です。詳細は後日提供されます。NIST は、2022 年初頭までに少数の候補を標準化のために選定することを見込んでいます。この目標を達成するため、第 3 ラウンドは標準化の第 1 段階の最終ラウンドとなりますが、一部の方式は将来の標準のために引き続き検討対象として残ります。

NIST is pleased with the progress of the PQC standardization effort but recognizes that current and future research may lead to promising schemes which were not part of the NIST PQC Standardization Project. NIST may adopt a mechanism to accept such proposals at a later date. In particular, NIST would be interested in a general-purpose digital signature scheme which is not based on structured lattices.

NIST は PQC 標準化の取り組みの進展を歓迎していますが、現在および将来の研究によって、NIST PQC 標準化プロジェクトの一部ではなかった有望な方式が生まれる可能性があることを認識しています。NIST は、そうした提案を受け付ける仕組みを後日採用することがあります。特に NIST は、構造化格子に基づかない汎用のデジタル署名方式に関心を持っています。

References

参考文献

[1] National Institute of Standards and Technology (2013) Digital Signature Standard (DSS). (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 186-4. https://doi.org/10.6028/NIST.FIPS.186-4

[1] National Institute of Standards and Technology (2013) Digital Signature Standard (DSS). (U.S. Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) 186-4. https://doi.org/10.6028/NIST.FIPS.186-4

[2] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R (2018) Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56A, Rev. 3. https://doi.org/10.6028/NIST.SP.800-56Ar3

[2] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R (2018) Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56A, Rev. 3. https://doi.org/10.6028/NIST.SP.800-56Ar3

[3] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56B, Rev. 2. https://doi.org/10.6028/NIST.SP.800-56Br2

[3] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56B, Rev. 2. https://doi.org/10.6028/NIST.SP.800-56Br2

[4] “Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms”, 81 Federal Register 92787 (December 20, 2016), pp. 92787-92788. https://federalregister.gov/d/2016-30615

[4] “Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms”, 81 Federal Register 92787 (December 20, 2016), pp. 92787-92788. https://federalregister.gov/d/2016-30615

[5] Moody D (2016) Post-Quantum Cryptography Standardization: Announcement and outline of NIST’s Call for Submissions. International Conference on Post-Quantum Cryptography - PQCrypto. Available at https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis

[5] Moody D (2016) Post-Quantum Cryptography Standardization: Announcement and outline of NIST’s Call for Submissions. International Conference on Post-Quantum Cryptography - PQCrypto. 入手先: https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis

[6] Chen L, Jordan S, Liu Y-K, Moody D, Peralta R, Perlner RA, Smith-Tone D (2016) Report on Post-Quantum Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105

[6] Chen L, Jordan S, Liu Y-K, Moody D, Peralta R, Perlner RA, Smith-Tone D (2016) Report on Post-Quantum Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105

[7] “Request for Comments on Post-Quantum Cryptography Requirements and Evaluation Criteria”, 81 Federal Register 50686 (August 2, 2016), pp. 50686-50687. https://federalregister.gov/d/2016-18150

[7] “Request for Comments on Post-Quantum Cryptography Requirements and Evaluation Criteria”, 81 Federal Register 50686 (August 2, 2016), pp. 50686-50687. https://federalregister.gov/d/2016-18150

[8] Workshop on Cybersecurity in a Post-Quantum World. National Institute of Standards and Technology, Gaithersburg, Maryland, April 2-3, 2015. Available at https://csrc.nist.gov/Events/2015/Workshop-on-Cybersecurity-in-a-Post-Quantum-World.

[8] Workshop on Cybersecurity in a Post-Quantum World. National Institute of Standards and Technology, Gaithersburg, Maryland, April 2-3, 2015. 入手先: https://csrc.nist.gov/Events/2015/Workshop-on-Cybersecurity-in-a-Post-Quantum-World.

[9] Alagic G, Alperin-Sheriff J, Apon D, Cooper DA, Dang QH, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D, Liu Y-K (2019) Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8240. https://doi.org/10.6028/NIST.IR.8240

[9] Alagic G, Alperin-Sheriff J, Apon D, Cooper DA, Dang QH, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D, Liu Y-K (2019) Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8240. https://doi.org/10.6028/NIST.IR.8240

[10] National Institute of Standards and Technology (2016) Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[10] National Institute of Standards and Technology (2016) Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. 入手先: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[11] Guo Q, Johansson T, Nilsson A (2020) A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/743

[11] Guo Q, Johansson T, Nilsson A (2020) A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/743

[12] Bernstein D, Lange T (eds.), eBACS: ECRYPT Benchmarking of Cryptographic Systems - SUPERCOP (2020). Available at https://bench.cr.yp.to/supercop.html

[12] Bernstein D, Lange T (eds.), eBACS: ECRYPT Benchmarking of Cryptographic Systems - SUPERCOP (2020). 入手先: https://bench.cr.yp.to/supercop.html

[13] Florida Atlantic University (2020), PQC-Wiki. Available at https://pqc-wiki.fau.edu/w/Special:DatabaseHome

[13] Florida Atlantic University (2020), PQC-Wiki. 入手先: https://pqc-wiki.fau.edu/w/Special:DatabaseHome

[14] PQShield (2020), PQCzoo. Available at https://pqczoo.com

[14] PQShield (2020), PQCzoo. 入手先: https://pqczoo.com

[15] PQClean (2020). Available at https://github.com/PQClean/PQClean

[15] PQClean (2020). 入手先: https://github.com/PQClean/PQClean

[16] pqm4: Post-quantum crypto library for the ARM Cortex-M4 (2020). Available at https://github.com/mupq/pqm4

[16] pqm4: Post-quantum crypto library for the ARM Cortex-M4 (2020). 入手先: https://github.com/mupq/pqm4

[17] McEliece R (1978) A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, DSN PR 42-44. NASA. Available at https://tmo.jpl.nasa.gov/progress_report2/42-44/44N.PDF

[17] McEliece R (1978) A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, DSN PR 42-44. NASA. 入手先: https://tmo.jpl.nasa.gov/progress_report2/42-44/44N.PDF

[18] Hülsing A, Ning K-C, Schwabe P, Weber F, Zimmermann PR (2020) Post-quantum WireGuard. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/379

[18] Hülsing A, Ning K-C, Schwabe P, Weber F, Zimmermann PR (2020) Post-quantum WireGuard. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/379

[19] Regev O (2004) New lattice-based cryptographic constructions, Journal of the ACM, 51(6): 899-942. https://doi.org/10.1145/1039488.1039490.

[19] Regev O (2004) New lattice-based cryptographic constructions, Journal of the ACM, 51(6): 899-942. https://doi.org/10.1145/1039488.1039490.

[20] Eiichiro F, Okamoto T (1999) Secure Integration of Asymmetric and Symmetric Encryption Schemes. Annual International Cryptology Conference - CRYPTO (Springer), pp. 537-544. https://doi.org/10.5555/646764.706343

[20] Eiichiro F, Okamoto T (1999) Secure Integration of Asymmetric and Symmetric Encryption Schemes. Annual International Cryptology Conference - CRYPTO (Springer), pp. 537-544. https://doi.org/10.5555/646764.706343

[21] Hofheinz D, Hövelmanns K, Kiltz E (2017) A Modular Analysis of the Fujisaki-Okamoto Transformation. Theory of Cryptography Conference (Springer), pp. 341-371. https://doi.org/10.1007/978-3-319-70500-2_12

[21] Hofheinz D, Hövelmanns K, Kiltz E (2017) A Modular Analysis of the Fujisaki-Okamoto Transformation. Theory of Cryptography Conference (Springer), pp. 341-371. https://doi.org/10.1007/978-3-319-70500-2_12

[22] Ravi P, Roy D, Bhasin S, Chattopadhyay A, Mukhopadhyay D (2019) Number “Not Used” Once - Practical Fault Attack on pqm4 Implementations of NIST Candidates. International Workshop on Constructive Side-Channel Analysis and Secure Design (Springer), pp. 232-250. https://doi.org/10.1007/978-3-030-16350-1_13

[22] Ravi P, Roy D, Bhasin S, Chattopadhyay A, Mukhopadhyay D (2019) Number “Not Used” Once - Practical Fault Attack on pqm4 Implementations of NIST Candidates. International Workshop on Constructive Side-Channel Analysis and Secure Design (Springer), pp. 232-250. https://doi.org/10.1007/978-3-030-16350-1_13

[23] Peikert C, Pepin Z (2019) Algebraically Structured LWE Revisited. Theory of Cryptography Conference (Springer), pp. 1-23. https://doi.org/10.1007/978-3-030-36030-6_1

[23] Peikert C, Pepin Z (2019) Algebraically Structured LWE Revisited. Theory of Cryptography Conference (Springer), pp. 1-23. https://doi.org/10.1007/978-3-030-36030-6_1

[24] Erdem A, Ducas L, Pöppelmann T, Schwabe P (2016) Post-quantum key exchange—a new hope. USENIX Security Symposium (USENIX association), pp. 327-343. https://doi.org/10.5555/3241094.3241120

[24] Erdem A, Ducas L, Pöppelmann T, Schwabe P (2016) Post-quantum key exchange—a new hope. USENIX Security Symposium (USENIX association), pp. 327-343. https://doi.org/10.5555/3241094.3241120

[25] Institute of Electrical and Electronics Engineers (2009) IEEE Standard 1363.1-2008 - Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices (IEEE, Piscataway, New Jersey, United States). https://doi.org/10.1109/IEEESTD.2009.4800404

[25] Institute of Electrical and Electronics Engineers (2009) IEEE Standard 1363.1-2008 - Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices (IEEE, Piscataway, New Jersey, United States). https://doi.org/10.1109/IEEESTD.2009.4800404

[26] American National Standards Institute (2010) ANSI X9.98-2010 -Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry (ANSI, New York City, United States). Available at https://webstore.ansi.org/standards/ascx9/ansix9982010r2017

[26] American National Standards Institute (2010) ANSI X9.98-2010 -Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry (ANSI, New York City, United States). 入手先: https://webstore.ansi.org/standards/ascx9/ansix9982010r2017

[27] Sendrier N, Vasseur V. (2020) About low DFR for QC-MDPC decoding. International Conference on Post-Quantum Cryptography – PQCrypto (Springer), pp. 20-34. https://doi.org/10.1007/978-3-030-44223-1_2

[27] Sendrier N, Vasseur V. (2020) About low DFR for QC-MDPC decoding. International Conference on Post-Quantum Cryptography – PQCrypto (Springer), pp. 20-34. https://doi.org/10.1007/978-3-030-44223-1_2

[28] Drucker N, Gueron S, Kostic D (2020) QC-MDPC decoders with several shades of gray. International Conference on Post-Quantum Cryptography -PQCrypto (Springer), pp. 35-50. https://doi.org/10.1007/978-3-030-44223-1_3

[28] Drucker N, Gueron S, Kostic D (2020) QC-MDPC decoders with several shades of gray. International Conference on Post-Quantum Cryptography -PQCrypto (Springer), pp. 35-50. https://doi.org/10.1007/978-3-030-44223-1_3

[29] Dachman-Soled D, Ducas L, Gong H, Rossi M (2020) LWE with Side Information: Attacks and Concrete Security Estimation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/292

[29] Dachman-Soled D, Ducas L, Gong H, Rossi M (2020) LWE with Side Information: Attacks and Concrete Security Estimation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/292

[30] Lyubashevsky V, Peikert C, Regev O (2010) On Ideal Lattices and Learning with Errors over Rings. Annual International Conference on the Theory and Applications of Cryptographic Techniques – EUROCRYPT (Springer), pp. 1-23. https://doi.org/10.1007/978-3-642-12190-5_1

[30] Lyubashevsky V, Peikert C, Regev O (2010) On Ideal Lattices and Learning with Errors over Rings. Annual International Conference on the Theory and Applications of Cryptographic Techniques – EUROCRYPT (Springer), pp. 1-23. https://doi.org/10.1007/978-3-642-12190-5_1

[31] Peikert C, Regev O, Stephens-Davidowitz N (2017) Pseudorandomness of Ring-LWE for Any Ring and Modulus. Annual ACM Symposium on the Theory of Computing Proceedings - STOC (ACM), pp. 461-473. https://doi.org/10.1145/3055399.3055489

[31] Peikert C, Regev O, Stephens-Davidowitz N (2017) Pseudorandomness of Ring-LWE for Any Ring and Modulus. Annual ACM Symposium on the Theory of Computing Proceedings - STOC (ACM), pp. 461-473. https://doi.org/10.1145/3055399.3055489

[32] Jaques S, Schanck J (2019) Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE. Annual International Cryptology Conference - CRYPTO (Springer), pp. 32-61. https://doi.org/10.1007/978-3-030-26948-7_2

[32] Jaques S, Schanck J (2019) Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE. Annual International Cryptology Conference - CRYPTO (Springer), pp. 32-61. https://doi.org/10.1007/978-3-030-26948-7_2

[33] Adj G, Cervantes-Vázquez D, Chi-Domínguez JJ, Menezes A, Rodríguez-Henríquez F (2019) On the Cost of Computing Isogenies Between Supersingular Elliptic Curves. International Conference on Selected Areas in Cryptography - SAC (Springer), pp. 322-343. https://doi.org/10.1007/978-3-030-10970-7_15

[33] Adj G, Cervantes-Vázquez D, Chi-Domínguez JJ, Menezes A, Rodríguez-Henríquez F (2019) On the Cost of Computing Isogenies Between Supersingular Elliptic Curves. International Conference on Selected Areas in Cryptography - SAC (Springer), pp. 322-343. https://doi.org/10.1007/978-3-030-10970-7_15

[34] Aurélien G, Montoya S, Renault G (2020) Attack on LAC Key Exchange in Misuse Situation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/063

[34] Aurélien G, Montoya S, Renault G (2020) Attack on LAC Key Exchange in Misuse Situation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/063

[35] D’Anvers JP, Tiepelt M, Vercauteren F, Verbauwhede I, (2019) Timing attacks on error correcting codes in post-quantum secure schemes. ACM Workshop on Theory of Implementation Security Workshop – TIS (ACM), pp. 2-9. https://doi.org/10.1145/3338467.3358948

[35] D’Anvers JP, Tiepelt M, Vercauteren F, Verbauwhede I, (2019) Timing attacks on error correcting codes in post-quantum secure schemes. ACM Workshop on Theory of Implementation Security Workshop – TIS (ACM), pp. 2-9. https://doi.org/10.1145/3338467.3358948

[36] Greuet A, Montoya S, Renault G (2020) Attack on LAC Key Exchange in Misuse Situation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/063

[36] Greuet A, Montoya S, Renault G (2020) Attack on LAC Key Exchange in Misuse Situation. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/063

[37] Guo Q, Johansson T, Yang J (2019) A Novel CCA Attack using Decryption Errors against LAC. Annual International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT (Springer), pp. 82-111. https://doi.org/10.1007/978-3-030-34578-5_4

[37] Guo Q, Johansson T, Yang J (2019) A Novel CCA Attack using Decryption Errors against LAC. Annual International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT (Springer), pp. 82-111. https://doi.org/10.1007/978-3-030-34578-5_4

[38] Post-Quantum Cryptography Submissions, Public Comments on LAC. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/LAC-official-comment.pdf, https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-2/official-comments/LAC-round2-official-comment.pdf

[38] Post-Quantum Cryptography Submissions, Public Comments on LAC. 入手先: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/LAC-official-comment.pdf, https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-2/official-comments/LAC-round2-official-comment.pdf

[39] Apon D, Perlner R, Robinson A (2020) Cryptanalysis of LEDAcrypt. Cryptology ePrint archive preprint. https://eprint.iacr.org/2020/455

[39] Apon D, Perlner R, Robinson A (2020) Cryptanalysis of LEDAcrypt. Cryptology ePrint archive preprint. https://eprint.iacr.org/2020/455

[40] Bardet M, Briaud P, Bros M, Gaborit P, Neiger V, Ruatta O, Tillich JP (2020) An Algebraic Attack on Rank Metric Code-Based Cryptosystems. Annual International Conference on the Theory and Applications of Cryptographic Techniques – EUROCRYPT (Springer), pp. 64-93. https://doi.org/10.1007/978-3-030-45727-3_3

[40] Bardet M, Briaud P, Bros M, Gaborit P, Neiger V, Ruatta O, Tillich JP (2020) An Algebraic Attack on Rank Metric Code-Based Cryptosystems. Annual International Conference on the Theory and Applications of Cryptographic Techniques – EUROCRYPT (Springer), pp. 64-93. https://doi.org/10.1007/978-3-030-45727-3_3

[41] Bardet M, Bros M, Cabarcas D, Gaborit P, Perlner R, Smith-Tone D, Tillich JP, Verbel J (2002) Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. arXiv preprint. https://arxiv.org/abs/2002.08322

[41] Bardet M, Bros M, Cabarcas D, Gaborit P, Perlner R, Smith-Tone D, Tillich JP, Verbel J (2002) Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. arXiv preprint. https://arxiv.org/abs/2002.08322

[42] Son Y (2019) A Note on Parameter Choices of Round5. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/949

[42] Son Y (2019) A Note on Parameter Choices of Round5. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/949

[43] Son Y, Cheon JH (2019) Revisiting the Hybrid attack on sparse and ternary secret LWE. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/1019

[43] Son Y, Cheon JH (2019) Revisiting the Hybrid attack on sparse and ternary secret LWE. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/1019

[44] Lyubashevsly V (2009) Fiat-Shamir with aborts: Applications to Lattice and Factoring-Based Signatures. International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT (Springer), pp. 598-616. https://doi.org/10.1007/978-3-642-10366-7_35

[44] Lyubashevsly V (2009) Fiat-Shamir with aborts: Applications to Lattice and Factoring-Based Signatures. International Conference on the Theory and Application of Cryptology and Information Security - ASIACRYPT (Springer), pp. 598-616. https://doi.org/10.1007/978-3-642-10366-7_35

[45] Don J, Fehr S, Majenz C, Schaffner C (2019) Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Annual International Cryptology Conference - CRYPTO (Springer), pp. 356-383. https://doi.org/10.1007/978-3-030-26951-7_13

[45] Don J, Fehr S, Majenz C, Schaffner C (2019) Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model. Annual International Cryptology Conference - CRYPTO (Springer), pp. 356-383. https://doi.org/10.1007/978-3-030-26951-7_13

[46] Smith-Tone D, Perlner R (2020) Rainbow Band Separation is Better than we Thought. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/702

[46] Smith-Tone D, Perlner R (2020) Rainbow Band Separation is Better than we Thought. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/702

[47] Albrecht M, Rechberger C, Schneider T, Tiessen T, Zohner M (2015) Ciphers for MPC and FHE. Annual International Conference on the Theory and Applications of Cryptographic Techniques- EUROCRYPT (Springer), pp. 430-454. https://doi.org/10.1007/978-3-662-46800-5_17

[47] Albrecht M, Rechberger C, Schneider T, Tiessen T, Zohner M (2015) Ciphers for MPC and FHE. Annual International Conference on the Theory and Applications of Cryptographic Techniques- EUROCRYPT (Springer), pp. 430-454. https://doi.org/10.1007/978-3-662-46800-5_17

[48] Ishai Y, Kushilevitz E, Ostrovsky R, Sahai A (2007) Zero-Knowledge from Secure Multiparty Computation. ACM Symposium on Theory of Computing -STOC (ACM), pp. 21-30. https://doi.org/10.1145/1250790.1250794

[48] Ishai Y, Kushilevitz E, Ostrovsky R, Sahai A (2007) Zero-Knowledge from Secure Multiparty Computation. ACM Symposium on Theory of Computing -STOC (ACM), pp. 21-30. https://doi.org/10.1145/1250790.1250794

[49] Gellersen T, Seker O, Eisenbarth T (2020) Differential Power Analysis of the Picnic Signature Scheme. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/267

[49] Gellersen T, Seker O, Eisenbarth T (2020) Differential Power Analysis of the Picnic Signature Scheme. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2020/267

[50] Guilhem C, Meyer L, Orsini E, Smart N (2019) BBQ: Using AES in Picnic Signatures. International Conference on Selected Areas in Cryptography – SAC (Springer), pp. 669-692. https://doi.org/10.1007/978-3-030-38471-5_27

[50] Guilhem C, Meyer L, Orsini E, Smart N (2019) BBQ: Using AES in Picnic Signatures. International Conference on Selected Areas in Cryptography – SAC (Springer), pp. 669-692. https://doi.org/10.1007/978-3-030-38471-5_27

[51] Laurent C, Martinelliand A, Prest T (2018) Grafting Trees: A Fault Attack against the SPHINCS framework. International Conference on Post-Quantum Cryptography -PQCrypto (Springer), pp. 165-184. https://doi.org/10.1007/978-3-319-79063-3_8

[51] Laurent C, Martinelliand A, Prest T (2018) Grafting Trees: A Fault Attack against the SPHINCS framework. International Conference on Post-Quantum Cryptography -PQCrypto (Springer), pp. 165-184. https://doi.org/10.1007/978-3-319-79063-3_8

[52] Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A (2018) Practical Fault Injection Attacks on SPHINCS. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2018/674

[52] Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A (2018) Practical Fault Injection Attacks on SPHINCS. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2018/674

[53] Kölbl S, Lauridsen M M, Mendel F, Rechberger C (2016) Haraka v2 – Efficient Short-Input Hashing for Post-Quantum Applications. IACR Transactions on Symmetric Cryptology, 2016(2):1-29. https://doi.org/10.13154/tosc.v2016.i2.1-29

[53] Kölbl S, Lauridsen M M, Mendel F, Rechberger C (2016) Haraka v2 – Efficient Short-Input Hashing for Post-Quantum Applications. IACR Transactions on Symmetric Cryptology, 2016(2):1-29. https://doi.org/10.13154/tosc.v2016.i2.1-29

[54] Ding J, Deaton J, Schmidt K, Vishakha, Zhang Z (2019) Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/1490

[54] Ding J, Deaton J, Schmidt K, Vishakha, Zhang Z (2019) Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme. Cryptology ePrint Archive preprint. https://eprint.iacr.org/2019/1490

[55] Duong D H, Van Luyen L, Tran HTN (2020) Choosing subfields for LUOV and lifting fields for rainbow. IET Information Security, 14(2):196-201. https://doi.org/10.1049/iet-ifs.2018.5288

[55] Duong D H, Van Luyen L, Tran HTN (2020) Choosing subfields for LUOV and lifting fields for rainbow. IET Information Security, 14(2):196-201. https://doi.org/10.1049/iet-ifs.2018.5288

[56] Kales D, Zaverucha G (2020) Forgery Attacks on MQDSSv2.0. Post-Quantum Cryptography Round 2 Submissions, Public Comments on MQDSS. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-2/official-comments/MQDSS-round2-official-comment.pdf

[56] Kales D, Zaverucha G (2020) Forgery Attacks on MQDSSv2.0. Post-Quantum Cryptography Round 2 Submissions, Public Comments on MQDSS. 入手先: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-2/official-comments/MQDSS-round2-official-comment.pdf

[57] Post-Quantum Cryptography Round 2 Submissions, Public Comments on qTESLA. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-2/official-comments/qTESLA-round2-official-comment.pdf

[57] Post-Quantum Cryptography Round 2 Submissions, Public Comments on qTESLA. 入手先: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-2/official-comments/qTESLA-round2-official-comment.pdf