目次

NIST IR 8545 日本語訳

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

[要約] NIST IR 8545 は、NIST 耐量子暗号標準化プロセスの第 4 ラウンドの評価と選定のプロセスを説明する状況報告書です。第 4 ラウンドで NIST は、検討対象として鍵確立のための 4 つの候補アルゴリズム、すなわち BIKE、Classic McEliece、HQC、SIKE を選びました。報告書は、一般からのフィードバックと内部レビューに基づくこれらの候補の評価と選定のプロセスを説明し、各候補アルゴリズムを要約して、標準化のために選定されたものを明らかにします。標準化される鍵確立アルゴリズムは HQC のみであり、NIST は、鍵確立のポートフォリオを拡充するため、HQC に基づく標準を策定します。

NIST Internal Report

NIST内部報告書

NIST IR 8545

NIST IR 8545

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

NIST耐量子暗号標準化プロセス第4ラウンドに関する状況報告書

Gorjan Alagic Maxime Bros Pierre Ciadoux David Cooper Quynh Dang Thinh Dang John Kelsey Jacob Lichtinger Yi-Kai Liu Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Hamilton Silberg Daniel Smith-Tone Noah Waller

Gorjan Alagic Maxime Bros Pierre Ciadoux David Cooper Quynh Dang Thinh Dang John Kelsey Jacob Lichtinger Yi-Kai Liu Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Hamilton Silberg Daniel Smith-Tone Noah Waller

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

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

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

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

NIST Internal Report

NIST内部報告書

NIST IR 8545

NIST IR 8545

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

NIST耐量子暗号標準化プロセス第4ラウンドに関する状況報告書

Gorjan Alagic Maxime Bros Pierre Ciadoux David Cooper Quynh Dang Thinh Dang John Kelsey Jacob Lichtinger Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Hamilton Silberg Daniel Smith-Tone Noah Waller Computer Security Division Information Technology Laboratory

Gorjan Alagic Maxime Bros Pierre Ciadoux David Cooper Quynh Dang Thinh Dang John Kelsey Jacob Lichtinger Carl Miller Dustin Moody Rene Peralta Ray Perlner Angela Robinson Hamilton Silberg Daniel Smith-Tone Noah Waller Computer Security Division Information Technology Laboratory

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

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

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

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

March 2025

2025年3月

U.S. Department of Commerce Howard Lutnick, Secretary

米国商務省 Howard Lutnick 長官

National Institute of Standards and Technology Craig Burkhardt, Acting Under Secretary of Commerce for Standards and Technology and Acting NIST Director

国立標準技術研究所 Craig Burkhardt、商務次官代理(標準・技術担当)兼 NIST 所長代理

Certain equipment, instruments, software, or materials, commercial or non-commercial, are identified in this paper in order to specify the experimental procedure adequately. Such identification does not imply recommendation or endorsement of any product or service by NIST, nor does it imply that the materials or equipment identified 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で入手できます。

NIST Technical Series Policies Copyright, Use, and Licensing Statements NIST Technical Series Publication Identifier Syntax

NIST技術シリーズの方針、著作権・使用・ライセンスに関する声明、NIST技術シリーズ刊行物識別子の構文

Publication History Approved by the NIST Editorial Review Board on 2025-03-05

刊行の経緯:2025-03-05にNIST編集審査委員会が承認

How to cite this NIST Technical Series Publication: Alagic G, Bros M, Ciadoux P, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Silberg H, Smith-Tone D, Waller N (2025) Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Internal Report (IR) NIST IR 8545. https://doi.org/10.6028/NIST.IR.8545

本NIST技術シリーズ刊行物の引用方法:Alagic G, Bros M, Ciadoux P, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Silberg H, Smith-Tone D, Waller N (2025) Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Internal Report (IR) NIST IR 8545. https://doi.org/10.6028/NIST.IR.8545

Author ORCID iDs Gorjan Alagic: 0000-0002-0107-6037 Maxime Bros: 0000-0001-7838-2529 Pierre Ciadoux: 0009-0001-2272-681X David Cooper: 0009-0001-2410-5830 Quynh Dang: 0009-0005-9801-6805 Thinh Dang: 0000-0001-9705-0925 John Kelsey: 0000-0002-3427-1744 Jacob Lichtinger: 0000-0003-2407-5309 Yi-Kai Liu: 0000-0001-7458-4721 Carl Miller: 0000-0003-1917-1531 Dustin Moody: 0000-0002-4868-6684 Rene Peralta: 0000-0002-2318-7563 Ray Perlner: 0000-0001-8793-2238 Angela Robinson: 0000-0002-1209-0379 Hamilton Silberg: 0009-0004-4178-8954 Daniel Smith-Tone: 0000-0002-7995-8734 Noah Waller: 0000-0002-6979-9725

著者のORCID iD Gorjan Alagic: 0000-0002-0107-6037 Maxime Bros: 0000-0001-7838-2529 Pierre Ciadoux: 0009-0001-2272-681X David Cooper: 0009-0001-2410-5830 Quynh Dang: 0009-0005-9801-6805 Thinh Dang: 0000-0001-9705-0925 John Kelsey: 0000-0002-3427-1744 Jacob Lichtinger: 0000-0003-2407-5309 Yi-Kai Liu: 0000-0001-7458-4721 Carl Miller: 0000-0003-1917-1531 Dustin Moody: 0000-0002-4868-6684 Rene Peralta: 0000-0002-2318-7563 Ray Perlner: 0000-0001-8793-2238 Angela Robinson: 0000-0002-1209-0379 Hamilton Silberg: 0009-0004-4178-8954 Daniel Smith-Tone: 0000-0002-7995-8734 Noah Waller: 0000-0002-6979-9725

Contact Information pqc-comments@nist.gov

連絡先pqc-comments@nist.gov

Additional Information Additional information about this publication is available at https://csrc.nist.gov/pubs/ir/8545/final, including related content, potential updates, and document history.

追加情報:本刊行物に関する追加情報(関連コンテンツ、更新の可能性、文書の履歴を含む)は、https://csrc.nist.gov/pubs/ir/8545/finalで入手できます。

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

すべてのコメントは、情報自由法(FOIA)に基づいて公開される場合があります。

Abstract

要旨

NIST is selecting public-key cryptographic algorithms through a public, competition-like process to specify additional digital signature, public-key encryption, and key-establishment algorithms to supplement FIPS 186-5, SP 800-56Ar3, and SP 800-56Br2. These algorithms are intended to protect sensitive information well into the foreseeable future, including after the advent of quantum computers. In the fourth round of the Post-Quantum Cryptography Standardization Process, NIST selected four candidate algorithms for key establishment to be studied: BIKE, Classic McEliece, HQC, and SIKE. This report describes the evaluation and selection process of these fourth-round candidates based on public feedback and internal review. The report summarizes each of the candidate algorithms and identifies those selected for standardization. The only key-establishment algorithm that will be standardized is HQC, and NIST will develop a standard based on HQC to augment its key-establishment portfolio.

NISTは、FIPS 186-5、SP 800-56Ar3、SP 800-56Br2を補完する、追加のデジタル署名、公開鍵暗号化、鍵確立のアルゴリズムを規定するため、公開の競技会に似たプロセスを通じて、公開鍵暗号アルゴリズムを選定しています。これらのアルゴリズムは、量子コンピュータの出現後も含め、予見できる将来にわたって機微な情報を保護することを意図しています。耐量子暗号標準化プロセスの第4ラウンドで、NISTは検討対象として、鍵確立のための4つの候補アルゴリズム、すなわちBIKE、Classic McEliece、HQC、SIKEを選びました。本報告書は、一般からのフィードバックと内部レビューに基づく、これらの第4ラウンドの候補の評価と選定のプロセスを説明します。報告書は各候補アルゴリズムを要約し、標準化のために選定されたものを明らかにします。標準化される鍵確立アルゴリズムはHQCのみであり、NISTは、鍵確立のポートフォリオを拡充するため、HQCに基づく標準を策定します。

Keywords

キーワード

cryptography; key-encapsulation mechanism (KEM); key establishment; post-quantum cryptography; quantum-resistant; quantum-safe.

暗号技術; 鍵カプセル化メカニズム(KEM); 鍵確立; 耐量子暗号; 量子耐性; 量子安全。

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の責務には、連邦情報システムにおける、国家安全保障に関連する情報以外の情報について、費用対効果の高いセキュリティとプライバシーのための管理上・運用上・技術上・物理上の標準とガイドラインの策定が含まれます。

Contents

目次

List of Tables

表の一覧

Supplemental Content

補足コンテンツ

The NIST Post-Quantum Cryptography Standardization Process web page is available at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization.

NIST耐量子暗号標準化プロセスのウェブページは、https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardizationで入手できます。

Acknowledgments

謝辞

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

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

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

NISTはまた、プロセスの4つのラウンドを通じて、候補アルゴリズムのセキュリティ、実装、性能の分析を提供してくれた暗号コミュニティの方々の尽力にも感謝します。これらの方々とアルゴリズムの提出者が力を合わせなければ、NISTは耐量子のデジタルアルゴリズムを標準化のために選定することはできませんでした。

The authors of this report also appreciate the efforts by other members of NIST’s PQC team who reviewed candidate algorithms, analyses, and public comments; performed testing; provided technical and administrative support; and participated in numerous meetings to discuss the selection of the candidate to be standardized. They are Zuzana Bajcsy, Lily Chen, Morris Dworkin, Sara Kerman, and Andrew Regenscheid.

本報告書の著者は、NISTのPQCチームの他のメンバーの尽力にも感謝します。彼らは、候補アルゴリズム、分析、パブリックコメントをレビューし、試験を実施し、技術面および管理面の支援を提供し、標準化する候補の選定を議論する数多くの会議に参加しました。Zuzana Bajcsy、Lily Chen、Morris Dworkin、Sara Kerman、Andrew Regenscheidの各氏です。

1. Introduction

1.はじめに

The National Institute of Standards and Technology (NIST) initiated the Post-Quantum Cryptography (PQC) Standardization Process in December 2016 to select quantum-resistant public-key cryptographic algorithms for standardization in response to the substantial development and advancement of quantum computing. After three rounds of evaluation and analysis, NIST announced the selection of the first algorithms to be standardized [2]. The key encapsulation mechanism (KEM) selected for standardization was CRYSTALS-Kyber (ML-KEM [3]). The digital signatures selected were CRYSTALS-Dilithium (ML-DSA [4]), Falcon (FN-DSA), and SPHINCS+ (SLH-DSA [5]). For a detailed explanation of NIST’s choices, as well as a summary of the third round, see NIST IR 8413 [2].

米国国立標準技術研究所(NIST)は、量子コンピューティングの著しい発展と進歩を受け、標準化のために耐量子の公開鍵暗号アルゴリズムを選定するため、2016年12月に耐量子暗号(PQC)標準化プロセスを開始しました。3回の評価と分析を経て、NISTは標準化する最初のアルゴリズムの選定を発表しました[2]。標準化のために選定された鍵カプセル化メカニズム(KEM)はCRYSTALS-Kyber(ML-KEM [3])でした。選定されたデジタル署名は、CRYSTALS-Dilithium(ML-DSA [4])、Falcon(FN-DSA)、SPHINCS+(SLH-DSA [5])でした。NISTの選択の詳しい説明と第3ラウンドの概要については、NIST IR 8413 [2]を参照してください。

In addition to those initial selections, NIST advanced four KEM candidates to the fourth round for continued evaluation: BIKE [6], Classic McEliece [7], HQC [8], and SIKE [9]. These algorithms were all based on different security assumptions than ML-KEM. NIST indicated that it would select one or two of the algorithms for standardization at the conclusion of the fourth round.

これらの最初の選定に加えて、NISTは4つのKEM候補、すなわちBIKE [6]、Classic McEliece [7]、HQC [8]、SIKE [9]を、継続的な評価のために第4ラウンドへ進めました。これらのアルゴリズムは、いずれもML-KEMとは異なる安全性の仮定に基づいています。NISTは、第4ラウンドの終了時に、これらのアルゴリズムのうち1つまたは2つを標準化のために選定すると示していました。

The fourth round began in July 2022 and involved a thorough analysis of the theoretical and empirical evidence used to justify the security of the candidates. During this time, the submitters of SIKE acknowledged its insecurity and recommended against its further use. The submission teams of the unbroken fourth-round candidates were invited to present updates for their candidate algorithms at the Fifth NIST PQC Standardization Conference in Rockville, Maryland, on April 10-12, 2024. The submitters participated in a joint panel to discuss the candidates’ merits, and several researchers presented work that was relevant to the PQC standardization process.

第4ラウンドは2022年7月に始まり、候補の安全性を裏づけるために用いられた理論的および経験的な証拠を徹底的に分析しました。この間に、SIKEの提出者はその安全性の欠如を認め、今後の使用を推奨しないとしました。破られていない第4ラウンドの候補の提出チームは、2024年4月10日から12日にメリーランド州ロックビルで開催された第5回NIST PQC標準化会議で、候補アルゴリズムの最新状況を発表するよう招かれました。提出者は合同パネルに参加して候補の長所を議論し、複数の研究者がPQC標準化プロセスに関連する研究を発表しました。

Throughout the fourth round, NIST received valuable feedback from the cryptographic community. Based on this feedback and internal reviews of the fourth-round candidates, NIST announced the selection of HQC in March 2025 for standardization.

第4ラウンドを通じて、NISTは暗号コミュニティから貴重なフィードバックを受けました。このフィードバックと、第4ラウンドの候補に対する内部レビューに基づき、NISTは2025年3月に、標準化のためのHQCの選定を発表しました。

Table 1 shows a timeline of major events with respect to the NIST PQC Standardization Process to date.

表1は、NIST PQC標準化プロセスにおける現在までの主要な出来事の経緯を示しています。

Table 1. Timeline of the NIST Post-Quantum Cryptography Standardization Process

表1. NIST耐量子暗号標準化プロセスの経緯

DateEvent
April 2015Workshop on Cybersecurity in a Post-Quantum World, NIST, Gaithersburg, MD
February 2016PQC Standardization: Announcement and outline of NIST’s Call for Submissions presentation given at PQCrypto 2016
April 2016Release of IR 8105, Report on Post-Quantum Cryptography [10]
December 2016Federal Register Notice – Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms [11]
November 30, 2017Submission Deadline for NIST PQC Standardization Process
December 2017Announcement of first-round candidates and beginning of first-round public comment period
April 2018First NIST PQC Standardization Conference, Ft. Lauderdale, FL
January 2019Announcement of second-round candidates; release of IR 8240, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process [12]; and beginning of second-round public comment period
August 2019Second NIST PQC Standardization Conference, Santa Barbara, CA
April 2020Call for feedback on the selection of third-round candidates
July 2020Announcement of third-round finalists and alternate candidates; release of IR 8309, Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process [13]; and beginning of third-round public comment period
June 2021Third NIST PQC Standardization Conference, held virtually
July 2022Announcement of candidate algorithms to be standardized and alternate candidates advancing to the fourth round; release of IR 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process; and beginning of fourth-round public comment period
October 2022Fourth round specifications published on NIST’s PQC website
November 2022Fourth NIST PQC Standardization Conference, held virtually
August 2023Draft versions of FIPS 203 [14], FIPS 204 [4], and FIPS 205 [5] posted for public comment
April 2024Fifth NIST PQC Standardization Conference, Gaithersburg, MD
August 2024Final versions of FIPS 203 [14], FIPS 204 [4], and FIPS 205 [5] published
January 2025Draft for KEM guidance SP 800-227 posted for public comment
March 2025Announcement of fourth-round candidate algorithm to be standardized and release of IR 8545, Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process
日付出来事
2015年4月Workshop on Cybersecurity in a Post-Quantum World(NIST、メリーランド州ゲイザースバーグ)
2016年2月PQC標準化: PQCrypto 2016でのNISTの公募(Call for Submissions)の発表と概要の説明
2016年4月IR 8105 Report on Post-Quantum Cryptography [10]の公開
2016年12月官報告示–公開鍵耐量子暗号アルゴリズムの候補募集の発表[11]
2017年11月30日NIST PQC標準化プロセスの提出期限
2017年12月第1ラウンドの候補の発表と、第1ラウンドのパブリックコメント期間の開始
2018年4月第1回NIST PQC標準化会議(フロリダ州フォートローダーデール)
2019年1月第2ラウンドの候補の発表、IR 8240 Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process [12]の公開、および第2ラウンドのパブリックコメント期間の開始
2019年8月第2回NIST PQC標準化会議(カリフォルニア州サンタバーバラ)
2020年4月第3ラウンドの候補の選定に関するフィードバックの募集
2020年7月第3ラウンドのファイナリストと代替候補の発表、IR 8309 Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process [13]の公開、および第3ラウンドのパブリックコメント期間の開始
2021年6月第3回NIST PQC標準化会議(オンライン開催)
2022年7月標準化する候補アルゴリズムと、第4ラウンドへ進む代替候補の発表、IR 8413 Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Processの公開、および第4ラウンドのパブリックコメント期間の開始
2022年10月第4ラウンドの仕様をNISTのPQCウェブサイトで公開
2022年11月第4回NIST PQC標準化会議(オンライン開催)
2023年8月FIPS 203 [14]、FIPS 204 [4]、FIPS 205 [5]のドラフト版をパブリックコメントのために掲載
2024年4月第5回NIST PQC標準化会議(メリーランド州ゲイザースバーグ)
2024年8月FIPS 203 [14]、FIPS 204 [4]、FIPS 205 [5]の最終版を公開
2025年1月KEMに関するガイダンスSP 800-227のドラフトをパブリックコメントのために掲載
2025年3月標準化する第4ラウンドの候補アルゴリズムの発表とIR 8545 Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Processの公開

1.1. Purpose and Organization of This Document

1.1.本書の目的と構成

This report summarizes the fourth round of the NIST PQC Standardization Process.

本報告書は、NIST PQC標準化プロセスの第4ラウンドを要約します。

Section 2 enumerates the candidates that were included in the fourth round. It also describes the evaluation criteria and selection process used to ultimately select HQC for standardization.

第2節では、第4ラウンドに含まれた候補を列挙します。また、最終的にHQCを標準化のために選定する際に用いた評価基準と選定プロセスについても説明します。

Section 3 summarizes each of the fourth-round candidates, including a brief description of the algorithm and its characteristics with regard to security, performance, and implementation. This section also presents the rationale for standardizing some candidate algorithms and not others.

第3節では、第4ラウンドの各候補について、アルゴリズムの簡単な説明と、セキュリティ、性能、実装に関するその特性を要約します。また、一部の候補アルゴリズムを標準化し、他を標準化しない理由も示します。

Section 4 concludes and describes the next steps in the standardization process.

第4節では結論を述べ、標準化プロセスの次のステップを説明します。

2. Evaluation Criteria and Selection Process

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

2.1. Acceptance of the Fourth-Round Candidates

2.1.第4ラウンドの候補の受理

NIST selected four candidate algorithms for the fourth round, all of which were KEMs. Classic McEliece was a third-round finalist, and the other three algorithms were alternates [13]. The set of finalists included the algorithms that NIST considered to be the most promising to fit the majority of use cases and be ready for standardization soon after the third round. The alternate candidates were regarded as potential candidates for future standardization, most likely after another round of evaluation.

NISTは第4ラウンドのために4つの候補アルゴリズムを選びました。そのすべてがKEMでした。Classic McElieceは第3ラウンドのファイナリストであり、他の3つのアルゴリズムは代替候補でした[13]。ファイナリストには、大多数のユースケースに適合し、第3ラウンド後すぐに標準化の準備が整う可能性が最も高いとNISTが考えたアルゴリズムが含まれていました。代替候補は、将来の標準化の候補となりうるものと見なされており、その場合はもう1回の評価ラウンドを経た後になる可能性が最も高いとされていました。

The submission teams were allowed to make minor modifications and resubmit their packages, which had to meet the same requirements as the original submissions. The complete updated specifications were posted on NIST’s PQC website [15] for public review on October 27, 2022. Most of the changes focused on fixing minor issues that were identified during the third round and clarifying or simplifying the submission specification. One modification of note that occurred during the fourth round is BIKE’s decoder. The thresholds for the decoder were altered to reduce the risk of decryption failure. No major redesigns or changes were allowed.

提出チームには、軽微な変更を加えて提出パッケージを再提出することが認められましたが、元の提出と同じ要件を満たす必要がありました。更新された仕様の全体は、2022年10月27日に、一般によるレビューのためにNISTのPQCウェブサイト[15]に掲載されました。変更の大半は、第3ラウンドで特定された軽微な問題の修正と、提出仕様の明確化または簡素化に重点を置いたものでした。第4ラウンドで行われた注目すべき変更の一つが、BIKEのデコーダです。復号失敗のリスクを減らすため、デコーダのしきい値が変更されました。大規模な再設計や変更は認められませんでした。

Table 2. Fourth-round KEM candidates organized by category, with the candidate selected for standardization bolded and in blue

表2.カテゴリ別に整理した第4ラウンドのKEM候補(標準化のために選定された候補は太字の青で表示)

Code-BasedIsogeny-Based
BIKESIKE
HQC
Classic McEliece
符号ベースアイソジェニーベース
BIKESIKE
HQC
Classic McEliece

2.2. Evaluation Criteria

2.2.評価基準

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

NISTの公募要領(Call for Proposals)[16]は、NIST PQC標準化プロセスを通じて候補アルゴリズムを比較するために用いる評価基準について、3つの大きな側面、すなわち1)セキュリティ、2)コストと性能、3)アルゴリズムと実装の特性を示しました。これらの基準を以下に説明し、それらが第4ラウンドの候補の評価にどのように影響したかを論じます。

2.2.1. Security

2.2.1.セキュリティ

As with the previous phases of the PQC Standardization Process, security was the most important factor that NIST considered when evaluating the fourth-round candidate schemes. In the third round of the PQC Standardization Process, NIST selected one KEM — Kyber — that was then standardized as ML-KEM in FIPS 203 [14]. The security of ML-KEM is based primarily on the presumed hardness of certain computational problems in lattices. As discussed in the third-round report, NIST values having a variety of computational hardness assumptions and aims to reduce the risk that a single cryptanalytic breakthrough will leave no viable standard for key establishment. In pursuit of that goal, NIST selected fourth-round candidates whose security was based on computational assumptions that differ significantly from that of ML-KEM. Specifically, the candidates consisted of the isogeny-based KEM SIKE and the code-based KEMs BIKE, HQC, and Classic McEliece. See Table 2.

PQC標準化プロセスのこれまでの段階と同様に、セキュリティは、NISTが第4ラウンドの候補方式を評価する際に考慮した最も重要な要素でした。PQC標準化プロセスの第3ラウンドで、NISTはKEMとしてKyberを1つ選定し、これはFIPS 203 [14]でML-KEMとして標準化されました。ML-KEMの安全性は、主に格子上の特定の計算問題が困難であるという想定に基づいています。第3ラウンドの報告書で論じたとおり、NISTは多様な計算困難性の仮定を持つことを重視しており、単一の暗号解読上の突破によって、実行可能な鍵確立の標準が残らなくなるリスクを減らすことを目指しています。その目標を追求するため、NISTは、ML-KEMとは大きく異なる計算上の仮定に安全性が基づく候補を、第4ラウンドの候補として選びました。具体的には、候補はアイソジェニーベースのKEMであるSIKEと、符号ベースのKEMであるBIKE、HQC、Classic McElieceで構成されていました。表2を参照してください。

NIST’s key-establishment standards are currently utilized in a wide variety of applications. The specific properties required for a key-establishment scheme to provide security in a given application can vary. However, in terms of formal security definitions, a single notion suffices for key-establishment schemes that are intended for general use: semantic security with respect to adaptive chosen ciphertext attacks (equivalently, IND-CCA2 security). ML-KEM is believed to satisfy IND-CCA2 security and is expected to serve as a general-purpose scheme in any application that calls for NIST-approved post-quantum key-establishment.

NISTの鍵確立標準は、現在、幅広い用途で利用されています。特定の用途でセキュリティを提供するために鍵確立方式に求められる固有の特性は、さまざまでありえます。しかし、形式的なセキュリティ定義の観点では、汎用を意図した鍵確立方式には単一の概念で足ります。それは、適応的選択暗号文攻撃に対する意味論的安全性(同等に、IND-CCA2安全性)です。ML-KEMはIND-CCA2安全性を満たすと考えられており、NISTが承認する耐量子の鍵確立を必要とするあらゆる用途で、汎用の方式として機能することが期待されています。

The formal security statuses of the fourth-round KEM candidates vary significantly. SIKE, the sole isogeny-based candidate, was broken and thus does not satisfy IND-CCA2 security [17]. The code-based candidates BIKE, HQC, and Classic McEliece are believed to satisfy IND-CCA2 security. However, NIST’s level of confidence in the IND-CCA2 security of these schemes is not equal. Notably, NIST has a higher level of confidence in the IND-CCA2 security of HQC than BIKE (see Sec. 3 for further details).

第4ラウンドのKEM候補の形式的なセキュリティ上の状況は、大きく異なります。アイソジェニーベースの唯一の候補であるSIKEは破られたため、IND-CCA2安全性を満たしません[17]。符号ベースの候補であるBIKE、HQC、Classic McElieceは、IND-CCA2安全性を満たすと考えられています。しかし、これらの方式のIND-CCA2安全性に対するNISTの確信の度合いは同じではありません。特に、NISTはBIKEよりもHQCのIND-CCA2安全性に高い確信を持っています(詳細は第3節を参照)。

Submitters to the fourth round were encouraged but not required to provide proofs of IND-CCA2 security (from clearly stated computational assumptions) in relevant models. NIST defined five security categories to compare the security strengths provided by the submissions. Submitters were asked to provide a classification of the security of the parameter sets of their schemes following the definitions provided in [16].

第4ラウンドの提出者は、関連するモデルにおけるIND-CCA2安全性の証明(明確に述べられた計算上の仮定からのもの)を提供することを奨励されましたが、必須ではありませんでした。NISTは、提出物が提供するセキュリティ強度を比較するため、5つのセキュリティカテゴリを定義しました。提出者は、[16]に示された定義に従って、自らの方式のパラメータセットのセキュリティの分類を提供するよう求められました。

NIST also listed other desirable security properties, such as resistance to side-channel and multi-key attacks and resistance to misuse. Submissions were encouraged to note any additional desirable security properties that they provided. Finally, NIST required submission packages to summarize known cryptanalytic attacks on the scheme and complexity estimates for those attacks.

NISTは、サイドチャネル攻撃やマルチキー攻撃への耐性、誤用への耐性など、そのほかの望ましいセキュリティ特性も挙げました。提出物は、提供する追加の望ましいセキュリティ特性があれば、それを記載することが奨励されました。最後にNISTは、提出パッケージに、方式に対する既知の暗号解読攻撃と、それらの攻撃の計算量の見積りを要約することを求めました。

2.2.2. Cost and Performance

2.2.2.コストと性能

The second-most important criterion when evaluating candidate algorithms was their performance characteristics:

候補アルゴリズムを評価する際に2番目に重要な基準は、その性能特性でした。

•Sizes of encapsulation keys and ciphertexts

•カプセル化鍵と暗号文のサイズ

•Computational efficiencies of encapsulations, decapsulations, and key generations (i.e., the speeds of the algorithms)

•カプセル化、デカプセル化、鍵生成の計算効率(すなわち、アルゴリズムの速度)

Tables 3 through 5 show representative benchmarks for key generations, encapsulations, and decapsulations of BIKE, HQC, and Classic McEliece, respectively. Each row is a specific parameter set from the corresponding submission. The “Level” columns indicate the security categories that the submission parameter sets claim to meet. BIKE and HQC each had one parameter set per security category, while Classic McEliece had two. The Classic McEliece f versions have faster key generation, while the non-f versions have simpler key generation.

表3から表5に、BIKE、HQC、Classic McElieceそれぞれの鍵生成、カプセル化、デカプセル化の代表的なベンチマークを示します。各行は、対応する提出物の特定のパラメータセットです。「Level」の列は、提出物のパラメータセットが満たすと主張しているセキュリティカテゴリを示します。BIKEとHQCはセキュリティカテゴリごとに1つのパラメータセットがあり、Classic McElieceには2つあります。Classic McElieceのfバージョンは鍵生成が高速であり、fでないバージョンは鍵生成がより単純です。

In these benchmarks, BIKE is 6-10 times slower than HQC in key generation, 5-7 times slower than HQC in decapsulation, and about twice as fast as HQC in encapsulation. Key generation in Classic McEliece is an outlier, being three orders of magnitude more costly than HQC.

これらのベンチマークでは、BIKEは鍵生成でHQCの6から10倍遅く、デカプセル化でHQCの5から7倍遅く、カプセル化ではHQCの約2倍速くなっています。Classic McElieceの鍵生成は外れ値であり、HQCよりも3桁多くのコストがかかります。

Parameter SetLevelkeygenencapsdecaps
BIKE Level 1I6371111428
BIKE Level 3III18922514313
BIKE Level 5V453550510382
パラメータセットレベルkeygenencapsdecaps
BIKE Level 1I6371111428
BIKE Level 3III18922514313
BIKE Level 5V453550510382

Table 3. Performance of BIKE in thousands of cycles on x86_64 [1]

表3. x86_64におけるBIKEの性能(千サイクル単位)[1]

Parameter SetLevelkeygenencapsdecaps
hqc-128I105197360
hqc-192III244460746
hqc-256V4478441410
パラメータセットレベルkeygenencapsdecaps
hqc-128I105197360
hqc-192III244460746
hqc-256V4478441410

Table 4. Performance of HQC in thousands of cycles on x86_64 [1]

表4. x86_64におけるHQCの性能(千サイクル単位)[1]

Parameter SetLevelkeygenencapsdecaps
mceliece348864I13734549120
mceliece348864f11418945120
mceliece460896III43036491232
mceliece460896f31360092231
mceliece6688128V674012196273
mceliece6688128f493758176274
mceliece6960119V602164167252
mceliece6960119f404166169253
mceliece8192128V686110203269
mceliece8192128f453985206269
パラメータセットレベルkeygenencapsdecaps
mceliece348864I13734549120
mceliece348864f11418945120
mceliece460896III43036491232
mceliece460896f31360092231
mceliece6688128V674012196273
mceliece6688128f493758176274
mceliece6960119V602164167252
mceliece6960119f404166169253
mceliece8192128V686110203269
mceliece8192128f453985206269

Table 5. Performance of Classic McEliece in thousands of cycles on x86_64 [1]

表5. x86_64におけるClassic McElieceの性能(千サイクル単位)[1]

Tables 6 through 8 show the sizes of keys and ciphertexts for BIKE, HQC, and Classic McEliece. The encapsulation keys of HQC are about 41-47 % larger than those of BIKE. The ciphertexts of HQC are about three times larger than the ciphertexts of BIKE.

表6から表8に、BIKE、HQC、Classic McElieceの鍵と暗号文のサイズを示します。HQCのカプセル化鍵はBIKEのものより約41〜47 %大きくなっています。HQCの暗号文はBIKEの暗号文の約3倍の大きさです。

Parameter SetLevelEncapsulation KeyDecapsulation KeyCiphertext
BIKE Level 1I15412811573
BIKE Level 3III30834193115
BIKE Level 5V51225805154
パラメータセットレベルカプセル化鍵デカプセル化鍵暗号文
BIKE Level 1I15412811573
BIKE Level 3III30834193115
BIKE Level 5V51225805154

Table 6. BIKE keys and ciphertext sizes in bytes

表6. BIKEの鍵と暗号文のサイズ(バイト単位)

Parameter SetLevelEncapsulation KeyDecapsulation KeyCiphertext
hqc-128I2249404497
hqc-192III4522409042
hqc-256V72454014485
パラメータセットレベルカプセル化鍵デカプセル化鍵暗号文
hqc-128I2249404497
hqc-192III4522409042
hqc-256V72454014485

Table 7. HQC keys and ciphertext sizes in bytes

表7. HQCの鍵と暗号文のサイズ(バイト単位)

Parameter SetLevelEncapsulation KeyDecapsulation KeyCiphertext
mceliece348864
mceliece348864f
I261120649296
mceliece460896
mceliece460896f
III52416013608156
mceliece6688128
mceliece6688128f
V104499213932208
mceliece6960119
mceliece6960119f
V104731913948194
mceliece8192128
mceliece8192128f
V135782414120208
パラメータセットレベルカプセル化鍵デカプセル化鍵暗号文
mceliece348864
mceliece348864f
I261120649296
mceliece460896
mceliece460896f
III52416013608156
mceliece6688128
mceliece6688128f
V104499213932208
mceliece6960119
mceliece6960119f
V104731913948194
mceliece8192128
mceliece8192128f
V135782414120208

Table 8. Classic McEliece keys and ciphertext sizes in bytes

表8. Classic McElieceの鍵と暗号文のサイズ(バイト単位)

There are a few studies comparing the performances of the KEMs in various protocols [18–21]. The study on the performance of post-quantum XML encryption and SAML SSO [21] contains data that compare BIKE and Classic McEliece in those protocols. For hybrid XML encryption, Classic McEliece slightly outperforms BIKE in decryption time and total time but results in much larger data sizes. When used for SAML SSO, BIKE generally outperforms Classic McEliece in time and produces much smaller bandwidths. Experiments on the performance of post-quantum KEMs in TLS 1.3 and QUIC [18–20] produce data that compare BIKE and HQC. Generally, when network conditions (e.g., transmission rates and packet loss) are ignored or sufficiently good, HQC results in faster handshakes. In contrast, when network conditions are sufficiently bad, BIKE outperforms HQC. Packet delay seems to affect both HQC and BIKE equally.

さまざまなプロトコルにおけるKEMの性能を比較した研究がいくつかあります[18–21]。耐量子XML暗号化とSAML SSOの性能に関する研究[21]には、それらのプロトコルにおけるBIKEとClassic McElieceを比較したデータが含まれています。ハイブリッドXML暗号化では、Classic McElieceは復号時間と合計時間でBIKEをわずかに上回りますが、データサイズははるかに大きくなります。SAML SSOで使用する場合、BIKEは一般に所要時間でClassic McElieceを上回り、必要な帯域幅もはるかに小さくなります。TLS 1.3とQUICにおける耐量子KEMの性能に関する実験[18–20]は、BIKEとHQCを比較したデータを示しています。一般に、ネットワーク条件(例:伝送速度やパケット損失)を無視するか、十分に良好な場合、HQCのほうがハンドシェイクが速くなります。対照的に、ネットワーク条件が十分に悪い場合は、BIKEがHQCを上回ります。パケット遅延は、HQCとBIKEに同じように影響するようです。

These results align with a prior expectation about the performances of BIKE and HQC based on their differences in speeds and sizes. When the size differences between HQC and BIKE do not affect the protocol execution time, the protocol runs faster with HQC. When the differences affect the protocol execution time noticeably, BIKE is more attractive than HQC. For TLS, BIKE would likely be more attractive than HQC over the web. The cited studies do not provide data for Classic McEliece, which is likely not a desirable choice for TLS 1.3 and QUIC due to its generally large encapsulation keys.

これらの結果は、速度とサイズの違いに基づくBIKEとHQCの性能に関する事前の予想と一致しています。HQCとBIKEのサイズの違いがプロトコルの実行時間に影響しない場合は、HQCを使うほうがプロトコルの実行は速くなります。その違いが実行時間に顕著に影響する場合は、BIKEのほうがHQCより魅力的です。TLSでは、ウェブ通信においてBIKEのほうがHQCより魅力的である可能性が高いでしょう。引用した研究にはClassic McElieceのデータがありません。一般にカプセル化鍵が大きいため、Classic McElieceはTLS 1.3とQUICに適した選択肢ではない可能性が高いです。

2.2.3. Algorithm and Implementation Characteristics

2.2.3.アルゴリズムと実装の特性

The Call for Proposals [22] also requested various desirable algorithm and implementation characteristics for consideration, particularly flexibility, simplicity, and ease of adoption.

公募要領(Call for Proposals)[22]は、考慮すべき望ましいアルゴリズムと実装の特性として、特に柔軟性、単純さ、採用の容易さなど、さまざまなものも求めていました。

An important characteristic of candidates is their potential performance impact on existing widely used protocols (e.g., TLS, IPSec, and SSH) and certificates. The third round included real-world experiments to identify potential performance problems with the algorithms. These experiments continued into the fourth round with a greater focus on HQC and BIKE (see Sec. 2.2.2).

候補の重要な特性は、広く使われている既存のプロトコル(例: TLS、IPSec、SSH)や証明書に与えうる性能上の影響です。第3ラウンドでは、アルゴリズムの潜在的な性能上の問題を特定するため、実環境での実験が行われました。これらの実験は第4ラウンドでも続き、HQCとBIKEにより重点が置かれました(2.2.2項を参照)。

NIST believes it is important to select cryptographic standards that will be capable of protecting sensitive government information as well as being widely adopted for use in industry. In selecting a cryptographic algorithm for standardization, an evaluation factor is whether a patent might hinder the adoption of a cryptographic standard. All submission teams were required to submit statements regarding knowledge of patents involving their algorithms and implementations, which are available on the NIST PQC fourth round submissions website [23]. The submitters of HQC indicated two patents that could potentially be relevant to an implementation of HQC. However, the patent owner committed and agreed to grant to any interested party on a worldwide basis a non-exclusive license for the purpose of implementing the standard without compensation and under reasonable terms and conditions that are demonstrably free of any unfair discrimination.1

NISTは、政府の機微な情報を保護できるとともに、産業界でも広く採用される暗号標準を選定することが重要だと考えています。標準化のための暗号アルゴリズムを選定する際の評価要素の一つは、特許が暗号標準の採用を妨げるおそれがあるかどうかです。すべての提出チームは、自らのアルゴリズムと実装に関わる特許についての認識を示す声明の提出を求められており、これらはNIST PQC第4ラウンドの提出物のウェブサイト[23]で入手できます。HQCの提出者は、HQCの実装に関連する可能性がある2件の特許を示しました。しかし、特許権者は、関心のある当事者に対し、世界的な基準で、標準を実装する目的の非独占的なライセンスを、無償で、不当な差別がないことが実証できる合理的な条件の下で付与することを約束し、同意しました。1

2.3. Selection of the Candidates for Standardization

2.3.標準化する候補の選定

In relative order of importance, NIST considered the security, cost and performance, and algorithm and implementation characteristics of the candidates in selecting what to standardize. Early in the fourth round, published cryptanalytic results demonstrated that SIKE was insecure [17, 24, 25], resulting in its removal from consideration [9].

標準化するものを選定するにあたり、NISTは重要度の高い順に、候補のセキュリティ、コストと性能、アルゴリズムと実装の特性を考慮しました。第4ラウンドの初期に、公表された暗号解読の結果によりSIKEが安全でないことが示され[17, 24, 25]、検討対象から外されました[9]。

1 See the Statement by Patent Owner included with the HQC submission at https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/final-ip-statements/HQC-Statements-Round4.pdf
1 HQCの提出物に含まれる特許権者の声明(Statement by Patent Owner)を参照してください: https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/final-ip-statements/HQC-Statements-Round4.pdf

In IR 8413 [2], NIST requested feedback on specific use cases for which Classic McEliece would be a good solution. Responses noted that Classic McEliece may provide better performance than BIKE or HQC for applications in which a public key can be transferred once and then used for several encapsulations (e.g., file encryption and virtual private networks [VPNs]) due to its small ciphertext size and fast encapsulation and decapsulation. There was also some interest in Classic McEliece based on the perception that it is a conservative choice. However, the interest expressed in Classic McEliece was limited, and having more standards to implement adds complexity to protocols and PQC migration.

IR 8413 [2]でNISTは、Classic McElieceが優れた解決策となる特定のユースケースについて、フィードバックを求めました。回答では、公開鍵を一度転送すれば複数のカプセル化に使えるアプリケーション(例:ファイル暗号化や仮想プライベートネットワーク[VPN])では、暗号文が小さく、カプセル化とデカプセル化が高速であるため、Classic McElieceがBIKEやHQCより良好な性能を提供する場合があると指摘されました。また、Classic McElieceは保守的な選択であるという認識から、これに一定の関心もありました。しかし、Classic McElieceに示された関心は限られており、実装すべき標準が増えるとプロトコルやPQCへの移行が複雑になります。

Classic McEliece is currently under consideration for standardization by the International Organization for Standardization (ISO). Concurrent standardization of Classic McEliece by NIST and ISO risks the creation of incompatible standards. After the ISO standardization process has been completed, NIST may consider developing a standard for Classic McEliece based on the ISO standard. However, Classic McEliece is no longer under consideration for standardization as part of the current NIST PQC Standardization Process.

Classic McElieceは、現在、国際標準化機構(ISO)で標準化が検討されています。NISTとISOがClassic McElieceを同時に標準化すると、互換性のない標準が作られるリスクがあります。ISOの標準化プロセスが完了した後に、NISTはISO標準に基づくClassic McElieceの標準の策定を検討する可能性があります。しかし、Classic McElieceは、現在のNIST PQC標準化プロセスの一環としての標準化の検討対象ではなくなっています。

At the end of the third round, NIST indicated its intent to standardize at most one of BIKE or HQC for use as a general-purpose KEM [2]. As specified in the Call for Proposals [22], submitted KEMs were evaluated based on how well they appear to provide IND-CCA2 security, particularly for KEMs intended for general use. While NIST has confidence in the indistinguishability under chosen-plaintext attack (IND-CPA) security of BIKE and HQC, both schemes require a sufficiently low decryption failure rate (DFR) in order to be IND-CCA2-secure. There is evidence that HQC has a sufficiently low DFR and recent work indicates that with minor modifications, BIKE achieves the same [26]. However, NIST does not consider the DFR analysis for BIKE to be as mature as that for HQC. Additionally, HQC is not believed to require additional modifications to achieve the desired security properties. Given the critical need for strong IND-CCA2 security in a general-purpose KEM, HQC was selected for standardization.

第3ラウンドの終了時に、NISTは、汎用KEMとして使用するため、BIKEまたはHQCのうち最大で1つを標準化する意向を示しました[2]。公募要領(Call for Proposals)[22]に規定されたとおり、提出されたKEMは、特に汎用を意図したKEMについて、IND-CCA2安全性をどの程度提供できると見られるかに基づいて評価されました。NISTはBIKEとHQCの選択平文攻撃に対する識別不能性(IND-CPA)の安全性には確信を持っていますが、どちらの方式も、IND-CCA2安全であるためには十分に低い復号失敗率(DFR)が必要です。HQCのDFRが十分に低いという証拠があり、最近の研究は、軽微な修正を加えればBIKEも同じ水準を達成することを示しています[26]。しかし、NISTは、BIKEのDFR分析がHQCのものほど成熟しているとは考えていません。さらに、HQCは、必要なセキュリティ特性を達成するために追加の修正を必要としないと考えられています。汎用KEMには強力なIND-CCA2安全性が不可欠であることから、HQCが標準化のために選定されました。

In summary, NIST has only selected HQC for standardization. The algorithms that were not selected are not under consideration for standardization by NIST as part of the current NIST PQC Standardization Process.

要約すると、NISTは標準化のためにHQCのみを選定しました。選定されなかったアルゴリズムは、現在のNIST PQC標準化プロセスの一環としてのNISTによる標準化の検討対象ではありません。

3. Summary of the Fourth-Round Candidates

3.第4ラウンドの候補の概要

This section describes each of the fourth-round candidates, including their advantages and disadvantages and why a scheme was selected for standardization or not.

この節では、第4ラウンドの各候補について、その長所と短所、および方式が標準化のために選定された理由または選定されなかった理由を説明します。

Section 3 of IR 8413[2] introduces some computational and security concepts and history that might be referenced throughout the subsequent subsections. The provided information reduced redundancy, as some of the candidates’ security analyses have properties in common. The information was not intended to be an exhaustive security or literature review.

IR 8413 [2]の第3節では、以降の各項で参照される可能性のある、計算およびセキュリティに関する概念と経緯を紹介しています。候補の中にはセキュリティ分析に共通する性質を持つものがあるため、提供した情報によって重複を減らしました。この情報は、セキュリティや文献を網羅的に調査したものを意図していません。

3.1. HQC

3.1. HQC

HQC (Hamming Quasi-Cyclic) is a KEM based on quasi-cyclic codes, where no trapdoor is hidden in the code [27]. It was designed to leverage the structural advantages of quasi-cyclic codes while maintaining a more direct security reduction to the problem of decoding a random linear code. Unlike the other code-based candidates, the only coding-theory hardness assumptions required by HQC’s security proof are parameterizations of the decisional Quasi-Cyclic Syndrome Decoding (QCSD) assumption. BIKE additionally assumes the hardness of Quasi-Cyclic Codeword Finding (QCCF), and Classic McEliece requires assumptions concerning binary Goppa codes [27, 28].

HQC(Hamming Quasi-Cyclic)は、トラップドアが符号に隠されていない準巡回符号に基づくKEMです[27]。準巡回符号の構造上の利点を活かしつつ、ランダムな線形符号の復号問題へのより直接的なセキュリティ上の帰着を維持するよう設計されました。他の符号ベースの候補と異なり、HQCの安全性証明に必要な符号理論上の困難性の仮定は、判定型の準巡回シンドローム復号(QCSD)の仮定をパラメータ化したものだけです。BIKEはさらに準巡回符号語探索(QCCF)の困難性を仮定し、Classic McElieceは二元Goppa符号に関する仮定を必要とします[27, 28]。

Design. HQC is similar in structure to Learning with Errors (LWE)-based cryptosystems, like Regev [29], LPR (Lyubashevsky, Peikert, Regev) [30], and ML-KEM [14]. The IND-CPA-secure public-key encryption (PKE) can be described as follows.

設計。HQCは、Regev [29]、LPR(Lyubashevsky、Peikert、Regev)[30]、ML-KEM [14]のような、Learning with Errors(LWE)ベースの暗号システムと構造が似ています。IND-CPA安全な公開鍵暗号化(PKE)は、次のように記述できます。

Let \(\mathscr{R} = \mathbb{F}_2[x]/(x^n - 1)\) for \(n\) prime such that \(x^n - 1\) has only two irreducible factors modulo 2. The secret key is a randomly sampled pair \((x, y) \in \mathscr{R}^2\), and the public key is the pair \((h, s = x + h \cdot y)\), where \(h\) is randomly sampled from \(\mathscr{R}\). Because the secret key is generated independently of the underlying quasi-cyclic code, there is no hidden structure in the HQC public parity-check matrix. This enables the security reduction to be independent of the decoding algorithm used for decryption [27]. In addition to \(h\), the public key includes a public generator matrix \(G \in \mathbb{F}_2^{k \times n}\) for a concatenated Reed-Muller Reed-Solomon (RMRS) code. The structure of this code is assumed to be visible to all parties.

\(\mathscr{R} = \mathbb{F}_2[x]/(x^n - 1)\)とし、\(n\)は、\(x^n - 1\)が2を法として2つの既約因子のみを持つような素数とします。秘密鍵はランダムにサンプリングされた組\((x, y) \in \mathscr{R}^2\)であり、公開鍵は組\((h, s = x + h \cdot y)\)で、\(h\)は\(\mathscr{R}\)からランダムにサンプリングされます。秘密鍵は基礎となる準巡回符号とは独立に生成されるため、HQCの公開パリティ検査行列には隠された構造がありません。これにより、セキュリティの帰着は、復号に用いる復号アルゴリズムから独立したものになります[27]。公開鍵には\(h\)に加えて、連接Reed-Muller Reed-Solomon(RMRS)符号の公開生成行列\(G \in \mathbb{F}_2^{k \times n}\)が含まれます。この符号の構造は、すべての当事者に見えると仮定されます。

To encrypt a message \(m \in \mathbb{F}_2^k\), the sender randomly samples three polynomials \(e, r_1, r_2 \in \mathscr{R}\) of appropriate low weights and responds with the ciphertext

メッセージ\(m \in \mathbb{F}_2^k\)を暗号化するには、送信者は、適切な低重みの3つの多項式\(e, r_1, r_2 \in \mathscr{R}\)をランダムにサンプリングし、次の暗号文を返します。

\[ c = (u, v) := (r_1 + h \cdot r_2, mG + s \cdot r_2 + e). \tag{1} \]
\[ c = (u, v) := (r_1 + h \cdot r_2, mG + s \cdot r_2 + e). \tag{1} \]

To decrypt, the receiver uses the decoding algorithm for an RMRS code to decode \((v - u \cdot y)\).

復号するには、受信者はRMRS符号の復号アルゴリズムを用いて\((v - u \cdot y)\)を復号します。

Security. The IND-CPA security of HQC relies on the difficulty of the QCSD with parity problem. Applying the Fujisaki Okamoto (FO) transform [31] to the CPA-secure PKE achieves an IND-CCA2 KEM.

セキュリティ。HQCのIND-CPA安全性は、パリティ付きQCSD問題の困難性に依拠しています。CPA安全なPKEにFujisaki Okamoto(FO)変換[31]を適用すると、IND-CCA2安全なKEMが得られます。

The decoder used in HQC has a well-defined minimum distance \(d\) and, consequently, a determinable error-correction capability \(\delta = \lfloor \frac{d-1}{2} \rfloor\). The probability that an HQC ciphertext includes error \(e\) such that \(|e| > \delta\) is captured in a closed-form analysis and used to produce a heuristic2 upper bound on the DFR. A sufficiently low DFR is required for the IND-CCA2 security proof of the relevant \(FO^{\not\perp}\) transform [31] to be valid and to prevent key-recovery attacks in a key-pair-reuse setting [32].

HQCで用いられる復号器は、明確に定義された最小距離\(d\)を持ち、したがって決定可能な誤り訂正能力\(\delta = \lfloor \frac{d-1}{2} \rfloor\)を持ちます。HQCの暗号文に誤り\(e\)が含まれ、かつ\(|e| > \delta\)となる確率は、閉形式の分析で捉えられ、DFRのヒューリスティック2な上界を導くために用いられます。関連する\(FO^{\not\perp}\)変換[31]のIND-CCA2安全性証明が成り立つため、また鍵ペアを再利用する設定での鍵復元攻撃[32]を防ぐために、十分に低いDFRが必要です。

As with the other code-based schemes, the best known attacks are based on information set decoding.

他の符号ベースの方式と同様に、最もよく知られた攻撃は情報集合復号に基づいています。

Performance. The quasi-cyclic structure of HQC enables small public-key and ciphertext sizes, although they are noticeably larger than the structured lattice KEMs. HQC ciphertexts and public keys are roughly 2.9 and 1.5 times the size of BIKE ciphertexts and public keys, respectively (see Tables 6 and 7).

性能。HQCの準巡回構造により、公開鍵と暗号文のサイズは小さく抑えられますが、構造化格子ベースのKEMよりは明らかに大きくなります。HQCの暗号文と公開鍵は、それぞれBIKEの暗号文と公開鍵の約2.9倍と1.5倍の大きさです(表6と表7を参照)。

Although the bandwidth of HQC exceeds that of BIKE, HQC’s key generation and decapsulation are significantly faster than those of BIKE (see Tables 3 and 4). As a result, the performances of HQC and BIKE in applications are difficult to compare. Experiments on TLS 1.3 handshake performance under varying network conditions have revealed that HQC outperforms BIKE under ideal network conditions [33]. However, in the case of nonzero packet loss rates, BIKE outperforms HQC. In addition to the benchmarks included in the HQC submission for a hardware implementation, there have been several hardware implementation results published in the literature [34–36].

HQCの帯域幅はBIKEを上回りますが、HQCの鍵生成とデカプセル化はBIKEより大幅に高速です(表3と表4を参照)。その結果、アプリケーションにおけるHQCとBIKEの性能は比較が困難です。さまざまなネットワーク条件でのTLS 1.3ハンドシェイクの性能に関する実験では、理想的なネットワーク条件ではHQCがBIKEを上回ることが明らかになっています[33]。しかし、パケット損失率がゼロでない場合は、BIKEがHQCを上回ります。HQCの提出物に含まれるハードウェア実装向けのベンチマークに加え、ハードウェア実装の結果が文献でいくつか公表されています[34–36]。

Significant events since Round 3. To address security and performance, HQC added a salt to mitigate multi-ciphertext attacks and switched to using implicit rejection for their FO transform. Additionally, several changes to the implementation were made to avoid timing attacks.

第3ラウンド以降の重要な出来事。セキュリティと性能に対処するため、HQCはマルチ暗号文攻撃を緩和するソルトを追加し、FO変換に暗黙的拒否(implicit rejection)を用いる方式へ切り替えました。さらに、タイミング攻撃を避けるため、実装にいくつかの変更が加えられました。

Overall assessment. NIST determined that HQC would provide a good complement to ML-KEM, since it is based on a different underlying security problem and still retains reasonable performance characteristics for general applications. The only other fourth-round candidate that could potentially serve this purpose was BIKE, which relies on similar code-based assumptions to HQC. Compared to BIKE, HQC has larger public key and ciphertext sizes but cheaper key generation and decryption. NIST was unable to make a definitive assessment as to which performance profile is better but found it likely that either performance profile would be acceptable for most general applications.

全体的な評価。NISTは、HQCがML-KEMとは異なる基礎的なセキュリティ問題に基づいており、かつ一般的なアプリケーションに対して妥当な性能特性を維持していることから、ML-KEMをよく補完すると判断しました。この目的を果たせる可能性があった第4ラウンドの唯一の他の候補はBIKEであり、HQCと似た符号ベースの仮定に依拠しています。BIKEと比べると、HQCは公開鍵と暗号文のサイズが大きい一方で、鍵生成と復号のコストが低くなっています。NISTは、どちらの性能プロファイルが優れているかについて決定的な評価を下すことはできませんでしたが、どちらの性能プロファイルでも、大半の一般的なアプリケーションにとって許容できる可能性が高いと判断しました。

The decisive factor in favor of HQC relative to BIKE is HQC’s stable DFR analysis. A sufficiently low DFR is required to achieve IND-CCA2 security, and there have been persistent uncertainties regarding BIKE’s DFR. While DFR estimation techniques for BIKE have recently improved, previous inaccurate DFR estimates have resulted in BIKE being attacked as late as the fourth round, and BIKE would likely require post-selection tweaks to achieve IND-CCA2 security. In contrast, DFR estimates for all HQC parameter sets have remained stable throughout the NIST PQC Standardization Process. The IND-CCA2 security of HQC has not been successfully attacked since May 2020 when HQC discarded parameter sets targeting a higher DFR than \(2^{-\lambda}\) for \(\lambda\) bits of security. NIST is confident that HQC as submitted provides a low enough DFR to achieve IND-CCA2 security.

BIKEに対してHQCを支持する決定的な要因は、HQCのDFR分析が安定していることです。IND-CCA2安全性を達成するには十分に低いDFRが必要であり、BIKEのDFRについては不確かさが持続的にありました。BIKEのDFRの推定手法は最近改善されましたが、以前の不正確なDFR推定により、第4ラウンドのかなり遅い時期までBIKEは攻撃を受けており、IND-CCA2安全性を達成するには、選定後に調整が必要になる可能性が高いでしょう。対照的に、すべてのHQCパラメータセットのDFR推定は、NIST PQC標準化プロセスを通じて安定していました。HQCのIND-CCA2安全性は、2020年5月にHQCが、\(2^{-\lambda}\)より高いDFRを目標とする(\(\lambda\)ビットのセキュリティに対する)パラメータセットを破棄して以降、破られていません。NISTは、提出されたとおりのHQCが、IND-CCA2安全性を達成するのに十分に低いDFRを提供すると確信しています。

2 HQC’s DFR analysis makes the simplifying assumption that the coordinates of \(\mathbf{e}' = \mathbf{x} \cdot \mathbf{r}_2 - \mathbf{r}_1 \cdot \mathbf{y} + \mathbf{e}\) are independent variables. The HQC submission document [8] gives theoretical and experimental justifications for this assumption.
2 HQCのDFR分析は、\(\mathbf{e}' = \mathbf{x} \cdot \mathbf{r}_2 - \mathbf{r}_1 \cdot \mathbf{y} + \mathbf{e}\)の各座標が独立な変数であるという単純化した仮定を置いています。HQCの提出文書[8]は、この仮定について理論的および実験的な根拠を示しています。

3.2. BIKE

3.2. BIKE

BIKE (Bit-Flipping Key Encapsulation) is a KEM based on binary linear quasi-cyclic moderate density parity check (QC-MDPC) codes [37]. The BIKE cryptosystem was initially designed for ephemeral key use but now claims to also support static key use.

BIKE(Bit-Flipping Key Encapsulation)は、二元線形の準巡回中密度パリティ検査(QC-MDPC)符号に基づくKEMです[37]。BIKE暗号システムは当初、一時鍵の使用向けに設計されましたが、現在は静的鍵の使用もサポートすると主張しています。

Design. The binary linear QC-MDPC code \(C(n,k)\) used in BIKE is constructed as follows. The secret key is a parity check matrix \(H_{r \times 2r}\) for a quasi-cyclic moderate density parity check code composed of two circulant blocks, where \(r\) is prime and chosen so that \(x^{r-1}\) has only two irreducible factors modulo 2. Each row of \(H\) has Hamming weight \(w \approx \sqrt{n}\), where \(w \equiv 2 \bmod 4\). All matrix operations in BIKE can be viewed as polynomial operations due to the isomorphism between the ring of \(v \times v\) circulant matrices and the polynomial ring \(\mathbb{F}_2[x]/(x^v + 1)\) for any \(v \in \mathbb{N}\). The secret key may then be thought of as a \(1 \times 2\) module \((h_0, h_1)\). The public key \(H_{\mathrm{pub}} = (1, h_0^{-1} h_1)\) is the secret key in systematic form, which is computed by multiplying \(H\) by \(h_0^{-1}\).

設計。BIKEで用いられる二元線形QC-MDPC符号\(C(n,k)\)は、次のように構成されます。秘密鍵は、2つの巡回ブロックからなる準巡回中密度パリティ検査符号のパリティ検査行列\(H_{r \times 2r}\)です。ここで\(r\)は素数で、\(x^{r-1}\)が2を法として2つの既約因子のみを持つように選ばれます。\(H\)の各行は、Hamming重み\(w \approx \sqrt{n}\)を持ち、\(w \equiv 2 \bmod 4\)です。\(v \times v\)巡回行列の環と多項式環\(\mathbb{F}_2[x]/(x^v + 1)\)の間には(任意の\(v \in \mathbb{N}\)について)同型があるため、BIKEのすべての行列演算は多項式演算と見なせます。したがって、秘密鍵は\(1 \times 2\)加群\((h_0, h_1)\)と考えることができます。公開鍵\(H_{\mathrm{pub}} = (1, h_0^{-1} h_1)\)は、\(H\)に\(h_0^{-1}\)を掛けて計算される、systematic formで表した秘密鍵です。

The underlying BIKE PKE follows Niederreiter-style encryption. At a high level, a message is encoded as an error vector \(e\) of weight \(t\), and the corresponding ciphertext is computed as \(H_{\mathrm{pub}} e^T\). Decryption is accomplished by multiplying the ciphertext by \(h_0\) to produce the syndrome \(He^T\) and then using the recommended Black-Grey-Flip bit-flipping decoder [38] to recover \(e\).

BIKEの基礎となるPKEは、Niederreiter型の暗号化に従います。大まかには、メッセージは誤りベクトル\(e\)(重み\(t\))として符号化され、対応する暗号文は\(H_{\mathrm{pub}} e^T\)として計算されます。復号は、暗号文に\(h_0\)を掛けて、シンドローム\(He^T\)を求め、その後、推奨されるBlack-Grey-Flipビット反転復号器[38]を用いて\(e\)を復元することで行われます。

Security. The proof of IND-CPA security of the underlying PKE in the random oracle model (ROM) depends on the difficulty of solving the decisional QCSD and QCCF problems. The FO transform, as described in [31], is applied to the CPA-secure PKE to achieve a claimed IND-CCA2 KEM. The PKE must be \(\delta\)-correct3 for \(\delta \le 2^{-\lambda}\) to apply this transformation.

セキュリティ。乱数オラクルモデル(ROM)における基礎となるPKEのIND-CPA安全性の証明は、判定型のQCSD問題とQCCF問題を解く困難性に依拠しています。[31]に記述されたFO変換をCPA安全なPKEに適用することで、IND-CCA2のKEMを達成すると主張しています。この変換を適用するには、PKEが\(\delta\)-correct3であり、\(\delta \le 2^{-\lambda}\)を満たさなければなりません。

Iterative bit-flipping decoders for QC-MDPC codes are difficult to analyze in closed form, and the anticipated DFR is too low to compute directly. Moreover, the DFR of MDPC and LDPC codes under iterative decoding follows two regimes: a waterfall region in which decoding failures decrease rapidly followed by an error floor region in which decoding failures decrease at a much slower pace as the signal-to-noise ratio increases. Understanding the DFR of BIKE has remained an open problem during the fourth round. Analyzing the BIKE DFR has involved studying the impacts of weak keys and near codewords on decoding performance.

QC-MDPC符号に対する反復ビット反転復号器は、閉形式での分析が難しく、想定されるDFRは直接計算するには低すぎます。さらに、反復復号におけるMDPC符号とLDPC符号のDFRは2つの領域に従います。復号失敗が急速に減少するウォーターフォール領域と、その後に続く、信号対雑音比が増加しても復号失敗の減少がはるかに緩やかなエラーフロア領域です。BIKEのDFRを理解することは、第4ラウンドの間、未解決の問題のままでした。BIKEのDFRの分析には、弱い鍵と近似符号語が復号性能に与える影響の研究が含まれていました。

3 A KEM is \(\delta\)-correct if the decapsulation fails (i.e., disagrees with encapsulation) with probability at most \(\delta\) on average over all keys and messages. Similarly, a decoder will be \(\delta\)-correct if its failure rate is at most \(\delta\) on average when the input is drawn uniformly.
3 KEMが\(\delta\)-correctであるとは、すべての鍵とメッセージにわたる平均で、デカプセル化が失敗する(すなわちカプセル化と一致しない)確率が高々 \(\delta\)であることをいいます。同様に、復号器が\(\delta\)-correctであるのは、入力が一様に抽出されたときの平均の失敗率が高々 \(\delta\)である場合です。

The first classification of weak keys for QC-MDPC codes was given in [39] and generalized in [40, 41]. Since these classes of weak keys have small cardinality, they were determined to have minimal impact on the overall BIKE DFR. A new class of weak keys was discovered [42] based on the gathering property. These weak keys were shown to cause an average DFR of a least \(2^{-117}\) for BIKE level 1 parameters, defeating the IND-CCA2 security of BIKE.

QC-MDPC符号の弱い鍵の最初の分類は[39]で示され、[40, 41]で一般化されました。これらの弱い鍵のクラスは要素数が小さいため、BIKE全体のDFRへの影響は最小限であると判断されました。収集特性(gathering property)に基づく弱い鍵の新たなクラスが発見されました[42]。これらの弱い鍵は、BIKEレベル1のパラメータで平均\(2^{-117}\)以上のDFRを引き起こし、BIKEのIND-CCA2安全性を損なうことが示されました。

The BIKE team studied the weak keys with the gathering property and found that the decoding failures were largely caused by incorrect flips happening early in the decoding process. Namely, bits not in error were incorrectly flipped during the first iterations of the decoder. To mitigate the effect of the gathering keys, the BIKE team introduced a new decoder known as BIKE-flip that sets a high bit-flipping threshold at the first decoding iteration and then gradually lowers the threshold throughout decoding [6]. Results indicated that the BIKE-flip decoder significantly reduced the impact of gathering keys, although this analysis was limited to classes of weak keys with a high enough DFR to be directly measured. Subsequently, a model introduced by [26] was able to predict variations in DFR based on the structure of a key. This would allow a modification of the BIKE key-generation algorithm in which keys that are not expected to have a typical value for the DFR are rejected.

BIKEチームは、収集特性を持つ弱い鍵を調べ、復号失敗の大半が、復号プロセスの初期に起こる誤った反転によって引き起こされることを見いだしました。すなわち、誤りのないビットが、復号器の最初の反復で誤って反転されていたのです。収集特性を持つ鍵の影響を緩和するため、BIKEチームはBIKE-flipとして知られる新しい復号器を導入しました。これは最初の復号反復でビット反転のしきい値を高く設定し、復号の過程でしきい値を徐々に下げていくものです[6]。結果は、BIKE-flip復号器が収集特性を持つ鍵の影響を大幅に減らすことを示しましたが、この分析は、直接測定できるほどDFRが高い弱い鍵のクラスに限られていました。その後、[26]で導入されたモデルにより、鍵の構造に基づくDFRの変動を予測できるようになりました。これにより、DFRが典型的な値になると見込まれない鍵を棄却するように、BIKEの鍵生成アルゴリズムを修正することが可能になります。

Near codewords are error vectors of low weight (\(u\)) that map to syndromes of low weight (\(v\)) and are well-studied in the LDPC literature as impediments to the iterative decoding process. Moreover, these vectors are known to significantly contribute to error floor behavior. A particular class of near codewords, where \(u = v = \frac{w}{2}\), was defined in [41] and shown to exist for BIKE. The impact of these near codewords on the decoding performance for BIKE was initially analyzed in [41] and further studied in [26]. In [26], a Markov model that tracked proximity to near codewords was used to predict the error floors for QC-MDPC codes under a generic iterative decoder. Results indicated that the error floor behavior in the BIKE DFR curves was dominated by convergence to these near codewords during failed decoding instances [26]. Furthermore, the model predicted that increasing BIKE security level 1 block lengths from \(r = 12323\) to \(r = 13477\) would result in a conservative DFR estimate of \(2^{-129.5}\) for typical keys.

近似符号語は、低重み(\(u\))の誤りベクトルであり、低重み(\(v\))のシンドロームに写像されます。これらは反復復号プロセスの妨げとしてLDPCの文献でよく研究されています。さらに、これらのベクトルはエラーフロアの挙動に大きく寄与することが知られています。\(u = v = \frac{w}{2}\)である近似符号語の特定のクラスが[41]で定義され、BIKEに存在することが示されました。これらの近似符号語がBIKEの復号性能に与える影響は、最初に[41]で分析され、[26]でさらに研究されました。[26]では、近似符号語への近接度を追跡するマルコフモデルを用いて、汎用の反復復号器におけるQC-MDPC符号のエラーフロアを予測しました。結果は、BIKEのDFR曲線におけるエラーフロアの挙動が、復号失敗の事例における、これらの近似符号語への収束に支配されていることを示しました[26]。さらにモデルは、BIKEのセキュリティレベル1のブロック長を\(r = 12323\)から\(r = 13477\)に増やすと、典型的な鍵について\(2^{-129.5}\)という保守的なDFR推定値になると予測しました。

Performance. The sizes of BIKE’s public keys and ciphertexts were roughly 70% and 30% of HQC’s, respectively. However, BIKE’s decapsulation and key-generation algorithms were roughly 5-6 times slower than HQC’s, respectively. The performance of BIKE and HQC in applications was difficult to compare. Experiments on TLS 1.3 handshake performance under varying network conditions have revealed that HQC outperforms BIKE under ideal network conditions [33]. However, BIKE outperforms HQC when non-zero packet loss rates are introduced.

性能。BIKEの公開鍵と暗号文のサイズは、それぞれHQCのおよそ70 %と30 %でした。しかし、BIKEのデカプセル化と鍵生成のアルゴリズムは、それぞれHQCのおよそ5倍と6倍遅いものでした。アプリケーションにおけるBIKEとHQCの性能は比較が困難でした。さまざまなネットワーク条件でのTLS 1.3ハンドシェイクの性能に関する実験では、理想的なネットワーク条件ではHQCがBIKEを上回ることが明らかになっています[33]。しかし、パケット損失率がゼロでない場合は、BIKEがHQCを上回ります。

Significant events since Round 3. The BIKE specification was updated at the beginning of the fourth round and included a change from the previous approach of sampling fixed-weight vectors to a data-oblivious technique. This modification had no noticeable performance impacts but eliminated certain side-channel attacks. To offer more resistance against multi-target key attacks, BIKE’s FO transform to attain IND-CCA2 security now includes a hash of part of the public key. As noted in the Security section above, a new decoder (BIKE-Flips) was used, which has better resilience to decryption failure for weak keys.

第3ラウンド以降の重要な出来事。BIKEの仕様は第4ラウンドの開始時に更新され、固定重みベクトルをサンプリングするこれまでの方法から、データ非依存の手法への変更が含まれました。この変更に目立った性能上の影響はありませんでしたが、特定のサイドチャネル攻撃を排除しました。マルチターゲット鍵攻撃へのさらなる耐性を提供するため、IND-CCA2安全性を達成するためのBIKEのFO変換には、公開鍵の一部のハッシュが含まれるようになりました。上記のSecurityの項で述べたとおり、新しい復号器(BIKE-Flips)が用いられ、弱い鍵に対する復号失敗への耐性が向上しています。

Overall assessment. NIST found that BIKE is a KEM that would complement ML-KEM well with respect to having a different underlying security problem and balanced performance characteristics. BIKE also offers smaller keys and ciphertexts than HQC. NIST reviewed several DFR analyses of BIKE, including recent results indicating that an approximate 9% increase in block size leads to a sufficiently low DFR for security level 1 parameters. Despite these promising results, NIST found the security analysis of HQC to be more mature and stable than that of BIKE. As such, NIST has not selected BIKE for standardization.

全体的な評価。NISTは、BIKEが、異なる基礎的なセキュリティ問題を持ち、バランスの取れた性能特性を備えている点で、ML-KEMをよく補完するKEMであると判断しました。BIKEは、HQCより小さい鍵と暗号文も提供します。NISTはBIKEのいくつかのDFR分析をレビューしました。これには、ブロックサイズを約9 %増やすと、セキュリティレベル1のパラメータで十分に低いDFRになることを示す最近の結果も含まれます。こうした有望な結果にもかかわらず、NISTは、HQCのセキュリティ分析のほうがBIKEのものより成熟し安定していると判断しました。そのため、NISTはBIKEを標準化のために選定していません。

3.3. Classic McEliece

3.3. Classic McEliece

Design. Classic McEliece is a code-based KEM that uses binary Goppa codes in the Niederreiter variant of the McEliece cryptosystem combined with standard techniques to achieve IND-CCA2 security. Due to the use of Goppa codes, the KEM has perfect correctness.4 It is a merger of the second-round submissions Classic McEliece and NTS-KEM. The original McEliece cryptosystem was published in [43] and was also based on binary Goppa codes.

設計。Classic McElieceは符号ベースのKEMであり、McEliece暗号システムのNiederreiter型で二元Goppa符号を用い、IND-CCA2安全性を達成するための標準的な手法と組み合わせています。Goppa符号を用いているため、このKEMは完全な正しさ(perfect correctness)を持ちます。4これは、第2ラウンドの提出物であるClassic McElieceとNTS-KEMを統合したものです。元のMcEliece暗号システムは[43]で公表され、やはり二元Goppa符号に基づいていました。

Security. The Classic McEliece submission cites [44] and other results as giving a tight proof of the submitted KEM’s IND-CCA2 security in the quantum random oracle model based on the assumption that the 1978 McEliece scheme provides one-way under chosen-plaintext attacks (OW-CPA) security. Confidence in the security of the 1978 scheme was mostly established based on the scheme’s long history of surviving cryptanalysis with only minor changes in the complexity of the best-known attack. Alternatively, the security of the scheme could be established under the assumptions that row-reduced parity check matrices for the binary Goppa codes used by Classic McEliece are indistinguishable from row-reduced parity check matrices for random linear codes of the same dimensions and that the syndrome decoding problem is hard for random linear codes with those dimensions. The state of the art in cryptanalysis does not contradict these assumptions, although binary Goppa codes with very different dimensions from those used by the Classic McEliece submission have been shown to be distinguishable from random codes [45]. More recent work [46] has proposed a distinguisher that claims to asymptotically break the indistinguishability of Goppa codes with parameters that are similar to those used by Classic McEliece but that target a much higher security level.

セキュリティ。Classic McElieceの提出物は、1978年のMcEliece方式が選択平文攻撃下での一方向性(OW-CPA)の安全性を提供するという仮定に基づき、量子乱数オラクルモデルにおける提出されたKEMのIND-CCA2安全性について、[44]およびその他の結果が厳密な証明を与えているとしています。1978年の方式の安全性への確信は、主に、最もよく知られた攻撃の計算量にわずかな変化しか生じないまま、暗号解読に耐えてきたという方式の長い歴史に基づいて確立されました。あるいは、方式の安全性は、Classic McElieceが用いる二元Goppa符号の行簡約されたパリティ検査行列が、同じ次元のランダムな線形符号の行簡約されたパリティ検査行列と識別不能であること、およびシンドローム復号問題がそれらの次元のランダムな線形符号に対して困難であることという仮定の下で確立することもできます。暗号解読の最先端はこれらの仮定と矛盾しませんが、Classic McElieceの提出物が用いるものとは大きく異なる次元の二元Goppa符号は、ランダムな符号と識別可能であることが示されています[45]。より最近の研究[46]は、Classic McElieceが用いるものに近いパラメータを持ちながら、はるかに高いセキュリティレベルを対象とするGoppa符号について、その識別不能性を漸近的に破ると主張する識別器を提案しました。

4 A perfectly correct KEM or PKE is one for which every ciphertext generated using the encapsulation/encryption function may be correctly decrypted using the decapsulation/decryption function. In contrast, some KEMs and PKEs have a very small decryption failure rate.
4 完全に正しい(perfectly correct)KEMまたはPKEとは、カプセル化/暗号化関数で生成されたすべての暗号文を、デカプセル化/復号関数で正しく復号できるものをいいます。対照的に、KEMやPKEの中には、復号失敗率が非常に小さいものもあります。

A number of approaches to the cryptanalysis of Classic McEliece have been studied. The most effective known attacks and those used to set the parameters of Classic McEliece are information set decoding attacks, which are similar to the best-known attacks against BIKE and HQC. Unlike the other two schemes, information set decoding is only applicable to message recovery, not key recovery. These attacks ignore the structure of the binary code and seek to recover the error vector based on its low Hamming weight. These techniques originated with Prange’s algorithm in 1962 [47] and have undergone a series of improvements [48–56]. However, the net effect of these improvements has been fairly modest, and most of the change in concrete security is due to improvements that were discovered more than 30 years ago. Quantum versions of information set decoding (ISD) algorithms have also been studied [57]. These results represent a generic Grover-based speedup of classical ISD algorithms and indicate that ISD algorithms can be sped up nearly as much as brute force search problems. In a multi-ciphertext setting, a further improvement [58] can reduce the cost of decoding a single ciphertext by a factor equal to approximately the square root of the number of ciphertexts.

Classic McElieceの暗号解読には、いくつもの手法が研究されてきました。最も効果的な既知の攻撃であり、Classic McElieceのパラメータの設定に用いられたものは情報集合復号攻撃であり、BIKEやHQCに対する最もよく知られた攻撃と似ています。他の2つの方式と異なり、情報集合復号は、メッセージの復元にのみ適用でき、鍵の復元には適用できません。これらの攻撃は二元符号の構造を無視し、誤りベクトルの低いHamming重みに基づいてそれを復元しようとします。これらの手法は1962年のPrangeのアルゴリズム[47]に始まり、一連の改良を経てきました[48–56]。しかし、これらの改良の正味の効果はかなり小さく、具体的な安全性の変化の大半は、30年以上前に発見された改良によるものです。情報集合復号(ISD)アルゴリズムの量子版も研究されています[57]。これらの結果は、Groverアルゴリズムに基づく、古典的なISDアルゴリズムの一般的な高速化を示すものであり、ISDアルゴリズムは総当たり探索問題とほぼ同程度に高速化できることを示しています。マルチ暗号文の設定では、さらなる改良[58]により、1つの暗号文を復号するコストを、暗号文の数の平方根にほぼ等しい係数で減らすことができます。

Key-recovery attacks have also been studied, which attempt to find the private key by algebraic techniques or brute-force searches. Algebraic techniques have been used to break variants of McEliece based on other algebraic codes [59–63] or Goppa codes with additional structure imposed [64], but they appear to be significantly more costly than ISD for attacking the parameters submitted for Classic McEliece. Nonetheless, algebraic attacks that target the structure of Goppa codes and achieve either key recovery or a distinguisher from a random linear code have remained an active area of research [46, 65–69].

代数的手法や総当たり探索によって秘密鍵を見つけようとする鍵復元攻撃も研究されています。代数的手法は、他の代数的符号に基づくMcElieceの変種[59–63]や、追加の構造を課したGoppa符号[64]を破るために用いられてきましたが、Classic McElieceに提出されたパラメータを攻撃するには、ISDよりはるかにコストがかかるようです。それでも、Goppa符号の構造を標的にして、鍵復元を達成する攻撃、またはランダムな線形符号と識別する識別器を実現する攻撃は、活発な研究分野であり続けています[46, 65–69]。

Performance. Classic McEliece has a very large public-key size and fairly slow key generation, which will likely make it undesirable in many common settings. However, its profile could have some advantages in settings where a public key is reused many times and does not need to be retransmitted for each new communication [70]. In particular, Classic McEliece has the smallest ciphertext sizes of any of the NIST PQC candidates.

性能。Classic McElieceは公開鍵のサイズが非常に大きく、鍵生成もかなり遅いため、多くの一般的な環境では望ましくないと思われます。しかし、公開鍵を何度も再利用し、新しい通信のたびに再送する必要がない環境では、そのプロファイルに利点がある場合があります[70]。特にClassic McElieceは、NIST PQCの候補の中で暗号文のサイズが最も小さくなっています。

Significant events since Round 3. At the beginning of the fourth round, the submission team introduced a modification to the FO transform to incorporate implicit rejection without plaintext confirmation. This tweak aimed to reduce the potential for patent concerns and simplify the specification and software code.

第3ラウンド以降の重要な出来事。第4ラウンドの開始時に、提出チームは、平文確認なしの暗黙的拒否(implicit rejection)を取り入れるため、FO変換に変更を加えました。この調整は、特許に関する懸念の可能性を減らし、仕様とソフトウェアコードを簡素化することを目的としていました。

During the fourth round, there has been significant progress in cryptanalysis techniques that are applicable to key recovery and the related problem of distinguishing a Goppa code from a random linear code [46, 66–69]. While these techniques are still far from concretely affecting the security of the submitted parameter sets of Classic McEliece, they somewhat weaken the argument that the long-term security of Classic McEliece is guaranteed by its long history of cryptanalysis.

第4ラウンドの間に、鍵復元と、Goppa符号をランダムな線形符号と識別する関連問題に適用できる暗号解読手法で、大きな進展がありました[46, 66–69]。これらの手法は、Classic McElieceに提出されたパラメータセットの安全性に具体的な影響を与えるにはまだほど遠いものの、Classic McElieceの長期的な安全性は暗号解読の長い歴史によって保証されているという論拠をある程度弱めています。

Additionally, during the third round, Classic McEliece was proposed to be added to the ISO/International Electrotechnical Commission (IEC) standard ISO/IEC 18033-2. This concurrent standardization effort remains active and ongoing.

さらに、第3ラウンドの間に、Classic McElieceをISO/国際電気標準会議(IEC)標準ISO/IEC 18033-2に追加することが提案されました。この並行する標準化の取り組みは、現在も活発に続いています。

Overall assessment. NIST remains confident in the security of Classic McEliece,5 although recent progress in cryptanalysis somewhat undermines the case for treating it as an especially conservative choice. Its large public-key size makes Classic McEliece an unattractive choice for most common applications, but it offers an excellent performance profile for applications that are sensitive to ciphertext size, where public keys are rarely transmitted.

全体的な評価。NISTはClassic McElieceの安全性に引き続き確信を持っています。5ただし、最近の暗号解読の進展は、これを特に保守的な選択として扱う論拠をいくらか弱めています。公開鍵のサイズが大きいため、Classic McElieceはほとんどの一般的なアプリケーションにとって魅力のない選択ですが、公開鍵がめったに送信されない、暗号文のサイズに敏感なアプリケーションには、優れた性能プロファイルを提供します。

NIST does not find the case for standardizing Classic McEliece compelling, due to skepticism that it will see widespread use. In the event that Classic McEliece does become widely used through other standards, and that NIST remains confident in its security while also determining that there is sufficient need, NIST may develop a NIST standard based on the widely used version.

NISTは、Classic McElieceが広く使われるようになるかどうかに懐疑的であるため、これを標準化する論拠は説得力があるとは考えていません。Classic McElieceが他の標準を通じて広く使われるようになり、NISTがその安全性に引き続き確信を持ち、かつ十分な必要性があると判断した場合には、NISTは、広く使われているバージョンに基づくNIST標準を策定する可能性があります。

3.4. SIKE

3.4. SIKE

Cryptographic schemes that are based on the hardness of the discrete logarithm problem on elliptic curves are known to be quantum-insecure because of Shor’s algorithm. However, elliptic curves can be used in a different way to construct PKE and KEM protocols. An isogeny from one elliptic curve to another elliptic curve (over the same field) is a rational map that is also a group homomorphism. Given two isogenous curves \(E\) and \(E'\), efficiently constructing an isogeny from \(E\) to \(E'\) is generally unknown. The assumed hardness of finding an isogeny between two elliptic curves combined with the Diffie–Hellman model for key exchange enables the construction of a family of isogeny-based KEMs.

楕円曲線上の離散対数問題の困難性に基づく暗号方式は、Shorのアルゴリズムにより量子に対して安全でないことが知られています。しかし、楕円曲線は、PKEやKEMのプロトコルを構成するために別の方法でも利用できます。ある楕円曲線から別の楕円曲線への(同じ体上の)アイソジェニーは、群準同型でもある有理写像です。アイソジェニーで結ばれた2つの曲線\(E\)と\(E'\)が与えられたとき、\(E\)から\(E'\)へのアイソジェニーを効率的に構成する方法は、一般には知られていません。2つの楕円曲線の間のアイソジェニーを見つけることが困難であるという仮定と、鍵交換のDiffie–Hellmanモデルを組み合わせると、アイソジェニーベースのKEMの族を構成できます。

SIKE is a KEM based on isogenies of supersingular elliptic curves that follows and improves upon the construction known as Supersingular Isogeny Diffie–Hellman (SIDH) [72]. In SIKE, one party prepares a secret isogeny \(\phi\) from a publicly known elliptic curve \(E_0\) to a new curve \(E\) and computes the images of the generators of a known torsion subgroup (under \(\phi\)) as the public key. This public key is then used to carry out a Diffie–Hellman procedure. The security of SIKE depends crucially on the assumption that it is infeasible for an adversary to compute the secret isogeny \(\phi\) from public information.

SIKEは、超特異楕円曲線のアイソジェニーに基づくKEMであり、Supersingular Isogeny Diffie–Hellman(SIDH)[72]として知られる構成に従い、それを改良したものです。SIKEでは、一方の当事者が、秘密のアイソジェニー\(\phi\)を、公に知られた楕円曲線\(E_0\)から新しい曲線\(E\)への写像として用意し、既知のねじれ部分群の生成元の(\(\phi\)による)像を、公開鍵として計算します。この公開鍵を用いて、Diffie–Hellmanの手順が実行されます。SIKEの安全性は、敵対者が公開情報から秘密のアイソジェニー\(\phi\)を計算することが実行不可能であるという仮定に決定的に依存しています。

However, in mid-2022, researchers showed that the secret isogeny \(\phi\) can be efficiently recovered from the public key [17]. Attacks on SIKE were further improved and generalized by other researchers [25, 73], and the authors of SIKE have acknowledged the break [9]. Attempts to patch the vulnerabilities were ineffective or had weaknesses in some instances [74]. While these attacks were devastating for SIKE, they do not apply to many other isogeny-based cryptographic schemes. The attacks relied on the information provided by the image of a torsion subgroup in the SIKE public key, while other isogeny-based schemes do not utilize these auxiliary torsion points.

しかし2022年半ばに、研究者らは、公開鍵から秘密のアイソジェニー\(\phi\)を効率的に復元できることを示しました[17]。SIKEへの攻撃は他の研究者によってさらに改良・一般化され[25, 73]、SIKEの著者もSIKEが破られたことを認めています[9]。脆弱性にパッチを当てる試みは、効果がなかったか、場合によっては弱点がありました[74]。これらの攻撃はSIKEにとって壊滅的でしたが、他の多くのアイソジェニーベースの暗号方式には適用されません。攻撃は、SIKEの公開鍵に含まれるねじれ部分群の像によって与えられる情報に依存していましたが、他のアイソジェニーベースの方式は、こうした補助的なねじれ点を利用していません。

5 Independent estimates [56, 71] of the cost of information set decoding algorithms have long suggested that Classic McEliece’s parameter sets (i.e., mceliece460896 and mceliece460896f) that claim Category 3 security fall short of their security target. However, NIST remains confident that these parameter sets at least meet the criteria for Category 2 security.
5情報集合復号アルゴリズムのコストについての独立した推定[56, 71]は、カテゴリ3のセキュリティを主張するClassic McElieceのパラメータセット(すなわちmceliece460896とmceliece460896f)が、そのセキュリティ目標に届かないことを以前から示唆してきました。しかし、NISTは、これらのパラメータセットが少なくともカテゴリ2のセキュリティの基準を満たすと、引き続き確信しています。

SIKE is an insecure KEM, and it has been eliminated from the NIST PQC project.

SIKEは安全でないKEMであり、NIST PQCプロジェクトから除外されました。

4. Conclusion

4. 結論

This report summarizes the evaluation criteria for selecting the fourth-round candidate algorithms, their basic designs, and their advantages and disadvantages. NIST greatly appreciates the participation in the NIST PQC Standardization Process. The announcement of the standardization of HQC marks the end of the fourth round, and also marks an end to the standardization process which began with the NIST Call for Proposals in 2016 [22]. We note that not all NIST PQC standardization is concluded, as NIST is also currently evaluating additional digital signatures [75].

本報告書は、第4ラウンドの候補アルゴリズムを選定するための評価基準、その基本設計、および長所と短所を要約しました。NISTは、NIST PQC標準化プロセスへの参加に深く感謝します。HQCの標準化の発表は、第4ラウンドの終わりを示すとともに、2016年のNIST公募要領(Call for Proposals)[22]から始まった標準化プロセスの終わりも示しています。なお、NISTは現在、追加のデジタル署名も評価している[75]ため、NISTのPQC標準化がすべて完了したわけではありません。

NIST will create a draft standard based on HQC and post it for public comment. After the comments are adjudicated, NIST will publish a final version in approximately two years. The standardization of HQC will be the second PQC KEM after ML-KEM. NIST recently published draft SP 800-227, Recommendations for Key-Encapsulation Mechanisms [76], which describes the basic definitions, properties, and applications of KEMs. It also provides recommendations for implementing and using KEMs in a secure manner.

NISTはHQCに基づく標準のドラフトを作成し、パブリックコメントのために掲載します。コメントへの対応が終わった後、NISTは約2年後に最終版を公開します。HQCの標準化は、ML-KEMに続く、2つ目のPQCのKEMになります。NISTは最近、KEMの基本的な定義、特性、用途を記述するドラフトのSP 800-227, Recommendations for Key-Encapsulation Mechanisms [76]を公開しました。同ドラフトは、KEMを安全に実装し使用するための推奨事項も示しています。

NIST plans to host another NIST PQC Standardization Conference in September 2025, with more details to be provided.

NISTは、2025年9月に、もう一つのNIST PQC標準化会議を開催する予定であり、詳細は追って提供されます。

References

参考文献

[1] Open quantum safe (OQS) algorithm performance visualizations. Available at https://openquantumsafe.org/benchmarking.

[1] Open quantum safe (OQS) algorithm performance visualizations.入手先: https://openquantumsafe.org/benchmarking.

[2] Alagic G, Apon D, Cooper DA, Dang QH, Dang T, Kelsey JM, Lichtinger J, Liu YK, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D (2022) Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8413-upd1, Includes updates as of September 26, 2022. https://doi.org/10.6028/NIST.IR.8413-upd1

[2] Alagic G, Apon D, Cooper DA, Dang QH, Dang T, Kelsey JM, Lichtinger J, Liu YK, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D (2022) Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8413-upd1, 2022年9月26日時点の更新を含みます。https://doi.org/10.6028/NIST.IR.8413-upd1

[3] National Institute of Standards and Technology (2015) SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 202. https://doi.org/10.6028/NIST.FIPS.202

[3] National Institute of Standards and Technology (2015) SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 202. https://doi.org/10.6028/NIST.FIPS.202

[4] National Institute of Standards and Technology (2024) Module-Lattic-Based Digital Signature Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 204. https://doi.org/10.6028/NIST.FIPS.204

[4] National Institute of Standards and Technology (2024) Module-Lattic-Based Digital Signature Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 204. https://doi.org/10.6028/NIST.FIPS.204

[5] National Institute of Standards and Technology (2024) Stateless Hash-Based Digital Signature Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 205. https://doi.org/10.6028/NIST.FIPS.205

[5] National Institute of Standards and Technology (2024) Stateless Hash-Based Digital Signature Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 205. https://doi.org/10.6028/NIST.FIPS.205

[6] Aragon N, Barreto PSLM, Bettaieb S, Bidoux L, Blazy O, Deneuville JC, Gaborit P, Ghosh S, Gueron S, Güneysu T, Melchor CA, Misoczk R, Persichetti E, Richter-Brockmann J, Sendrier N, Tillich JP, Vasseur V, Zémor G (2022) BIKE: Bit Flipping Key Encapsulation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[6] Aragon N, Barreto PSLM, Bettaieb S, Bidoux L, Blazy O, Deneuville JC, Gaborit P, Ghosh S, Gueron S, Güneysu T, Melchor CA, Misoczk R, Persichetti E, Richter-Brockmann J, Sendrier N, Tillich JP, Vasseur V, Zémor G (2022) BIKE: Bit Flipping Key Encapsulation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[7] Bernstein DJ, Chou T, Cid C, Gilcher J, Lange T, Maram V, von Maurich I, Misoczki R, Niederhagen R, Persichetti E, Peters C, Sendrier N, Szefer J, Tjhai CJ, Tomlinson M, Wang W (2022) Classic McEliece algorithm specifications and supporting documentation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[7] Bernstein DJ, Chou T, Cid C, Gilcher J, Lange T, Maram V, von Maurich I, Misoczki R, Niederhagen R, Persichetti E, Peters C, Sendrier N, Szefer J, Tjhai CJ, Tomlinson M, Wang W (2022) Classic McEliece algorithm specifications and supporting documentation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[8] Melchor CA, Aragon N, Bettaieb S, Bidoux L, Blazy O, Deneuville JC, Gaborit P, Persichetti E, Zémor G, Bos J, Dion A, Lacan J, Robert JM, Veron P (2022) HQC algorithm specifications and supporting documentation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[8] Melchor CA, Aragon N, Bettaieb S, Bidoux L, Blazy O, Deneuville JC, Gaborit P, Persichetti E, Zémor G, Bos J, Dion A, Lacan J, Robert JM, Veron P (2022) HQC algorithm specifications and supporting documentation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[9] Jao D, Azarderakhsh R, Campagna M, Costello C, Feo LD, Hess B, Jalali A, Koziel B, LaMacchia B, Longa P, Naehrig M, Renes J, Soukharev V, Urbanik D, Pereira G, Karabina K, Hutchinson A (2022) Supersingular Isogeny Key Encapsulation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[9] Jao D, Azarderakhsh R, Campagna M, Costello C, Feo LD, Hess B, Jalali A, Koziel B, LaMacchia B, Longa P, Naehrig M, Renes J, Soukharev V, Urbanik D, Pereira G, Karabina K, Hutchinson A (2022) Supersingular Isogeny Key Encapsulation, 4th Round submission to the NIST’s post-quantum cryptography standardization process. https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions.

[10] Chen L, Jordan S, Liu YK, Moody D, Peralta R, Perlner R, Smith-Tone D (2016) Report on post-quantum cryptography (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105

[10] Chen L, Jordan S, Liu YK, Moody D, Peralta R, Perlner R, Smith-Tone D (2016) Report on post-quantum cryptography (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8105. https://doi.org/10.6028/NIST.IR.8105

[11] National Institute of Standards and Technology (2016) Announcing request for nominations for public-key post-quantum cryptographic algorithms. Federal Register 81(244):92787–92788. https://federalregister.gov/a/2016-30615.

[11] National Institute of Standards and Technology (2016) Announcing request for nominations for public-key post-quantum cryptographic algorithms. Federal Register 81(244):92787–92788. https://federalregister.gov/a/2016-30615.

[12] Alagic G, Alperin-Sheriff J, Apon D, Cooper D, Dang Q, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2019) Status report on the first round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8240. https://doi.org/10.6028/NIST.IR.8240

[12] Alagic G, Alperin-Sheriff J, Apon D, Cooper D, Dang Q, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2019) Status report on the first round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8240. https://doi.org/10.6028/NIST.IR.8240

[13] Alagic G, Alperin-Sheriff J, Apon D, Cooper D, Dang Q, Kelsey J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2020) Status report on the second round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8309. https://doi.org/10.6028/NIST.IR.8309

[13] Alagic G, Alperin-Sheriff J, Apon D, Cooper D, Dang Q, Kelsey J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Smith-Tone D (2020) Status report on the second round of the NIST post-quantum cryptography standardization process (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) 8309. https://doi.org/10.6028/NIST.IR.8309

[14] National Institute of Standards and Technology (2024) Module-Lattice-Based Key-Encapsulation Mechanism Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 203. https://doi.org/10.6028/NIST.FIPS.203

[14] National Institute of Standards and Technology (2024) Module-Lattice-Based Key-Encapsulation Mechanism Standard. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 203. https://doi.org/10.6028/NIST.FIPS.203

[15] National Institute of Standards and Technology (2016) NIST post-quantum cryptography standardization. Available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.

[15] National Institute of Standards and Technology (2016) NIST post-quantum cryptography standardization.入手先: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.

[16] National Institute of Standards and Technology (2022) Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/call-for-proposals-dig-sig-sept-2022.pdf.

[16] National Institute of Standards and Technology (2022) Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process.入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/call-for-proposals-dig-sig-sept-2022.pdf.

[17] Castryck W, Decru T (2023) An Efficient Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 423–447. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_15

[17] Castryck W, Decru T (2023) An Efficient Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 423–447. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_15

[18] Kempf M, Gauder N, Jaeger B, Zirngibl J, Carle G (2024) A Quantum of QUIC: Dissecting Cryptography with Post-Quantum Insights. IFIP Networking, pp 195–203. https://doi.org/10.23919/IFIPNetworking62109.2024.10619916

[18] Kempf M, Gauder N, Jaeger B, Zirngibl J, Carle G (2024) A Quantum of QUIC: Dissecting Cryptography with Post-Quantum Insights. IFIP Networking, pp 195–203. https://doi.org/10.23919/IFIPNetworking62109.2024.10619916

[19] Sosnowski M, Wiedner F, Hauser E, Steger L, Schoinianakis D, Gallenmüller S, Carle G (2023) The performance of post-quantum TLS 1.3. Companion of the 19th International Conference on emerging Networking EXperiments and Technologies, pp 19–27. https://doi.org/https://doi.org/10.1145/3624354.3630585

[19] Sosnowski M, Wiedner F, Hauser E, Steger L, Schoinianakis D, Gallenmüller S, Carle G (2023) The performance of post-quantum TLS 1.3. Companion of the 19th International Conference on emerging Networking EXperiments and Technologies, pp 19–27. https://doi.org/https://doi.org/10.1145/3624354.3630585

[20] Henrich J, Heinemann A, Wiesmaier A, Schmitt N (2023) Performance impact of PQC KEMs on TLS 1.3 under varying network characteristics. ISC 2023: 26th International Conference on Information Security, eds Athanasopoulos E, Mennink B (Springer, Cham, Switzerland, Groningen, The Netherlands), Lecture Notes in Computer Science, Vol. 14411, pp 267–287. https://doi.org/10.1007/978-3-031-49187-0_14

[20] Henrich J, Heinemann A, Wiesmaier A, Schmitt N (2023) Performance impact of PQC KEMs on TLS 1.3 under varying network characteristics. ISC 2023: 26th International Conference on Information Security, eds Athanasopoulos E, Mennink B (Springer, Cham, Switzerland, Groningen, The Netherlands), Lecture Notes in Computer Science, Vol. 14411, pp 267–287. https://doi.org/10.1007/978-3-031-49187-0_14

[21] Müller J, Oupický J (2024) Post-quantum XML and SAML single sign-on. Proceedings on Privacy Enhancing Technologies 2024(4):525–543. https://doi.org/10.56553/popets-2024-0128

[21] Müller J, Oupický J (2024) Post-quantum XML and SAML single sign-on. Proceedings on Privacy Enhancing Technologies 2024(4):525–543. https://doi.org/10.56553/popets-2024-0128

[22] National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

[22] National Institute of Standards and Technology (2016) Submission requirements and evaluation criteria for the post-quantum cryptography standardization process.入手先: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

[23] National Institute of Standards and Technology (2022) NIST post-quantum cryptography standardization round 4 submissions. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.

[23] National Institute of Standards and Technology (2022) NIST post-quantum cryptography standardization round 4 submissions.入手先: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.

[24] Maino L, Martindale C (2022) An attack on SIDH with arbitrary starting curve, Cryptology ePrint Archive preprint. Available at https://ia.cr/2022/1026.

[24] Maino L, Martindale C (2022) An attack on SIDH with arbitrary starting curve, Cryptology ePrint Archive preprint.入手先: https://ia.cr/2022/1026.

[25] Robert D (2023) Breaking SIDH in Polynomial Time. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 472–503. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_17

[25] Robert D (2023) Breaking SIDH in Polynomial Time. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 472–503. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_17

[26] Arpin S, Lau JB, Perlner R, Robinson A, Tillich JP, Vasseur V (2025) Error floor prediction with Markov models for QC-MDPC codes, Cryptology ePrint Archive, Paper 2025/153. Available at https://eprint.iacr.org/2025/153.

[26] Arpin S, Lau JB, Perlner R, Robinson A, Tillich JP, Vasseur V (2025) Error floor prediction with Markov models for QC-MDPC codes, Cryptology ePrint Archive, Paper 2025/153.入手先: https://eprint.iacr.org/2025/153.

[27] Aguilar-Melchor C, Blazy O, Deneuville JC, Gaborit P, Zémor G (2018) Efficient encryption from random quasi-cyclic codes. IEEE Transactions on Information Theory 64(5):3927–3943. https://doi.org/https://doi.org/10.1109/TIT.2018.2804444

[27] Aguilar-Melchor C, Blazy O, Deneuville JC, Gaborit P, Zémor G (2018) Efficient encryption from random quasi-cyclic codes. IEEE Transactions on Information Theory 64(5):3927–3943. https://doi.org/https://doi.org/10.1109/TIT.2018.2804444

[28] Aragon N, Gaborit P, Z’emor G (2020) HQC-RMRS, an instantiation of the HQC encryption framework with a more efficient auxiliary error-correcting code. ArXiv abs/2005.10741.

[28] Aragon N, Gaborit P, Z’emor G (2020) HQC-RMRS, an instantiation of the HQC encryption framework with a more efficient auxiliary error-correcting code. ArXiv abs/2005.10741.

[29] Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing STOC ’05 (Association for Computing Machinery, New York, NY, USA), p 84–93. https://doi.org/10.1145/1060590.1060603

[29] Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing STOC ’05 (Association for Computing Machinery, New York, NY, USA), p 84–93. https://doi.org/10.1145/1060590.1060603

[30] Lyubashevsky V, Peikert C, Regev O (2010) On ideal lattices and learning with errors over rings. Advances in Cryptology – EUROCRYPT 2010, ed Gilbert H (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 1–23. https://doi.org/https://doi.org/10.1007/978-3-642-13190-5_1

[30] Lyubashevsky V, Peikert C, Regev O (2010) On ideal lattices and learning with errors over rings. Advances in Cryptology – EUROCRYPT 2010, ed Gilbert H (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 1–23. https://doi.org/https://doi.org/10.1007/978-3-642-13190-5_1

[31] Hofheinz D, Hövelmanns K, Kiltz E (2017) A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography, eds Kalai Y, Reyzin L (Springer International Publishing, Cham), pp 341–371. https://doi.org/https://doi.org/10.1007/978-3-319-70500-2_12

[31] Hofheinz D, Hövelmanns K, Kiltz E (2017) A modular analysis of the Fujisaki-Okamoto transformation. Theory of Cryptography, eds Kalai Y, Reyzin L (Springer International Publishing, Cham), pp 341–371. https://doi.org/https://doi.org/10.1007/978-3-319-70500-2_12

[32] Guo Q, Johansson T (2020) A new decryption failure attack against HQC. Advances in Cryptology – ASIACRYPT 2020, eds Moriai S, Wang H (Springer International Publishing, Cham), pp 353–382. https://doi.org/https://doi.org/10.1007/978-3-030-64837-4_12

[32] Guo Q, Johansson T (2020) A new decryption failure attack against HQC. Advances in Cryptology – ASIACRYPT 2020, eds Moriai S, Wang H (Springer International Publishing, Cham), pp 353–382. https://doi.org/https://doi.org/10.1007/978-3-030-64837-4_12

[33] Henrich J, Heinemann A, Wiesmaier A, Schmitt N (2023) Performance Impact of PQC KEMs on TLS 1.3 Under Varying Network Characteristics. Information Security, eds Athanasopoulos E, Mennink B (Springer Nature Switzerland, Cham), pp 267–287. https://doi.org/https://doi.org/10.1007/978-3-031-49187-0_14

[33] Henrich J, Heinemann A, Wiesmaier A, Schmitt N (2023) Performance Impact of PQC KEMs on TLS 1.3 Under Varying Network Characteristics. Information Security, eds Athanasopoulos E, Mennink B (Springer Nature Switzerland, Cham), pp 267–287. https://doi.org/https://doi.org/10.1007/978-3-031-49187-0_14

[34] Deshpande S, Xu C, Nawan M, Nawaz K, Szefer J (2023) Fast and efficient hardware implementation of HQC. Selected Areas in Cryptography - SAC 2023 - 30th International Conference, Fredericton, Canada, August 14-18, 2023, Revised Selected Papers, eds Carlet C, Mandal K, Rijmen V (Springer), Lecture Notes in Computer Science, Vol. 14201, pp 297–321. https://doi.org/10.1007/978-3-031-53368-6\_15

[34] Deshpande S, Xu C, Nawan M, Nawaz K, Szefer J (2023) Fast and efficient hardware implementation of HQC. Selected Areas in Cryptography - SAC 2023 - 30th International Conference, Fredericton, Canada, August 14-18, 2023, Revised Selected Papers, eds Carlet C, Mandal K, Rijmen V (Springer), Lecture Notes in Computer Science, Vol. 14201, pp 297–321. https://doi.org/10.1007/978-3-031-53368-6\_15

[35] Li C, Song S, Tian J, Wang Z, Koç ÇK (2023) An efficient hardware design for fast implementation of HQC. 36th IEEE International System-on-Chip Conference, SOCC 2023, Santa Clara, CA, USA, September 5-8, 2023, eds Becker J, Marshall A, Harbaum T, Ganguly A, Siddiqui F, McLaughlin K (IEEE), pp 1–6. https://doi.org/10.1109/SOCC58585.2023.10257054

[35] Li C, Song S, Tian J, Wang Z, Koç ÇK (2023) An efficient hardware design for fast implementation of HQC. 36th IEEE International System-on-Chip Conference, SOCC 2023, Santa Clara, CA, USA, September 5-8, 2023, eds Becker J, Marshall A, Harbaum T, Ganguly A, Siddiqui F, McLaughlin K (IEEE), pp 1–6. https://doi.org/10.1109/SOCC58585.2023.10257054

[36] Antognazza F, Barenghi A, Pelosi G, Susella R (2024) A high efficiency hardware design for the post-quantum KEM HQC. IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2024, Tysons Corner, VA, USA, May 6-9, 2024 (IEEE), pp 431–441. https://doi.org/10.1109/HOST55342.2024.10545409

[36] Antognazza F, Barenghi A, Pelosi G, Susella R (2024) A high efficiency hardware design for the post-quantum KEM HQC. IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2024, Tysons Corner, VA, USA, May 6-9, 2024 (IEEE), pp 431–441. https://doi.org/10.1109/HOST55342.2024.10545409

[37] Misoczki R, Tillich JP, Sendrier N, Barreto PSLM (2013) MDPC-McEliece: New McEliece variants from moderate density parity-check codes. 2013 IEEE International Symposium on Information Theory, pp 2069–2073. https://doi.org/https://doi.org/10.1109/ISIT.2013.6620590

[37] Misoczki R, Tillich JP, Sendrier N, Barreto PSLM (2013) MDPC-McEliece: New McEliece variants from moderate density parity-check codes. 2013 IEEE International Symposium on Information Theory, pp 2069–2073. https://doi.org/https://doi.org/10.1109/ISIT.2013.6620590

[38] Drucker N, Gueron S, Kostic D (2020) QC-MDPC decoders with several shades of gray. Post-Quantum Cryptography, eds Ding J, Tillich JP (Springer International Publishing, Cham), pp 35–50. https://doi.org/https://doi.org/10.1007/978-3-030-44223-1_3

[38] Drucker N, Gueron S, Kostic D (2020) QC-MDPC decoders with several shades of gray. Post-Quantum Cryptography, eds Ding J, Tillich JP (Springer International Publishing, Cham), pp 35–50. https://doi.org/https://doi.org/10.1007/978-3-030-44223-1_3

[39] Drucker N, Gueron S, Kostic D (2020) On constant-time QC-MDPC decoders with negligible failure rate. Code-Based Cryptography, eds Baldi M, Persichetti E, Santini P (Springer International Publishing, Cham), pp 50–79. https://doi.org/https://doi.org/10.1007/978-3-030-54074-6_4

[39] Drucker N, Gueron S, Kostic D (2020) On constant-time QC-MDPC decoders with negligible failure rate. Code-Based Cryptography, eds Baldi M, Persichetti E, Santini P (Springer International Publishing, Cham), pp 50–79. https://doi.org/https://doi.org/10.1007/978-3-030-54074-6_4

[40] Aydin N, Yildiz B, Uludag S (2020) A class of weak keys for the QC-MDPC cryptosystem. Algebraic and Combinatorial Coding Theory 2020, pp 1–4. https://doi.org/10.1109/ACCT51235.2020.9383383

[40] Aydin N, Yildiz B, Uludag S (2020) A class of weak keys for the QC-MDPC cryptosystem. Algebraic and Combinatorial Coding Theory 2020, pp 1–4. https://doi.org/10.1109/ACCT51235.2020.9383383

[41] Vasseur V (2021) Post-quantum cryptography: a study of the decoding of QC-MDPC codes. Ph.D. thesis. Université de Paris, Paris, France.

[41] Vasseur V (2021) Post-quantum cryptography: a study of the decoding of QC-MDPC codes. Ph.D. thesis. Université de Paris, Paris, France.

[42] Wang T, Wang A, Wang X (2023) Exploring decryption failures of BIKE: New class of weak keys and key recovery attacks. Advances in Cryptology – CRYPTO 2023, eds Handschuh H, Lysyanskaya A (Springer Nature Switzerland, Cham), pp 70–100. https://doi.org/https://doi.org/10.1007/978-3-031-38548-3_3

[42] Wang T, Wang A, Wang X (2023) Exploring decryption failures of BIKE: New class of weak keys and key recovery attacks. Advances in Cryptology – CRYPTO 2023, eds Handschuh H, Lysyanskaya A (Springer Nature Switzerland, Cham), pp 70–100. https://doi.org/https://doi.org/10.1007/978-3-031-38548-3_3

[43] McEliece RJ (1978) A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report 44:114–116.

[43] McEliece RJ (1978) A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report 44:114–116.

[44] Bindel N, Hamburg M, Hövelmanns K, Hülsing A, Persichetti E (2019) Tighter proofs of CCA security in the quantum random oracle model. Theory of Cryptography, eds Hofheinz D, Rosen A (Springer International Publishing, Cham), pp 61–90. https://doi.org/https://doi.org/10.1007/978-3-030-36033-7_3

[44] Bindel N, Hamburg M, Hövelmanns K, Hülsing A, Persichetti E (2019) Tighter proofs of CCA security in the quantum random oracle model. Theory of Cryptography, eds Hofheinz D, Rosen A (Springer International Publishing, Cham), pp 61–90. https://doi.org/https://doi.org/10.1007/978-3-030-36033-7_3

[45] Faugère JC, Gauthier-Umanã V, Otmani A, Perret L, Tillich JP (2011) A distinguisher for high rate McEliece cryptosystems. 2011 IEEE Information Theory Workshop, pp 282–286. https://doi.org/https://doi.org/10.1109/ITW.2011.6089437

[45] Faugère JC, Gauthier-Umanã V, Otmani A, Perret L, Tillich JP (2011) A distinguisher for high rate McEliece cryptosystems. 2011 IEEE Information Theory Workshop, pp 282–286. https://doi.org/https://doi.org/10.1109/ITW.2011.6089437

[46] Randriambololona H (2024) The syzygy distinguisher. IACR Cryptol ePrint Arch :1193Available at https://eprint.iacr.org/2024/1193.

[46] Randriambololona H (2024) The syzygy distinguisher. IACR Cryptol ePrint Arch :1193 入手先 https://eprint.iacr.org/2024/1193.

[47] Prange E (1962) The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5):5–9. https://doi.org/https://doi.org/10.1109/TIT.1962.1057777

[47] Prange E (1962) The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory 8(5):5–9. https://doi.org/https://doi.org/10.1109/TIT.1962.1057777

[48] Stern J (1989) A method for finding codewords of small weight. Coding Theory and Applications, eds Cohen G, Wolfmann J (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 106–113. https://doi.org/https://doi.org/10.1007/BFb0019850

[48] Stern J (1989) A method for finding codewords of small weight. Coding Theory and Applications, eds Cohen G, Wolfmann J (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 106–113. https://doi.org/https://doi.org/10.1007/BFb0019850

[49] Dumer I (1991) On minimum distance decoding of linear codes. Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory, pp 50–52.

[49] Dumer I (1991) On minimum distance decoding of linear codes. Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory, pp 50–52.

[50] May A, Meurer A, Thomae E (2011) Decoding random linear codes in \(\tilde{O}(2^{0.054n})\). Advances in Cryptology – ASIACRYPT 2011, eds Lee DH, Wang X (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 107–124. https://doi.org/https://doi.org/10.1007/978-3-642-25385-0_6

[50] May A, Meurer A, Thomae E (2011) Decoding random linear codes in \(\tilde{O}(2^{0.054n})\). Advances in Cryptology – ASIACRYPT 2011, eds Lee DH, Wang X (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 107–124. https://doi.org/https://doi.org/10.1007/978-3-642-25385-0_6

[51] Bernstein DJ, Lange T, Peters C (2011) Smaller decoding exponents: Ball-collision decoding. Advances in Cryptology – CRYPTO 2011, ed Rogaway P (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 743–760. https://doi.org/https://doi.org/10.1007/978-3-642-22792-9_42

[51] Bernstein DJ, Lange T, Peters C (2011) Smaller decoding exponents: Ball-collision decoding. Advances in Cryptology – CRYPTO 2011, ed Rogaway P (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 743–760. https://doi.org/https://doi.org/10.1007/978-3-642-22792-9_42

[52] Becker A, Joux A, May A, Meurer A (2012) Decoding random binary linear codes in \(2^{n/20}\): How \(1+1=0\) improves information set decoding. Advances in Cryptology – EUROCRYPT 2012, eds Pointcheval D, Johansson T (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 520–536. https://doi.org/https://doi.org/10.1007/978-3-642-29011-4_31

[52] Becker A, Joux A, May A, Meurer A (2012) Decoding random binary linear codes in \(2^{n/20}\): How \(1+1=0\) improves information set decoding. Advances in Cryptology – EUROCRYPT 2012, eds Pointcheval D, Johansson T (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 520–536. https://doi.org/https://doi.org/10.1007/978-3-642-29011-4_31

[53] May A, Ozerov I (2015) On computing nearest neighbors with applications to decoding of binary linear codes. Advances in Cryptology – EUROCRYPT 2015, eds Oswald E, Fischlin M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 203–228. https://doi.org/https://doi.org/10.1007/978-3-662-46800-5_9

[53] May A, Ozerov I (2015) On computing nearest neighbors with applications to decoding of binary linear codes. Advances in Cryptology – EUROCRYPT 2015, eds Oswald E, Fischlin M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 203–228. https://doi.org/https://doi.org/10.1007/978-3-662-46800-5_9

[54] Canto Torres R, Sendrier N (2016) Analysis of information set decoding for a sub-linear error weight. Post-Quantum Cryptography, ed Takagi T (Springer International Publishing, Cham), pp 144–161. https://doi.org/https://doi.org/10.1007/978-3-319-29360-8_10

[54] Canto Torres R, Sendrier N (2016) Analysis of information set decoding for a sub-linear error weight. Post-Quantum Cryptography, ed Takagi T (Springer International Publishing, Cham), pp 144–161. https://doi.org/https://doi.org/10.1007/978-3-319-29360-8_10

[55] Both L, May A (2017) Optimizing BJMM with nearest neighbors: full decoding in \(2^{2n/21}\) and McEliece security. The Tenth International Workshop on Coding and Cryptography, pp –. Available at https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/bjmm+.pdf.

[55] Both L, May A (2017) Optimizing BJMM with nearest neighbors: full decoding in \(2^{2n/21}\) and McEliece security. The Tenth International Workshop on Coding and Cryptography, pp –.入手先: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/bjmm+.pdf.

[56] Guo Q, Johansson T, Nguyen V (2024) A new sieving-style information-set decoding algorithm. IEEE Trans Inf Theory 70(11):8303–8319. https://doi.org/10.1109/TIT.2024.3457150

[56] Guo Q, Johansson T, Nguyen V (2024) A new sieving-style information-set decoding algorithm. IEEE Trans Inf Theory 70(11):8303–8319. https://doi.org/10.1109/TIT.2024.3457150

[57] Kirshanova E (2018) Improved quantum information set decoding. Post-Quantum Cryptography, eds Lange T, Steinwandt R (Springer International Publishing, Cham), pp 507–527. https://doi.org/https://doi.org/10.1007/978-3-319-79063-3_24

[57] Kirshanova E (2018) Improved quantum information set decoding. Post-Quantum Cryptography, eds Lange T, Steinwandt R (Springer International Publishing, Cham), pp 507–527. https://doi.org/https://doi.org/10.1007/978-3-319-79063-3_24

[58] Sendrier N (2011) Decoding one out of many. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 51–67. https://doi.org/https://doi.org/10.1007/978-3-642-25405-5_4

[58] Sendrier N (2011) Decoding one out of many. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 51–67. https://doi.org/https://doi.org/10.1007/978-3-642-25405-5_4

[59] Sidelnikov VM, Shestakov SO (1992) On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 2(4):439–444. https://doi.org/doi:10.1515/dma.1992.2.4.439

[59] Sidelnikov VM, Shestakov SO (1992) On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 2(4):439–444. https://doi.org/doi:10.1515/dma.1992.2.4.439

[60] Wieschebrink C (2010) Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. Post-Quantum Cryptography, ed Sendrier N (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 61–72. https://doi.org/https://doi.org/10.1007/978-3-642-12929-2_5

[60] Wieschebrink C (2010) Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. Post-Quantum Cryptography, ed Sendrier N (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 61–72. https://doi.org/https://doi.org/10.1007/978-3-642-12929-2_5

[61] Couvreur A, Gaborit P, Gauthier-Umaña V, Otmani A, Tillich JP (2014) Distinguisher-based attacks on public-key cryptosystems using Reed—Solomon codes. Designs, Codes and Cryptography 73(2):641–666. https://doi.org/10.1007/s10623-014-9967-z

[61] Couvreur A, Gaborit P, Gauthier-Umaña V, Otmani A, Tillich JP (2014) Distinguisher-based attacks on public-key cryptosystems using Reed—Solomon codes. Designs, Codes and Cryptography 73(2):641–666. https://doi.org/10.1007/s10623-014-9967-z

[62] Minder L, Shokrollahi A (2007) Cryptanalysis of the Sidelnikov cryptosystem. Advances in Cryptology - EUROCRYPT 2007, ed Naor M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 347–360. https://doi.org/https://doi.org/10.1007/978-3-540-72540-4_20

[62] Minder L, Shokrollahi A (2007) Cryptanalysis of the Sidelnikov cryptosystem. Advances in Cryptology - EUROCRYPT 2007, ed Naor M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 347–360. https://doi.org/https://doi.org/10.1007/978-3-540-72540-4_20

[63] Borodin MA, Chizhov IV (2014) Effective attack on the McEliece cryptosystem based on Reed-Muller codes. Discrete Mathematics and Applications 24(5):273–280. https://doi.org/10.1515/dma-2014-0024

[63] Borodin MA, Chizhov IV (2014) Effective attack on the McEliece cryptosystem based on Reed-Muller codes. Discrete Mathematics and Applications 24(5):273–280. https://doi.org/10.1515/dma-2014-0024

[64] Faugère JC, Otmani A, Perret L, de Portzamparc F, Tillich JP (2015) Structural cryptanalysis of McEliece schemes with compact keys. Designs, Codes and Cryptography 79:87 – 112. https://doi.org/https://doi.org/10.1007/s10623-015-0036-z

[64] Faugère JC, Otmani A, Perret L, de Portzamparc F, Tillich JP (2015) Structural cryptanalysis of McEliece schemes with compact keys. Designs, Codes and Cryptography 79:87 – 112. https://doi.org/https://doi.org/10.1007/s10623-015-0036-z

[65] Couvreur A, Otmani A, Tillich J (2014) Polynomial time attack on wild McEliece over quadratic extensions. Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, eds Nguyen PQ, Oswald E (Springer), Lecture Notes in Computer Science, Vol. 8441, pp 17–39. https://doi.org/10.1007/978-3-642-55220-5\_2

[65] Couvreur A, Otmani A, Tillich J (2014) Polynomial time attack on wild McEliece over quadratic extensions. Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, eds Nguyen PQ, Oswald E (Springer), Lecture Notes in Computer Science, Vol. 8441, pp 17–39. https://doi.org/10.1007/978-3-642-55220-5\_2

[66] Mora R, Tillich J (2023) On the dimension and structure of the square of the dual of a Goppa code. Des Codes Cryptogr 91(4):1351–1372. https://doi.org/10.1007/S10623-022-01153-W

[66] Mora R, Tillich J (2023) On the dimension and structure of the square of the dual of a Goppa code. Des Codes Cryptogr 91(4):1351–1372. https://doi.org/10.1007/S10623-022-01153-W

[67] Bardet M, Mora R, Tillich J (2024) Polynomial time key-recovery attack on high rate random alternant codes. IEEE Trans Inf Theory 70(6):4492–4511. https://doi.org/10.1109/TIT.2023.3334592

[67] Bardet M, Mora R, Tillich J (2024) Polynomial time key-recovery attack on high rate random alternant codes. IEEE Trans Inf Theory 70(6):4492–4511. https://doi.org/10.1109/TIT.2023.3334592

[68] Couvreur A, Mora R, Tillich J (2023) A new approach based on quadratic forms to attack the mceliece cryptosystem. Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV, eds Guo J, Steinfeld R (Springer), Lecture Notes in Computer Science, Vol. 14441, pp 3–38. https://doi.org/10.1007/978-981-99-8730-6\_1

[68] Couvreur A, Mora R, Tillich J (2023) A new approach based on quadratic forms to attack the mceliece cryptosystem. Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV, eds Guo J, Steinfeld R (Springer), Lecture Notes in Computer Science, Vol. 14441, pp 3–38. https://doi.org/10.1007/978-981-99-8730-6\_1

[69] Mora R (2024) On the matrix code of quadratic relationships for a Goppa code. Advances in Mathematics of Communications 19. https://doi.org/10.3934/amc.2024026

[69] Mora R (2024) On the matrix code of quadratic relationships for a Goppa code. Advances in Mathematics of Communications 19. https://doi.org/10.3934/amc.2024026

[70] Hülsing A, Ning KC, Schwabe P, Weber FJ, Zimmermann PR (2021) Post-quantum wireguard. 2021 IEEE Symposium on Security and Privacy (SP), pp 304–321. https://doi.org/https://doi.org/10.1109/SP40001.2021.00030

[70] Hülsing A, Ning KC, Schwabe P, Weber FJ, Zimmermann PR (2021) Post-quantum wireguard. 2021 IEEE Symposium on Security and Privacy (SP), pp 304–321. https://doi.org/https://doi.org/10.1109/SP40001.2021.00030

[71] Esser A, Bellini E (2022) Syndrome decoding estimator. Public-Key Cryptography – PKC 2022, eds Hanaoka G, Shikata J, Watanabe Y (Springer International Publishing, Cham), pp 112–141. https://doi.org/https://doi.org/10.1007/978-3-030-97121-2_5

[71] Esser A, Bellini E (2022) Syndrome decoding estimator. Public-Key Cryptography – PKC 2022, eds Hanaoka G, Shikata J, Watanabe Y (Springer International Publishing, Cham), pp 112–141. https://doi.org/https://doi.org/10.1007/978-3-030-97121-2_5

[72] Jao D, De Feo L (2011) Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 19–34. https://doi.org/https://doi.org/10.1007/978-3-642-25405-5_2

[72] Jao D, De Feo L (2011) Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 19–34. https://doi.org/https://doi.org/10.1007/978-3-642-25405-5_2

[73] Maino L, Martindale C, Panny L, Pope G, Wesolowski B (2023) A Direct Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 448–471. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_16

[73] Maino L, Martindale C, Panny L, Pope G, Wesolowski B (2023) A Direct Key Recovery Attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, eds Hazay C, Stam M (Springer Nature Switzerland, Cham), pp 448–471. https://doi.org/https://doi.org/10.1007/978-3-031-30589-4_16

[74] Castryck W, Vercauteren F (2023) A Polynomial Time Attack on Instances of M-SIDH and FESTA. Advances in Cryptology – ASIACRYPT 2023, eds Guo J, Steinfeld R (Springer Nature Singapore, Singapore), pp 127–156. https://doi.org/https://doi.org/10.1007/978-981-99-8739-9_5

[74] Castryck W, Vercauteren F (2023) A Polynomial Time Attack on Instances of M-SIDH and FESTA. Advances in Cryptology – ASIACRYPT 2023, eds Guo J, Steinfeld R (Springer Nature Singapore, Singapore), pp 127–156. https://doi.org/https://doi.org/10.1007/978-981-99-8739-9_5

[75] Alagic G, Bros M, Ciadoux P, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Silberg H, Smith-Tone D, Waller N (2024) Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8528. https://doi.org/10.6028/NIST.IR.8528

[75] Alagic G, Bros M, Ciadoux P, Cooper D, Dang Q, Dang T, Kelsey J, Lichtinger J, Liu YK, Miller C, Moody D, Peralta R, Perlner R, Robinson A, Silberg H, Smith-Tone D, Waller N (2024) Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8528. https://doi.org/10.6028/NIST.IR.8528

[76] Alagic G, Barker EB, Chen L, Moody D, Robinson A, Silberg H, Waller N (2025) Recommendation for key-encapsulation mechanisms (U.S. Department of Commerce, Washington, D.C.), Special Publication 800-227 (Initial Public Draft). https://doi.org/10.6028/NIST.SP.800-227.ipd

[76] Alagic G, Barker EB, Chen L, Moody D, Robinson A, Silberg H, Waller N (2025) Recommendation for key-encapsulation mechanisms (U.S. Department of Commerce, Washington, D.C.), Special Publication 800-227 (Initial Public Draft). https://doi.org/10.6028/NIST.SP.800-227.ipd

Appendix A. List of Symbols, Abbreviations, and Acronyms

付録A.記号、略語、頭字語の一覧

BIKE Bit-Flipping Key Encapsulation

BIKE Bit-Flipping Key Encapsulation(ビット反転鍵カプセル化)

CCA Chosen Ciphertext Attack

CCA Chosen Ciphertext Attack(選択暗号文攻撃)

CPA Chosen Plaintext Attack

CPA Chosen Plaintext Attack(選択平文攻撃)

DFR Decryption Failure Rate

DFR Decryption Failure Rate(復号失敗率)

FIPS Federal Information Processing Standards

FIPS Federal Information Processing Standards(連邦情報処理標準)

FO Fujisaki Okamoto

FO Fujisaki Okamoto

IEC International Electrotechnical Commission

IEC International Electrotechnical Commission(国際電気標準会議)

IND-CCA2 Indistinguishability under Adaptive Chosen-Ciphertext Attack

IND-CCA2 Indistinguishability under Adaptive Chosen-Ciphertext Attack(適応的選択暗号文攻撃に対する識別不能性)

IND-CPA Indistinguishability under Chosen-Plaintext Attack

IND-CPA Indistinguishability under Chosen-Plaintext Attack(選択平文攻撃に対する識別不能性)

IPsec Internet Protocol Security

IPsec Internet Protocol Security(インターネットプロトコルセキュリティ)

ISD Information Set Decoding

ISD Information Set Decoding(情報集合復号)

ISO International Organization for Standardization

ISO International Organization for Standardization(国際標準化機構)

HQC Hamming Quasi-Cyclic

HQC Hamming Quasi-Cyclic

KEM Key-Encapsulation Mechanism

KEM Key-Encapsulation Mechanism(鍵カプセル化メカニズム)

LWE Learning With Errors

LWE Learning With Errors

ML-KEM Module Lattice-Based Key-Encapsulation Mechanism (based on Kyber)

ML-KEM Module Lattice-Based Key-Encapsulation Mechanism(モジュール格子ベースの鍵カプセル化メカニズム。Kyberに基づく)

NIST National Institute of Standards and Technology

NIST National Institute of Standards and Technology(米国国立標準技術研究所)

NIST IR NIST Interagency or Internal Report

NIST IR NIST Interagency or Internal Report(NIST機関間報告書または内部報告書)

OW-CPA One-Way under Chosen Plaintext Attack

OW-CPA One-Way under Chosen Plaintext Attack(選択平文攻撃下での一方向性)

PKE Public-Key Encryption

PKE Public-Key Encryption(公開鍵暗号化)

PQC Post-Quantum Cryptography

PQC Post-Quantum Cryptography(耐量子暗号)

QC-MDPC Quasi-Cyclic Moderate Density Parity Check

QC-MDPC Quasi-Cyclic Moderate Density Parity Check(準巡回中密度パリティ検査)

QCCF Quasi-Cyclic Codeword Finding

QCCF Quasi-Cyclic Codeword Finding(準巡回符号語探索)

QCSD Quasi-Cyclic Syndrome Decoding

QCSD Quasi-Cyclic Syndrome Decoding(準巡回シンドローム復号)

QUIC Quick UDP Internet Connections

QUIC Quick UDP Internet Connections

RMRS Reed-Muller Reed-Solomon

RMRS Reed-Muller Reed-Solomon

ROM Random Oracle Model

ROM Random Oracle Model(乱数オラクルモデル)

SAML SSO Security Assertion Markup Language Single Sign-On

SAML SSO Security Assertion Markup Language Single Sign-On(セキュリティアサーションマークアップ言語によるシングルサインオン)

SIKE Supersingular Isogeny Key Encapsulation

SIKE Supersingular Isogeny Key Encapsulation(超特異アイソジェニー鍵カプセル化)

SIDH Supersingular Isogeny Diffie-Hellman

SIDH Supersingular Isogeny Diffie-Hellman(超特異アイソジェニーDiffie-Hellman)

SP Special Publication

SP Special Publication(特別刊行物)

SSH Secure Shell

SSH Secure Shell(セキュアシェル)

TLS Transport Layer Security

TLS Transport Layer Security(トランスポート層セキュリティ)

VPN Virtual Private Network

VPN Virtual Private Network(仮想プライベートネットワーク)

XML Extensible Markup Language

XML Extensible Markup Language(拡張可能マークアップ言語)