目次

NIST IR 8528 日本語訳

英語タイトル : Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process
日本語タイトル : NIST 耐量子暗号標準化プロセスにおける追加デジタル署名方式の第 1 ラウンドに関する状況報告
公開日 : 2024-10-24
原文URL : https://csrc.nist.gov/pubs/ir/8528/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 276 / 277 ブロック

[要約] NIST IR 8528 は、NIST 耐量子暗号(PQC)標準化プロセスにおける追加デジタル署名の第 1 ラウンドの評価基準と選定プロセスを説明する状況報告です。NIST は 2022 年 7 月に追加のデジタル署名の提案を募集し、2023 年 6 月 1 日に 50 件の提出パッケージを受け取り、そのうち 40 件を第 1 ラウンド候補として受理しました。一般からのフィードバックと第 1 ラウンド候補の内部審査に基づき、NIST は 2024 年 10 月に 14 の署名アルゴリズムを第 2 ラウンド候補として選定したことを発表しました。第 2 ラウンドの候補は、CROSS、FAEST、HAWK、LESS、MAYO、Mirath、MQOM、PERK、QR-UOV、RYDE、SDitH、SNOVA、SQIsign、UOV です。

NIST Internal Report NIST IR 8528

NIST 内部報告書 NIST IR 8528

Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process

NIST 耐量子暗号標準化プロセスにおける追加デジタル署名方式の第 1 ラウンドに関する状況報告

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

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

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

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

NIST Internal Report NIST IR 8528

NIST 内部報告書 NIST IR 8528

Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process

NIST 耐量子暗号標準化プロセスにおける追加デジタル署名方式の第 1 ラウンドに関する状況報告

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

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

Computer Security Division(コンピュータセキュリティ部門) Information Technology Laboratory(情報技術研究所)

Yi-Kai Liu

Yi-Kai Liu

Applied and Computational Mathematics Division Information Technology Laboratory

Applied and Computational Mathematics Division(応用・計算数学部門) Information Technology Laboratory(情報技術研究所)

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

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

October 2024

2024 年 10 月

U.S. Department of Commerce Gina M. Raimondo, Secretary

米国商務省 Gina M. Raimondo 長官

National Institute of Standards and Technology

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

Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

Laurie E. Locascio、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

NIST テクニカルシリーズのポリシー

Copyright, Use, and Licensing Statements

著作権、利用、ライセンスに関する声明

NIST Technical Series Publication Identifier Syntax

NIST テクニカルシリーズ刊行物の識別子の構文

Publication History

刊行履歴

Approved by the NIST Editorial Review Board on 2024-10-16

2024-10-16 に NIST 編集審査委員会(Editorial Review Board)により承認済み

How to cite this NIST Technical Series Publication:

この 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 (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 IR 8528. https://doi.org/10.6028/NIST.IR.8528

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 IR 8528. https://doi.org/10.6028/NIST.IR.8528

Author ORCID iDs

著者の 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

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/8528/final, including related content, potential updates, and document history.

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

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

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

Abstract

概要

NIST is in the process of evaluating public-key digital signature algorithms for potential standardization to protect sensitive information into the foreseeable future, including after the advent of quantum computers. Any signature scheme that is eventually selected would augment FIPS 204, Module-Lattice-Based Digital Signature Standard; FIPS 205, Stateless Hash-Based Digital Signature Standard; FIPS 186-5, Digital Signature Standard (DSS); and SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes. This report describes the evaluation criteria and selection process of the First Round of the Additional Digital Signatures for the NIST Post-Quantum Cryptography (PQC) Standardization Process. Based on public feedback and internal reviews of the first-round candidates, NIST selected 14 candidate algorithms to move forward to the second round of evaluation: CROSS, FAEST, HAWK, LESS, MAYO, Mirath (merger of MIRA/MiRitH), MQOM, PERK, QR-UOV, RYDE, SDitH, SNOVA, SQIsign, and UOV.

NIST は、量子コンピュータの出現後も含め、予見できる将来にわたって機微な情報を保護するため、標準化の可能性がある公開鍵デジタル署名アルゴリズムの評価を進めています。最終的に選定される署名方式は、FIPS 204『Module-Lattice-Based Digital Signature Standard』、FIPS 205『Stateless Hash-Based Digital Signature Standard』、FIPS 186-5『Digital Signature Standard (DSS)』、SP 800-208『Recommendation for Stateful Hash-Based Signature Schemes』を補完するものとなります。本報告書は、NIST 耐量子暗号(PQC)標準化プロセスにおける追加デジタル署名の第 1 ラウンドの評価基準と選定プロセスを説明します。NIST は、一般からのフィードバックと第 1 ラウンド候補の内部審査に基づき、14 の候補アルゴリズムを第 2 ラウンドの評価に進めることにしました。CROSS、FAEST、HAWK、LESS、MAYO、Mirath(MIRA と MiRitH の統合)、MQOM、PERK、QR-UOV、RYDE、SDitH、SNOVA、SQIsign、UOV です。

Keywords

キーワード

cryptography; digital signatures; post-quantum cryptography; quantum-resistant; quantum safe.

暗号技術、デジタル署名、耐量子暗号、耐量子、量子安全。

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 Additional Digital Signatures for PQC Standardization Process webpage is available at https://csrc.nist.gov/Projects/pqc-dig-sig/standardization.

NIST の PQC 標準化プロセスにおける追加デジタル署名のウェブページは https://csrc.nist.gov/Projects/pqc-dig-sig/standardization で入手できます。

Acknowledgments

謝辞

NIST would like to thank all of the candidate submission teams who developed, designed, and analyzed the post-quantum public-key digital signature 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 first round. NIST would not be able to select additional post-quantum digital signature algorithms for standardization without the combined efforts of these individuals and the algorithm submitters.

NIST はまた、第 1 ラウンドの間に候補アルゴリズムのセキュリティ、実装、性能の分析を行った暗号コミュニティの人々の尽力にも感謝します。これらの人々とアルゴリズム提出者の共同の取り組みがなければ、NIST は標準化のために追加の耐量子デジタル署名アルゴリズムを選定することはできません。

The authors of this report are also appreciative of the efforts by 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 second-round candidates. They are Zuzana Bajcsy, Larry Bassham, Lily Chen, Morris Dworkin, Sara Kerman, and Andrew Regenscheid.

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

1. Introduction

1. はじめに

The National Institute of Standards and Technology (NIST) initiated the public 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 [1]. The public-key encapsulation mechanism (KEM) selected for standardization was CRYSTALS-Kyber (ML-KEM). The digital signatures selected were CRYSTALS-Dilithium (ML-DSA), Falcon (FN-DSA), and SPHINCS+ (SLH-DSA). Except for SPHINCS+, all of these schemes are based on the computational hardness of problems that involve structured lattices. While several non-lattice-based KEMs remained under consideration in the fourth round, no signature schemes remained.

米国国立標準技術研究所(NIST)は、量子コンピューティングの大幅な発展と進歩を受け、標準化のための耐量子公開鍵暗号アルゴリズムを選定するため、2016 年 12 月に一般公開の耐量子暗号(PQC)標準化プロセスを開始しました。3 ラウンドの評価と分析を経て、NIST は最初に標準化するアルゴリズムの選定を発表しました [1]。標準化のために選定された公開鍵カプセル化メカニズム(KEM)は CRYSTALS-Kyber(ML-KEM)でした。選定されたデジタル署名は CRYSTALS-Dilithium(ML-DSA)、Falcon(FN-DSA)、SPHINCS+(SLH-DSA)です。SPHINCS+ を除き、これらの方式はいずれも構造化格子に関わる問題の計算困難性に基づいています。第 4 ラウンドでも格子に基づかない KEM がいくつか検討対象として残りましたが、署名方式は残りませんでした。

In July 2022, NIST called for additional digital signature proposals to be considered in the PQC standardization process to diversify its post-quantum signature portfolio. Since two signature schemes based on structured lattices had already been standardized, NIST expressed particular interest in additional general-purpose signature schemes based on a security assumption that did not use structured lattices as well as signature schemes with short signatures and fast verification.

NIST は、耐量子署名のポートフォリオを多様化するため、2022 年 7 月に PQC 標準化プロセスで検討する追加のデジタル署名の提案を募集しました。構造化格子に基づく署名方式がすでに 2 つ標準化されていたため、NIST は特に、構造化格子を用いない安全性の仮定に基づく汎用の追加署名方式と、署名が短く検証が高速な署名方式に関心があることを表明しました。

NIST published the Call for Proposals for Additional Digital Signatures [2], which specified the submission requirements and evaluation criteria, and received 50 submission packages on June 1, 2023. Of those, NIST accepted 40 First-Round Candidates that consisted of signature schemes based on a variety of different security assumptions. The submission packages of the first-round candidates were posted online at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures for public review and comment.

NIST は、提出要件と評価基準を定めた追加デジタル署名の提案募集 [2] を公開し、2023 年 6 月 1 日に 50 件の提出パッケージを受け取りました。このうち NIST は、さまざまな異なる安全性の仮定に基づく署名方式から成る 40 件を第 1 ラウンド候補として受理しました。第 1 ラウンド候補の提出パッケージは、一般からの審査とコメントのため、https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures にオンラインで掲載されました。

The Fifth NIST PQC Standardization Conference was held in Rockville, Maryland, on April 10-12, 2024. The submission teams of the accepted first-round candidates were invited to present posters for their candidate algorithms. Throughout the first round, NIST received significant feedback from the cryptographic community. Based on the public feedback and internal reviews of the first-round candidates, NIST announced the selection of 14 signature algorithms as Second-Round Candidates in October 2024 to move forward to the next stage of the standardization process.

第 5 回 NIST PQC 標準化会議は、2024 年 4 月 10 日から 12 日にかけて、メリーランド州ロックビルで開催されました。受理された第 1 ラウンド候補の提出チームは、自らの候補アルゴリズムのポスターを発表するよう招待されました。第 1 ラウンドを通じて、NIST は暗号コミュニティから多くのフィードバックを受けました。NIST は、一般からのフィードバックと第 1 ラウンド候補の内部審査に基づき、標準化プロセスの次の段階に進める第 2 ラウンド候補として、14 の署名アルゴリズムを選定したことを 2024 年 10 月に発表しました。

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

表 1 は、これまでの NIST PQC 標準化プロセスにおける追加デジタル署名に関する主な出来事のタイムラインを示します。

Table 1. Timeline of the Additional Digital Signatures for the NIST PQC Standardization Process

表 1. NIST PQC 標準化プロセスにおける追加デジタル署名のタイムライン

DateEvent
July 2022NIST announced a forthcoming Call for Proposals for Additional Digital Signatures to diversify its portfolio [1].
September 2022The Call for Proposals for Additional Digital Signatures was published, outlining the submission requirements and evaluation criteria [2].
June 2023Submission deadline for the Additional Digital Signatures process.
July 2023NIST announced 40 First-Round candidates. The public comment period for the first-round candidates began.
April 2024The Fifth NIST PQC Standardization Conference was held in Rockville, Maryland. Submission teams presented posters for their candidate algorithms.
October 2024NIST announced 14 Second-Round candidates. NIST IR 8528, Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process, was released. The public comment period for the second-round candidates began.
日付出来事
2022 年 7 月NIST は、ポートフォリオを多様化するため、追加デジタル署名の提案募集を近く行うことを発表しました [1]。
2022 年 9 月提出要件と評価基準を示した追加デジタル署名の提案募集が公開されました [2]。
2023 年 6 月追加デジタル署名プロセスの提出期限。
2023 年 7 月NIST は 40 件の第 1 ラウンド候補を発表しました。第 1 ラウンド候補に対するパブリックコメント期間が始まりました。
2024 年 4 月第 5 回 NIST PQC 標準化会議がメリーランド州ロックビルで開催されました。提出チームが候補アルゴリズムのポスターを発表しました。
2024 年 10 月NIST は 14 件の第 2 ラウンド候補を発表しました。NIST IR 8528『Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process』が公開されました。第 2 ラウンド候補に対するパブリックコメント期間が始まりました。

1.1. Purpose and Organization of This Document

1.1. 本書の目的と構成

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

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

Section 2 enumerates the candidates that were included in the first round. It also describes the evaluation criteria and selection process used to ultimately select the second-round candidates.

第 2 節では、第 1 ラウンドに含まれていた候補を列挙します。あわせて、最終的に第 2 ラウンド候補を選定するために用いた評価基準と選定プロセスを説明します。

Section 3 summarizes each of the second-round candidates with a brief description of the algorithm, the properties of interest, and characteristics that might cause some concern. This report focuses on the reasons why candidate algorithms were selected rather than providing detailed justifications for why candidate algorithms were not selected.

第 3 節では、第 2 ラウンド候補のそれぞれについて、アルゴリズムの概要、注目すべき特性、懸念が生じうる特徴を簡潔に説明します。本報告書は、候補アルゴリズムが選定されなかった理由の詳細な根拠を示すのではなく、選定された理由に重点を置きます。

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

第 4 節では、第 2 ラウンド候補に対して許容される変更の規定や、最終候補を選定するための評価プロセスなど、NIST PQC 標準化プロセスにおける追加デジタル署名の次のステップを説明します。

2. Evaluation Criteria and the Selection Process

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

2.1. Acceptance of the First-Round Candidates

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

NIST received 50 candidate algorithm submission packages by the entry deadline of June 1, 2023. Of these, NIST accepted 40 first-round candidates that met both the submission requirements and the minimum acceptability criteria for being “complete and proper submissions,” as defined in [2].

NIST は、2023 年 6 月 1 日の応募期限までに 50 件の候補アルゴリズムの提出パッケージを受け取りました。このうち NIST は、提出要件と、[2] で定義された「完全かつ適正な提出」としての最低限の受理基準の両方を満たした 40 件を、第 1 ラウンド候補として受理しました。

Table 2. First-round digital signature candidates organized by category, with the candidates selected to advance to the second round bolded and in blue. The starred signature schemes MIRA and MiRitH merged to form a new candidate Mirath.

表 2. カテゴリ別の第 1 ラウンドのデジタル署名候補(第 2 ラウンドに進む候補は太字の青で表示)。星印の付いた署名方式 MIRA と MiRitH は統合され、新しい候補 Mirath となりました。

Code-BasedLattice-BasedMPC-in-the-HeadMultivariate
CROSSEagleSignBiscuit3WISE
Enhanced pqsigRMEHTv4MIRA*DME-Sign
FuLeecaHAETAEMiRitH*HPPC
LESSHAWKMQOMMAYO
MEDSHuFuPERKPROV
WAVERaccoonRYDEQR-UOV
SQUIRRELSSDitHSNOVA
OtherTUOV
ALTEQSymmetric-BasedIsogeny-BasedUOV
eMLE-Sig 2.0AIMerSQIsignVOX
KAZ-SIGNAscon-Sign
PREONFAEST
Xifrat1-Sign.ISPHINCS-alpha
符号ベース格子ベースMPC-in-the-Head多変数
CROSSEagleSignBiscuit3WISE
Enhanced pqsigRMEHTv4MIRA*DME-Sign
FuLeecaHAETAEMiRitH*HPPC
LESSHAWKMQOMMAYO
MEDSHuFuPERKPROV
WAVERaccoonRYDEQR-UOV
SQUIRRELSSDitHSNOVA
その他TUOV
ALTEQ共通鍵ベース同種写像ベースUOV
eMLE-Sig 2.0AIMerSQIsignVOX
KAZ-SIGNAscon-Sign
PREONFAEST
Xifrat1-Sign.ISPHINCS-alpha

The criteria for determining the first round candidates included provisions for reference and optimized C code implementations, known-answer tests, a written specification, and required intellectual property statements. These were the sole criteria used to judge the submission packages. Other factors, such as security, cost, and algorithm and implementation characteristics of the candidates were not considered during the review process prior to the first round, nor did cryptanalysis or performance data of a submission impact the acceptance of the first-round candidates.

第 1 ラウンド候補を決定するための基準には、リファレンス実装と最適化 C コード実装、既知解テスト、文書による仕様、必須の知的財産に関する声明の規定が含まれていました。提出パッケージの判定に用いた基準はこれらのみです。セキュリティ、コスト、候補のアルゴリズムと実装の特性といったその他の要素は、第 1 ラウンド前の審査プロセスでは考慮しておらず、提出物の暗号解読や性能のデータも、第 1 ラウンド候補の受理には影響しませんでした。

2.2. Evaluation Criteria

2.2. 評価基準

NIST’s Call for Proposals [2] identified three broad aspects of the evaluation criteria that would be used to compare candidate signature algorithms throughout the NIST PQC Standardization Process: 1) security, 2) cost and performance, and 3) algorithm and implementation characteristics. As NIST seeks to diversify its signature portfolio, submissions also needed to significantly differ from signature schemes that have already been selected by NIST for standardization. In particular, the Call for Proposals specifically stated that submissions should, at a minimum, meet one of the following criteria:

NIST の提案募集 [2] は、NIST PQC 標準化プロセス全体を通じて候補署名アルゴリズムの比較に用いる評価基準として、1) セキュリティ、2) コストと性能、3) アルゴリズムと実装の特性という 3 つの大きな側面を示していました。NIST は署名のポートフォリオの多様化を目指しているため、提出物は、すでに NIST が標準化のために選定した署名方式と大きく異なる必要もありました。特に提案募集では、提出物が最低限、次の基準のいずれかを満たすべきであると明記されていました。

•Lattice-based schemes should provide at least one large performance advantage over both CRYSTALS-Dilithium and Falcon.

•格子ベースの方式は、CRYSTALS-Dilithium と Falcon の両方に対して、少なくとも 1 つの大きな性能上の優位性を示すべきです。

•Non-lattice-based algorithms should provide at least one large performance advantage over SPHINCS+.

•格子ベースではないアルゴリズムは、SPHINCS+ に対して、少なくとも 1 つの大きな性能上の優位性を示すべきです。

2.3. Security

2.3. セキュリティ

As with the PQC Standardization Process, security was the most important factor when evaluating the candidate signature algorithms. NIST intends to standardize post-quantum signatures for use in a wide variety of internet protocols (e.g., TLS, SSH, IKE, IPsec, OCSP, and DNSSEC) and other applications (e.g., certificate transparency, document signing, code signing, and firmware updates).

PQC 標準化プロセスと同様に、候補署名アルゴリズムの評価ではセキュリティが最も重要な要素でした。NIST は、多様なインターネットプロトコル(TLS、SSH、IKE、IPsec、OCSP、DNSSEC など)やその他の用途(証明書の透明性、文書署名、コード署名、ファームウェア更新など)で使用する耐量子署名を標準化する意向です。

Submitters were encouraged but not required to provide proofs of security in relevant models. Digital signature schemes needed to enable existentially unforgeable signatures with respect to an adaptive chosen message attack (EUF-CMA security).

提出者は、関連するモデルにおけるセキュリティの証明を提供することが推奨されていましたが、必須ではありませんでした。デジタル署名方式は、適応的選択メッセージ攻撃に対して存在的偽造不可能な署名(EUF-CMA 安全性)を実現する必要がありました。

NIST defined five security categories to compare the security strengths provided by the submissions. Submitters were asked to provide a preliminary classification, according to the definitions provided in [2], with a focus on meeting the requirements for categories 1, 2, and/or 3. It was also recommended that submitters provide at least one parameter set with a substantially higher level of security (i.e., either category 4 or 5).

NIST は、提出物が提供するセキュリティ強度を比較するため、5 つのセキュリティカテゴリを定義しました。提出者は、[2] の定義に従い、カテゴリ 1、2、3 の要件を満たすことに重点を置いて、暫定的な分類を提示するよう求められました。また、提出者は、大幅に高いセキュリティレベル(すなわちカテゴリ 4 または 5)のパラメータセットを少なくとも 1 つ提供することも推奨されていました。

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 additional desirable security properties provided beyond standard unforgeability (e.g., exclusive ownership, message-bound signatures, and non re-signability). Finally, NIST required submission packages to summarize known cryptanalytic attacks on the scheme and complexity estimates for these attacks.

NIST はまた、サイドチャネル攻撃やマルチキー攻撃への耐性、誤用への耐性など、そのほかの望ましいセキュリティ特性も挙げました。提出物には、標準的な偽造不可能性にとどまらず、提供される追加の望ましいセキュリティ特性(排他的所有性、メッセージ束縛署名、再署名不可能性など)を記載することが推奨されていました。最後に NIST は、提出パッケージに、その方式に対する既知の暗号解読攻撃と、その攻撃の計算量の推定値を要約することを求めました。

2.4. Cost and Performance

2.4. コストと性能

The second-most important criterion when evaluating candidate algorithms involved cost and performance, including:

候補アルゴリズムの評価で 2 番目に重要な基準はコストと性能であり、次の項目を含みます。

•The size of public keys and signatures

•公開鍵と署名のサイズ

•Computational efficiency of the signing and verification operations, as well as key generation (i.e., the speed of the algorithms)

•署名および検証の操作と鍵生成の計算効率(すなわちアルゴリズムの速度)

Memory requirements refer to both code size and random-access memory (RAM) requirements for software implementations, as well as gate counts for hardware implementations.

メモリ要件とは、ソフトウェア実装ではコードサイズとランダムアクセスメモリ(RAM)の要件の両方、ハードウェア実装ではゲート数を指します。

The Call for Proposals required all submitters to include performance estimates on the NIST reference platform — an Intel x64 that runs Windows or Linux and supports the GCC compiler. NIST performed a preliminary efficiency analysis on the reference platform but also invited the public to conduct similar tests on additional platforms. NIST hopes that candidate algorithms will offer comparable or improved performance over the currently standardized algorithms.

提案募集は、すべての提出者に、NIST のリファレンスプラットフォーム(Windows または Linux が動作し、GCC コンパイラをサポートする Intel x64)での性能推定値を含めるよう求めていました。NIST はリファレンスプラットフォームで予備的な効率分析を実施しましたが、一般にも、ほかのプラットフォームで同様のテストを行うよう呼びかけました。NIST は、候補アルゴリズムが、現在標準化されているアルゴリズムと同等またはそれ以上の性能を提供することを期待しています。

2.5. Algorithm and Implementation Characteristics

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

The Additional Digital Signatures for the NIST PQC Standardization Process received many candidate algorithms with new and unique designs and features that are not present in the current NIST standardized public-key algorithms. NIST prefers candidate algorithms with greater flexibility (e.g., those capable of running efficiently on a wide variety of platforms and those that used parallelism or instruction set extensions to achieve higher performance) and simple and elegant designs that reflect the submission team’s understanding and confidence. Finally, NIST considered factors that could hinder or promote the adoption of an algorithm or implementation, such as intellectual property or terms of licenses to interested parties.

NIST PQC 標準化プロセスにおける追加デジタル署名には、現在 NIST が標準化している公開鍵アルゴリズムにはない、新しく独自の設計や特徴を持つ候補アルゴリズムが多数寄せられました。NIST は、より柔軟性の高い候補アルゴリズム(多様なプラットフォームで効率的に動作できるもの、並列処理や命令セット拡張を使って高い性能を実現するものなど)や、提出チームの理解と確信を反映した、単純で洗練された設計の候補アルゴリズムを好みます。最後に NIST は、知的財産や関心を持つ当事者へのライセンス条件など、アルゴリズムや実装の採用を妨げうる、または促進しうる要素を考慮しました。

2.6. Selection of the Candidates to Advance to the Second Round

2.6. 第 2 ラウンドに進む候補の選定

NIST selected 14 second-round candidates from the 40 first-round candidates using the evaluation criteria specified in [2]. In relative order of importance, NIST considered the security, cost and performance, and algorithm and implementation characteristics of a candidate in selecting the second-round candidates.

NIST は、[2] に定めた評価基準を用いて、40 件の第 1 ラウンド候補から 14 件の第 2 ラウンド候補を選定しました。第 2 ラウンド候補の選定にあたって NIST は、重要度の高い順に、候補のセキュリティ、コストと性能、アルゴリズムと実装の特性を考慮しました。

NIST evaluated the security arguments presented in the submission packages, internal and external cryptanalysis, and the overall quantity, quality, and maturity of analysis relevant to each candidate, including the analysis of similar schemes. NIST also considered attacks that directly demonstrated that a candidate fell short of NIST’s stated security targets as well as attacks that brought the candidate’s underlying security assumptions into question or showed room for improvement.

NIST は、提出パッケージに示されたセキュリティ上の論拠、内部および外部の暗号解読、類似の方式の解析を含む各候補に関連する解析の全体的な量・質・成熟度を評価しました。また NIST は、候補が NIST の示したセキュリティ目標に届かないことを直接示した攻撃や、候補の基礎となるセキュリティの仮定に疑問を投げかけた、または改善の余地を示した攻撃も考慮しました。

When evaluating the performance of the candidates, NIST considered the public key and signature sizes as well as the computational estimates given in the submission documentation. NIST also established internal performance benchmarks and considered the external feedback and performance estimates that were provided by the cryptographic community.

候補の性能を評価するにあたり、NIST は、公開鍵と署名のサイズ、および提出文書に示された計算量の推定値を考慮しました。また NIST は、独自の内部性能ベンチマークを設け、暗号コミュニティから寄せられた外部のフィードバックと性能推定値も考慮しました。

In a few cases, a submitted design was selected in part for its uniqueness and elegance. NIST generally favored designs that were based on clear design principles or otherwise illustrated an innovative idea. This diversity of designs will enable cryptographers and cryptanalysts to expand the scope of ideas in their field and make it harder for a single type of attack to eliminate the bulk of the candidates remaining in the standardization process.

いくつかの事例では、提出された設計が、その独自性と洗練さも一因となって選定されました。NIST は一般に、明確な設計原則に基づく設計や、革新的な着想を示す設計を好みました。こうした設計の多様性により、暗号研究者や暗号解読者は自分たちの分野の着想の範囲を広げることができ、単一の種類の攻撃で標準化プロセスに残る候補の大半を排除することが難しくなります。

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

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

Table 3. Second-round digital signature candidates organized by category

表 3. カテゴリ別の第 2 ラウンドのデジタル署名候補

Code-BasedLattice-BasedMPC-in-the-HeadMultivariate
CROSSHawkMirath (MIRA/MiRitH)UOV
LESSMQOMMAYO
PERKQR-UOV
Symmetric-BasedIsogeny-BasedRYDESNOVA
FAESTSQIsignSDitH
符号ベース格子ベースMPC-in-the-Head多変数
CROSSHawkMirath (MIRA/MiRitH)UOV
LESSMQOMMAYO
PERKQR-UOV
共通鍵ベース同種写像ベースRYDESNOVA
FAESTSQIsignSDitH

3. Summary of the Second-Round Candidates

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

This section describes each of the second-round candidates, including their advantages and disadvantages, and why a scheme was selected to advance to the second round.

本節では、第 2 ラウンドの各候補について、その長所と短所、および方式が第 2 ラウンドに進むために選定された理由を説明します。

3.1. CROSS

3.1. CROSS

CROSS [3] is a signature scheme that uses the Fiat-Shamir transform on a zero-knowledge proof of knowledge (ZKPoK) identification protocol. CROSS has two variants, each depending on the NP-hard hardness of one of the two variants of the Syndrome Decoding Problem (SDP): the Restricted Syndrome Decoding Problem (R-SDP) and the Restricted Syndrome Decoding Problem with subgroup G (R-SDP(G)). The security of R-SDP is considered more conservative than that of R-SDP(G). However, schemes based on the R-SDP(G) problem offer better performance in both signature size and algorithm runtime.

CROSS [3] は、知識のゼロ知識証明(ZKPoK)の識別プロトコルに Fiat-Shamir 変換を適用する署名方式です。CROSS には 2 つの変種があり、それぞれ、シンドローム復号問題(SDP)の 2 つの変種のうち一方の NP 困難性に依存しています。2 つの変種とは、制限付きシンドローム復号問題(R-SDP)と、部分群 G を伴う制限付きシンドローム復号問題(R-SDP(G))です。R-SDP のセキュリティは R-SDP(G) より保守的であると考えられています。一方、R-SDP(G) 問題に基づく方式は、署名サイズとアルゴリズムの実行時間の両方でより良い性能を示します。

CROSS implements both variants with parameter sets at levels 1, 3, and 5. Additionally, each parameter set has a “fast” and “small” version, like SLH-DSA. These fast and small versions have signature sizes similar to the corresponding SLH-DSA parameter sets. Several parameter sets of CROSS — especially the three fast parameter sets under the R-SDP(G) — have noticeably smaller signature sizes than their corresponding SLH-DSA parameter sets. All parameter sets of CROSS have small public keys. CROSS has a similar verification runtime as SLH-DSA but a significantly reduced signature generation time (particularly for the small versions compared to SLH-DSA) and very quick key generation (similar to ML-DSA).

CROSS は、両方の変種をレベル 1、3、5 のパラメータセットで実装しています。さらに各パラメータセットには、SLH-DSA と同様に「fast」版と「small」版があります。これらの fast 版と small 版の署名サイズは、対応する SLH-DSA のパラメータセットと同程度です。CROSS のいくつかのパラメータセット、特に R-SDP(G) の 3 つの fast パラメータセットは、対応する SLH-DSA のパラメータセットより署名サイズが著しく小さくなっています。CROSS のすべてのパラメータセットは公開鍵が小さく、検証の実行時間は SLH-DSA と同程度ですが、署名生成時間は大幅に短く(特に small 版を SLH-DSA と比較した場合)、鍵生成も非常に高速(ML-DSA と同程度)です。

While there are no known attacks against either of the two CROSS variants, the problems are relatively new. NIST looks forward to further analysis of the underlying problems and the ZKPoK identification protocol. CROSS has advanced to the second round in part due to NIST’s interest in it as a non-lattice scheme that demonstrates performance benefits over SLH-DSA.

CROSS の 2 つの変種のどちらに対しても既知の攻撃はありませんが、これらの問題は比較的新しいものです。NIST は、基礎となる問題と ZKPoK 識別プロトコルのさらなる解析を期待しています。CROSS が第 2 ラウンドに進んだのは、SLH-DSA に対する性能面の利点を示す、格子ベースではない方式として NIST が関心を持っていることが一因です。

3.2. LESS

3.2. LESS

LESS [4] is constructed by applying the Fiat-Shamir transform to an interactive ZKPoK of the solution to a computational code equivalence problem. The security of LESS is based on the difficulty of the Linear Equivalence Problem (LEP): recovering the secret isometry that maps a given full-rank generator matrix to the public key (a full-rank generator matrix in systematic form). One round of the protocol results in a soundness error of \(\frac{1}{2}\). Soundness error is sufficiently reduced by generating \(s\) private isometries that map to multiple public keys for each protocol instance and repeating the protocol \(t\) times.

LESS [4] は、計算量的な符号同値問題の解についての対話型 ZKPoK に、Fiat-Shamir 変換を適用して構成されています。LESS のセキュリティは、線形同値問題(LEP)の困難性に基づきます。LEP とは、与えられたフルランクの生成行列を公開鍵(システマティック形式のフルランクの生成行列)に写す秘密の等長変換を復元する問題です。プロトコルの 1 ラウンドでは、健全性誤差は \(\frac{1}{2}\) になります。健全性誤差は、プロトコルのインスタンスごとに複数の公開鍵に写る \(s\) 個の秘密の等長変換を生成し、プロトコルを \(t\) 回繰り返すことで十分に小さくなります。

LESS signatures are smaller than SLH-DSA with much larger public keys. Recent work has emerged to use the Canonical Form Linear Equivalence Problem, which results in even smaller signatures (i.e., less than 3Kb) for the same public key sizes [5].

LESS の署名は SLH-DSA より小さい一方、公開鍵ははるかに大きくなります。最近、正準形線形同値問題を用いる研究が登場しており、同じ公開鍵サイズでさらに小さい署名(すなわち 3Kb 未満)が得られます [5]。

The LEP (and a canonical form version of LEP) will require more analysis to build confidence in the security of LESS. While an updated version of LESS based on the canonical form LEP would offer a non-lattice-based digital signature with signature sizes comparable to ML-DSA, it is unclear how competitive the overall performance profile will be compared to UOV-based signature schemes.

LESS のセキュリティへの信頼を築くには、LEP(および LEP の正準形版)についてさらなる解析が必要です。正準形 LEP に基づく LESS の更新版は、ML-DSA に匹敵する署名サイズを持つ、格子ベースではないデジタル署名を提供することになりますが、全体的な性能プロファイルが UOV ベースの署名方式と比べてどの程度競争力を持つかは不明です。

3.3. HAWK

3.3. HAWK

HAWK [6] is a lattice-based hash-and-sign signature scheme that is closely related to Falcon. The central mathematical objects in HAWK are matrices of elements from the same family of rings used in the lattice-based algorithms chosen for standardization. The secret key is an efficient basis for the lattice. To sign, a message is hashed and interpreted as a vector \(\mathbf{h}\). The efficient basis is then used to find an element in the lattice that is sufficiently close to \(\mathbf{h}\) without leaking information about the secret key. In order to keep the efficient basis secret, Falcon uses the Fast Fourier Transform, which uses floating point arithmetic. In contrast, HAWK, relies on the one more shortest vector problem (omSVP) and search module lattice isomorphism problem (smLIP) to keep secret information from leaking.

HAWK [6] は、Falcon と密接に関連する格子ベースのハッシュ・署名(hash-and-sign)方式です。HAWK の中心的な数学的対象は、標準化のために選定された格子ベースのアルゴリズムで使われているものと同じ環の族の元を成分とする行列です。秘密鍵は格子の効率的な基底です。署名するには、メッセージをハッシュし、ベクトル \(\mathbf{h}\) として解釈します。次に、効率的な基底を使って、秘密鍵に関する情報を漏らすことなく、\(\mathbf{h}\) に十分近い格子の元を見つけます。効率的な基底を秘密にするため、Falcon は浮動小数点演算を用いる高速フーリエ変換を使います。これに対して HAWK は、情報の漏えいを防ぐために、one more shortest vector problem(omSVP)と search module lattice isomorphism problem(smLIP)に依拠しています。

NIST has chosen to keep HAWK under consideration because of its strong performance. Due to their similarities, HAWK has a similar performance profile to Falcon. The key and signature sizes for HAWK are comparable — and, in some instances, better — than those of Falcon. Additionally, while Falcon uses floating-point arithmetic, HAWK can be implemented without the use of floating-point arithmetic.

NIST は、HAWK の高い性能を理由に、HAWK を引き続き検討対象とすることにしました。両者の類似性により、HAWK の性能プロファイルは Falcon と似ています。HAWK の鍵サイズと署名サイズは Falcon と同程度で、場合によってはより優れています。さらに、Falcon は浮動小数点演算を使用しますが、HAWK は浮動小数点演算を使わずに実装できます。

However, the security arguments for HAWK use elements that are not as well-studied as those for Falcon. The authors of HAWK center their security argument on two problems that are variants of more conventional lattice problems: omSVP and smLIP. NIST encourages the community to study the security arguments and underlying assumptions for HAWK more deeply in order to enable further comparison with NIST’s current signature standards.

しかし、HAWK のセキュリティ上の論拠は、Falcon のものほど十分に研究されていない要素を用いています。HAWK の著者は、より従来的な格子問題の変種である omSVP と smLIP という 2 つの問題を中心にセキュリティの論拠を構成しています。NIST は、NIST の現行の署名標準とのさらなる比較を可能にするため、HAWK のセキュリティ上の論拠と基礎となる仮定をより深く研究するようコミュニティに奨励します。

3.4. Mirath (MIRA/MiRitH)

3.4. Mirath (MIRA/MiRitH)

MIRA [7] and MiRitH [8] are signature schemes constructed in the Multi-Party Computation in the Head (MPCitH) paradigm. Signatures for both schemes are generated by applying the Fiat-Shamir transform to a ZKPoK of the solution of the MinRank problem. Security for both MIRA and MiRitH is based on the hardness of the MinRank problem: given \(k\) matrices of dimension \(m \times n\) over a field \(\mathbb{F}_q\), a linear combination with rank \(r\) must be found.

MIRA [7] と MiRitH [8] は、マルチパーティ計算のインザヘッド(Multi-Party Computation in the Head、MPCitH)パラダイムで構成された署名方式です。どちらの方式の署名も、MinRank 問題の解についての ZKPoK に Fiat-Shamir 変換を適用して生成されます。MIRA と MiRitH のどちらのセキュリティも MinRank 問題の困難性に基づいています。この問題では、体 \(\mathbb{F}_q\) 上の \(m \times n\) 次元の行列 \(k\) 個が与えられたとき、ランク \(r\) の線形結合を見つける必要があります。

MIRA and MiRitH contain variants that use a hypercube structure, which is an optimization within the MPCitH paradigm [9] that uses additive secret sharing, allowing the MPCitH protocol to be parallelized. This optimization also allows for \(D + 1\) computations rather than \(2^D\), where \(D\) is the number of parallel repetitions of the protocol, requiring higher computational costs while containing smaller signatures.

MIRA と MiRitH には、ハイパーキューブ構造を用いる変種があります。これは、加法的秘密分散を用いる MPCitH パラダイム内の最適化 [9] であり、MPCitH プロトコルの並列化を可能にします。この最適化により、\(2^D\) 回ではなく \(D + 1\) 回の計算で済みます。ここで \(D\) はプロトコルの並列反復の回数です。計算コストは高くなりますが、署名は小さくなります。

Both schemes have parameter sets with key sizes in between SLH-DSA and Falcon and signature sizes that are similar to SLH-DSA. The performance for key generation of both schemes is similar to ML-DSA, while the performance for signing and verifying sits between ML-DSA and Falcon. With ongoing research and evolving techniques in the MPCitH paradigm, signature sizes are expected to improve [10], while underlying security assumptions should remain unchanged.

どちらの方式にも、鍵サイズが SLH-DSA と Falcon の中間で、署名サイズが SLH-DSA と同程度のパラメータセットがあります。どちらの方式も鍵生成の性能は ML-DSA と同程度で、署名と検証の性能は ML-DSA と Falcon の中間に位置します。MPCitH パラダイムでは研究が進み技術が発展しているため、署名サイズは改善されると見込まれる一方 [10]、基礎となるセキュリティの仮定は変わらないはずです。

NIST advanced Mirath, a merged submission that combines MIRA and MiRitH [11], to the second round as a result of its competitive performance with other MPCitH schemes.

NIST は、他の MPCitH 方式と比べた競争力のある性能を理由に、MIRA と MiRitH を統合した提出物である Mirath [11] を第 2 ラウンドに進めました。

3.5. MQOM

3.5. MQOM

MQOM [12] is a signature built on the MPCitH paradigm based on the hardness of solving a random multivariate system of quadratic equations with an equal number of variables and equations. While the problem of solving multivariate quadratic systems has been well-studied, the recent result of [13] may have a small effect on the MQOM parameters needed to meet the target security levels.

MQOM [12] は、変数の数と方程式の数が等しいランダムな多変数 2 次方程式系を解く問題の困難性に基づく、MPCitH パラダイム上の署名方式です。多変数 2 次方程式系を解く問題は十分に研究されていますが、[13] の最近の成果は、目標とするセキュリティレベルを満たすために必要な MQOM のパラメータにわずかな影響を与える可能性があります。

As with other signatures based on in the head techniques, such as MPCitH, Threshold in the Head and Vector Oblivious Linear Evaluation in the Head (VOLEitH), MQOM offers very small public keys with signatures of intermediate size between those of ML-DSA and SLH-DSA. It is expected that significant improvements in the performance and signature size of MQOM will be obtained using new techniques (i.e., techniques from Threshold in the Head) [10] that will not change the underlying security assumptions.

MPCitH、Threshold in the Head、Vector Oblivious Linear Evaluation in the Head(VOLEitH)などの、インザヘッド技術に基づく他の署名と同様に、MQOM は非常に小さい公開鍵と、ML-DSA と SLH-DSA の中間のサイズの署名を提供します。基礎となるセキュリティの仮定を変えない新しい技術(すなわち Threshold in the Head の技術)[10] を用いることで、MQOM の性能と署名サイズが大幅に改善されると見込まれます。

Overall, even if the parameters may need to be adjusted, MQOM is expected to have highly competitive performance within the fast-moving area of MPC/VOLE/Threshold in the Head signatures. NIST hopes that second-round tweaks of MQOM (and the other MPC/VOLE/Threshold in the Head signatures) will yield a better understanding of the possible performance trade-offs and signature sizes that can be obtained from various well-known hardness assumptions.

全体として、パラメータの調整が必要になる可能性があるとしても、MQOM は、変化の速い MPC/VOLE/Threshold in the Head 署名の分野で、非常に競争力のある性能を持つと見込まれます。NIST は、MQOM(および他の MPC/VOLE/Threshold in the Head 署名)の第 2 ラウンドでの調整により、よく知られたさまざまな困難性の仮定から得られる性能のトレードオフや署名サイズについて、理解が深まることを期待しています。

3.6. PERK

3.6. PERK

PERK [14] is a signature that consists of a ZKPoK of a secret permutation. Given a matrix \(\mathbf{H}\) and an array \(\mathbf{x}\), the signatory proves that they know a permutation \(\pi\) such that \(\pi(\mathbf{x})\) is in the kernel of \(H\) (i.e., \(\mathbf{H}(\pi(\mathbf{x})) = \mathbf{0}\)). The security assumption, called the Permuted Kernel Problem, is that it is hard to find such a permutation given random \(\mathbf{H}\) and \(\mathbf{x}\) over a finite field \(\mathbb{F}_q\). The proof uses MPC techniques. The computation is simulated by replacing random choices with the result of a hash on the message being signed.

PERK [14] は、秘密の置換についての ZKPoK から成る署名方式です。行列 \(\mathbf{H}\) と配列 \(\mathbf{x}\) が与えられたとき、署名者は、\(\pi(\mathbf{x})\) が \(H\) の核に含まれる(すなわち \(\mathbf{H}(\pi(\mathbf{x})) = \mathbf{0}\))ような置換 \(\pi\) を知っていることを証明します。置換核問題(Permuted Kernel Problem)と呼ばれるセキュリティの仮定は、有限体 \(\mathbb{F}_q\) 上のランダムな \(\mathbf{H}\) と \(\mathbf{x}\) が与えられたとき、そのような置換を見つけることが困難であるというものです。この証明には MPC の技術を用います。計算は、ランダムな選択を、署名対象のメッセージのハッシュの結果で置き換えることでシミュレートされます。

As with other MPCitH schemes, the underlying techniques for building the ZKPoK were vastly improved after the initial submission was received. For PERK in particular, the submitted version relied on a possibly stronger assumption than the Permuted Kernel Problem. An updated version proposed by the PERK team resolves that issue and should achieve a significant reduction in the length of the signature.

他の MPCitH 方式と同様に、ZKPoK を構築するための基礎技術は、最初の提出物を受け取った後に大幅に改善されました。特に PERK では、提出された版は、置換核問題よりも強い可能性のある仮定に依拠していました。PERK チームが提案した更新版はその問題を解決しており、署名長を大幅に削減できるはずです。

Even with these improvements, PERK is expected to be slower than ML-DSA and comparable in speed to SLH-DSA. The size of the PERK signature is expected to be larger than ML-DSA but significantly smaller than SLH-DSA.

こうした改善があっても、PERK は ML-DSA より低速で、速度は SLH-DSA と同程度になると見込まれます。PERK の署名サイズは ML-DSA より大きいものの、SLH-DSA よりは大幅に小さいと見込まれます。

The Permuted Kernel Assumption is PERK’s only hardness assumption beyond standard assumptions from symmetric-key cryptography. Although the problem was proposed about 30 years ago, there is uncertainty about its concrete complexity. More research on this assumption would help increase confidence in the concrete parameters of PERK for various security levels.

置換核の仮定は、共通鍵暗号の標準的な仮定を除けば、PERK の唯一の困難性の仮定です。この問題は約 30 年前に提案されましたが、具体的な計算量には不確実性があります。この仮定についてさらに研究を行えば、さまざまなセキュリティレベルに対する PERK の具体的なパラメータへの信頼を高めるのに役立ちます。

3.7. RYDE

3.7. RYDE

RYDE [15] is a signature scheme constructed in the MPCitH paradigm. Like other MPCitH signature schemes, the construction of RYDE involves generating a random equation together with a solution. The satisfiability of such an equation and the knowledge of a solution as a witness are proved in zero-knowledge. A Fiat-Shamir transform is applied to remove the interaction between the prover and the verifier.

RYDE [15] は、MPCitH パラダイムで構成された署名方式です。他の MPCitH 署名方式と同様に、RYDE の構成では、ランダムな方程式をその解とともに生成します。そのような方程式の充足可能性と、証拠(witness)としての解の知識が、ゼロ知識で証明されます。証明者と検証者の間のやり取りをなくすために、Fiat-Shamir 変換が適用されます。

The design of RYDE revolves around the conjecturally hard problem of Rank Syndrome Decoding, which is to solve a system of linear equations over a finite field for a solution of small rank, where rank is defined in a special way for a tuple of elements in a finite extension of a prime field. RYDE uses a slight optimization of the rank-checking protocol in [16]. Given a set of arithmetic constraints that represent an instance of the Rank Syndrome Decoding problem, RYDE produces two variants of the signature scheme by applying two different MPCitH techniques: the hypercube approach using additive secret sharing [17] and Threshold Computation in the Head with linear threshold secret sharing [18, 19]. Significant improvements to RYDE were proposed during round one, including new modelling for the Rank Syndrome Decoding problem and adoption of the VOLEitH framework [20].

RYDE の設計は、ランクシンドローム復号という、困難であると予想されている問題を中心にしています。これは、有限体上の線形方程式系について、ランクの小さい解を求める問題であり、ここでのランクは、素体の有限拡大体の元のタプルに対して特別な方法で定義されます。RYDE は [16] のランク検査プロトコルをわずかに最適化して用います。RYDE は、ランクシンドローム復号問題のインスタンスを表す算術的な制約の集合が与えられると、2 つの異なる MPCitH 技術を適用して、署名方式の 2 つの変種を生成します。加法的秘密分散を用いるハイパーキューブ方式 [17] と、線形しきい値秘密分散を用いる Threshold Computation in the Head [18, 19] です。第 1 ラウンドの間に、ランクシンドローム復号問題の新しいモデル化や VOLEitH フレームワークの採用 [20] など、RYDE の大幅な改善が提案されました。

NIST advanced RYDE to the second round of evaluation because of the scheme’s competitive performance within the category of MPCitH and VOLEitH signature schemes, especially with the recent proposed improvements. The underlying hard problem of Rank Syndrome Decoding also appears unstructured, and the corresponding security assumption is seemingly conservative.

NIST は、特に最近提案された改善を踏まえ、MPCitH および VOLEitH 署名方式の分野での RYDE の競争力のある性能を理由に、RYDE を第 2 ラウンドの評価に進めました。基礎となる困難な問題であるランクシンドローム復号は、構造化されていないようにも見え、対応するセキュリティの仮定は保守的であるようです。

3.8. SDitH

3.8. SDitH

Syndrome Decoding in the Head (SDitH) [21] follows the MPCitH framework and offers parameter sets using two optimization techniques. The hypercube variant uses additive secret sharing and has a method of converting a single protocol instance over \(2^D\) parties into \(D\) instances over two parties. This variant yields smaller signatures with higher computational cost. The threshold variant, which was first presented in [22], uses low-threshold linear secret sharing and only requires the prover to reveal \(l\) parties’ views instead of \(N - 1\) for some threshold \(l\).

Syndrome Decoding in the Head(SDitH)[21] は MPCitH フレームワークに従い、2 つの最適化技術を用いたパラメータセットを提供します。ハイパーキューブ変種は加法的秘密分散を用い、\(2^D\) 個の参加者にわたる単一のプロトコルインスタンスを、2 者にわたる \(D\) 個のインスタンスに変換する方法を備えています。この変種は、計算コストが高くなる代わりに署名が小さくなります。しきい値変種は [22] で初めて示されたもので、低しきい値の線形秘密分散を用い、証明者に \(N - 1\) 個ではなく、あるしきい値 \(l\) について \(l\) 個の参加者のビューのみを開示させます。

The security is based on the hardness of solving the \(d\)-split variant of the syndrome decoding problem for random linear codes over finite fields. When \(d = 1\), the \(d\)-split variant is equivalent to SDP, which is known to be NP-hard and whose security is believed to be well-understood. The original SDitH specification overestimated security by a few bits due to multiple solutions to the syndrome decoding instances. The parameter sets were updated to ensure that the number of expected solutions is below 1.1.

セキュリティは、有限体上のランダム線形符号に対するシンドローム復号問題の \(d\) 分割変種を解く困難性に基づきます。\(d = 1\) のとき、\(d\) 分割変種は SDP と等価であり、SDP は NP 困難であることが知られ、そのセキュリティは十分に理解されていると考えられています。元の SDitH 仕様は、シンドローム復号のインスタンスに複数の解があるため、セキュリティを数ビット過大に見積もっていました。パラメータセットは、期待される解の数が 1.1 を下回るように更新されました。

The overall performance of SDitH can be seen as outperforming SLH-DSA but not ML-DSA or Falcon. SDitH features very small keys with signature sizes that fall between the SLH-DSA “small” and “fast” parameter sets. Although SDitH is closely related to a known NP-hard problem, NIST believes SDitH can benefit from more security analysis. Overall, SDitH is competitive with the other MPCitH candidates.

SDitH の全体的な性能は、SLH-DSA を上回るが ML-DSA や Falcon には及ばないとみなせます。SDitH は非常に小さい鍵を持ち、署名サイズは SLH-DSA の「small」と「fast」のパラメータセットの中間にあります。SDitH は既知の NP 困難問題と密接に関連していますが、NIST は SDitH がさらなるセキュリティ解析の恩恵を受けられると考えています。全体として、SDitH は他の MPCitH 候補と競合できる水準にあります。

3.9. UOV

3.9. UOV

The Unbalanced Oil and Vinegar (UOV) digital signature scheme [23] is the oldest unbroken multivariate cryptosystem and was proposed in [24]. The construction of UOV is based on a system of quadratic equations for which there is a secret subspace on which the system evaluates to zero. This scheme offers EUF-CMA security following the hash-and-sign paradigm with this quadratic system and a salt using a construction similar to the one proposed by [25].

Unbalanced Oil and Vinegar(UOV)デジタル署名方式 [23] は、破られていない最古の多変数暗号システムであり、[24] で提案されました。UOV の構成は、評価値がゼロになる秘密の部分空間が存在する 2 次方程式系に基づきます。この方式は、この 2 次方程式系とソルトを用いて、[25] が提案したものに類似した構成によるハッシュ・署名(hash-and-sign)パラダイムに従い、EUF-CMA 安全性を提供します。

The performance advantages of UOV are its short signatures and very fast signing and verification speeds. UOV has also been a central object of study in multivariate cryptography for 25 years. However, a primary drawback of the scheme is the size of the public key. The submission package offers trade-offs between public key size and verification speed, but even the smaller public keys are quite large. For this reason, NIST anticipates that UOV will primarily be applied to applications that require small signatures, fast verification, and offline transmission of the key.

UOV の性能上の利点は、署名が短く、署名と検証が非常に高速なことです。UOV は 25 年にわたり、多変数暗号の中心的な研究対象でもあります。しかし、この方式の主な欠点は公開鍵のサイズです。提出パッケージは公開鍵サイズと検証速度のトレードオフを提供していますが、小さいほうの公開鍵でもかなり大きくなります。このため NIST は、UOV が主に、小さい署名、高速な検証、鍵のオフライン送信を必要とする用途に適用されると予想しています。

While UOV is a mature and fairly stable scheme, an attack in the last four years marginally reduced the security of some of its parameter regimes [26]. NIST recommends that the community remain vigilant and continue to critically analyze the security of UOV.

UOV は成熟したかなり安定した方式ですが、過去 4 年間に行われた攻撃により、一部のパラメータ領域のセキュリティがわずかに低下しました [26]。NIST は、コミュニティが警戒を続け、UOV のセキュリティを批判的に解析し続けることを推奨します。

3.10. MAYO

3.10. MAYO

MAYO [27] is a variant of UOV with smaller public keys made by “whipping” a very small quadratic map into a larger one with a UOV structure [28]. This very small quadratic map is denoted here as mini-UOV. Thus, MAYO key recovery reduces to finding mini-UOV oil space, and MAYO signature forgery reduces to trying to invert the whipped UOV-like map. Thanks to this extra structure, MAYO significantly improves the public key size relative to UOV while inheriting UOV’s small signature size. While it is not as fast as UOV, MAYO is still very efficient.

MAYO [27] は、非常に小さい 2 次写像を、UOV 構造を持つより大きな写像へ「ホイップ(whipping)」することで [28]、公開鍵を小さくした UOV の変種です。この非常に小さい 2 次写像は、ここでは mini-UOV と表記します。したがって、MAYO の鍵復元は mini-UOV のオイル空間を見つける問題に帰着し、MAYO の署名偽造は、ホイップされた UOV 類似の写像の逆写像を求めようとする問題に帰着します。この追加の構造により、MAYO は UOV の小さい署名サイズを引き継ぎつつ、UOV に比べて公開鍵サイズを大幅に改善しています。MAYO は UOV ほど高速ではありませんが、それでも非常に効率的です。

Recent results on solving underdetermined systems of multivariate equations [29] might slightly impact MAYO’s security [30]. However, NIST maintains interest in MAYO for its competitive performance and encourages further research to assess whether the additional structure makes MAYO vulnerable to cryptanalysis.

劣決定の多変数方程式系を解くことに関する最近の成果 [29] は、MAYO のセキュリティにわずかに影響する可能性があります [30]。しかし NIST は、MAYO の競争力のある性能を理由に引き続き関心を持っており、追加の構造によって MAYO が暗号解読に対して脆弱になるかどうかを評価するための、さらなる研究を推奨します。

3.11. QR-UOV

3.11. QR-UOV

QR-UOV [31] is a variant of UOV with smaller public keys by using quotient rings with techniques from [32]. Unlike UOV matrices whose elements belong to a finite field \(\mathbb{F}_q\), QR-UOV public matrices contain elements in a degree \(n\) field extension represented by a quotient ring. As a result, each \(n \times n\) block in the public key uses only \(n\) coefficients, where \(n^2\) would be needed in general. Thanks to this extra structure, QR-UOV public keys are 50 % smaller in comparison to UOV. While the performance of QR-UOV is slower than UOV, it is still competitive.

QR-UOV [31] は、[32] の技術を用いた商環により公開鍵を小さくした UOV の変種です。要素が有限体 \(\mathbb{F}_q\) に属する UOV の行列とは異なり、QR-UOV の公開行列は、商環で表される \(n\) 次の体拡大の要素を含みます。その結果、公開鍵内の各 \(n \times n\) ブロックは、一般には \(n^2\) 個必要なところ、わずか \(n\) 個の係数で済みます。この追加の構造により、QR-UOV の公開鍵は UOV と比べて 50 % 小さくなります。QR-UOV の性能は UOV より低速ですが、それでも競争力があります。

A previous attempt that relied on quotient rings was broken [33], and another candidate in the Additional Call for Digital Signatures that incorporated the same technique was also attacked [34, 35].

商環に依拠した以前の試みは破られており [33]、追加デジタル署名の提案募集における別の候補で、同じ技術を取り入れたものも攻撃を受けました [34, 35]。

NIST maintains interest in QR-UOV for its competitive performance, but the structure of QR-UOV requires further study. NIST anticipates that the performance could be improved and encourages the designers to further optimize their implementation.

NIST は、QR-UOV の競争力のある性能を理由に引き続き関心を持っていますが、QR-UOV の構造にはさらなる研究が必要です。NIST は性能が改善される余地があると見込んでおり、設計者が実装をさらに最適化することを推奨します。

3.12. SNOVA

3.12. SNOVA

The SNOVA construction utilizes the well-studied design of UOV and adds extra structure to reduce the public key size. The SNOVA submission [36] is based on the SNOVA signature scheme [37], which is a simplified version of the NOVA signature scheme [38] by the same authors.

SNOVA の構成は、十分に研究された UOV の設計を利用し、公開鍵サイズを小さくするために追加の構造を加えたものです。SNOVA の提出物 [36] は、同じ著者による NOVA 署名方式 [38] を簡略化した SNOVA 署名方式 [37] に基づいています。

SNOVA uses public matrices whose coefficients belong to a noncommutative ring, namely a ring of square matrices over a finite field. Thanks to this extra structure, SNOVA obtains significantly smaller public keys compared to UOV (comparable to or slightly smaller than those of MAYO) while still being relatively fast. SNOVA is a bit slower than MAYO but in the same range.

SNOVA は、係数が非可換環、すなわち有限体上の正方行列の環に属する公開行列を用います。この追加の構造により、SNOVA は UOV と比べて公開鍵を大幅に小さくしています(MAYO の公開鍵と同程度か、わずかに小さい)。それでも、SNOVA は比較的高速です。SNOVA は MAYO より少し低速ですが、同じ範囲にあります。

During the first round, SNOVA suffered an attack [39, 40] that affected some of the submitted parameter sets. In [41], SNOVA updated their parameters but then suffered a new attack [42]. Nonetheless, some of the submitted parameter sets of SNOVA survived both attacks, and it appears the remaining parameter sets can be patched to avoid the attacks with little effect on performance. Notably, the parameter sets that survived cryptanalysis were those with the smallest public keys for each security level.

第 1 ラウンドの間に、SNOVA は、提出されたパラメータセットの一部に影響する攻撃 [39, 40] を受けました。[41] で SNOVA はパラメータを更新しましたが、その後、新たな攻撃 [42] を受けました。それでも、SNOVA の提出されたパラメータセットの一部は両方の攻撃を免れており、残りのパラメータセットも、性能への影響を小さくしたままパッチを当てて攻撃を回避できるように見えます。特筆すべきことに、暗号解読を免れたパラメータセットは、各セキュリティレベルで公開鍵が最も小さいものでした。

The novelty of SNOVA and its history of attacks lead NIST to question its security even more so than the other structured-UOV schemes aimed at significantly reduced key size. Yet the fact that SNOVA still has unbroken parameter sets with the smallest public keys available for UOV-based schemes makes it an attractive candidate for continued study.

SNOVA の新規性と攻撃を受けてきた経緯から、NIST は、鍵サイズの大幅な削減を目指す他の構造化 UOV 方式よりも、そのセキュリティにいっそう疑問を持っています。しかし、SNOVA には、UOV ベースの方式で利用可能な最小の公開鍵を持つ、破られていないパラメータセットが依然としてあるため、引き続き研究する魅力的な候補となっています。

3.13. FAEST

3.13. FAEST

FAEST [43] is a digital signature scheme constructed via a relatively new technique called VOLEitH [44]. This technique is related to the MPCitH approach [45] used by several other signature schemes in the NIST post-quantum standardization process. Both MPCitH and VOLEitH can be used to construct digital signature schemes whose unforgeability relies only on the security of some symmetric-key cipher \(E\). In the case of FAEST, \(E\) is AES128, AES192, and AES256 for security levels 1, 3, and 5, respectively. A signing key of FAEST is then a key \(k\) of \(E\), and a corresponding verification key is a pair \((x, y)\) such that \(E_k(x) = y\).

FAEST [43] は、VOLEitH [44] と呼ばれる比較的新しい技術によって構成されたデジタル署名方式です。この技術は、NIST の耐量子標準化プロセスの他のいくつかの署名方式が用いる MPCitH のアプローチ [45] に関連しています。MPCitH と VOLEitH はどちらも、偽造不可能性が、ある共通鍵暗号 \(E\) のセキュリティのみに依存するデジタル署名方式の構成に使えます。FAEST では、\(E\) は、セキュリティレベル 1、3、5 に対してそれぞれ AES128、AES192、AES256 です。FAEST の署名鍵は \(E\) の鍵 \(k\) であり、対応する検証鍵は \(E_k(x) = y\) を満たす組 \((x, y)\) です。

Just as with MPCitH, VOLEitH involves constructing an interactive ZKPoK based on certain computations with shares of the signing key and then compiling that ZKPoK into a non-interactive scheme via the Fiat-Shamir paradigm [46]. However, the computations involving the shares of the signing key are significantly different in VOLEitH and MPCitH. In the case of VOLEitH, these computations are based on a certain two-party primitive called Vector Oblivious Linear Evaluation. This results in FAEST having significantly smaller signatures compared to similar MPCitH schemes [43]. Moreover, the public keys of FAEST are very small (i.e., between 32 and 64 bytes), and the key generation, signing, and verification speeds are all competitive.

MPCitH と同様に、VOLEitH では、署名鍵のシェアに関する特定の計算に基づいて対話型 ZKPoK を構成し、その ZKPoK を Fiat-Shamir パラダイム [46] によって非対話型の方式にコンパイルします。ただし、署名鍵のシェアに関する計算は、VOLEitH と MPCitH で大きく異なります。VOLEitH では、これらの計算は Vector Oblivious Linear Evaluation と呼ばれる特定の 2 者間プリミティブに基づきます。その結果、FAEST は類似の MPCitH 方式と比べて署名が大幅に小さくなっています [43]。さらに、FAEST の公開鍵は非常に小さく(すなわち 32 バイトから 64 バイト)、鍵生成、署名、検証の速度はいずれも競争力があります。

While the theoretical security of FAEST is based only on symmetric-key assumptions, its performance is significantly better than most other schemes with that property, including SLH-DSA [47]. However, the performance of FAEST is not competitive with lattice-based schemes, such as ML-DSA and FN-DSA. FAEST is thus a promising scheme for applications that do not require the performance provided by lattice-based signatures.

FAEST の理論上のセキュリティは共通鍵の仮定のみに基づいていますが、その性能は、SLH-DSA [47] を含む、その性質を持つほとんどの他の方式よりも大幅に優れています。ただし FAEST の性能は、ML-DSA や FN-DSA などの格子ベースの方式に対抗できるものではありません。したがって FAEST は、格子ベースの署名が提供する性能を必要としない用途にとって有望な方式です。

The core technique of VOLEitH that underlies FAEST was introduced in 2023 [44]. The construction is somewhat complex, and the security proof is very technical. New results are appearing frequently in this active area. As a result, FAEST might undergo modifications in the near future. More work is needed for the scheme to stabilize and for the general community of cryptographers and cryptanalysts to become deeply familiar with and confident in the technical aspects of FAEST.

FAEST の基礎となる VOLEitH の中核技術は、2023 年に導入されました [44]。その構成はやや複雑で、セキュリティ証明は非常に技術的です。この活発な分野では、新しい成果が頻繁に現れています。その結果、FAEST は近い将来、変更される可能性があります。この方式が安定し、暗号研究者や暗号解読者の一般のコミュニティが FAEST の技術的な側面に深く精通し、確信を持てるようになるには、さらなる取り組みが必要です。

3.14. SQIsign

3.14. SQIsign

SQIsign [48] is a unique signature scheme that is designed using isogeny graphs of elliptic curves. Like several other candidates, SQIsign uses the Fiat-Shamir paradigm to turn a zero-knowledge identification scheme into a signature scheme. Security is based on the knowledge of a secret elliptic curve isogeny.

SQIsign [48] は、楕円曲線の同種写像グラフを用いて設計された、独自の署名方式です。他のいくつかの候補と同様に、SQIsign は Fiat-Shamir パラダイムを用いて、ゼロ知識の識別方式を署名方式に変換します。セキュリティは、秘密の楕円曲線の同種写像の知識に基づきます。

There has been a lot of recent activity related to the security of isogeny-based cryptosystems. Most notably, the KEM candidate SIKE [49] was shown to be vulnerable to efficient attacks that completely undermined its security claims [50–53]. Attempts to patch the vulnerabilities were ineffective [54]. As a result, more study is needed to establish greater confidence in isogeny-based schemes. SQIsign relies upon a different hardness assumption than SIKE, and consequentially, the aforementioned attacks do not work on SQIsign. Specifically, SIKE included additional information about the secret isogeny (i.e., the image of certain points) that were needed for key establishment. SQIsign uses new techniques that do not require this extra information to be shared.

同種写像ベースの暗号システムのセキュリティに関しては、最近多くの動きがありました。最も注目すべきは、KEM 候補の SIKE [49] が、そのセキュリティの主張を完全に覆す効率的な攻撃に対して脆弱であることが示されたことです [50–53]。脆弱性にパッチを当てる試みは効果がありませんでした [54]。その結果、同種写像ベースの方式への確信を高めるには、さらなる研究が必要です。SQIsign は SIKE とは異なる困難性の仮定に依拠しているため、前述の攻撃は SQIsign には通用しません。具体的には、SIKE では鍵確立に必要な秘密の同種写像に関する追加情報(すなわち特定の点の像)を含めていました。SQIsign は、この追加情報を共有する必要がない新しい技術を用いています。

SQIsign has the smallest combined size of public keys and signature sizes of all of the first-round candidates and even both ML-DSA and Falcon. In terms of computational efficiency of signing and verifying, SQIsign is noticeably slower than many of the other candidates, although verification is much faster than signing. New variants of SQIsign have been proposed with improved performance and a stronger security assumption compared to the originally submitted version [55, 56].

SQIsign は、第 1 ラウンドのすべての候補、さらには ML-DSA と Falcon の中でも、公開鍵サイズと署名サイズの合計が最小です。署名と検証の計算効率では、SQIsign は他の多くの候補より著しく低速ですが、検証は署名よりはるかに高速です。当初の提出版と比べて、性能が向上し、より強いセキュリティ仮定を持つ SQIsign の新しい変種が提案されています [55, 56]。

SQIsign is a very new design, and as such, will need more evaluation and analysis. NIST hopes that more research will lead to further optimizations that improve the performance of SQIsign, although it seems unlikely that signing will ever be competitive to the signing times of ML-DSA. However, SQIsign differs greatly from every other signature candidate, improving the diversity of security assumptions and performance profiles for the standardization process. Therefore, NIST advanced SQIsign to the second round.

SQIsign は非常に新しい設計であり、そのためさらなる評価と解析が必要です。NIST は、研究が進めばさらなる最適化が行われて SQIsign の性能が向上することを期待していますが、署名が ML-DSA の署名時間に匹敵するようになる可能性は低いように思われます。しかし SQIsign は他のすべての署名候補と大きく異なり、標準化プロセスにおけるセキュリティの仮定と性能プロファイルの多様性を高めます。そのため NIST は、SQIsign を第 2 ラウンドに進めました。

4. Conclusion

4. 結論

The announcement of the 14 second-round candidates marks the start of the second round of the Additional Digital Signatures for the NIST PQC Standardization Process. This report summarized the evaluation criteria used to select these candidate algorithms, the basic designs of the second-round candidates, and their advantages and disadvantages. NIST greatly appreciates the participation in the NIST PQC Standardization Process.

14 件の第 2 ラウンド候補の発表は、NIST PQC 標準化プロセスにおける追加デジタル署名の第 2 ラウンドの開始を意味します。本報告書は、これらの候補アルゴリズムを選定するために用いた評価基準、第 2 ラウンド候補の基本設計、およびその長所と短所を要約しました。NIST は、NIST PQC 標準化プロセスへの参加に深く感謝します。

Submitters of the second-round candidates will be allowed to adjust and improve their submissions to fix inconsistencies, problems, or shortcomings in the specifications or source code. Any changes must be submitted to NIST by January 17, 2025, in a complete submission package, as defined in [2]. More details will be provided on the pqc-forum [57] and the webpage https://csrc.nist.gov/projects/pqc-dig-sig.

第 2 ラウンド候補の提出者は、仕様やソースコードの不整合、問題、欠点を修正するため、提出物を調整、改善することが認められます。変更は、[2] で定義された完全な提出パッケージとして、2025 年 1 月 17 日までに NIST に提出しなければなりません。詳細は、pqc-forum [57] とウェブページ https://csrc.nist.gov/projects/pqc-dig-sig で提供されます。

Over the next several months, NIST invites the cryptographic community to evaluate the 14 second-round signature candidates. Some of the second-round candidates have received little or no published cryptanalysis by the cryptographic community-at-large. With the number of candidates substantially reduced from the first round, we hope that the combined efforts of the cryptographic community will evaluate the remaining candidates and provide NIST with feedback that supports or refutes the security claims of the submitters. NIST is also interested in additional performance data on each of the candidates, including optimized implementations written in assembly code or using instruction set extensions as well as analyses of the implementation suitability of candidate algorithms in constrained platforms and performance data for hardware implementations.

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

NIST plans to host another NIST PQC Standardization Conference in September 2025. Submitters of the second-round candidates will be invited to present their updated algorithms. In 2026, NIST plans to select finalists for a third round of evaluation. More detailed plans will be provided at a later date.

NIST は、2025 年 9 月に、もう 1 回 NIST PQC 標準化会議を開催する予定です。第 2 ラウンド候補の提出者は、更新したアルゴリズムを発表するよう招待されます。NIST は 2026 年に、第 3 ラウンドの評価に進める最終候補を選定する予定です。より詳細な計画は、後日提供されます。

References

参考文献

[1] 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

[1] 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

[2] 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.

[2] 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.

[3] Baldi M, Barenghi A, Bitzer S, Karl P, Manganiello F, Pavoni A, Pelosi G, Santini P, Schupp J, Slaughter F, Wachter-Zeh A, Weger V (2023) CROSS: Codes and Restricted Objects Signature Scheme, Submission to the NIST Post-Quantum Cryptography Standardization Process, Algorithm Specifications and Supporting Documentation. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/CROSS-spec-web.pdf.

[3] Baldi M, Barenghi A, Bitzer S, Karl P, Manganiello F, Pavoni A, Pelosi G, Santini P, Schupp J, Slaughter F, Wachter-Zeh A, Weger V (2023) CROSS: Codes and Restricted Objects Signature Scheme, Submission to the NIST Post-Quantum Cryptography Standardization Process, Algorithm Specifications and Supporting Documentation. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/CROSS-spec-web.pdf.

[4] Baldi M, Barenghi A, andJean François Biasse LB, Esser A, Gaj K, Mohajerani K, Pelosi G, Persichetti E, Saarinen MJO, Santini P, Wallace R (2023) LESS: Linear Equivalence Signature Scheme. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/less-spec-web.pdf.

[4] Baldi M, Barenghi A, and Jean François Biasse LB, Esser A, Gaj K, Mohajerani K, Pelosi G, Persichetti E, Saarinen MJO, Santini P, Wallace R (2023) LESS: Linear Equivalence Signature Scheme. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/less-spec-web.pdf.

[5] Chou T, Persichetti E, Santini P (2023) On Linear Equivalence, Canonical Forms, and Digital Signatures, Cryptology ePrint Archive preprint. Available at https://ia.cr/2023/1533.

[5] Chou T, Persichetti E, Santini P (2023) On Linear Equivalence, Canonical Forms, and Digital Signatures, Cryptology ePrint Archive preprint. 入手先: https://ia.cr/2023/1533.

[6] Bos JW, Bronchain O, Ducas L, Fehr S, Huang YH, Porning T, Postlethwaite EW, Prest T, Pulls LN, van Woerden W (2023) HAWK, version 1.0. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/hawk-spec-web.pdf.

[6] Bos JW, Bronchain O, Ducas L, Fehr S, Huang YH, Porning T, Postlethwaite EW, Prest T, Pulls LN, van Woerden W (2023) HAWK, version 1.0. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/hawk-spec-web.pdf.

[7] Aragon N, Bardet M, Bidoux L, Chi-Domínguez JJ, Dyseryn V, Feneuil T, Gaborit P, Neveu R, Rivain M, Tillich JP (2023) MIRA Specifications. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MIRA-spec-web.pdf.

[7] Aragon N, Bardet M, Bidoux L, Chi-Domínguez JJ, Dyseryn V, Feneuil T, Gaborit P, Neveu R, Rivain M, Tillich JP (2023) MIRA Specifications. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MIRA-spec-web.pdf.

[8] Adj G, Rivera-Zamarripa L, Verbel J, Bellini E, Barbero S, Esser A, Sanna C, Zweydinger F (2023) MiRitH (MinRank in the Head). Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MiRitH_spec-web.pdf.

[8] Adj G, Rivera-Zamarripa L, Verbel J, Bellini E, Barbero S, Esser A, Sanna C, Zweydinger F (2023) MiRitH (MinRank in the Head). 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MiRitH_spec-web.pdf.

[9] Aguilar-Melchor C, Gama N, Howe J, Hülsing A, Joseph D, Yue D (2022) The Return of the SDitH, Cryptology ePrint Archive preprint. https://ia.cr/2022/1645.

[9] Aguilar-Melchor C, Gama N, Howe J, Hülsing A, Joseph D, Yue D (2022) The Return of the SDitH, Cryptology ePrint Archive preprint. https://ia.cr/2022/1645.

[10] Rivain M (2024) Constructions for digital signatures part III: Threshold-computation-in-the-head. Available at https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/pqc-seminars/presentations/16-threshold-in-the-head-07022024.pdf.

[10] Rivain M (2024) Constructions for digital signatures part III: Threshold-computation-in-the-head. 入手先: https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/pqc-seminars/presentations/16-threshold-in-the-head-07022024.pdf.

[11] Bidoux L (2024) Merge of MIRA and MiRitH schemes, PQC-Forum Post. Available at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/pAEqDYwhXqM/m/lOved79qAQAJ.

[11] Bidoux L (2024) Merge of MIRA and MiRitH schemes, PQC-Forum Post. 入手先: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/pAEqDYwhXqM/m/lOved79qAQAJ.

[12] Feneuil T, Rivain M (2023) MQOM: MQ on my Mind, Algorithm Specifications and Supporting Documentation (Version 1.0). Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MQOM-spec-web.pdf.

[12] Feneuil T, Rivain M (2023) MQOM: MQ on my Mind, Algorithm Specifications and Supporting Documentation (Version 1.0). 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/MQOM-spec-web.pdf.

[13] Furue H, Kudo M (2024) Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings. Post-Quantum Cryptography: 15th International Workshop, PQCrypto 2024, Oxford, UK, June 12–14, 2024, Proceedings, Part II (Springer-Verlag, Berlin, Heidelberg), p 109–143. https://doi.org/10.1007/978-3-031-62746-0_6

[13] Furue H, Kudo M (2024) Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings. Post-Quantum Cryptography: 15th International Workshop, PQCrypto 2024, Oxford, UK, June 12–14, 2024, Proceedings, Part II (Springer-Verlag, Berlin, Heidelberg), p 109–143. https://doi.org/10.1007/978-3-031-62746-0_6

[14] Aaraj N, Bettaieb S, Bidoux L, Budroni A, Dyseryn V, Esser A, Gaborit P, Kulkarni M, Mateu V, Palumbi M, Perin L, Tillich JP (2023) PERK. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/PERK-spec-web.pdf.

[14] Aaraj N, Bettaieb S, Bidoux L, Budroni A, Dyseryn V, Esser A, Gaborit P, Kulkarni M, Mateu V, Palumbi M, Perin L, Tillich JP (2023) PERK. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/PERK-spec-web.pdf.

[15] Aragon N, Bardet M, Bidoux L, Chi-Domínguez JJ, Dyseryn V, Feneuil T, Gaborit P, Joux A, Rivain M, Tillich JP, Vinçotte A (2023) RYDE specifications. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/ryde-spec-web.pdf.

[15] Aragon N, Bardet M, Bidoux L, Chi-Domínguez JJ, Dyseryn V, Feneuil T, Gaborit P, Joux A, Rivain M, Tillich JP, Vinçotte A (2023) RYDE specifications. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/ryde-spec-web.pdf.

[16] Feneuil T (2024) Building MPCitH-Based Signatures from MQ, MinRank, and Rank SD. Applied Cryptography and Network Security, eds Pöpper C, Batina L (Springer Nature Switzerland, Cham), pp 403–431. https://doi.org/10.1007/978-3-031-54770-6_16

[16] Feneuil T (2024) Building MPCitH-Based Signatures from MQ, MinRank, and Rank SD. Applied Cryptography and Network Security, eds Pöpper C, Batina L (Springer Nature Switzerland, Cham), pp 403–431. https://doi.org/10.1007/978-3-031-54770-6_16

[17] Aguilar-Melchor C, Gama N, Howe J, Hülsing A, Joseph D, Yue D (2023) The Return of the SDitH. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V (Springer-Verlag, Berlin, Heidelberg), p 564–596. https://doi.org/10.1007/978-3-031-30589-4_20

[17] Aguilar-Melchor C, Gama N, Howe J, Hülsing A, Joseph D, Yue D (2023) The Return of the SDitH. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V (Springer-Verlag, Berlin, Heidelberg), p 564–596. https://doi.org/10.1007/978-3-031-30589-4_20

[18] Feneuil T, Rivain M (2022) Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head, Cryptology ePrint Archive preprint. https://ia.cr/2022/1407.

[18] Feneuil T, Rivain M (2022) Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head, Cryptology ePrint Archive preprint. https://ia.cr/2022/1407.

[19] Feneuil T, Rivain M (2023) Threshold Computation in the Head: Improved Framework for Post-Quantum Signatures and Zero-Knowledge Arguments, Cryptology ePrint Archive preprint. https://ia.cr/2023/1573.

[19] Feneuil T, Rivain M (2023) Threshold Computation in the Head: Improved Framework for Post-Quantum Signatures and Zero-Knowledge Arguments, Cryptology ePrint Archive preprint. https://ia.cr/2023/1573.

[20] Bidoux L, Feneuil T, Gaborit P, Neveu R, Rivain M (2024) Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank, Cryptology ePrint Archive preprint. https://ia.cr/2024/541.

[20] Bidoux L, Feneuil T, Gaborit P, Neveu R, Rivain M (2024) Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank, Cryptology ePrint Archive preprint. https://ia.cr/2024/541.

[21] Melchor CA, Feneuil T, Gama N, Gueron S, Howe J, Joseph D, Joux A, Persichetti E, Randrianarisoa TH, Rivain M, Yue D (2023) The Syndrome Decoding in the Head (SD-in-the-Head) Signature Scheme, Algorithm Specifications and Supporting Documentation – Version 1.0. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/SDitH-spec-web.pdf.

[21] Melchor CA, Feneuil T, Gama N, Gueron S, Howe J, Joseph D, Joux A, Persichetti E, Randrianarisoa TH, Rivain M, Yue D (2023) The Syndrome Decoding in the Head (SD-in-the-Head) Signature Scheme, Algorithm Specifications and Supporting Documentation – Version 1.0. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/SDitH-spec-web.pdf.

[22] Feneuil T, Joux A, Rivain M (2022) Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs. Advances in Cryptology – CRYPTO 2022, eds Dodis Y, Shrimpton T (Springer Nature Switzerland, Cham), pp 541–572. https://doi.org/10.1007/978-3-031-15979-4_19

[22] Feneuil T, Joux A, Rivain M (2022) Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs. Advances in Cryptology – CRYPTO 2022, eds Dodis Y, Shrimpton T (Springer Nature Switzerland, Cham), pp 541–572. https://doi.org/10.1007/978-3-031-15979-4_19

[23] Beullens W, Chen MS, Ding J, Gong B, Kannwischer MJ, Patarin J, Peng BY, Schmidt D, Shih CJ, Tao C, Yang BY (2023) UOV: Unbalanced Oil and Vinegar, Algorithm Specifications and Supporting Documentation, Version 1.0. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/UOV-spec-web.pdf.

[23] Beullens W, Chen MS, Ding J, Gong B, Kannwischer MJ, Patarin J, Peng BY, Schmidt D, Shih CJ, Tao C, Yang BY (2023) UOV: Unbalanced Oil and Vinegar, Algorithm Specifications and Supporting Documentation, Version 1.0. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/UOV-spec-web.pdf.

[24] Kipnis A, Patarin J, Goubin L (1999) Unbalanced Oil and Vinegar Signature Schemes. Advances in Cryptology — EUROCRYPT ’99, ed Stern J (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 206–222. https://doi.org/10.1007/3-540-48910-X_15

[24] Kipnis A, Patarin J, Goubin L (1999) Unbalanced Oil and Vinegar Signature Schemes. Advances in Cryptology — EUROCRYPT ’99, ed Stern J (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 206–222. https://doi.org/10.1007/3-540-48910-X_15

[25] Sakumoto K, Shirai T, Hiwatari H (2011) On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 68–82. https://doi.org/10.1007/978-3-642-25405-5_5

[25] Sakumoto K, Shirai T, Hiwatari H (2011) On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack. Post-Quantum Cryptography, ed Yang BY (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 68–82. https://doi.org/10.1007/978-3-642-25405-5_5

[26] Beullens W (2021) Improved Cryptanalysis of UOV and Rainbow. Advances in Cryptology – EUROCRYPT 2021, eds Canteaut A, Standaert FX (Springer International Publishing, Cham), pp 348–373. https://doi.org/10.1007/978-3-030-77870-5_13

[26] Beullens W (2021) Improved Cryptanalysis of UOV and Rainbow. Advances in Cryptology – EUROCRYPT 2021, eds Canteaut A, Standaert FX (Springer International Publishing, Cham), pp 348–373. https://doi.org/10.1007/978-3-030-77870-5_13

[27] Beullens W, Campos F, Celi S, Hess B, Kannwischer MJ (2023) MAYO. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/mayo-spec-web.pdf.

[27] Beullens W, Campos F, Celi S, Hess B, Kannwischer MJ (2023) MAYO. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/mayo-spec-web.pdf.

[28] Beullens W (2022) MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps. Selected Areas in Cryptography, eds AlTawy R, Hülsing A (Springer International Publishing, Cham), pp 355–376. https://doi.org/10.1007/978-3-030-99277-4_17

[28] Beullens W (2022) MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps. Selected Areas in Cryptography, eds AlTawy R, Hülsing A (Springer International Publishing, Cham), pp 355–376. https://doi.org/10.1007/978-3-030-99277-4_17

[29] Hashimoto Y (2023) An improvement of algorithms to solve under-defined systems of multivariate quadratic equations. JSIAM Letters 15:53–56. https://doi.org/10.14495/jsiaml.15.53

[29] Hashimoto Y (2023) An improvement of algorithms to solve under-defined systems of multivariate quadratic equations. JSIAM Letters 15:53–56. https://doi.org/10.14495/jsiaml.15.53

[30] Takeshi K, Beullens W (2024) Round 1 (Additional Signatures) OFFICIAL COMMENT: MAYO, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/MAYO-round1-dig-sig-official-comment.pdf.

[30] Takeshi K, Beullens W (2024) Round 1 (Additional Signatures) OFFICIAL COMMENT: MAYO, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/MAYO-round1-dig-sig-official-comment.pdf.

[31] Furue H, Ikematsu Y, Hoshino F, Takagi T, Yasuda K, Miyazawa T, Saito T, Nagai A (2023) QR-UOV. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/qruov-spec-web.pdf.

[31] Furue H, Ikematsu Y, Hoshino F, Takagi T, Yasuda K, Miyazawa T, Saito T, Nagai A (2023) QR-UOV. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/qruov-spec-web.pdf.

[32] Furue H, Ikematsu Y, Kiyomura Y, Takagi T (2021) A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV. Advances in Cryptology – ASIACRYPT 2021, eds Tibouchi M, Wang H (Springer International Publishing, Cham), pp 187–217. https://doi.org/10.1007/978-3-030-92068-5_7

[32] Furue H, Ikematsu Y, Kiyomura Y, Takagi T (2021) A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV. Advances in Cryptology – ASIACRYPT 2021, eds Tibouchi M, Wang H (Springer International Publishing, Cham), pp 187–217. https://doi.org/10.1007/978-3-030-92068-5_7

[33] Furue H, Kinjo K, Ikematsu Y, Wang Y, Takagi T (2020) A Structural Attack on Block-Anti-Circulant UOV at SAC 2019. Post-Quantum Cryptography, eds Ding J, Tillich JP (Springer International Publishing, Cham), pp 323–339. https://doi.org/10.1007/978-3-030-44223-1_18

[33] Furue H, Kinjo K, Ikematsu Y, Wang Y, Takagi T (2020) A Structural Attack on Block-Anti-Circulant UOV at SAC 2019. Post-Quantum Cryptography, eds Ding J, Tillich JP (Springer International Publishing, Cham), pp 323–339. https://doi.org/10.1007/978-3-030-44223-1_18

[34] Furue H (2023) Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/VOX-round1-dig-sig-official-comment.pdf.

[34] Furue H (2023) Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/VOX-round1-dig-sig-official-comment.pdf.

[35] Guo H, Jin Y, Pan Y, He X, Gong B, Ding J (2024) Practical and Theoretical Cryptanalysis of VOX. Post-Quantum Cryptography, eds Saarinen MJ, Smith-Tone D (Springer Nature Switzerland, Cham), pp 186–208. https://doi.org/10.1007/978-3-031-62746-0_9

[35] Guo H, Jin Y, Pan Y, He X, Gong B, Ding J (2024) Practical and Theoretical Cryptanalysis of VOX. Post-Quantum Cryptography, eds Saarinen MJ, Smith-Tone D (Springer Nature Switzerland, Cham), pp 186–208. https://doi.org/10.1007/978-3-031-62746-0_9

[36] Wang LC, Chou CY, Ding J, Kuan YL, Li MS, Tseng BS, Tseng PE, Wang CC (2023) SNOVA, Proposal for NISTPQC: Digital Signature Schemes project. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/SNOVA-spec-web.pdf.

[36] Wang LC, Chou CY, Ding J, Kuan YL, Li MS, Tseng BS, Tseng PE, Wang CC (2023) SNOVA, Proposal for NISTPQC: Digital Signature Schemes project. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/SNOVA-spec-web.pdf.

[37] Wang LC, Tseng PE, Kuan YL, Chou CY (2022) A Simple Noncommutative UOV Scheme, Cryptology ePrint Archive preprint. Available at https://ia.cr/2022/1742.

[37] Wang LC, Tseng PE, Kuan YL, Chou CY (2022) A Simple Noncommutative UOV Scheme, Cryptology ePrint Archive preprint. 入手先: https://ia.cr/2022/1742.

[38] Wang LC, Tseng PE, Kuan YL, Chou CY (2022) NOVA, a Noncommutative-ring Based Unbalanced Oil and Vinegar Signature Scheme with Key-randomness Alignment, Cryptology ePrint Archive preprint. Available at https://ia.cr/2022/665.

[38] Wang LC, Tseng PE, Kuan YL, Chou CY (2022) NOVA, a Noncommutative-ring Based Unbalanced Oil and Vinegar Signature Scheme with Key-randomness Alignment, Cryptology ePrint Archive preprint. 入手先: https://ia.cr/2022/665.

[39] Ikematsu Y, Akiyama R (2024) Revisiting the security analysis of SNOVA. Proceedings of the 11th ACM Asia Public-Key Cryptography Workshop APKC ’24 (Association for Computing Machinery, New York, NY, USA), p 54–61. https://doi.org/10.1145/3659467.3659900

[39] Ikematsu Y, Akiyama R (2024) Revisiting the security analysis of SNOVA. Proceedings of the 11th ACM Asia Public-Key Cryptography Workshop APKC ’24 (Association for Computing Machinery, New York, NY, USA), p 54–61. https://doi.org/10.1145/3659467.3659900

[40] Li P, Ding J (2024) Cryptanalysis of the SNOVA Signature Scheme. Post-Quantum Cryptography, eds Saarinen MJ, Smith-Tone D (Springer Nature Switzerland, Cham), pp 79–91. https://doi.org/10.1007/978-3-031-62746-0_4

[40] Li P, Ding J (2024) Cryptanalysis of the SNOVA Signature Scheme. Post-Quantum Cryptography, eds Saarinen MJ, Smith-Tone D (Springer Nature Switzerland, Cham), pp 79–91. https://doi.org/10.1007/978-3-031-62746-0_4

[41] Team S (2024) Round 1 (Additional Signatures) OFFICIAL COMMENT: SNOVA, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/SNOVA-round1-dig-sig-official-comment.pdf.

[41] Team S (2024) Round 1 (Additional Signatures) OFFICIAL COMMENT: SNOVA, NIST PQC Forum. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/official-comments/SNOVA-round1-dig-sig-official-comment.pdf.

[42] Beullens W (2024) Improved Cryptanalysis of SNOVA, Cryptology ePrint Archive preprint. Available at https://ia.cr/2024/1297.

[42] Beullens W (2024) Improved Cryptanalysis of SNOVA, Cryptology ePrint Archive preprint. 入手先: https://ia.cr/2024/1297.

[43] Baum C, Braun L, de Saint Guilhem CD, Klooß M, Majenz C, Mukherjee S, Ramacher S, Rechberger C, Orsini E, Roy L, Scholl P (2023) FAEST: Algorithm Specifications, Version 1.0. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/FAEST-spec-web.pdf.

[43] Baum C, Braun L, de Saint Guilhem CD, Klooß M, Majenz C, Mukherjee S, Ramacher S, Rechberger C, Orsini E, Roy L, Scholl P (2023) FAEST: Algorithm Specifications, Version 1.0. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/FAEST-spec-web.pdf.

[44] Baum C, Braun L, de Saint Guilhem CD, Klooß M, Orsini E, Roy L, Scholl P (2023) Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head. Advances in Cryptology – CRYPTO 2023, eds Handschuh H, Lysyanskaya A (Springer Nature Switzerland, Cham), pp 581–615. https://doi.org/10.1007/978-3-031-38554-4_19

[44] Baum C, Braun L, de Saint Guilhem CD, Klooß M, Orsini E, Roy L, Scholl P (2023) Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head. Advances in Cryptology – CRYPTO 2023, eds Handschuh H, Lysyanskaya A (Springer Nature Switzerland, Cham), pp 581–615. https://doi.org/10.1007/978-3-031-38554-4_19

[45] Ishai Y, Kushilevitz E, Ostrovsky R, Sahai A (2007) Zero-Knowledge from Secure Multi-party Computation. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing STOC ’07 (Association for Computing Machinery, New York, NY, USA), p 21–30. https://doi.org/10.1145/1250790.1250794

[45] Ishai Y, Kushilevitz E, Ostrovsky R, Sahai A (2007) Zero-Knowledge from Secure Multi-party Computation. Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing STOC ’07 (Association for Computing Machinery, New York, NY, USA), p 21–30. https://doi.org/10.1145/1250790.1250794

[46] Fiat A, Shamir A (1987) How To Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology — CRYPTO’ 86, ed Odlyzko AM (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 186–194. https://doi.org/10.1007/3-540-47721-7_12

[46] Fiat A, Shamir A (1987) How To Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology — CRYPTO’ 86, ed Odlyzko AM (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 186–194. https://doi.org/10.1007/3-540-47721-7_12

[47] 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

[47] 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

[48] Chavez-Saab J, Santos MCR, de Feo L, Eriksen JK, Hess B, Kohel D, Leroux A, Meyer M, Panny L, Patranabis S, Petit C, Henríquez FR, Schaeffler S, Wesolowski B (2022) SQISsign: Algorithm specifications and supporting documentation. Available at https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/sqisign-spec-web.pdf.

[48] Chavez-Saab J, Santos MCR, de Feo L, Eriksen JK, Hess B, Kohel D, Leroux A, Meyer M, Panny L, Patranabis S, Petit C, Henríquez FR, Schaeffler S, Wesolowski B (2022) SQISsign: Algorithm specifications and supporting documentation. 入手先: https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/sqisign-spec-web.pdf.

[49] Jao D, Azarderakhsh R, Campagna M, Costello C, de Feo L, Hess B, Hutchinson A, Jalali A, Karabina K, Koziel B, LaMacchia B, Longa P, Naehrig M, Pereira G, Renes J, Soukharev V, Urbanik D (2022) Supersingular Isogeny Key Encapsulation, Submission to the NIST’s post-quantum cryptography standardization process. Available at https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/submissions/SIKE-Round4.zip.

[49] Jao D, Azarderakhsh R, Campagna M, Costello C, de Feo L, Hess B, Hutchinson A, Jalali A, Karabina K, Koziel B, LaMacchia B, Longa P, Naehrig M, Pereira G, Renes J, Soukharev V, Urbanik D (2022) Supersingular Isogeny Key Encapsulation, Submission to the NIST’s post-quantum cryptography standardization process. 入手先: https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/round-4/submissions/SIKE-Round4.zip.

[50] 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/10.1007/978-3-031-30589-4_15

[50] 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/10.1007/978-3-031-30589-4_15

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

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

[52] 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/10.1007/978-3-031-30589-4_16

[52] 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/10.1007/978-3-031-30589-4_16

[53] 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/10.1007/978-3-031-30589-4_17

[53] 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/10.1007/978-3-031-30589-4_17

[54] 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/10.1007/978-981-99-8739-9_5

[54] 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/10.1007/978-981-99-8739-9_5

[55] Dartois P, Leroux A, Robert D, Wesolowski B (2024) SQIsignHD: New Dimensions in Cryptography. Advances in Cryptology – EUROCRYPT 2024, eds Joye M, Leander G (Springer Nature Switzerland, Cham), pp 3–32. https://doi.org/10.1007/978-3-031-58716-0_1

[55] Dartois P, Leroux A, Robert D, Wesolowski B (2024) SQIsignHD: New Dimensions in Cryptography. Advances in Cryptology – EUROCRYPT 2024, eds Joye M, Leander G (Springer Nature Switzerland, Cham), pp 3–32. https://doi.org/10.1007/978-3-031-58716-0_1

[56] Basso A, Feo LD, Dartois P, Leroux A, Maino L, Pope G, Robert D, Wesolowski B (2024) SQIsign2D-West: The Fast, the Small, and the Safer, Cryptology ePrint Archive preprint. https://ia.cr/2024/760.

[56] Basso A, Feo LD, Dartois P, Leroux A, Maino L, Pope G, Robert D, Wesolowski B (2024) SQIsign2D-West: The Fast, the Small, and the Safer, Cryptology ePrint Archive preprint. https://ia.cr/2024/760.

[57] (2024) NIST pqc-forum mailing list. Available at https://groups.google.com/a/list.nist.gov/g/pqc-forum.

[57] (2024) NIST pqc-forum mailing list. 入手先: https://groups.google.com/a/list.nist.gov/g/pqc-forum.

Appendix A. List of Symbols, Abbreviations, and Acronyms

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

DNSSEC Domain Name System Security Extensions

DNSSEC ドメインネームシステムセキュリティ拡張(Domain Name System Security Extensions)

DSS Digital Signature Standard

DSS デジタル署名標準(Digital Signature Standard)

EUF-CMA Existential Unforgeability under Chosen-Message Attack

EUF-CMA 適応的選択メッセージ攻撃に対する存在的偽造不可能性(Existential Unforgeability under Chosen-Message Attack)

FIPS Federal Information Processing Standards

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

FN-DSA FFT-Over-NTRU-Lattice-Based Digital Signature Algorithm; based on Falcon.

FN-DSA FFT-Over-NTRU-Lattice-Based Digital Signature Algorithm(FFTオーバーNTRU格子ベースデジタル署名アルゴリズム)。Falcon に基づきます。

IKE Internet Key Exchange

IKE インターネット鍵交換(Internet Key Exchange)

IPsec Internet Protocol Security

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

ITL Information Technology Laboratory

ITL 情報技術研究所(Information Technology Laboratory)

KEM Key-Encapsulation Mechanism

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

LEP Linear Equivalence Problem

LEP 線形同値問題(Linear Equivalence Problem)

ML-DSA Module-Lattice-Based Digital Signature Algorithm; based on CRYSTALS-Dilithium.

ML-DSA モジュール格子ベースデジタル署名アルゴリズム。CRYSTALS-Dilithium に基づきます。

ML-KEM Module-Lattice-Based Digital Signature Algorithm; based on CRYSTALS-Kyber.

ML-KEM モジュール格子ベース鍵カプセル化メカニズム。CRYSTALS-Kyber に基づきます。

MPC Multi-Party Computation

MPC マルチパーティ計算(Multi-Party Computation)

MPCith Multi-Party Computation in the Head

MPCith マルチパーティ計算のインザヘッド(Multi-Party Computation in the Head)

NIST National Institute of Standards and Technology

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

NISTIR NIST Interagency or Internal Report

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

omSVP One More Shortest Vector Problem

omSVP もう一つの最短ベクトル問題(One More Shortest Vector Problem)

OCSP Online Certificate Status Protocol

OCSP オンライン証明書ステータスプロトコル(Online Certificate Status Protocol)

PQC Post-Quantum Cryptography

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

R-SDP Restricted Syndrome Decoding Problem

R-SDP 制限付きシンドローム復号問題(Restricted Syndrome Decoding Problem)

R-SDP(G) Restricted Syndrome Decoding Problem with subgroup G

R-SDP(G) 部分群 G を伴う制限付きシンドローム復号問題(Restricted Syndrome Decoding Problem with subgroup G)

SDP Syndrome Decoding Problem

SDP シンドローム復号問題(Syndrome Decoding Problem)

SLH-DSA Stateless Hash-Based Digital Signature Algorithm; based on SPHINCS+.

SLH-DSA ステートレスハッシュベースデジタル署名アルゴリズム。SPHINCS+ に基づきます。

smLIP Search Module Lattice Isomorphism Problem

smLIP 探索モジュール格子同型問題(Search Module Lattice Isomorphism Problem)

SP Special Publication

SP 特別刊行物(Special Publication)

SSH Secure Shell

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

TLS Transport Layer Security

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

UOV Unbalanced Oil and Vinegar

UOV 非均衡オイル・アンド・ビネガー(Unbalanced Oil and Vinegar)

VOLEitH Vector Oblivious Linear Evaluation in the Head

VOLEitH ヘッド内ベクトル秘匿線形評価(Vector Oblivious Linear Evaluation in the Head)

ZKPoK Zero-Knowledge Proof of Knowledge

ZKPoK 知識のゼロ知識証明(Zero-Knowledge Proof of Knowledge)