目次

NIST IR 8240 日本語訳

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

[要約] NIST IR 8240 は、NIST 耐量子暗号標準化プロセスの第 1 ラウンドについて報告する文書です。2017 年 11 月に 82 件の候補アルゴリズムが提出され、そのうち 69 件が第 1 ラウンドの候補として受理されました。本報告書は、一般からのフィードバックと内部レビューに基づく評価基準と選定プロセスを説明しています。2019 年 1 月 30 日に第 2 ラウンドに進むと発表された 26 件の候補アルゴリズム(公開鍵暗号化・鍵確立が 17 件、デジタル署名が 9 件)を要約しています。

NISTIR 8240

NISTIR 8240

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

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

Gorjan Alagic
Jacob Alperin-Sheriff
Daniel Apon
David Cooper
Quynh Dang
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
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.8240

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

図表
[NIST logo — not reproduced on this unofficial site]

[NIST のロゴ。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。]

NISTIR 8240

NISTIR 8240

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

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

Gorjan Alagic
Jacob Alperin-Sheriff
Daniel Apon
David Cooper
Quynh Dang
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
Carl Miller
Dustin Moody
Rene Peralta
Ray Perlner
Angela Robinson
Daniel Smith-Tone
コンピュータセキュリティ部門
情報技術研究所

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

Yi-Kai Liu
応用・計算数学部門
情報技術研究所

This publication is available free of charge from:

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

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

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

January 2019

2019 年 1 月

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

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

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 Internal Report 8240
27 pages (January 2019)

米国国立標準技術研究所 内部報告書 8240
27 ページ(2019 年 1 月)

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

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

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.

米国国立標準技術研究所(NIST)の情報技術研究所(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 signature, public-key encryption, and key-establishment algorithms to augment FIPS 186-4, Digital Signature Standard (DSS), as well as special publications SP 800-56A Revision 2, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization. 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.

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

In November 2017, 82 candidate algorithms were submitted to NIST for consideration. Among these, 69 met both the minimum acceptance criteria and our submission requirements, and were accepted as First-Round Candidates on Dec. 20, 2017, marking the beginning of the First Round of the NIST Post-Quantum Cryptography Standardization Process. This report describes the evaluation criteria and selection process, based on public feedback and internal review of the first-round candidates, and summarizes the 26 candidate algorithms announced on January 30, 2019 for moving forward to the second round of the competition. The 17 Second-Round Candidate public-key encryption and key-establishment algorithms are BIKE, Classic McEliece, CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (merger of LEDAkem/LEDApkc), NewHope, NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM), NTRU Prime, NTS-KEM, ROLLO (merger of LAKE/LOCKER/Ouroboros-R), Round5 (merger of Hila5/Round2), RQC, SABER, SIKE, and Three Bears. The 9 Second-Round Candidates for digital signatures are CRYSTALS-DILITHIUM, FALCON, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow, and SPHINCS+.

2017 年 11 月に、82 件の候補アルゴリズムが検討のために NIST に提出されました。このうち 69 件が、最低限の受理基準と提出要件の両方を満たしたとして、2017 年 12 月 20 日に第 1 ラウンド候補として受理され、NIST 耐量子暗号標準化プロセスの第 1 ラウンドが始まりました。本報告書は、第 1 ラウンド候補に対する一般からのフィードバックと内部レビューに基づく、評価基準と選定プロセスを説明し、2019 年 1 月 30 日に競技の第 2 ラウンドに進むと発表された 26 件の候補アルゴリズムを要約します。第 2 ラウンド候補のうち、公開鍵暗号化および鍵確立のアルゴリズム 17 件は、BIKE、Classic McEliece、CRYSTALS-KYBER、FrodoKEM、HQC、LAC、LEDAcrypt(LEDAkem/LEDApkc の統合)、NewHope、NTRU(NTRUEncrypt/NTRU-HRSS-KEM の統合)、NTRU Prime、NTS-KEM、ROLLO(LAKE/LOCKER/Ouroboros-R の統合)、Round5(Hila5/Round2 の統合)、RQC、SABER、SIKE、Three Bears です。デジタル署名の第 2 ラウンド候補 9 件は、CRYSTALS-DILITHIUM、FALCON、GeMSS、LUOV、MQDSS、Picnic、qTESLA、Rainbow、SPHINCS+ です。

Keywords

キーワード

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

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

Supplemental Content

補足資料

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

NIST 耐量子暗号標準化プロセスの Web ページは次の場所にあります。

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 is grateful for the efforts of all candidate submission teams who developed, designed, and analyzed post-quantum public-key algorithms and prepared detailed submission packages describing their algorithms. The cryptographic community’s response of 82 candidate algorithms submitted to the competition was very encouraging. We were also pleased about the graceful and forthright manner with which several of the submitters recognized and accepted the shortcomings of their submissions.

NIST は、耐量子公開鍵アルゴリズムを開発・設計・分析し、アルゴリズムを詳細に記述した提出パッケージを用意した、すべての候補提出チームの尽力に感謝します。競技会に 82 件の候補アルゴリズムが提出されるという暗号コミュニティの反応は、非常に心強いものでした。また、複数の提出者が、自らの提出物の欠点を認め、潔く率直に受け入れてくれたことも、うれしく思います。

NIST is also grateful for the efforts of those in the cryptographic community that provided security, implementation and performance analysis of the candidate algorithms during the first round, as well as the numerous cryptanalysts that attacked the submissions. NIST would not be able to select new post-quantum public-key algorithm for standardization without the combined efforts of these individuals and the algorithm submitters.

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

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

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

Table of Contents

目次

List of Appendices

付録一覧

1 Introduction

1 はじめに

The National Institute of Standards and Technology 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 in each of digital signature, public-key encryption, and key-establishment. The new standards will augment FIPS 186-4, Digital Signature Standard (DSS) [1], as well as Special Publications 800-56A Revision 3, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography [2], and 800-56B, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization [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 PQC (post-quantum cryptography) Standardization Process hereafter in this document.

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

The PQC standardization process is NIST’s response to advances in the development of quantum computers. These machines exploit quantum mechanical phenomena to solve mathematical problems that are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break the public-key cryptosystems currently standardized by NIST, which consist of digital signatures and key-establishment schemes. Quantum computers will have an impact on symmetric-key cryptosystems, however the impact will not be as drastic. The goal of post-quantum cryptography is to develop cryptographic systems that are secure against both quantum and classical computers and can interoperate with existing protocols and networks.

PQC 標準化プロセスは、量子コンピューターの開発の進展に対する NIST の対応です。量子コンピューターは、量子力学的現象を利用して、従来のコンピューターでは困難または解決不可能な数学の問題を解きます。大規模な量子コンピューターが構築されれば、現在 NIST が標準化している、デジタル署名と鍵確立方式からなる公開鍵暗号システムを破ることができるようになります。量子コンピューターは共通鍵暗号システムにも影響を与えますが、その影響はそれほど劇的ではありません。耐量子暗号の目標は、量子コンピューターと古典コンピューターの両方に対して安全で、既存のプロトコルやネットワークと相互運用できる暗号システムを開発することです。

Prior to beginning the NIST PQC Standardization Process, NIST held a workshop in April 2015 [4] to discuss issues related to post-quantum cryptography and its potential future standardization. One year later, NIST released NISTIR 8105, Report on Post-Quantum Cryptography [5], which shared NIST’s understanding about the status of quantum computing and post-quantum cryptography and outlined NIST’s initial plan to move forward in that space. The preliminary details of the NIST PQC Standardization Process were announced in a presentation [6] at PQCrypto 2016.

NIST は、NIST PQC 標準化プロセスを開始する前の 2015 年 4 月に、耐量子暗号とその将来の標準化の可能性に関する課題を論じるためのワークショップ [4] を開催しました。その 1 年後、NIST は NISTIR 8105, Report on Post-Quantum Cryptography [5] を公表しました。この報告書は、量子コンピューティングと耐量子暗号の現状に関する NIST の理解を共有し、この分野で前進するための NIST の当初の計画を概説したものです。NIST PQC 標準化プロセスの予備的な詳細は、PQCrypto 2016 での発表 [6] で公表されました。

NIST published Proposed Requirements and Evaluation Criteria in a Federal Register Notice in August 2016 [7] for public comment. These requirements and evaluation criteria were updated, based on public feedback, and included in a later, second Federal Register Notice published on December 20, 2016 (FRN-Dec16) [8]. This Notice called for public submissions for post-quantum public-key cryptographic algorithms and marked the start of the NIST PQC Standardization Process.

NIST は、2016 年 8 月に、パブリックコメントを求めるため、連邦官報告示で要件と評価基準の案(Proposed Requirements and Evaluation Criteria)[7] を公表しました。これらの要件と評価基準は、一般からのフィードバックに基づいて更新され、2016 年 12 月 20 日に公表された後続の 2 回目の連邦官報告示(FRN-Dec16)[8] に含められました。この告示は、耐量子公開鍵暗号アルゴリズムの一般からの提出を呼びかけるものであり、NIST PQC 標準化プロセスの開始を示すものでした。

Candidate submissions were due on November 30, 2017, at which time NIST received 82 submission packages. This was a great response from the worldwide cryptographic community, which had submitted 21 candidate algorithms for the Advanced Encryption Standard (AES) competition in 1998 [9], and 64 packages for the Secure Hash Algorithm 3 (SHA-3) competition in 2008 [10]. Of the 82 submissions, NIST announced the acceptance of 69 First-Round Candidates as meeting both the submission requirements and minimum acceptability criteria on December 20, 2017. The 69 submissions consisted of 20 digital signature schemes, and 49 public-key encryption (PKE) or key encapsulation mechanisms (KEMs). Submission packages of the first-round candidates were posted online at https://www.nist.gov/pqcrypto for public review and comment.

候補の提出期限は 2017 年 11 月 30 日で、その時点で NIST は 82 件の提出パッケージを受け取りました。これは、1998 年の Advanced Encryption Standard(AES)競技会 [9] に 21 件の候補アルゴリズム、2008 年の Secure Hash Algorithm 3(SHA-3)競技会 [10] に 64 件のパッケージを提出した世界の暗号コミュニティからの大きな反応でした。82 件の提出のうち、NIST は 2017 年 12 月 20 日に、提出要件と最低限の受理基準の両方を満たしたとして、69 件を第 1 ラウンド候補として受理すると発表しました。69 件の提出は、20 件のデジタル署名方式と、49 件の公開鍵暗号化(PKE)または鍵カプセル化メカニズム(KEM)で構成されていました。第 1 ラウンド候補の提出パッケージは、一般からのレビューとコメントのため、https://www.nist.gov/pqcrypto でオンライン公開されました。

NIST held the First NIST PQC Standardization Conference in Ft. Lauderdale, FL on April 11-13, 2018 [11], co-located with PQCrypto 2018. Submitters of the accepted first-round candidates were invited to present their algorithms. NIST also discussed its plan to narrow down the pool of candidates to focus the community’s attention and start the second round of the Standardization Process. Throughout the first round, NIST received much feedback from the cryptographic community. Based on the public feedback and internal reviews of the first-round candidates, NIST announced the selection of 26 algorithms as Second-Round Candidates on January 30, 2019 to move forward to the next stage of the standardization process.

NIST は、2018 年 4 月 11 日から 13 日に、PQCrypto 2018 と併催して、フロリダ州フォートローダーデールで第 1 回 NIST PQC 標準化会議 [11] を開催しました。受理された第 1 ラウンド候補の提出者は、自らのアルゴリズムを発表するよう招待されました。NIST はまた、コミュニティの注意を集中させ、標準化プロセスの第 2 ラウンドを始めるため、候補を絞り込む計画についても議論しました。第 1 ラウンドを通じて、NIST は暗号コミュニティから多くのフィードバックを受け取りました。第 1 ラウンド候補に対する一般からのフィードバックと内部レビューに基づいて、NIST は 2019 年 1 月 30 日に、26 件のアルゴリズムを第 2 ラウンド候補として選定し、標準化プロセスの次の段階に進めると発表しました。

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

NIST PQC 標準化プロセスに関する主な出来事の年表を以下に示します。

•April 2-3, 2015 Workshop on Cybersecurity in a Post-Quantum World, NIST, Gaithersburg, MD

•2015 年 4 月 2 日~3 日 耐量子時代のサイバーセキュリティに関するワークショップ(Workshop on Cybersecurity in a Post-Quantum World)、NIST、メリーランド州ゲイサーズバーグ

•February 24, 2016 PQC Standardization: Announcement and outline of NIST’s Call for Submissions presentation given at PQCrypto 2016

•2016 年 2 月 24 日 PQCrypto 2016 でプレゼンテーション「PQC 標準化: NIST の提出募集の発表と概要(PQC Standardization: Announcement and outline of NIST’s Call for Submissions)」を実施

•April 28, 2016 NISTIR 8105, Report on Post-Quantum Cryptography, released

•2016 年 4 月 28 日 NISTIR 8105, Report on Post-Quantum Cryptography を公表

•August 2, 2016 Federal Register Notice - Proposed Requirements and Evaluation Criteria announced for public comment

•2016 年 8 月 2 日 連邦官報告示 - 要件と評価基準の案(Proposed Requirements and Evaluation Criteria)をパブリックコメント向けに発表

•December 20, 2016 Federal Register Notice – Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms

•2016 年 12 月 20 日 連邦官報告示 – 耐量子公開鍵暗号アルゴリズムの推薦募集(Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms)を発表

•November 30, 2017 Submission Deadline for NIST PQC Standardization Process

•2017 年 11 月 30 日 NIST PQC 標準化プロセスの提出期限

•December 20, 2017 First-Round Candidates were announced. The public comment period on the first-round candidates began.

•2017 年 12 月 20 日 第 1 ラウンド候補を発表。第 1 ラウンド候補に対するパブリックコメント期間が開始。

•April 11-13, 2018 First NIST PQC Standardization Conference, Ft. Lauderdale, FL

•2018 年 4 月 11 日~13 日 第 1 回 NIST PQC 標準化会議、フロリダ州フォートローダーデール

•January 30, 2019 The First Round ended and the Second Round began. Second-Round candidates announced. The public comment period on the second-round candidates began.

•2019 年 1 月 30 日 第 1 ラウンドが終了し、第 2 ラウンドが開始。第 2 ラウンド候補を発表。第 2 ラウンド候補に対するパブリックコメント期間が開始。

•March 15, 2019 Deadline for updated submission packages for the Second Round

•2019 年 3 月 15 日 第 2 ラウンド向けの更新版提出パッケージの提出期限

•August 22-24, 2019 2nd NIST PQC Standardization Conference, Santa Barbara, CA

•2019 年 8 月 22 日~24 日 第 2 回 NIST PQC 標準化会議(2nd NIST PQC Standardization Conference)、カリフォルニア州サンタバーバラ

1.1 Purpose and Organization of this Document

1.1 本書の目的と構成

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

本書の目的は、NIST PQC 標準化プロセスの第 1 ラウンドについて報告することです。本書は次のように構成されています。

Section 2 describes the determination of the first-round candidates using the submission requirements and minimum acceptability requirements defined in FRN-Dec16 [8] for all submissions. It then describes the evaluation criteria and selection process used to ultimately select the second-round candidates.

第 2 節では、すべての提出物に対して FRN-Dec16 [8] で定義された提出要件と最低限の受理要件を用いた、第 1 ラウンド候補の決定について説明します。続いて、第 2 ラウンド候補を最終的に選定するために用いた評価基準と選定プロセスを説明します。

Section 3 summarizes the 26 selected second-round candidates. For each candidate, we provide a brief description of the algorithm and the properties that interested us, as well as characteristics that might cause some concern. This report focuses on the reasons why candidate algorithms were selected, rather than providing detailed justifications for why candidate algorithms were not selected to move to the next round.

第 3 節では、選定された 26 件の第 2 ラウンド候補を要約します。各候補について、アルゴリズムの簡単な説明と、私たちが関心を持った特性、および懸念を生じさせうる特徴を示します。本報告書は、候補アルゴリズムが次のラウンドに進むものとして選定されなかった理由の詳細な根拠を示すのではなく、候補アルゴリズムが選定された理由に焦点を当てます。

Section 4 describes the next steps in the NIST PQC Standardization Process, including provisions for allowable modifications to the second-round candidates and the evaluation process for selecting finalists.

第 4 節では、第 2 ラウンド候補に認める修正の規定や、ファイナリストを選定するための評価プロセスなど、NIST PQC 標準化プロセスの次の段階を説明します。

2 Evaluation Criteria and the Selection Process

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

2.1 Acceptance of the First Round Candidates

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

NIST received 82 candidate algorithm submission packages by the November 30, 2017 entry deadline for the NIST PQC Standardization Process. Of these, NIST accepted 69 first-round candidates as meeting both the submission requirements and the minimum acceptability criteria for being “complete and proper submissions”, as defined in FRN-Dec16. The criteria included provisions for reference and optimized C code implementations, known-answer tests, a written specification, and required intellectual property statements. In addition, the algorithms were required to be implementable in a wide range of hardware and software platforms.

NIST は、NIST PQC 標準化プロセスの応募期限である 2017 年 11 月 30 日までに、82 件の候補アルゴリズムの提出パッケージを受け取りました。このうち NIST は、FRN-Dec16 で定義された提出要件と、提出物が「完全かつ適切」であるための最低限の受理基準の両方を満たしたとして、69 件を第 1 ラウンド候補として受理しました。この基準には、参照実装と最適化された C コード実装、既知解テスト、文書による仕様、および必須の知的財産に関する声明の規定が含まれていました。加えて、アルゴリズムは幅広いハードウェアおよびソフトウェアのプラットフォームで実装可能であることが必須でした。

First Round Candidates

第 1 ラウンド候補

BIG QUAKEGravity-SPHINCSLUOV
BIKEGuess AgainMcNie
CFPKMGuiMersenne-756839
Classic McElieceHILA5MQDSS
Compact LWEHiMQ-3NewHope
CRYSTALS-DILITHIUMHK-17NTRUEncrypt
CRYSTALS-KYBERHQCNTRU-HRSS-KEM
DAGSKCLNTRU Prime
Ding Key ExchangeKINDINTS-KEM
DMELACOdd Manhattan
DRSLAKEOuroboros-R
DualModeMSLEDAkemPicnic
Edon-KLEDApkcPost-quantum RSA Encryption
EMBLEM/R.EMBLEMLeptonPost-quantum RSA Signature
FALCONLIMApqNTRUSign
FrodoKEMLizardpqsigRM
GeMSSLOCKERQC-MDPC-KEM
GiophantusLOTUSqTESLA
RaCoSSRound2SPHINCS+
RainbowRQCSRTPI
RamstakeRVBThree Bears
RankSignSABERTitanium
RLCE-KEMSIKEWalnutDSA
BIG QUAKEGravity-SPHINCSLUOV
BIKEGuess AgainMcNie
CFPKMGuiMersenne-756839
Classic McElieceHILA5MQDSS
Compact LWEHiMQ-3NewHope
CRYSTALS-DILITHIUMHK-17NTRUEncrypt
CRYSTALS-KYBERHQCNTRU-HRSS-KEM
DAGSKCLNTRU Prime
Ding Key ExchangeKINDINTS-KEM
DMELACOdd Manhattan
DRSLAKEOuroboros-R
DualModeMSLEDAkemPicnic
Edon-KLEDApkcPost-quantum RSA Encryption
EMBLEM/R.EMBLEMLeptonPost-quantum RSA Signature
FALCONLIMApqNTRUSign
FrodoKEMLizardpqsigRM
GeMSSLOCKERQC-MDPC-KEM
GiophantusLOTUSqTESLA
RaCoSSRound2SPHINCS+
RainbowRQCSRTPI
RamstakeRVBThree Bears
RankSignSABERTitanium
RLCE-KEMSIKEWalnutDSA

These were the sole criteria used to judge the 82 submission packages. Other factors, such as security, cost, and algorithm and implementation characteristics of the candidates did not enter the review process prior to the first round, nor did cryptanalysis or performance data of a submission impact the acceptance of the first-round candidates.

これらは、82 件の提出パッケージの判定に用いた唯一の基準でした。安全性、コスト、候補のアルゴリズムと実装の特性といったその他の要因は、第 1 ラウンドの前のレビュープロセスには入っておらず、提出物の暗号解読や性能のデータが第 1 ラウンド候補の受理に影響することもありませんでした。

2.2 Evaluation Criteria

2.2 評価基準

FRN-Dec16 identified three broad aspects of evaluation criteria that would be used to compare candidate algorithms throughout the NIST PQC Standardization Process. The three aspects are: 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 first-round candidate evaluations.

FRN-Dec16 は、NIST PQC 標準化プロセスの全体を通じて候補アルゴリズムを比較するために用いる評価基準の、3 つの大きな側面を特定しました。3 つの側面は、1) 安全性、2) コストと性能、3) アルゴリズムと実装の特性です。これらの基準を以下に説明し、それらが第 1 ラウンド候補の評価にどう影響したかを論じます。

2.2.1 Security
2.2.1 安全性

As was the case for the past AES and SHA-3 competitions, security is the most important factor when evaluating the candidate post-quantum algorithms. NIST intends to standardize post-quantum public-key algorithms for use in a wide variety of protocols, such as Transport Layer Security (TLS), Secure Shell (SSH), Internet Key Exchange (IKE), Internet Protocol Security (IPsec), and Domain Name System Security Extensions (DNSSEC). Schemes will be evaluated by the security they provide in these (and other) applications.

過去の AES や SHA-3 の競技会の場合と同様に、安全性は、耐量子公開鍵アルゴリズムの候補を評価する際に最も重要な要因です。NIST は、Transport Layer Security(TLS)、Secure Shell(SSH)、Internet Key Exchange(IKE)、Internet Protocol Security(IPsec)、Domain Name System Security Extensions(DNSSEC)など、幅広いプロトコルで使われる耐量子公開鍵アルゴリズムを標準化するつもりです。各方式は、これら(およびその他)の用途で提供する安全性によって評価されます。

Submitters were encouraged, but not required, to provide proofs of security in relevant models. For general-use encryption and key-establishment schemes, FRN-Dec16 asked for “semantically secure” schemes with respect to adaptive chosen ciphertext attack (IND-CCA2 security). For ephemeral use cases, NIST will consider semantic security with respect to chosen plaintext attack (IND-CPA security). Digital signature schemes need to enable existentially unforgeable signatures with respect to an adaptive chosen message attack (EUF-CMA security).

提出者は、関連するモデルでの安全性の証明を提供することが奨励されましたが、必須ではありませんでした。汎用の暗号化方式および鍵確立方式について、FRN-Dec16 は、適応的選択暗号文攻撃に関して「意味論的に安全」な方式(IND-CCA2 安全性)を求めました。短期的(エフェメラル)な用途については、NIST は、選択平文攻撃に関する意味論的安全性(IND-CPA 安全性)を考慮します。デジタル署名方式は、適応的選択メッセージ攻撃に関して存在的に偽造不可能な署名(EUF-CMA 安全性)を実現できる必要があります。

While recognizing that there are significant uncertainties in estimating the security strengths of the post-quantum candidate algorithms, NIST defined five security categories to be able to better compare the security strength provided by the submissions. Submitters were asked to provide a preliminary classification, according to the definitions provided in FRN-Dec16, with a focus on meeting the requirements for categories 1, 2, and/or 3.

NIST は、耐量子アルゴリズム候補の安全強度の見積もりには大きな不確実性があることを認識しつつ、提出物が提供する安全強度をより適切に比較できるよう、5 つの安全性カテゴリーを定義しました。提出者は、カテゴリー 1、2、または 3(あるいはそのいくつか)の要件を満たすことに重点を置き、FRN-Dec16 で示された定義に従って予備的な分類を提示するよう求められました。

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

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

2.2.2 Cost and Performance
2.2.2 コストと性能

FRN-Dec16 identified cost as the second-most important criterion when evaluating candidate algorithms. In this case, cost includes computational efficiency and memory requirements. This includes, for example:

FRN-Dec16 は、候補アルゴリズムを評価する際の 2 番目に重要な基準として、コストを特定しました。ここでのコストには、計算効率とメモリ要件が含まれます。これには、たとえば次のものが含まれます。

•The size of public keys, ciphertext, and signatures

•公開鍵、暗号文、署名のサイズ

•Computation efficiency of key generation, as well as the public and private key operations

•鍵生成、ならびに公開鍵および秘密鍵の操作の計算効率

•Probability of decryption failures

•復号失敗の確率

Computational efficiency essentially refers to the speed of an algorithm. NIST hopes that candidate algorithms will offer comparable or improved performance over the currently standardized public-key algorithms. Memory requirements refer both to code size and random-access memory (RAM) requirements for software implementations, as well as gate counts for hardware implementations.

計算効率は、基本的にアルゴリズムの速度を指します。NIST は、候補アルゴリズムが、現在標準化されている公開鍵アルゴリズムと同等またはそれ以上の性能を提供することを期待しています。メモリ要件は、ソフトウェア実装のコードサイズとランダムアクセスメモリ(RAM)要件、およびハードウェア実装のゲート数の両方を指します。

FRN-Dec16 required all submitters to include performance estimates on the NIST reference platform, an Intel x64 running Windows or Linux and supporting the GNU Compiler Collection (GCC) compiler. NIST performed a preliminary efficiency analysis on the reference platform, but also invited the public to conduct similar tests on additional platforms.

FRN-Dec16 は、すべての提出者に、NIST の参照プラットフォーム(Windows または Linux が動作し、GNU Compiler Collection(GCC)コンパイラをサポートする Intel x64)での性能の見積もりを含めることを求めました。NIST は、参照プラットフォームで予備的な効率分析を実施しましたが、一般にも、ほかのプラットフォームで同様のテストを行うよう呼びかけました。

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

The NIST PQC Standardization Process received many candidate algorithms with new and interesting designs, and with unique features that are not present in the current NIST standardized public-key algorithms. Candidate algorithms with greater flexibility may be given preference over other algorithms. This includes algorithms capable of running efficiently on a wide variety of platforms, as well as algorithms that use parallelism or instruction set extensions to achieve higher performance. In addition, simple and elegant designs are preferable, which reflects better understanding and confidence of the design team and encourages further analysis. Finally, NIST will consider any factors which might hinder or promote adoption of an algorithm or implementation, including, but not limited to, intellectual property covering an algorithm or implementation and the availability and terms of licenses to interested parties.

NIST PQC 標準化プロセスには、新しく興味深い設計や、現在 NIST が標準化している公開鍵アルゴリズムにはない独自の特徴を持つ、多くの候補アルゴリズムが提出されました。より高い柔軟性を持つ候補アルゴリズムは、ほかのアルゴリズムより優先される場合があります。これには、幅広いプラットフォームで効率的に動作できるアルゴリズムや、並列処理または命令セット拡張を使ってより高い性能を達成するアルゴリズムが含まれます。加えて、シンプルでエレガントな設計が望ましいとされます。これは、設計チームの理解と自信がより深いことを反映しており、さらなる分析を促すためです。最後に NIST は、アルゴリズムや実装の採用を妨げたり促したりしうる要因を考慮します。これには、アルゴリズムや実装を対象とする知的財産、関心のある当事者へのライセンスの利用可能性と条件が含まれますが、これらに限りません。

2.3 Selection of Second Round Candidates

2.3 第 2 ラウンド候補の選定

NIST selected 26 second-round candidates from the 69 first-round candidates using the evaluation criteria specified in FRN-Dec16. In relative order of importance, NIST considered the security, cost and performance, and algorithm and implementation characteristics of a candidate in selecting the second-round candidates.

NIST は、FRN-Dec16 で指定された評価基準を用いて、69 件の第 1 ラウンド候補から 26 件の第 2 ラウンド候補を選定しました。第 2 ラウンド候補の選定にあたっては、重要度の高い順に、候補の安全性、コストと性能、アルゴリズムと実装の特性を考慮しました。

For the security evaluation of an algorithm, NIST studied the security arguments presented in the submission package, as well as external cryptanalysis submitted to NIST or published elsewhere. NIST researchers also conducted internal cryptanalysis.

アルゴリズムの安全性評価のため、NIST は、提出パッケージに示された安全性の論拠と、NIST に提出された、または他所で公表された外部の暗号解読を調べました。NIST の研究者も、内部で暗号解読を実施しました。

NIST considered not only attacks that directly demonstrated that a candidate fell short of NIST’s stated security targets, but also attacks that brought the candidate’s underlying security assumptions into question, or that gave the appearance of room for improvement. NIST also considered the overall quantity, quality, and maturity of analysis relevant to each candidate, including analysis of similar schemes.

NIST は、候補が NIST の示した安全性の目標に届かないことを直接示した攻撃だけでなく、候補の基盤となる安全性の仮定に疑問を投げかけた攻撃や、改善の余地があるように見せた攻撃も考慮しました。また NIST は、類似の方式の分析を含め、各候補に関連する分析の全体的な量、質、成熟度も考慮しました。

After security, performance was the next most important criterion in selecting the second-round candidates. When evaluating the performance of the candidates, NIST considered both the key/ciphertext/signature sizes as well as the computational estimates given by the submitters in their submission documentation and in their presentations at the First NIST PQC Standardization Conference. NIST also performed internal performance benchmarks using the code from the submission packages. In addition, NIST considered the external feedback and performance estimates provided by the cryptographic community. We note that NIST stated “performance considerations will not play a major role in the early portion of the evaluation process [12,13],” and NIST did not use the implementation performance numbers as a primary factor in its decision.

安全性に次いで、第 2 ラウンド候補の選定で最も重要な基準は性能でした。候補の性能を評価する際、NIST は、鍵・暗号文・署名のサイズと、提出者が提出文書と第 1 回 NIST PQC 標準化会議での発表で示した計算量の見積もりの両方を考慮しました。NIST はまた、提出パッケージのコードを使って、内部で性能ベンチマークを実施しました。さらに NIST は、暗号コミュニティから寄せられた外部のフィードバックと性能の見積もりも考慮しました。NIST が「性能に関する考慮は、評価プロセスの初期段階では主要な役割を果たさない [12,13]」と述べていたとおり、NIST は実装の性能の数値を判断の主要な要因としては用いませんでした。

In a few cases, a submitted design was selected in part for its uniqueness and elegance. NIST generally favored those designs that were based on clear design principles or otherwise illustrative of an innovative idea. NIST feels that the diversity of designs will provide an opportunity for cryptographers and cryptanalysts to expand the scope of ideas in their field, and it will also be less likely that a single type of attack will eliminate the bulk of the candidates remaining in the standardization process.

いくつかの場合には、提出された設計が、その独自性とエレガントさを一因として選定されました。NIST は、明確な設計原理に基づいている設計や、革新的なアイデアを示している設計を、概して好意的に評価しました。NIST は、設計の多様性が、暗号研究者や暗号解読者にとって、それぞれの分野のアイデアの幅を広げる機会になると考えています。また、単一の種類の攻撃によって、標準化プロセスに残っている候補の大半が脱落する可能性も低くなります。

The algorithms which were not selected to advance to the next round are not under consideration for standardization by NIST.

次のラウンドに進むものとして選定されなかったアルゴリズムは、NIST による標準化の検討対象ではありません。

Second Round Candidates

第 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

3 Summary of Second Round Candidates

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

Each of the candidates selected to move on the next round is discussed below, including a summary of the basic design, performance characteristics, and known (crypt)analysis. In addition, the discussion includes suggested areas that the submitters may wish to address in order to improve their candidate’s chances of making it further in the process.

次のラウンドに進むものとして選定された各候補を、基本設計、性能特性、既知の(暗号)解析の要約を含めて、以下で論じます。加えて、候補が先に進める可能性を高めるために提出者が取り組むことが望ましい点も示します。

We first discuss the 17 public-key encryption and key-establishment schemes (in Sections 3.1 to 3.17), and then the 9 digital signature schemes (in Sections 3.18 to 3.26). The candidates are roughly grouped by similar categories; i.e. lattice-based, code-based, multivariate, etc.

まず、17 件の公開鍵暗号化および鍵確立方式(3.1 節から 3.17 節)を論じ、続いて 9 件のデジタル署名方式(3.18 節から 3.26 節)を論じます。候補は、格子ベース、符号ベース、多変数など、似た区分でおおまかにまとめています。

3.1 CRYSTALS-KYBER

3.1 CRYSTALS-KYBER

Kyber is a family of key encapsulation mechanisms offering chosen ciphertext (i.e., IND-CCA) security based on the presumed post-quantum hardness of the Module Learning with Errors (MLWE) problem. Kyber contains a standard Learning with Errors (LWE)-style CPA-secure public-key encryption scheme, where the underlying algebraic object is a module over a power-of-2 cyclotomic ring. This choice of parameters enables very efficient computations using the Number Theoretic Transform (NTT). The noise is sampled according to a centered binomial distribution. CCA security is achieved via a well-known variant of the Fujisaki-Okamoto transform, where the session key is transported using an encryption-based approach.

Kyber は、Module Learning with Errors(MLWE)問題の耐量子的な困難性という想定に基づく、選択暗号文(すなわち IND-CCA)安全性を提供する鍵カプセル化メカニズムのファミリーです。Kyber には、標準的な Learning with Errors(LWE)型の CPA 安全な公開鍵暗号化方式が含まれ、その基盤となる代数的対象は、2 のべき乗次の円分環上の加群です。このパラメーターの選択により、数論変換(NTT)を使った非常に効率的な計算が可能になります。ノイズは、中心二項分布に従ってサンプリングされます。CCA 安全性は、Fujisaki-Okamoto 変換のよく知られた変種によって実現され、セッション鍵は暗号化ベースの手法で輸送されます。

It is straightforward to adjust Kyber’s security strength levels. One adjustment simply varies the rank of the underlying module (in the range {2,3,4}) and adjusts the noise distribution parameter (in the range {5,4,3}, respectively). Kyber’s performance is among the most competitive proposals for key exchange.

Kyber の安全強度レベルは簡単に調整できます。調整の 1 つは、基盤となる加群のランクを({2,3,4} の範囲で)変え、ノイズ分布のパラメーターを(それぞれ {5,4,3} の範囲で)調整するだけです。Kyber の性能は、鍵交換の提案の中で最も競争力のあるものの 1 つです。

The security of Kyber relies on a variant of a well-studied problem. The submission offers a tight security proof in the random oracle model (ROM) and a non-tight security proof in the quantum random oracle model (QROM), both based on the MLWE assumption. We note that a potential issue is that the security proof does not directly apply to Kyber itself, but rather to a modified version of the scheme which does not compress the public key. Without this modification, Kyber may in fact be relying on a different (or additional) rounding-like assumption. If that is the case, this may lead to a cryptanalytic concern, as the known reductions between MLWE and Module Learning with Rounding (MLWR) may not apply for the parameters selected by Kyber.

Kyber の安全性は、よく研究されている問題の変種に依拠しています。提出物は、いずれも MLWE の仮定に基づく、ランダムオラクルモデル(ROM)での tight な安全性証明と、量子ランダムオラクルモデル(QROM)での非 tight な安全性証明を提供しています。潜在的な問題として、安全性証明が Kyber 自体には直接適用されず、公開鍵を圧縮しない修正版の方式に適用されるという点があります。この修正がなければ、Kyber は実際には、異なる(または追加の)丸めに類する仮定に依拠している可能性があります。その場合、MLWE と Module Learning with Rounding(MLWR)の間の既知の帰着が、Kyber が選んだパラメーターには適用できない可能性があるため、暗号解読上の懸念につながるかもしれません。

3.2 FrodoKEM

3.2 FrodoKEM

FrodoKEM is a CCA-secure key encapsulation mechanism that uses algebraically unstructured lattices. The security is based on the standard learning with errors problem. The secrets are sampled from a discrete Gaussian distribution over the integers and the algorithm is implemented in constant time. Extensive analysis, by both the design team and external researchers, has been devoted to the security of LWE for various parametrizations.

FrodoKEM は、代数的に構造化されていない格子を使う、CCA 安全な鍵カプセル化メカニズムです。安全性は、標準的な Learning with Errors 問題に基づいています。シークレットは整数上の離散ガウス分布からサンプリングされ、アルゴリズムは定数時間で実装されています。さまざまなパラメーター設定について、設計チームと外部の研究者の双方によって、LWE の安全性に関する広範な分析が行われてきました。

FrodoKEM takes a conservative approach resulting in larger key sizes than other lattice schemes. This conservative approach is beneficial, as FrodoKEM could still be secure even if specialized attacks were found on lattices with ring or module structure as used in most of the other lattice-based submissions. FrodoKEM manages to present lower bandwidth (public key size plus ciphertext size) and faster running times than other unstructured lattices submissions.

FrodoKEM は保守的なアプローチをとっており、その結果、ほかの格子方式より鍵サイズが大きくなります。この保守的なアプローチは有益です。ほかの格子ベースの提出物の大半が使っている、環や加群の構造を持つ格子に対する特殊な攻撃が見つかったとしても、FrodoKEM は安全であり続けられる可能性があるためです。FrodoKEM は、ほかの構造を持たない格子の提出物より、低い帯域幅(公開鍵サイズと暗号文サイズの合計)と高速な実行時間を示すことができています。

The FrodoKEM specification includes parameter sets for security levels 1 and 3. The team may wish to consider providing a parameter set for level 5.

FrodoKEM の仕様には、安全性レベル 1 と 3 のパラメーターセットが含まれています。チームは、レベル 5 のパラメーターセットの提供を検討するとよいかもしれません。

3.3 LAC

3.3 LAC

LAC is a cryptosystem based on the poly-LWE variant of the Learning with Errors problem. One notable difference from other similar schemes is LAC’s use of the modulus \(q = 251\), allowing each element of a polynomial to fit in a single byte. LAC uses a very narrow distribution for secrets and errors to ensure that the LWE problem remains difficult with such a small modulus. A BCH (Bose-Chaudhuri-Hocquenghem) code is also used to decode to a shared secret.

LAC は、Learning with Errors 問題の poly-LWE 変種に基づく暗号システムです。ほかの類似の方式との顕著な違いの 1 つは、LAC が法 \(q = 251\) を使うことで、多項式の各要素が 1 バイトに収まる点です。LAC は、こうした小さな法でも LWE 問題が困難なままであるように、シークレットとエラーに非常に狭い分布を使います。共有シークレットへの復号には、BCH(Bose-Chaudhuri-Hocquenghem)符号も使われます。

Although the scheme is very fast and generates competitively small public keys and ciphertexts, NIST lacks full confidence in the robustness of the category 5 parameters. Several public comments have already demonstrated some vulnerabilities to CCA attacks with the current LAC level 5 parameters. NIST believes the LAC submission would also benefit from having a side-channel resistant implementation. Second round tweaks will need to address these issues to ensure that LAC remains competitive.

この方式は非常に高速で、競争力のある小さな公開鍵と暗号文を生成しますが、NIST は、カテゴリー 5 のパラメーターの頑健性に完全な確信を持っていません。複数のパブリックコメントが、LAC の現行のレベル 5 パラメーターについて、CCA 攻撃に対する一部の脆弱性を既に示しています。NIST は、LAC の提出物は、サイドチャネル攻撃に耐性のある実装を備えることでも改善されると考えています。LAC が競争力を保てるよう、第 2 ラウンドでの調整でこれらの問題に対処する必要があります。

3.4 NewHope

3.4 NewHope

NewHope is a lattice-based cryptosystem of KEMs, achieving CPA and CCA security based on the quantum hardness of the Ring Learning with Errors (RLWE) problem. The scheme uses power-of-2 cyclotomic rings with a common modulus. The RLWE secret and errors are sampled from the centered binomial distribution, and the public key is ephemeral. Polynomial multiplication is specified using the NTT. CCA security is achieved by a variant of the Fujisaki Okamoto transform. The session key is transported using an encryption-based approach for noisy key agreement.

NewHope は、KEM による格子ベースの暗号システムで、Ring Learning with Errors(RLWE)問題の量子的な困難性に基づいて、CPA 安全性と CCA 安全性を実現します。この方式は、共通の法を持つ 2 のべき乗次の円分環を使います。RLWE のシークレットとエラーは中心二項分布からサンプリングされ、公開鍵は短期的(エフェメラル)です。多項式の乗算は NTT を使って規定されています。CCA 安全性は Fujisaki Okamoto 変換の変種によって実現されます。セッション鍵は、ノイズのある鍵合意のための暗号化ベースの手法で輸送されます。

NewHope has competitive performance in terms of bandwidth and clock cycles among the candidates for post-quantum key-establishment. Some other candidates in the same category may have superior performance, but in many cases, this is due to more aggressive design choices, which may or may not be preferable in the long-term.

NewHope は、耐量子鍵確立の候補の中で、帯域幅とクロックサイクルの点で競争力のある性能を備えています。同じ区分のほかの候補の中には、より優れた性能を持つものもありますが、多くの場合、それはより積極的な設計上の選択によるものであり、長期的に望ましいかどうかは分かりません。

3.5 NTRU (merger of NTRUEncrypt and NTRU-HRSS-KEM)

3.5 NTRU(NTRUEncrypt と NTRU-HRSS-KEM の統合)

NTRU encryption is a lattice-based one-way CPA-secure (OW-CPA) public-key encryption scheme which was invented around 1996 [14]. The security of NTRU encryption has been reasonably-well understood and scrutinized for decades. Many variants of the scheme and their derived key encapsulation mechanisms have been developed since, including the NTRUEncrypt and NTRU-HRSS-KEM submissions. These two submissions have announced a merged scheme, which will be known as NTRU.

NTRU 暗号化は、1996 年頃に考案された、格子ベースの一方向 CPA 安全(OW-CPA)な公開鍵暗号化方式です [14]。NTRU 暗号化の安全性は、数十年にわたって、かなりよく理解され、精査されてきました。その後、NTRUEncrypt と NTRU-HRSS-KEM の提出物を含め、この方式の多くの変種と、そこから導かれる鍵カプセル化メカニズムが開発されました。これら 2 つの提出物は、NTRU として知られることになる統合方式を発表しました。

The security of NTRU relies on a somewhat stronger assumption than LWE or RLWE, sometimes referred to as the “NTRU assumption”. The KEM in the merged submission is a tight IND-CCA2 security transformation from a deterministic OW-CPA-secure public key encryption scheme in the quantum random oracle model. The submission has two options for the deterministic PKE scheme in the KEM. The derived KEM has no decryption failures and avoids both the “evaluation at 1” issue and invertibility checks during key generation.

NTRU の安全性は、LWE や RLWE よりやや強い、「NTRU 仮定」と呼ばれることもある仮定に依拠しています。統合された提出物の KEM は、量子ランダムオラクルモデルにおいて、決定的な OW-CPA 安全な公開鍵暗号化方式から得られる、tight な IND-CCA2 安全性の変換です。提出物は、KEM 内の決定的な PKE 方式について 2 つの選択肢を提示しています。導かれる KEM には復号失敗がなく、「1 での評価」の問題と、鍵生成時の可逆性の検査のいずれも避けられます。

Three parameter sets are specified with three ring instances. The KEM has good sizes for keys and ciphertext. Encapsulation and decapsulation seem to be efficient. While creating no known security weaknesses, the NTRU construction produces a lattice that has somewhat more structure than in similarly efficient RLWE and MLWE cryptosystems (due to having shorter than expected vectors). This is an area for further analysis.

3 つのリング(環)インスタンスで、3 つのパラメーターセットが規定されています。KEM の鍵と暗号文のサイズは良好です。カプセル化と脱カプセル化は効率的であるように見えます。既知の安全性の弱点を生じさせるものではありませんが、NTRU の構成が生成する格子は、同程度に効率的な RLWE や MLWE の暗号システムより、やや構造が多くなります(期待より短いベクトルを持つため)。これはさらなる分析が必要な分野です。

3.6 NTRU Prime

3.6 NTRU Prime

The NTRU Prime submission includes two distinct KEMs, known as “Streamlined NTRU Prime” and “NTRU LPRime”. The KEMs are both CCA-secure, built on deterministic OW-CPA-secure public key encryption functions. Streamlined NTRU Prime uses a rounding technique in encapsulation instead of using the message \(m\), as in the original NTRU encryption. NTRU LPRime can be considered a Ring Learning with Rounding (RLWR)-based KEM which has only one secret random variable generated in key generation and encapsulation steps and those steps deploy the rounding technique. Unlike NTRU and streamlined NTRU Prime, NTRU LPRime does not use a lattice with unusually short vectors.

NTRU Prime の提出物には、「Streamlined NTRU Prime」と「NTRU LPRime」として知られる、2 つの異なる KEM が含まれます。両 KEM とも CCA 安全で、決定的な OW-CPA 安全な公開鍵暗号化関数の上に構築されています。Streamlined NTRU Prime は、元の NTRU 暗号化のようにメッセージ \(m\) を使う代わりに、カプセル化で丸め技法を使います。NTRU LPRime は、鍵生成とカプセル化のステップで生成される秘密の確率変数が 1 つだけで、それらのステップで丸め技法を用いる、Ring Learning with Rounding(RLWR)ベースの KEM とみなせます。NTRU や Streamlined NTRU Prime と異なり、NTRU LPRime は、異常に短いベクトルを持つ格子を使いません。

The main novelty of NTRU Prime is the use of an irreducible non-cyclotomic polynomial, and an inert prime \(q\) so that the relevant ring is actually a field with large Galois group. These intentional design choices ensure that NTRU Prime avoids non-trivial ring homomorphisms and the structure of cyclotomic polynomial rings which are potential security weaknesses. In addition, the KEMs have no decryption failures and are implemented in constant time.

NTRU Prime の主な新規性は、既約な非円分多項式と、関連する環が実際には大きなガロア群を持つ体になるような不活性素数 \(q\) を使うことです。こうした意図的な設計上の選択により、NTRU Prime は、安全性上の弱点になりうる、非自明な環準同型と、円分多項式環の構造を避けています。加えて、これらの KEM には復号失敗がなく、定数時間で実装されています。

The KEMs have good sizes for keys and ciphertexts. Encapsulation and decapsulation speeds seem to be very competitive against other candidates. NTRU LPRime also has fast key generation. The two KEMs use the same ring (field) with two different parameter sets, all with their claimed security level as 5. It should be noted that the claimed security strength uses a cost model for lattice attacks with higher complexity than many of the other lattice-based candidates. If the cost model used were the same as for those submissions, the claimed security level would be lower. The NTRU Prime team may wish to consider adding other parameter sets for other security levels.

これらの KEM の鍵と暗号文のサイズは良好です。カプセル化と脱カプセル化の速度は、ほかの候補と比べて非常に競争力があるように見えます。NTRU LPRime は鍵生成も高速です。2 つの KEM は、同じ環(体)を 2 つの異なるパラメーターセットで使い、いずれも主張される安全性レベルは 5 です。主張される安全強度は、ほかの格子ベースの候補の多くより計算量の大きい、格子攻撃のコストモデルを使っていることに注意すべきです。それらの提出物と同じコストモデルを使えば、主張される安全性レベルはより低くなります。NTRU Prime チームは、ほかの安全性レベル向けのパラメーターセットを追加することを検討するとよいかもしれません。

3.7 Round5 (merger of HILA5 and Round2)

3.7 Round5(HILA5 と Round2 の統合)

Round5 is a lattice-based cryptosystem over prime cyclotomic rings, formed by a merger between Round2 and Hila5. The scheme proposes a KEM and public-key encryption scheme with security based on the decisional Learning with Rounding (LWR) problem with sparse ternary secrets, including a ring-variant. An error-correcting code from the family of codes, XEf, is applied to reduce decryption and decapsulation failures. This error-correcting code family generalizes XE5, an original contribution of Hila5.

Round5 は、素数円分環上の格子ベースの暗号システムで、Round2 と Hila5 の統合によって形成されました。この方式は、疎な三値のシークレットを持つ判定版の Learning with Rounding(LWR)問題(環版を含む)に基づく安全性を持つ、KEM と公開鍵暗号化方式を提案しています。復号と脱カプセル化の失敗を減らすため、符号族 XEf の誤り訂正符号が適用されています。この誤り訂正符号族は、Hila5 が独自に寄与した XE5 を一般化したものです。

Round5 offers competitive performance and some of the lowest bandwidth requirements among the lattice-based proposals. The structured and unstructured lattice options allow Round5 to address a variety of use cases.

Round5 は、競争力のある性能を提供し、格子ベースの提案の中で最も低い部類の帯域幅要件を備えています。構造化格子と非構造化格子の選択肢により、Round5 はさまざまなユースケースに対応できます。

Concerns were raised regarding the calculation of Round5 decryption and decapsulation failures. New parameters were suggested by the submitters to remedy this problem and the CCA-secure encryption scheme now has failure rates reportedly below \(2^{-128}\). Round5 incorporates some internal building blocks that could use more documentation and security analysis. NIST hopes that Round5’s selection as a second-round candidate will lead to more such analysis.

Round5 の復号と脱カプセル化の失敗の計算について、懸念が示されました。この問題を解決するため、提出者から新しいパラメーターが提案され、CCA 安全な暗号化方式の失敗率は、報告によれば \(2^{-128}\) 未満になりました。Round5 には、さらなる文書化と安全性分析が必要な内部構成要素がいくつか含まれています。NIST は、Round5 が第 2 ラウンド候補に選定されることで、そうした分析が増えることを期待しています。

3.8 SABER

3.8 SABER

SABER is a family of lattice-based PKEs and KEMs, achieving CPA and CCA security based on the quantum hardness of the Module Learning with Rounding problem. The scheme uses modules of varying rank over a fixed power-of-2 cyclotomic ring with fixed dimension and modulus for security levels 1, 3, and 5. The MLWR secret distribution is the centered binomial distribution, and a hash of the session key is hashed with the public key for multi-target protection. Polynomial multiplication is specified using Toom-Cook and Karatsuba. CCA security is achieved by a variant of the Fujisaki-Okamoto transform. The session key is transported using an encryption-based approach for noisy key agreement.

SABER は、格子ベースの PKE と KEM のファミリーで、Module Learning with Rounding 問題の量子的な困難性に基づいて CPA 安全性と CCA 安全性を実現します。この方式は、安全性レベル 1、3、5 に対して、次元と法を固定した、固定の 2 のべき乗次の円分環上で、ランクの異なる加群を使います。MLWR のシークレットの分布は中心二項分布で、マルチターゲット攻撃への対策として、セッション鍵のハッシュを公開鍵とともにハッシュします。多項式の乗算は、Toom-Cook 法と Karatsuba 法を使って規定されています。CCA 安全性は Fujisaki-Okamoto 変換の変種によって実現されます。セッション鍵は、ノイズのある鍵合意のための暗号化ベースの手法で輸送されます。

SABER has very competitive performance among all candidates for post-quantum key exchange. It achieves one of the lower costs for bandwidth at each security level.

SABER は、耐量子鍵交換のすべての候補の中で、非常に競争力のある性能を備えています。各安全性レベルで、帯域幅のコストが最も低い部類に入ります。

The most significant security concern for SABER is whether or not it is overstretching the concrete hardness of (Module) Learning with Rounding. While there are no known (M)LWR-related attacks that exploit the chosen parameters, the reductions between bounded-sample MLWE and MLWR are rather loose and do not apply in SABER's case. NIST views SABER as an opportunity to highlight the need for (and benefit of) further analysis of (M)LWR with small parameters and bounded samples, to continue improving overall confidence in the assumption.

SABER にとって最も重大な安全性上の懸念は、(Module)Learning with Rounding の具体的な困難性を過大に見積もっていないかどうかです。選ばれたパラメーターを悪用する(M)LWR 関連の攻撃は知られていませんが、サンプル数に上限のある MLWE と MLWR の間の帰着はかなり緩く、SABER の場合には適用できません。NIST は、SABER を、この仮定に対する全体的な信頼を高め続けるために、小さなパラメーターとサンプル数に上限のある(M)LWR をさらに分析する必要性(とその利点)を強調する機会とみています。

3.9 Three Bears

3.9 Three Bears

Three Bears is a variant of the Module Learning with Errors problem. Instead of the underlying ring being a polynomial with an indeterminate x, the indeterminate x is evaluated, yielding instead a ring modulo an integer. As instantiated, this integer is a generalized Mersenne prime of special form. This choice allows the use of already highly-optimized big integer arithmetic libraries and code which is a major benefit, in particular libraries for the Ed448-Goldilocks elliptic curve.

Three Bears は、Module Learning with Errors 問題の変種です。基盤となる環が不定元 x を持つ多項式である代わりに、不定元 x に値を代入して、整数を法とする環を得ます。実際のインスタンスでは、この整数は特殊な形の一般化メルセンヌ素数です。この選択により、すでに高度に最適化された多倍長整数演算のライブラリとコード、特に Ed448-Goldilocks 楕円曲線のライブラリを使えることは、大きな利点です。

The scheme appears to be one of the fastest submissions received by NIST, with very competitive key sizes. It also adds variety to the family of LWE-like schemes and may be easier for non-experts to understand than schemes laden with algebraic number theory concepts. However, the security assumption upon which Three Bears is based is new and requires more analysis.

この方式は、NIST が受け取った提出物の中で最も高速なものの 1 つで、鍵サイズも非常に競争力があるように見えます。また、LWE 型の方式のファミリーに多様性を加え、代数的整数論の概念に満ちた方式よりも、専門家でない人にとって理解しやすい可能性があります。ただし、Three Bears が基礎とする安全性の仮定は新しく、さらなる分析が必要です。

The Three Bears specification would benefit from some changes. It currently relies significantly on an unpublished e-print work for understandability (see [15]). A more self-contained specification would be useful.

Three Bears の仕様は、いくつかの変更によって改善が期待できます。現在の仕様は、理解しやすさのために未公表の e-print の成果にかなり依存しています([15] を参照)。より自己完結した仕様が有用です。

3.10 Classic McEliece

3.10 Classic McEliece

Classic McEliece is an IND-CCA2 key encapsulation mechanism (KEM). The proposal is based on the well-known McEliece cryptosystem [16], the first code-based public-key cryptosystem published in 1978. The KEM’s public key determines a random binary Goppa code and generates a ciphertext by adding error to a codeword. Decapsulation is done by decoding. Security is based on the hardness of decoding a general linear code, and the assumption that a random binary Goppa code is indistinguishable from a random linear code.

Classic McEliece は、IND-CCA2 の鍵カプセル化メカニズム(KEM)です。この提案は、1978 年に公表された最初の符号ベースの公開鍵暗号システムである、よく知られた McEliece 暗号システム [16] に基づいています。KEM の公開鍵がランダムな二元 Goppa 符号を決定し、符号語に誤りを加えることで暗号文を生成します。脱カプセル化は復号によって行われます。安全性は、一般の線形符号を復号することの困難性と、ランダムな二元 Goppa 符号がランダムな線形符号と区別できないという仮定に基づいています。

There is a long history of analysis of the security problem, which has not significantly altered the attack complexity. Classic McEliece also has very short ciphertexts, on the order of 200 bytes, and seems to have good performance for encapsulation and decapsulation.

この安全性の問題については長い分析の歴史があり、攻撃の計算量を大きく変えるには至っていません。Classic McEliece は、暗号文も 200 バイト程度と非常に短く、カプセル化と脱カプセル化の性能も良好であるように見えます。

The main drawback to McEliece-type cryptosystems is the large public key size, which exceeds one million bytes. The submission only included parameter sets for category 5 security, so the submitters may wish to generate parameter sets for other security categories.

McEliece 型暗号システムの主な欠点は、公開鍵のサイズが 100 万バイトを超えることです。提出物にはカテゴリー 5 の安全性に対応するパラメーターセットしか含まれていなかったため、提出者はほかの安全性カテゴリーのパラメーターセットも生成することを検討してもよいです。

3.11 NTS-KEM

3.11 NTS-KEM

The NTS-KEM submission is an IND-CCA2 KEM based on the well-known McEliece cryptosystem [15]. The KEM’s public key determines a random binary Goppa code and generates a ciphertext by adding error to a codeword. Decapsulation is done by decoding. Security is based on the hardness of decoding a general linear code, and the assumption that a random binary Goppa code is indistinguishable from a random linear code.

NTS-KEM の提出物は、よく知られた McEliece 暗号システム [15] に基づく IND-CCA2 の KEM です。KEM の公開鍵がランダムな二元 Goppa 符号を決定し、符号語に誤りを加えることで暗号文を生成します。脱カプセル化は復号によって行われます。安全性は、一般の線形符号を復号することの困難性と、ランダムな二元 Goppa 符号がランダムな線形符号と区別できないという仮定に基づいています。

There is a long history of analysis of the security problem, which has not significantly altered the attack complexity. NTS-KEM also has very short ciphertexts and seems to have good performance for encapsulation and decapsulation. The main drawback is the large public key size.

この安全性の問題については長い分析の歴史があり、攻撃の計算量を大きく変えるには至っていません。NTS-KEM も、暗号文が非常に短く、カプセル化と脱カプセル化の性能も良好であるように見えます。主な欠点は、公開鍵のサイズが大きいことです。

In contrast, there are a few differences between NTS-KEM and Classic McEliece. For example, NTS-KEM generates their keys in a different way and selects different polynomials. The NTS-KEM team provided parameters for security categories 1, 3, and 5, while Classic McEliece only has level 5. NTS-KEM could make their implementation constant time to provide security against side-channel attacks.

一方、NTS-KEM と Classic McEliece にはいくつかの違いがあります。たとえば、NTS-KEM は鍵を異なる方法で生成し、異なる多項式を選びます。NTS-KEM チームは安全性カテゴリー 1、3、5 のパラメーターを提供しましたが、Classic McEliece はレベル 5 のみです。NTS-KEM は、サイドチャネル攻撃に対する安全性を確保するため、実装を定数時間にできます。

3.12 BIKE

3.12 BIKE

BIKE is a code-based KEM, combining three similar constructions that all use a bit-flipping decoder for a Quasi-Cyclic Moderate-Density-Parity-Check (QC-MDPC) code in their decapsulation algorithms. All three constructions are intended to be used ephemerally with a strict prohibition on key reuse – that is to say, BIKE targets IND-CPA security and makes no attempt to make it difficult for an attacker to mount a chosen ciphertext attack if keys are reused. This design decision was made by the submitters, based on the difficulty of designing a bit-flipping decoder with a low enough decoding failure rate to allow an efficient IND-CCA2-secure construction.

BIKE は符号ベースの KEM で、脱カプセル化アルゴリズムに準巡回 Moderate-Density-Parity-Check(QC-MDPC)符号のビット反転復号器を使う、3 つの類似した構成を組み合わせたものです。3 つの構成はいずれも短期的(エフェメラル)に使われることを意図しており、鍵の再利用が厳しく禁止されています。つまり、BIKE は IND-CPA 安全性を目標としており、鍵が再利用された場合に、攻撃者が選択暗号文攻撃を仕掛けることを困難にしようとはしていません。この設計上の判断は、効率的な IND-CCA2 安全な構成を可能にするほど復号失敗率の低いビット反転復号器を設計することの難しさに基づいて、提出者が行ったものです。

BIKE offers key and ciphertext sizes and performance that are competitive with ring and module lattice schemes (especially at the lower security categories). The constructions used in BIKE are fairly new, dating from the 2010s, but there are a number of features that increase confidence in their security and mitigate concern. In particular, the schemes are structurally quite similar to well-studied lattice cryptosystems. BIKE I and II are similar to NTRU and BIKE III is similar to RLWE cryptosystems, substituting shortness in the Hamming metric for shortness in the Euclidean metric. BIKE also offers a security proof based on decisional variants with parity of the Quasi-Cyclic Syndrome Decoding (QCSD) and Quasi-Cyclic Codeword Finding (QCCF) problems. Security strengths are based on information-set-decoding attacks, which have a long history of analysis during which the complexity of such attacks have not greatly changed.

BIKE は、環や加群の格子方式(特に低い安全性カテゴリー)に匹敵する、鍵と暗号文のサイズおよび性能を提供します。BIKE で使われている構成は、2010 年代に始まったかなり新しいものですが、その安全性への信頼を高め、懸念を和らげるいくつかの特徴があります。特に、これらの方式は、よく研究されている格子暗号システムと構造がかなり似ています。BIKE I と II は NTRU に、BIKE III は RLWE 暗号システムに似ており、ユークリッド距離での短さをハミング距離での短さに置き換えています。BIKE は、準巡回シンドローム復号(QCSD)問題と準巡回符号語探索(QCCF)問題のパリティ付き判定版に基づく、安全性証明も提供しています。安全強度は情報集合復号攻撃に基づいており、この攻撃には長い分析の歴史があり、その間に攻撃の計算量は大きく変わっていません。

Possible areas for further analysis related to BIKE include pursuing chosen ciphertext security by improving the decoding failure rate for QC-MDPC codes, investigating the relation between the search and decisional variants of the QCSD and QCCF problems, and investigating the effect, if any, of the quasi-cyclic code structure on security.

BIKE に関連するさらなる分析の可能性のある分野には、QC-MDPC 符号の復号失敗率を改善することによる選択暗号文安全性の追求、QCSD 問題と QCCF 問題の探索版と判定版の関係の調査、準巡回符号の構造が安全性に与える影響(もしあれば)の調査があります。

3.13 HQC

3.13 HQC

HQC is a code-based public key encryption scheme based on the hardness of the decisional QCSD problem with parity, targeting IND-CCA2 security. It uses a construction similar to RLWE-based PKE schemes, substituting shortness in the Hamming metric for shortness in the Euclidean metric, combined with a public error correction code.

HQC は、パリティ付き判定版 QCSD 問題の困難性に基づく、IND-CCA2 安全性を目標とした符号ベースの公開鍵暗号化方式です。RLWE ベースの PKE 方式に似た構成を使い、ユークリッド距離での短さをハミング距離での短さに置き換え、公開の誤り訂正符号と組み合わせています。

HQC presents a strong argument that its decryption failure rate is low enough to obtain chosen-ciphertext security. This is the strongest argument, at present, of CCA security among the second-round candidate code-based cryptosystems, where information set decoding is the limiting attack for both private key recovery and message recovery (BIKE, HQC, and LEDAcrypt). However, it pays a significant penalty in key and ciphertext size in comparison to the others (although it still compares very favorably in key size and overall communication bandwidth to the candidate code-based cryptosystems based on Goppa codes).

HQC は、復号失敗率が選択暗号文安全性を得られるほど低いという強い論拠を示しています。これは、情報集合復号が秘密鍵の復元とメッセージの復元の両方にとって限界となる攻撃である、第 2 ラウンド候補の符号ベース暗号システム(BIKE、HQC、LEDAcrypt)の中で、現時点で CCA 安全性についての最も強い論拠です。ただし、ほかのものと比べて、鍵と暗号文のサイズで大きな代償を払っています(それでも、Goppa 符号に基づく符号ベース暗号システムの候補と比べれば、鍵サイズと全体の通信帯域幅は非常に有利です)。

Possible areas for further analysis related to HQC include investigating the relation between the search and decisional variants of the QCSD problem, and investigating the effect, if any, of the quasi-cyclic code structure on security.

HQC に関連するさらなる分析の可能性のある分野には、QCSD 問題の探索版と判定版の関係の調査、準巡回符号の構造が安全性に与える影響(もしあれば)の調査があります。

3.14 LEDAcrypt (merger of LEDAkem and LEDApkc)

3.14 LEDAcrypt(LEDAkem と LEDApkc の統合)

LEDAcrypt is a merger of two very similar code-based schemes, using quasi-cyclic Low-Density-Parity-Check (QC-LDPC) codes. The private parity check matrix for the public code is formed by multiplying the underlying QC-LDPC matrix by a similarly sparse square matrix. This results in a code which is quite similar to the QC-MDPC codes used in BIKE, but with some additional structure. While such codes could be decoded using a bit-flipping algorithm as in BIKE, LEDAcrypt instead uses a slightly different decoding algorithm called Q-decoding.

LEDAcrypt は、準巡回 Low-Density-Parity-Check(QC-LDPC)符号を使う、非常によく似た 2 つの符号ベース方式の統合です。公開符号の秘密のパリティ検査行列は、基盤となる QC-LDPC 行列に、同様に疎な正方行列を掛けて形成されます。その結果、BIKE で使われる QC-MDPC 符号とかなり似ていますが、追加の構造を持つ符号が得られます。このような符号は、BIKE のようにビット反転アルゴリズムで復号できますが、LEDAcrypt は代わりに、Q 復号と呼ばれる、やや異なる復号アルゴリズムを使います。

One area where LEDAcrypt may add value to the pool of second round candidates is in defending against chosen ciphertext attacks. While the submitted versions of LEDAkem and LEDApkc did not provide a low enough decryption failure rate to claim IND-CCA2 security according to the standards outlined in the NIST Call for Proposals [8], the parameters suggested for LEDAcrypt do claim a decryption failure rate that may be low enough. This is of interest, because if these parameters can in fact be used to provide IND-CCA2 security, then they would be better than the key and ciphertext sizes of HQC, the most similar scheme to LEDAcrypt that claims IND-CCA2 security.

LEDAcrypt が第 2 ラウンド候補群に価値を加えうる分野の 1 つは、選択暗号文攻撃への防御です。提出された LEDAkem と LEDApkc の各版は、NIST の提案募集 [8] で示された基準に従うと、IND-CCA2 安全性を主張できるほど復号失敗率が低くありませんでしたが、LEDAcrypt で提案されたパラメーターでは、復号失敗率が十分に低い可能性があるとされています。これらのパラメーターが実際に IND-CCA2 安全性を提供するために使えるのであれば、興味深いことです。その場合、IND-CCA2 安全性を主張する方式のうち、LEDAcrypt に最も似た方式である HQC と比べて、鍵サイズと暗号文サイズの点で優れます。

Possible areas for further analysis related to LEDAcrypt include investigation of how the security of LEDAcrypt is affected by the additional structure of the underlying code in comparison to QC-MDPC codes, and whether the updated parameters really do give a low enough decryption failure rate to obtain IND-CCA2 security.

LEDAcrypt に関連するさらなる分析の可能性のある分野には、QC-MDPC 符号と比べた基盤となる符号の追加の構造が LEDAcrypt の安全性にどう影響するかの調査と、更新されたパラメーターが実際に IND-CCA2 安全性を得られるほど低い復号失敗率を与えるかどうかの調査があります。

3.15 Rollo (merger of LAKE, LOCKER, and Ouroboros-R)

3.15 Rollo(LAKE、LOCKER、Ouroboros-R の統合)

ROLLO is a merger combining the three rank-based first round submissions LAKE, LOCKER, and Ouroboros-R. The submitters have not suggested changing or eliminating any of the three constructions, but the merger will eliminate some redundancy between the three specifications. Each of the three merged schemes uses a decoding algorithm for ideal Low Rank Parity Check (LRPC) codes in its decryption or decapsulation algorithm. LAKE and LOCKER are based on an NTRU-like construction, while Ouroboros-R is based on an RLWE-like construction, substituting the rank metric for the Euclidean metric in each case. The primary difference between LAKE and LOCKER is that LOCKER has adjusted its parameters to make the decryption failure rate low enough that it may claim IND-CCA2 security. The other two schemes only target IND-CPA security. Security proofs are provided based on decisional variants of the Ideal Rank Syndrome Decoding (IRSD) problem and the ideal LRPC distinguishing problem. LAKE and LOCKER require both assumptions, while Ouroboros-R only requires the former.

ROLLO は、ランクベースの第 1 ラウンド提出物である LAKE、LOCKER、Ouroboros-R の 3 つを組み合わせた統合です。提出者は 3 つの構成のいずれも変更または削除することを提案していませんが、この統合によって、3 つの仕様の間の一部の重複が解消されます。統合された 3 つの方式はいずれも、復号または脱カプセル化アルゴリズムに、イデアル Low Rank Parity Check(LRPC)符号の復号アルゴリズムを使います。LAKE と LOCKER は NTRU に似た構成に、Ouroboros-R は RLWE に似た構成に基づいており、いずれもユークリッド距離をランク距離に置き換えています。LAKE と LOCKER の主な違いは、LOCKER が、IND-CCA2 安全性を主張できるほど復号失敗率が低くなるようにパラメーターを調整していることです。ほかの 2 つの方式は、IND-CPA 安全性のみを目標としています。安全性証明は、イデアルランクシンドローム復号(IRSD)問題と、イデアル LRPC 識別問題の判定版に基づいて提供されています。LAKE と LOCKER は両方の仮定を必要としますが、Ouroboros-R は前者のみを必要とします。

In cryptographic literature, rank-based cryptosystems like the component schemes of ROLLO are often grouped with code-based cryptosystems using the Hamming metric, but they are subject to significantly different cryptanalytic attacks. As such, including rank-based cryptosystems in our pool of second round candidates adds significant diversity. Moreover, the key size and overall bandwidth of LAKE are better than that of any other submitted lattice or code-based, for the same security against known attacks. Nonetheless, rank-based cryptography is quite new and not as well studied as lattice-based cryptography or code-based cryptography using the Hamming metric. More cryptanalysis on rank-based primitives would be valuable.

暗号の文献では、ROLLO の構成方式のようなランクベースの暗号システムは、ハミング距離を使う符号ベースの暗号システムとまとめられることが多いですが、大きく異なる暗号解読攻撃を受けます。そのため、ランクベースの暗号システムを第 2 ラウンド候補群に含めることは、大きな多様性を加えます。さらに、LAKE の鍵サイズと全体の帯域幅は、既知の攻撃に対して同じ安全性を持つ、提出されたほかのどの格子ベースまたは符号ベースの方式よりも優れています。とはいえ、ランクベースの暗号はかなり新しく、格子ベースの暗号や、ハミング距離を使う符号ベースの暗号ほどには研究されていません。ランクベースのプリミティブに対する暗号解読がさらに行われることには価値があります。

One particular area that could use more study is algebraic attacks targeting rank syndrome decoding and LRPC key recovery. Additionally, further study on separation or reduction between decisional and search variants of IRSD and LRPC key recovery/distinguishing may be of interest. Another area of cryptanalysis that needs more study, relevant to LOCKER in particular, is how decryption failures can be used to mount a chosen ciphertext attack and whether precomputation of ciphertexts by the adversary can be used to significantly increase the decryption failure rate. Finally, it should be mentioned that documentation for ROLLO as well as the documentation provided for the first-round submissions LAKE, LOCKER, and Ouroboros-R is somewhat sparse on details, such as canonical encodings for support spaces.

特にさらなる研究が必要な分野の 1 つは、ランクシンドローム復号と LRPC の鍵復元を標的とする代数的攻撃です。加えて、IRSD と LRPC の鍵復元/識別の判定版と探索版の間の分離または帰着に関するさらなる研究も、関心の対象となりえます。さらなる研究が必要な暗号解読のもう 1 つの分野は、特に LOCKER に関連する、復号失敗を選択暗号文攻撃にどのように利用できるか、また攻撃者による暗号文の事前計算によって復号失敗率を大幅に高められるかどうかです。最後に、ROLLO の文書、および第 1 ラウンド提出物である LAKE、LOCKER、Ouroboros-R に提供された文書は、サポート空間の正準エンコーディングなどの詳細がやや乏しいことにも言及すべきです。

3.16 RQC

3.16 RQC

RQC is a rank-based public key encryption algorithm based on the hardness of a decisional version of the Ideal Rank Syndrome Decoding (IRSD) problem, targeting IND-CCA2 security. It uses a construction similar to RLWE, substituting shortness in the rank metric for shortness in the Euclidean metric, combined with a public error correction code.

RQC は、イデアルランクシンドローム復号(IRSD)問題の判定版の困難性に基づく、IND-CCA2 安全性を目標としたランクベースの公開鍵暗号化アルゴリズムです。RLWE に似た構成を使い、ユークリッド距離での短さをランク距離での短さに置き換え、公開の誤り訂正符号と組み合わせています。

RQC completely eliminates decryption failures and does not need to assume the hardness of the ideal LRPC distinguishing problem. As such, RQC represents a more conservative approach to IND-CCA2 security than the LOCKER variant of ROLLO, which is the other rank-based second-round candidate algorithm targeting IND-CCA2 security. However, RQC comparatively suffers in decryption speed and ciphertext size.

RQC は復号失敗を完全に排除しており、イデアル LRPC 識別問題の困難性を仮定する必要がありません。そのため RQC は、IND-CCA2 安全性を目標とするもう 1 つのランクベースの第 2 ラウンド候補アルゴリズムである ROLLO の LOCKER 変種よりも、IND-CCA2 安全性に対して保守的なアプローチを示しています。ただし RQC は、相対的に復号速度と暗号文サイズで劣ります。

One particular area of cryptanalysis that could use more study is algebraic attack targeting rank syndrome decoding. Additionally, further study on separation or reduction between decisional and search variants of IRSD may be of interest.

さらなる研究が必要な暗号解読の特定の分野の 1 つは、ランクシンドローム復号を標的とする代数的攻撃です。加えて、IRSD の判定版と探索版の間の分離または帰着に関するさらなる研究も、関心の対象となりえます。

Like ROLLO, RQC could benefit from filling in some details in its specification, such as canonical encodings for support spaces and further specification of the use of public Gabidulin codes.

ROLLO と同様に、RQC も、サポート空間の正準エンコーディングや、公開 Gabidulin 符号の使用に関するさらなる規定など、仕様の細部を補うことが改善につながる可能性があります。

3.17 SIKE

3.17 SIKE

SIKE was the only candidate based on arithmetic properties of elliptic curves over finite fields. While quantum computers will break currently deployed elliptic curve cryptosystems, SIKE uses pseudo-random walks on supersingular isogeny graphs of curves, which are not known to be susceptible to quantum attacks. The nature of SIKE allows for a key exchange algorithm which is very similar to the classic Diffie-Hellman. The submission includes a CPA-secure encryption scheme which is converted to a CCA-secure KEM via a standard transformation.

SIKE は、有限体上の楕円曲線の算術的性質に基づく唯一の候補でした。量子コンピューターは現在配備されている楕円曲線暗号システムを破りますが、SIKE は、量子攻撃に対して脆弱であるとは知られていない、曲線の超特異同種写像グラフ上の擬似ランダムウォークを使います。SIKE の性質により、古典的な Diffie-Hellman と非常によく似た鍵交換アルゴリズムが可能になります。提出物には、標準的な変換によって CCA 安全な KEM に変換される CPA 安全な暗号化方式が含まれています。

SIKE has the smallest key sizes among all the remaining submissions, with public keys less than 750 bytes even for its level 5 security parameters. Another advantage of SIKE is that it can leverage existing optimized code for elliptic curve operations and can thus be easily combined with traditional elliptic curve cryptography to create a hybrid classical/post-quantum scheme. The SIKE scheme also benefits from much research into protecting elliptic curve operations from side-channel attacks.

SIKE は、残っているすべての提出物の中で最も鍵サイズが小さく、レベル 5 の安全性パラメーターでも公開鍵は 750 バイト未満です。SIKE のもう 1 つの利点は、楕円曲線演算の既存の最適化されたコードを活用できるため、従来の楕円曲線暗号と容易に組み合わせて、古典暗号と耐量子暗号のハイブリッド方式を作れることです。SIKE 方式は、楕円曲線演算をサイドチャネル攻撃から保護するための多くの研究の恩恵も受けます。

The basic security problem upon which SIKE relies, finding isogenies between supersingular elliptic curves, has not been studied as much as some of the security problems associated with other submissions. Another drawback is that the performance of SIKE seems to be an order of magnitude slower than many of the other candidates.

SIKE が依拠する基本的な安全性の問題である、超特異楕円曲線間の同種写像を求めることは、ほかの提出物に関連する一部の安全性の問題ほどには研究されていません。もう 1 つの欠点は、SIKE の性能が、ほかの多くの候補より 1 桁遅いように見えることです。

3.18 CRYSTALS-DILITHIUM

3.18 CRYSTALS-DILITHIUM

Dilithium is a lattice-based signature scheme, constructed using the Fiat-Shamir heuristic, whose security is based on the hardness of the MLWE problem. Dilithium is part of the CRYSTALS suite, together with the key exchange mechanism Kyber. The main novelty of Dilithium is that the size of the public key is reduced by omitting some of the low-order bits; to compensate for this, each signature includes an extra "hint" that allows the verifier to check the signature.

Dilithium は、Fiat-Shamir ヒューリスティックを用いて構成された格子ベースの署名方式で、その安全性は MLWE 問題の困難性に基づいています。Dilithium は、鍵交換メカニズムの Kyber とともに、CRYSTALS スイートの一部です。Dilithium の主な新規性は、下位ビットの一部を省くことで公開鍵のサイズを小さくしている点です。これを補うため、各署名には、検証者が署名を検証できるようにする追加の"ヒント"が含まれます。

Dilithium offers fairly good performance and is relatively straightforward to implement.

Dilithium はかなり良好な性能を提供し、比較的単純に実装できます。

The best known attacks against Dilithium are based on lattice basis reduction, without making significant use of the algebraic structure of the MLWE problem. The parameter choices for Dilithium are based on conservative estimates of the costs of these attacks. Dilithium has a formal security proof in the classical random oracle model. This proof is nontrivial, and it breaks down in the quantum random oracle model; however no attacks are known. NIST would encourage further analysis of all aspects of this scheme.

Dilithium に対する最もよく知られた攻撃は、MLWE 問題の代数的構造を大きくは利用しない、格子基底簡約に基づくものです。Dilithium のパラメーターの選択は、これらの攻撃のコストの保守的な見積もりに基づいています。Dilithium には、古典的なランダムオラクルモデルでの形式的な安全性証明があります。この証明は自明ではなく、量子ランダムオラクルモデルでは成り立たなくなりますが、攻撃は知られていません。NIST は、この方式のあらゆる側面のさらなる分析を奨励します。

3.19 FALCON

3.19 FALCON

Falcon is a lattice-based signature scheme, based on GPV (Gentry-Peikert-Vaikuntanathan) Gaussian sampling, using the NTRU lattice. The main novelty is a very fast recursive algorithm for Gaussian sampling, using a tree data structure (the "Falcon tree").

Falcon は、NTRU 格子を使い、GPV(Gentry-Peikert-Vaikuntanathan)ガウスサンプリングに基づく格子ベースの署名方式です。主な新規性は、木構造のデータ構造("Falcon ツリー")を使った、ガウスサンプリングのための非常に高速な再帰アルゴリズムです。

The best known attacks against Falcon are based on lattice basis reduction, without significantly exploiting the special structure of the NTRU lattice. Falcon has a formal security proof in the quantum random oracle model.

Falcon に対する最もよく知られた攻撃は、NTRU 格子の特殊な構造を大きくは利用しない、格子基底簡約に基づくものです。Falcon には、量子ランダムオラクルモデルでの形式的な安全性証明があります。

Falcon offers very good performance. However, it is quite complicated to implement, as it relies heavily on the "tower of fields" structure of the number field and requires double-precision floating-point arithmetic. More work is needed to ensure that the signing algorithm is secure against side-channel attacks.

Falcon は非常に良好な性能を提供します。ただし、数体の"体の塔"構造に大きく依存し、倍精度浮動小数点演算を必要とするため、実装はかなり複雑です。署名アルゴリズムがサイドチャネル攻撃に対して安全であることを確保するには、さらなる作業が必要です。

3.20 qTESLA

3.20 qTESLA

qTESLA is a lattice-based signature scheme which uses the assumption that RLWE distributions are indistinguishable from random. The public key in qTESLA is, roughly speaking, a sample of a RLWE distribution. The signer keeps secret information about this sample and uses that information along with a hash function to produce signatures. Signature verification involves some simple arithmetic within the chosen ring, and then the recomputation of a hash function.

qTESLA は、RLWE 分布がランダムと区別できないという仮定を使う、格子ベースの署名方式です。qTESLA の公開鍵は、大まかに言えば、RLWE 分布のサンプルです。署名者はこのサンプルに関する秘密の情報を保持し、その情報をハッシュ関数とともに使って署名を生成します。署名の検証では、選ばれた環の中で簡単な算術演算を行い、その後ハッシュ関数を再計算します。

qTESLA has reasonably good performance parameters that are comparable to the other lattice-based signature schemes. The submitters of qTESLA have claimed a tight security proof for the schemes in the quantum random oracle model. It was noticed that a bug in the security proof requires an adjustment of the parameters (which reduces the efficiency of the scheme). Furthermore, the security argument assumes (among other things) a conjecture about the distribution of random elements in the ring. Considering that the conjecture doesn’t seem to fit the form of a typical security assumption, NIST hopes to get a better understanding of the implications of such a stronger (and unusual) assumption in the second round.

qTESLA は、ほかの格子ベースの署名方式に匹敵する、かなり良好な性能のパラメーターを備えています。qTESLA の提出者は、量子ランダムオラクルモデルでの方式の tight な安全性証明を主張しました。安全性証明にバグがあり、パラメーターの調整が必要であることが分かりました(これにより方式の効率が低下します)。さらに、安全性の議論は、(とりわけ)環内のランダムな要素の分布に関する予想を仮定しています。この予想は典型的な安全性の仮定の形に合っていないように見えるため、NIST は、第 2 ラウンドで、このようなより強い(かつ珍しい)仮定が持つ意味についての理解が深まることを期待しています。

3.21 GeMSS

3.21 GeMSS

GeMSS is a "big-field" multivariate digital signature scheme in the well-studied HFEv- (Hidden Field Equations) family. The scheme transforms the basic HFEv- design assumed to have existential unforgeability into a EUF-CMA secure signature scheme using the Feistel-Patarin construction. The existential unforgeability claim for the HFEv- design is loosely related to the well-studied MQ (multivariate quadratic) and MinRank problems.

GeMSS は、よく研究されている HFEv-(Hidden Field Equations)ファミリーの、"ビッグフィールド"型の多変数デジタル署名方式です。この方式は、存在的偽造不可能性を持つと仮定される基本の HFEv- 設計を、Feistel-Patarin 構成を使って EUF-CMA 安全な署名方式に変換します。HFEv- 設計の存在的偽造不可能性の主張は、よく研究されている MQ(多変数二次)問題や MinRank 問題と緩やかに関連しています。

GeMSS offers some of the smallest signature lengths among all submissions. GeMSS also benefits from the fact that the HFEv- construction is one of the most studied signature primitives in the literature.

GeMSS は、すべての提出物の中で最も短い部類の署名長を提供します。また GeMSS は、HFEv- 構成が文献で最も研究されている署名プリミティブの 1 つであるという点でも有利です。

Aside from signature size and verification time, other performance characteristics of GeMSS raise some concerns. The signing time is quite high and the public keys are quite large; these properties may be features of GeMSS that are inherent to the HFEv- methodology. Still, the security analyses suggest that there are possible tradeoffs among the degree bound, minus projection rank, and number of vinegar variables, for example, that may have an impact on various performance characteristics. We hope as a second-round candidate that further optimizations can be found.

署名サイズと検証時間以外の GeMSS の性能特性には、いくつかの懸念があります。署名時間はかなり長く、公開鍵はかなり大きいです。これらの性質は、HFEv- の方法論に固有の GeMSS の特徴である可能性があります。それでも、安全性分析によれば、たとえば次数の上限、マイナス射影のランク、ビネガー変数の数の間にトレードオフの可能性があり、それがさまざまな性能特性に影響しうることが示唆されています。第 2 ラウンド候補として、さらなる最適化が見つかることを期待しています。

3.22 LUOV

3.22 LUOV

LUOV is a "small-field" multivariate digital signature scheme based on the Unbalanced Oil and Vinegar (UOV) scheme. The main innovation of the scheme is to specify the public key as a map on a certain finite field while publishing coefficients on a subfield. The scheme avoids attacks directly exploiting the subfield structure by using a hash-and-sign approach, ensuring that the extension field must be used. The scheme also uses a pseudorandom generator to construct a part of the public key for which a corresponding private key portion can be solved, similar to the constructions in cyclic-UOV, cyclic-Rainbow and their pseudorandom counterparts.

LUOV は、Unbalanced Oil and Vinegar(UOV)方式に基づく、"スモールフィールド"型の多変数デジタル署名方式です。この方式の主な革新は、公開鍵を特定の有限体上の写像として規定しながら、部分体上の係数を公開する点です。この方式は、ハッシュして署名する手法を使い、拡大体を使わなければならないようにすることで、部分体の構造を直接利用する攻撃を避けています。また、cyclic-UOV、cyclic-Rainbow、およびそれらの擬似乱数版の構成と同様に、対応する秘密鍵部分を解ける公開鍵の一部を構成するために、擬似乱数生成器も使います。

LUOV offers an explicit tradeoff between key size and signature length, making the scheme flexible to disparate use cases. The sum of the public key size and signature length is the smallest for the candidate multivariate signature schemes. The scheme also has a message-recovery mode which conceivably may be of interest.

LUOV は、鍵サイズと署名長の間に明示的なトレードオフを提供し、方式をさまざまなユースケースに柔軟に対応できるものにしています。公開鍵サイズと署名長の合計は、多変数署名方式の候補の中で最も小さくなっています。この方式にはメッセージ復元モードもあり、関心を引く可能性があります。

UOV has been a central object of study in multivariate cryptography for twenty years; thus, LUOV is derived from a seemingly solid foundation. The lifting innovation is very new, however, and could use more security analysis in the second round.

UOV は 20 年にわたって多変数暗号の中心的な研究対象でした。そのため、LUOV は、一見堅固な基盤から導かれています。ただし、リフティングの革新は非常に新しく、第 2 ラウンドでさらなる安全性分析が必要です。

3.23 MQDSS

3.23 MQDSS

MQDSS is a multivariate digital signature scheme derived from a provably secure identification scheme based on the MQ problem. The signature scheme is constructed from the identification scheme via the application of a generalization of the Fiat-Shamir Transform appropriate for 5-pass identification schemes. We note that the proposed parameters do not satisfy the hypotheses of the security reduction.

MQDSS は、MQ 問題に基づく証明可能安全な識別方式から導かれる多変数デジタル署名方式です。この署名方式は、5 パスの識別方式に適した Fiat-Shamir 変換の一般化を識別方式に適用することで構成されています。提案されたパラメーターが、安全性の帰着の仮説を満たしていないことに注意が必要です。

MQDSS supports pseudorandom key generation with large signatures. The performance characteristics of MQDSS are most directly comparable to those of hash-based signature schemes.

MQDSS は、大きな署名を伴う擬似乱数による鍵生成をサポートします。MQDSS の性能特性は、ハッシュベースの署名方式の性能特性と最も直接的に比較できます。

MQDSS could use more security analysis for the more aggressively chosen parameter sets. We expect that as a better understanding of boundary case security is developed that further optimization is possible. NIST is moving MQDSS forward with the hope that further research will result in improved parameters and performance.

MQDSS は、より積極的に選ばれたパラメーターセットについて、さらなる安全性分析が必要です。境界ケースの安全性についての理解が深まれば、さらなる最適化が可能になると期待しています。NIST は、さらなる研究によってパラメーターと性能が改善されることを期待して、MQDSS を先に進めます。

3.24 Rainbow

3.24 Rainbow

Rainbow is a multivariate digital signature scheme that is a generalization of the UOV structure allowing parameterizations that are more efficient at the cost of additional algebraic structure. The Rainbow signature in its format of the submission has been studied for about fifteen years with various parameters. Rainbow claims EUF-CMA security utilizing a hash construction with a random salt.

Rainbow は、UOV の構造を一般化した多変数デジタル署名方式で、追加の代数的構造を代償として、より効率的なパラメーター化を可能にします。提出された形式の Rainbow 署名は、さまざまなパラメーターで約 15 年間研究されてきました。Rainbow は、ランダムなソルトを使うハッシュ構成を利用して、EUF-CMA 安全性を主張しています。

The spectrum of Rainbow parameters allows for optimization in a diverse array of use cases. A further benefit of Rainbow is that it has also been studied in other contexts, including in lightweight applications.

Rainbow のパラメーターの幅広さにより、多様なユースケースで最適化が可能です。Rainbow のさらなる利点は、軽量なアプリケーションを含む、ほかの文脈でも研究されてきたことです。

The Rainbow submission offers parameter sets targeting all of the security levels indicated in the NIST Call for Proposals [8]. As a second-round candidate, we expect that greater focus on a narrower set of specifications will be reached. Furthermore, we hope that more research will be inspired on the collection of optimization techniques for Rainbow keys that exists in the literature and that was not considered in the Rainbow submission, ideally leading the community toward a consensus on their feasibility. In addition, the implementation of Rainbow could be greatly improved.

Rainbow の提出物は、NIST の提案募集 [8] で示されたすべての安全性レベルを対象とするパラメーターセットを提供しています。第 2 ラウンド候補としては、より絞り込まれた仕様に、より焦点が当てられることを期待します。さらに、文献に存在するものの Rainbow の提出物では考慮されていなかった、Rainbow の鍵の最適化手法の集合について、さらなる研究が促され、理想的には、その実現可能性についてコミュニティの合意につながることを期待しています。加えて、Rainbow の実装は大幅に改善できる可能性があります。

3.25 Picnic

3.25 Picnic

Picnic is a signature scheme that uses no number-theoretic or structured hardness assumptions. The security reductions are to hash functions and symmetric block ciphers. A Picnic signature is a non-interactive zero-knowledge proof of knowledge of the secret key. The plaintext 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 output the proof. The length of the signature depends on the multiplicative complexity of the encryption scheme and on the specific technique to construct a zero-knowledge proof of knowledge (from the field of secure multi-party computation). Picnic has small public key size, large signatures, and both signing and verifying are slow. Key generation is quite efficient.

Picnic は、数論的な、あるいは構造を持つ困難性の仮定を一切使わない署名方式です。安全性の帰着先は、ハッシュ関数と共通鍵ブロック暗号です。Picnic の署名は、秘密鍵の知識に関する非対話型ゼロ知識証明です。署名される平文は、秘密鍵の保持者だけが証明を出力できるように、(ハッシュを介して)知識の証明のチャレンジに組み込まれます。署名の長さは、暗号化方式の乗法的複雑度と、(秘密計算の分野の)ゼロ知識の知識証明を構成する具体的な技法に依存します。Picnic は、公開鍵サイズが小さく、署名が大きく、署名と検証の両方が低速です。鍵生成はかなり効率的です。

Picnic is a highly modular design. The cryptographic primitives – hash and block cipher -- could be instantiated in different ways. The submitted design uses lowMC, a block cipher with low multiplicative complexity. LowMC has not been studied as much as AES, and hence needs much more analysis. The effect of using AES instead of lowMC in Picnic seems to be an expansion of the signature length by a factor that ranges from 6 to 9, depending on the block size. Improvements in secure multi-party computation techniques would translate into smaller signatures. It is worth noting that the security requirements for the underlying block cipher are less stringent than the general security requirements of a block-cipher because only a single (random plaintext, ciphertext) pair is ever revealed.

Picnic は、非常にモジュール性の高い設計です。暗号プリミティブ、すなわちハッシュとブロック暗号は、異なる方法でインスタンス化できます。提出された設計では、乗法的複雑度の低いブロック暗号である lowMC を使っています。LowMC は AES ほどには研究されていないため、はるかに多くの分析が必要です。Picnic で lowMC の代わりに AES を使った場合の影響は、ブロックサイズに応じて、署名長が 6 倍から 9 倍に拡大することのようです。秘密計算の技法が改善されれば、署名はより小さくなります。(ランダムな平文、暗号文)のペアが 1 組だけしか明かされないため、基盤となるブロック暗号に対する安全性要件は、ブロック暗号の一般的な安全性要件ほど厳しくない点は注目に値します。

There is a multi-target attack reported on the Picnic submission, and the Picnic team has proposed a countermeasure in addition to a number of other modifications to improve efficiency, as well as a new, tight security proof that avoids the forking lemma. However, being a novel scheme, Picnic would still benefit from much more scrutiny and analysis.

Picnic の提出物に対しては、マルチターゲット攻撃が報告されており、Picnic のチームは、効率を向上させる多数のその他の修正に加えて、対策を提案し、フォーキング補題を避ける新しい tight な安全性証明も示しました。しかし、新しい方式であるため、Picnic には、はるかに多くの精査と分析がなお必要です。

3.26 SPHINCS+

3.26 SPHINCS+

SPHINCS+ is a stateless hash-based signature scheme. Hash-based signature schemes were first proposed in the late 1970s, and many improvements have been developed since then. SPHINCS+ uses two different hash-based signature schemes: Winternitz One-Time Signature Plus (WOTS+), a one-time signature scheme, and Forest of Random Subsets (FORS), a few-time signature scheme. A SPHINCS+ key pair consists of \(2^{60}\) or more FORS key pairs. Multiple levels of Merkle hash trees are used in order to enable the individual FORS public keys to be authenticated. Each of the FORS public keys and the root of each of the Merkle hash trees is signed using WOTS+. Messages are signed using a pseudorandomly selected FORS key, and a message signature consists of the FORS signature, one WOTS+ signature for each Merkle tree level, and the intermediate hash values needed to traverse each Merkle tree for verification.

SPHINCS+ は、ステートレスなハッシュベースの署名方式です。ハッシュベースの署名方式は 1970 年代後半に初めて提案され、それ以来、多くの改良が開発されてきました。SPHINCS+ は、2 つの異なるハッシュベースの署名方式を使います。1 つは一回署名方式の Winternitz One-Time Signature Plus(WOTS+)、もう 1 つは数回署名方式の Forest of Random Subsets(FORS)です。SPHINCS+ の鍵ペアは、\(2^{60}\) 個以上の FORS 鍵ペアで構成されます。個々の FORS 公開鍵を認証できるようにするため、複数階層の Merkle ハッシュ木が使われます。各 FORS 公開鍵と各 Merkle ハッシュ木のルートは、WOTS+ で署名されます。メッセージは、擬似ランダムに選ばれた FORS 鍵で署名され、メッセージの署名は、FORS 署名、Merkle 木の各階層に 1 つずつの WOTS+ 署名、および検証のために各 Merkle 木をたどるのに必要な中間ハッシュ値で構成されます。

The primary advantage of SPHINCS+ is that its security relies solely on the preimage resistance of the hash function used. SPHINCS+ also has very small public keys – 32 to 64 bytes, depending on the security level. The disadvantage is that signing is very slow and signatures are relatively large, although SPHINCS+ offers different parameter choices that trade off signature size for speed.

SPHINCS+ の主な利点は、その安全性が、使用するハッシュ関数の原像計算困難性のみに依拠していることです。SPHINCS+ は、公開鍵も、安全性レベルに応じて 32 から 64 バイトと非常に小さくなります。欠点は、署名が非常に遅く、署名が比較的大きいことですが、SPHINCS+ は、署名サイズと速度をトレードオフするさまざまなパラメーターの選択肢を提供しています。

SPHINCS+ uses a pseudorandom function (PRF) to generate keys and bitmasks for each hash function call in order to protect against multi-target attacks against the hash function. Most of the cost of signature generation and verification is the time spent generating these keys and bitmasks. A possible second-round tweak might involve a more efficient technique for protecting against multi-target attacks.

SPHINCS+ は、ハッシュ関数に対するマルチターゲット攻撃から保護するため、擬似ランダム関数(PRF)を使って、各ハッシュ関数呼び出しのための鍵とビットマスクを生成します。署名の生成と検証のコストの大部分は、これらの鍵とビットマスクの生成に費やされる時間です。第 2 ラウンドでの調整として、マルチターゲット攻撃から保護するより効率的な技法が考えられるかもしれません。

4 Conclusion and Next Steps

4 結論と今後の予定

The announcement of the 26 second-round candidates marks the start of the second round of the NIST PQC Standardization Process. This report summarized the evaluation criteria used to select these candidate algorithms, and briefly described the basic design of the second-round candidates, along with advantages and disadvantages already noted in these submissions.

26 件の第 2 ラウンド候補の発表は、NIST PQC 標準化プロセスの第 2 ラウンドの開始を示します。本報告書は、これらの候補アルゴリズムを選定するために用いた評価基準を要約し、第 2 ラウンド候補の基本設計と、これらの提出物で既に指摘されている利点と欠点を簡潔に説明しました。

Submitters of the second-round candidates will be allowed to tweak their submissions to improve upon them if they wish, and fix any inconsistencies, problems or shortcomings in the specifications or source code. Any changes must be submitted to NIST by March 15, 2019 in a complete submission package, as defined in FRN-Dec16. More details will be provided on the webpage https://www.nist.gov/pqcrypto.

第 2 ラウンド候補の提出者は、希望すれば、提出物を改善するために調整を加え、仕様やソースコードの不整合、問題、欠点を修正することが認められます。変更はすべて、FRN-Dec16 で定義された完全な提出パッケージとして、2019 年 3 月 15 日までに NIST に提出しなければなりません。詳細は Web ページ https://www.nist.gov/pqcrypto で提供されます。

The next twelve to eighteen months will consist of a public review on the remaining 26 second-round post-quantum candidates. Some of the second-round candidates have received little or no published cryptanalysis by the cryptographic community-at-large. With the number of candidates substantially reduced from the first round, we hope that the combined efforts of the cryptographic community will evaluate the remaining candidates and provide NIST with feedback that supports or refutes the security claims of the submitters. We are also interested in additional performance data on each of the candidates. This includes optimized implementations written in assembly code or using instruction set extensions, and analyses of implementation suitability of candidate algorithms in constrained platforms, as well as performance data for hardware implementations.

今後の 12 か月から 18 か月は、残る 26 件の第 2 ラウンドの耐量子候補に対する公開レビューの期間となります。第 2 ラウンド候補の一部は、暗号コミュニティ全体からの、公表された暗号解読をほとんど、あるいはまったく受けていません。候補の数が第 1 ラウンドから大幅に減ったことで、暗号コミュニティの総力によって、残った候補が評価され、提出者の安全性の主張を裏付ける、または反証するフィードバックが NIST に寄せられることを期待しています。NIST は、各候補に関する追加の性能データにも関心があります。これには、アセンブリコードや命令セット拡張を使って書かれた最適化実装、制約のあるプラットフォームでの候補アルゴリズムの実装適性の分析、ハードウェア実装の性能データが含まれます。

NIST plans to host the Second NIST PQC Standardization Conference at the University of California Santa Barbara on August 22-24, 2019, following Crypto 2019. Submitters of the second-round candidates will be invited to present their updated algorithms. In 2020, NIST plans to either select finalists for a final round or select a small number of candidates for standardization. More detailed plans will be provided at a later date.

NIST は、Crypto 2019 に続いて、2019 年 8 月 22 日から 24 日に、カリフォルニア大学サンタバーバラ校で第 2 回 NIST PQC 標準化会議を開催する予定です。第 2 ラウンド候補の提出者は、更新したアルゴリズムを発表するよう招待されます。2020 年に NIST は、最終ラウンドに向けたファイナリストを選定するか、標準化に向けた少数の候補を選定する予定です。より詳細な計画は、後日示されます。

Appendix A—References

付録 A—参考文献

[1] U.S. Department of Commerce. Digital Signature Standard (DSS), Federal Information Processing Standards (FIPS) Publication 186-4, July 2013, 121pp. https://doi.org/10.6028/NIST.FIPS.186-4.

[1] U.S. Department of Commerce. Digital Signature Standard (DSS), Federal Information Processing Standards (FIPS) Publication 186-4, July 2013, 121pp. https://doi.org/10.6028/NIST.FIPS.186-4.

[2] NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2018, 141pp. https://doi.org/10.6028/NIST.SP.800-56Ar3.

[2] NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2018, 141pp. https://doi.org/10.6028/NIST.SP.800-56Ar3.

[3] NIST Special Publication (SP) 800-56B Revision 1, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, September 2014, 121pp. https://doi.org/10.6028/NIST.SP.800-56Br1.

[3] NIST Special Publication (SP) 800-56B Revision 1, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, National Institute of Standards and Technology, Gaithersburg, Maryland, September 2014, 121pp. https://doi.org/10.6028/NIST.SP.800-56Br1.

[4] NIST 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.

[4] NIST 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.

[5] L. Chen, S. Jordan, Y.K. Liu, D. Moody, R. Peralta, R. Perlner, D. Smith-tone, Report on Post-Quantum Cryptography, NISTIR 8105, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2016, 10pp. https://doi.org/10.6028/NIST.IR.8105.

[5] L. Chen, S. Jordan, Y.K. Liu, D. Moody, R. Peralta, R. Perlner, D. Smith-tone, Report on Post-Quantum Cryptography, NISTIR 8105, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2016, 10pp. https://doi.org/10.6028/NIST.IR.8105.

[6] D. Moody, Post-Quantum Cryptography Standardization: Announcement and outline of NIST’s Call for Submissions, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis.

[6] D. Moody, Post-Quantum Cryptography Standardization: Announcement and outline of NIST’s Call for Submissions, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis.

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

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

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

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

[9] “Establishment of NIST Smart Grid Advisory Committee and Solicitation of Nominations for Members,” 75 Federal Register 7 (January 12, 2010), pp. 1595-1596. https://federalregister.gov/a/2010-344 [accessed 2/25/14].

[9] “Establishment of NIST Smart Grid Advisory Committee and Solicitation of Nominations for Members,” 75 Federal Register 7 (January 12, 2010), pp. 1595-1596. https://federalregister.gov/a/2010-344 [参照日: 2/25/14].

[10] U.S. Department of Commerce. Advanced Encryption Standard (AES), Federal Information Processing Standards (FIPS) Publication 197, November 2001, 47pp. https://doi.org/10.6028/NIST.FIPS.197.

[10] U.S. Department of Commerce. Advanced Encryption Standard (AES), Federal Information Processing Standards (FIPS) Publication 197, November 2001, 47pp. https://doi.org/10.6028/NIST.FIPS.197.

[11] U.S. Department of Commerce. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions), Federal Information Processing Standards (FIPS) Publication 202, August 2015, 29pp. https://doi.org/10.6028/NIST.FIPS.202.

[11] U.S. Department of Commerce. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Federal Information Processing Standards (FIPS) Publication 202, August 2015, 29pp. https://doi.org/10.6028/NIST.FIPS.202.

[12] NIST pqc-forum mailing list 2018-05-04, Jacob Alperin-Sheriff, https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/xFxHuxPXTO4/wZCFL734AQAJ.

[12] NIST pqc-forum mailing list 2018-05-04, Jacob Alperin-Sheriff, https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/xFxHuxPXTO4/wZCFL734AQAJ.

[13] D. Moody, Let’s Get Ready to Rumble – The NIST PQC “Competition”, PQCrypto 2018, Ft. Lauderdale, Florida, April 11, 2018, https://csrc.nist.gov/Presentations/2018/Let-s-Get-Ready-to-Rumble-The-NIST-PQC-Competiti.

[13] D. Moody, Let’s Get Ready to Rumble – The NIST PQC “Competition”, PQCrypto 2018, Ft. Lauderdale, Florida, April 11, 2018, https://csrc.nist.gov/Presentations/2018/Let-s-Get-Ready-to-Rumble-The-NIST-PQC-Competiti.

[14] J. Hoffstein, J. Pipher, and J.H. Silverman, NTRU: A ring-based public key cryptosystem, in ANTS, Lecture Notes in Comput. Sci. 423, J. Buhler, ed., Springer, Berlin, 1998, pp. 267-288.

[14] J. Hoffstein, J. Pipher, and J.H. Silverman, NTRU: A ring-based public key cryptosystem, in ANTS, Lecture Notes in Comput. Sci. 423, J. Buhler, ed., Springer, Berlin, 1998, pp. 267-288.

[15] G. Chunsheng, Integer version of ring-LWE and its applications. Cryptology ePrint Archive, Report 2017/641, 2017. http://eprint.iacr.org/2017/641.

[15] G. Chunsheng, Integer version of ring-LWE and its applications. Cryptology ePrint Archive, Report 2017/641, 2017. http://eprint.iacr.org/2017/641.

[16] R. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, Jet Propulsion Laboratory, Pasadena, CA, 1978. http://ipnpr.jpl.nasa.gov/progressreport2/42-44/ 44N.pdf.

[16] R. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, Jet Propulsion Laboratory, Pasadena, CA, 1978. http://ipnpr.jpl.nasa.gov/progressreport2/42-44/ 44N.pdf.