[要約] RFC 8391は、XMSS: eXtended Merkle Signature Scheme（拡張メルクル署名方式）に関する文書です。これは、量子コンピュータの出現によって従来の公開鍵暗号が脆弱になる可能性に対処するための、量子耐性のある署名スキームを提供します。主に長期的なセキュリティが必要なシステムや、将来的に量子コンピュータによる攻撃から保護する必要がある通信に利用されます。関連するRFCとしては、RFC 8554（LMS: Leighton-Micali署名）があり、これも量子耐性のある署名方式に関するものです。
Internet Research Task Force (IRTF) A. Huelsing
Request for Comments: 8391 TU Eindhoven
Category: Informational D. Butin
ISSN: 2070-1721 TU Darmstadt
S. Gazdag
genua GmbH
J. Rijneveld
Radboud University
A. Mohaisen
University of Central Florida
May 2018
XMSS: eXtended Merkle Signature Scheme
XMSS：拡張マークル署名スキーム
Abstract
概要
This note describes the eXtended Merkle Signature Scheme (XMSS), a hash-based digital signature system that is based on existing descriptions in scientific literature. This note specifies Winternitz One-Time Signature Plus (WOTS+), a one-time signature scheme; XMSS, a single-tree scheme; and XMSS^MT, a multi-tree variant of XMSS. Both XMSS and XMSS^MT use WOTS+ as a main building block. XMSS provides cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that it only relies on the properties of cryptographic hash functions. XMSS provides strong security guarantees and is even secure when the collision resistance of the underlying hash function is broken. It is suitable for compact implementations, is relatively simple to implement, and naturally resists side-channel attacks. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers.
このノートでは、科学文献の既存の説明に基づいたハッシュベースのデジタル署名システムであるeXtended Merkle Signature Scheme（XMSS）について説明します。このメモは、ワンタイム署名方式であるWinternitzワンタイム署名プラス（WOTS +）を指定しています。 XMSS、単一ツリースキーム。 XMSS ^ MT、XMSSのマルチツリーバリアント。 XMSSとXMSS ^ MTはどちらも、WOTS +をメインの構成要素として使用します。 XMSSは、数学的問題の推測される困難さに依存することなく、暗号化デジタル署名を提供します。代わりに、暗号化ハッシュ関数のプロパティのみに依存することが証明されています。 XMSSは強力なセキュリティ保証を提供し、基盤となるハッシュ関数の衝突抵抗が壊れた場合でも安全です。コンパクトな実装に適しており、実装が比較的簡単で、当然サイドチャネル攻撃に耐性があります。他のほとんどの署名システムとは異なり、ハッシュベースの署名はこれまでのところ、量子コンピュータを使用した既知の攻撃に耐えることができます。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for informational purposes.
このドキュメントはInternet Standards Trackの仕様ではありません。情報提供を目的として公開されています。
This document is a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development activities. These results might not be suitable for deployment. This RFC represents the consensus of the Crypto Forum Research Group of the Internet Research Task Force (IRTF). Documents approved for publication by the IRSG are not candidates for any level of Internet Standard; see Section 2 of RFC 7841.
この文書は、Internet Research Task Force（IRTF）の製品です。 IRTFは、インターネット関連の研究開発活動の結果を公開しています。これらの結果は、展開に適さない可能性があります。このRFCは、インターネット研究タスクフォース（IRTF）の暗号フォーラム研究グループの合意を表します。 IRSGによる公開が承認されたドキュメントは、どのレベルのインターネット標準の候補にもなりません。 RFC 7841のセクション2をご覧ください。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc8391.
このドキュメントの現在のステータス、エラータ、およびフィードバックの提供方法に関する情報は、https：//www.rfc-editor.org/info/rfc8391で入手できます。
Copyright Notice
著作権表示
Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved.
Copyright（c）2018 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
この文書は、BCP 78およびIETF文書に関するIETFトラストの法的規定（https://trustee.ietf.org/license-info）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。
Table of Contents
目次
1. Introduction ....................................................5
1.1. CFRG Note on Post-Quantum Cryptography .....................6
1.2. Conventions Used in This Document ..........................7
2. Notation ........................................................7
2.1. Data Types .................................................7
2.2. Functions ..................................................7
2.3. Operators ..................................................8
2.4. Integer-to-Byte Conversion .................................9
2.5. Hash Function Address Scheme ...............................9
2.6. Strings of Base w Numbers .................................12
2.7. Member Functions ..........................................13
3. Primitives .....................................................14
3.1. WOTS+: One-Time Signatures ................................14
3.1.1. WOTS+ Parameters ...................................14
3.1.1.1. WOTS+ Functions ...........................15
3.1.2. WOTS+ Chaining Function ............................15
3.1.3. WOTS+ Private Key ..................................16
3.1.4. WOTS+ Public Key ...................................17
3.1.5. WOTS+ Signature Generation .........................17
3.1.6. WOTS+ Signature Verification .......................19
3.1.7. Pseudorandom Key Generation ........................20
4. Schemes ........................................................20
4.1. XMSS: eXtended Merkle Signature Scheme ....................20
4.1.1. XMSS Parameters ....................................21
4.1.2. XMSS Hash Functions ................................22
4.1.3. XMSS Private Key ...................................22
4.1.4. Randomized Tree Hashing ............................23
4.1.5. L-Trees ............................................23
4.1.6. TreeHash ...........................................24
4.1.7. XMSS Key Generation ................................25
4.1.8. XMSS Signature .....................................27
4.1.9. XMSS Signature Generation ..........................28
4.1.10. XMSS Signature Verification .......................30
4.1.11. Pseudorandom Key Generation .......................32
4.1.12. Free Index Handling and Partial Private Keys ......33
4.2. XMSS^MT: Multi-Tree XMSS ..................................33
4.2.1. XMSS^MT Parameters .................................33
4.2.2. XMSS^MT Key Generation .............................33
4.2.3. XMSS^MT Signature ..................................36
4.2.4. XMSS^MT Signature Generation .......................37
4.2.5. XMSS^MT Signature Verification .....................39
4.2.6. Pseudorandom Key Generation ........................40
4.2.7. Free Index Handling and Partial Private Keys .......40
5. Parameter Sets .................................................40
5.1. Implementing the Functions ................................41
5.2. WOTS+ Parameters ..........................................43
5.3. XMSS Parameters ...........................................43
5.3.1. Parameter Guide ....................................44
5.4. XMSS^MT Parameters ........................................45
5.4.1. Parameter Guide ....................................47
6. Rationale ......................................................49
7. Reference Code .................................................50
8. IANA Considerations ............................................50
9. Security Considerations ........................................54
9.1. Security Proofs ...........................................55
9.2. Minimal Security Assumptions ..............................56
9.3. Post-Quantum Security .....................................56
10. References ....................................................57
10.1. Normative References .....................................57
10.2. Informative References ...................................58
Appendix A. WOTS+ XDR Formats ....................................60
A.1. WOTS+ Parameter Sets ......................................60
A.2. WOTS+ Signatures ..........................................60
A.3. WOTS+ Public Keys .........................................61
Appendix B. XMSS XDR Formats .....................................61
B.1. XMSS Parameter Sets .......................................61
B.2. XMSS Signatures ...........................................62
B.3. XMSS Public Keys ..........................................64
Appendix C. XMSS^MT XDR Formats ..................................65
C.1. XMSS^MT Parameter Sets ....................................65
C.2. XMSS^MT Signatures ........................................67
C.3. XMSS^MT Public Keys .......................................71
Acknowledgements ..................................................73
Authors' Addresses ................................................74
A (cryptographic) digital signature scheme provides asymmetric message authentication. The key generation algorithm produces a key pair consisting of a private and a public key. A message is signed using a private key to produce a signature. A message/signature pair can be verified using a public key. A One-Time Signature (OTS) scheme allows using a key pair to sign exactly one message securely. A Many-Time Signature (MTS) system can be used to sign multiple messages.
（暗号）デジタル署名スキームは、非対称メッセージ認証を提供します。鍵生成アルゴリズムは、秘密鍵と公開鍵で構成される鍵ペアを生成します。メッセージは、秘密鍵を使用して署名され、署名を生成します。メッセージ/署名のペアは、公開鍵を使用して検証できます。ワンタイム署名（OTS）スキームでは、キーペアを使用して1つのメッセージに安全に署名できます。複数回署名（MTS）システムを使用して、複数のメッセージに署名できます。
OTS schemes, and MTS schemes composed from them, were proposed by Merkle in 1979 [Merkle83]. They were well-studied in the 1990s and have regained interest from the mid 2000s onwards because of their resistance against quantum-computer-aided attacks. These kinds of signature schemes are called hash-based signature schemes as they are built out of a cryptographic hash function. Hash-based signature schemes generally feature small private and public keys as well as fast signature generation and verification; however, they also feature large signatures and relatively slow key generation. In addition, they are suitable for compact implementations that benefit various applications and are naturally resistant to most kinds of side-channel attacks.
OTSスキーム、およびそれらから構成されるMTSスキームは、1979年にMerkleによって提案されました[Merkle83]。彼らは1990年代によく研究され、量子コンピュータ支援攻撃に対する抵抗力のために2000年代半ば以降から関心を取り戻しました。これらの種類の署名スキームは、暗号化ハッシュ関数から構築されるため、ハッシュベースの署名スキームと呼ばれます。ハッシュベースの署名スキームは、通常、小さな秘密鍵と公開鍵、および高速な署名の生成と検証を特徴としています。ただし、署名が大きく、キー生成が比較的遅いことも特徴です。さらに、さまざまなアプリケーションにメリットをもたらすコンパクトな実装に適しており、ほとんどの種類のサイドチャネル攻撃に対して自然に耐性があります。
Some progress has already been made toward introducing and standardizing hash-based signatures. Buchmann, Dahmen, and Huelsing proposed the eXtended Merkle Signature Scheme (XMSS) [BDH11], which offers better efficiency than Merkle's original scheme and a modern security proof in the standard model. McGrew, Curcio, and Fluhrer authored an Internet-Draft [MCF18] specifying the Leighton-Micali Signature (LMS) scheme, which builds on the seminal works by Lamport, Diffie, Winternitz, and Merkle, taking a different approach than XMSS and relying entirely on security arguments in the random oracle model. Very recently, the stateless hash-based signature scheme SPHINCS was introduced [BHH15], with the intent of being easier to deploy in current applications. A reasonable next step toward introducing hash-based signatures is to complete the specifications of the basic algorithms -- LMS, XMSS, SPHINCS, and/or variants.
ハッシュベースの署名の導入と標準化に向けて、すでにいくつかの進歩がありました。 Buchmann、Dahmen、Huelsingは、拡張されたマークル署名方式（XMSS）[BDH11]を提案しました。 McGrew、Curcio、およびFluhrerは、Limport、Diffie、Winternitz、およびMerkleによる独創的な作品に基づいて構築されたLeighton-Micali Signature（LMS）スキームを指定するInternet-Draft [MCF18]を作成し、XMSSとは異なるアプローチを採用し、完全に依存していますランダムオラクルモデルのセキュリティ引数について。ごく最近、ステートレスハッシュベースの署名スキームSPHINCSが導入され[BHH15]、現在のアプリケーションでの展開が容易になることを意図しています。ハッシュベースの署名を導入するための次のステップは、基本的なアルゴリズム（LMS、XMSS、SPHINCS、および/またはバリアント）の仕様を完成させることです。
The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest stateful hash-based signature scheme. It has the smallest signatures out of such schemes and comes with a multi-tree variant that solves the problem of slow key generation. Moreover, it can be shown that XMSS is secure, making only mild assumptions on the underlying hash function. In particular, it is not required that the cryptographic hash function is collision-resistant for the security of XMSS. Improvements upon XMSS, as described in [HRS16], are part of this note.
拡張マークル署名方式（XMSS）[BDH11]は、最新のステートフルハッシュベースの署名方式です。それはそのようなスキームの中で最小のシグネチャを持ち、遅いキー生成の問題を解決するマルチツリーバリアントが付属しています。さらに、XMSSは安全であり、基礎となるハッシュ関数については穏やかな仮定しかしていません。特に、暗号化ハッシュ関数がXMSSのセキュリティのために衝突耐性がある必要はありません。 [HRS16]で説明されているXMSSの改善は、このノートの一部です。
This document describes a single-tree and a multi-tree variant of XMSS. It also describes WOTS+, a variant of the Winternitz OTS scheme introduced in [Huelsing13] that is used by XMSS. The schemes are described with enough specificity to ensure interoperability between implementations.
このドキュメントでは、XMSSの単一ツリーと複数ツリーのバリアントについて説明します。また、XMSSで使用される[Huelsing13]で導入されたWinternitz OTSスキームの変形であるWOTS +についても説明します。スキームは、実装間の相互運用性を保証するのに十分な詳細度で説明されています。
This document is structured as follows. Notation is introduced in Section 2. Section 3 describes the WOTS+ signature system. MTS schemes are defined in Section 4: the eXtended Merkle Signature Scheme (XMSS) in Section 4.1 and its multi-tree variant (XMSS^MT) in Section 4.2. Parameter sets are described in Section 5. Section 6 describes the rationale behind choices in this note. Section 7 gives information about the reference code. The IANA registry for these signature systems is described in Section 8. Finally, security considerations are presented in Section 9.
このドキュメントは次のように構成されています。表記法はセクション2で紹介されています。セクション3では、WOTS +署名システムについて説明します。 MTSスキームはセクション4で定義されています：セクション4.1の拡張マークル署名スキーム（XMSS）とセクション4.2のマルチツリーバリアント（XMSS ^ MT）。パラメータセットについては、セクション5で説明します。セクション6では、この注記の選択の根拠について説明します。セクション7は、参照コードに関する情報を提供します。これらの署名システムのIANAレジストリについては、セクション8で説明します。最後に、セキュリティに関する考慮事項をセクション9で示します。
All post-quantum algorithms documented by the Crypto Forum Research Group (CFRG) are today considered ready for experimentation and further engineering development (e.g., to establish the impact of performance and sizes on IETF protocols). However, at the time of writing, we do not have significant deployment experience with such algorithms.
Crypto Forum Research Group（CFRG）によって文書化されたすべてのポスト量子アルゴリズムは、今日、実験およびさらなるエンジニアリング開発の準備ができていると見なされています（たとえば、IETFプロトコルに対するパフォーマンスとサイズの影響を確立するため）。ただし、執筆時点では、そのようなアルゴリズムを使用した展開に関する重要な経験はありません。
Many of these algorithms come with specific restrictions, e.g., change of classical interface or less cryptanalysis of proposed parameters than established schemes. CFRG has consensus that all documents describing post-quantum technologies include the above paragraph and a clear additional warning about any specific restrictions, especially as those might affect use or deployment of the specific scheme. That guidance may be changed over time via document updates.
これらのアルゴリズムの多くには、従来のインターフェースの変更や、確立されたスキームよりも提案されたパラメーターの解読性の低下など、特定の制限が伴います。 CFRGは、ポスト量子テクノロジーを説明するすべてのドキュメントに上記のパラグラフと特定のスキームの使用または展開に影響を与える可能性がある特定の制限に関する明確な追加警告が含まれていることに合意しています。そのガイダンスは、ドキュメントの更新を通じて時間の経過とともに変更される可能性があります。
Additionally, for XMSS:
さらに、XMSSの場合：
CFRG consensus is that we are confident in the cryptographic security of the signature schemes described in this document against quantum computers, given the current state of the research community's knowledge about quantum algorithms. Indeed, we are confident that the security of a significant part of the Internet could be made dependent on the signature schemes defined in this document, if developers take care of the following.
CFRGのコンセンサスは、量子アルゴリズムに対する研究コミュニティの知識の現状を考えると、量子コンピュータに対するこのドキュメントで説明されている署名方式の暗号セキュリティに自信があるということです。実際、インターネットの重要な部分のセキュリティは、開発者が次のことに注意を払えば、このドキュメントで定義されている署名方式に依存する可能性があると確信しています。
In contrast to traditional signature schemes, the signature schemes described in this document are stateful, meaning the secret key changes over time. If a secret key state is used twice, no cryptographic security guarantees remain. In consequence, it becomes feasible to forge a signature on a new message. This is a new property that most developers will not be familiar with and requires careful handling of secret keys. Developers should not use the schemes described here except in systems that prevent the reuse of secret key states.
従来の署名方式とは対照的に、このドキュメントで説明する署名方式はステートフルです。つまり、秘密鍵は時間とともに変化します。秘密鍵の状態が2回使用される場合、暗号化によるセキュリティの保証は残りません。その結果、新しいメッセージの署名を偽造することが可能になります。これは、ほとんどの開発者が慣れていない新しいプロパティであり、秘密鍵の慎重な処理が必要です。開発者は、秘密鍵の状態の再利用を防ぐシステムを除いて、ここで説明されているスキームを使用しないでください。
Note that the fact that the schemes described in this document are stateful also implies that classical APIs for digital signatures cannot be used without modification. The API MUST be able to handle a secret key state; in particular, this means that the API MUST allow to return an updated secret key state.
このドキュメントで説明されているスキームがステートフルであることは、デジタル署名用の従来のAPIを変更せずに使用できないことも意味していることに注意してください。 APIは秘密鍵の状態を処理できる必要があります。特に、これはAPIが更新された秘密鍵の状態を返すことを許可する必要があることを意味します。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.
キーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「NOT RECOMMENDED」、「MAY」、「OPTIONALこのドキュメントの「」は、BCP 14 [RFC2119] [RFC8174]で説明されているように解釈されます。
Bytes and byte strings are the fundamental data types. A byte is a sequence of eight bits. A single byte is denoted as a pair of hexadecimal digits with a leading "0x". A byte string is an ordered sequence of zero or more bytes and is denoted as an ordered sequence of hexadecimal characters with a leading "0x". For example, 0xe534f0 is a byte string of length 3. An array of byte strings is an ordered, indexed set starting with index 0 in which all byte strings have identical length. We assume big-endian representation for any data types or structures.
バイトとバイト文字列は、基本的なデータ型です。 1バイトは8ビットのシーケンスです。 1バイトは、先頭に「0x」が付いた16進数のペアとして表されます。バイト文字列は、0バイト以上の順序付けられたシーケンスであり、先頭に「0x」が付いた16進文字の順序付けられたシーケンスとして示されます。たとえば、0xe534f0は長さ3のバイト文字列です。バイト文字列の配列は、すべてのバイト文字列が同じ長さである、インデックス0で始まる順序付けされたインデックス付きセットです。すべてのデータ型または構造についてビッグエンディアン表現を想定しています。
If x is a non-negative real number, then we define the following functions:
xが負でない実数の場合、次の関数を定義します。
ceil(x): returns the smallest integer greater than or equal to x.
ceil（x）：x以上の最小の整数を返します。
floor(x): returns the largest integer less than or equal to x.
floor（x）：x以下の最大の整数を返します。
lg(x): returns the logarithm to base 2 of x.
lg（x）：xの2を底とする対数を返します。
When a and b are integers, mathematical operators are defined as follows:
aとbが整数の場合、数学演算子は次のように定義されます。
^ : a ^ b denotes the result of a raised to the power of b.
^：a ^ bは、bの累乗の結果を示します。
* : a * b denotes the product of a and b. This operator is sometimes omitted in the absence of ambiguity, as in usual mathematical notation.
* ：a * bは、aとbの積を示します。この演算子は、通常の数学表記のように、あいまいさがなければ省略されることがあります。
/ : a / b denotes the quotient of a by non-zero b.
/：a / bは、非ゼロbによるaの商を示します。
% : a % b denotes the non-negative remainder of the integer division of a by b.
％：a％bは、aのbによる整数除算の負でない剰余を示します。
+ : a + b denotes the sum of a and b.
+ ：a + bは、aとbの合計を示します。
- : a - b denotes the difference of a and b.
- ：a-bは、aとbの差を示します。
++ : a++ denotes incrementing a by 1, i.e., a = a + 1.
++：a ++は、aを1ずつ増やすことを示します。つまり、a = a + 1です。
<< : a << b denotes a logical left shift with b being non-negative, i.e., a * 2^b.
<<：a << bは論理的な左シフトを示し、bは負ではありません。つまり、a * 2 ^ bです。
>> : a >> b denotes a logical right shift with b being non-negative, i.e., floor(a / 2^b).
>>：a >> bは論理的な右シフトを示し、bは負ではありません。つまり、floor（a / 2 ^ b）です。
The standard order of operations is used when evaluating arithmetic expressions.
演算式を評価するときは、演算の標準的な順序が使用されます。
Arrays are used in the common way, where the i^th element of an array A is denoted A[i]. Byte strings are treated as arrays of bytes where necessary: if X is a byte string, then X[i] denotes its i^th byte, where X[0] is the leftmost byte.
配列は一般的な方法で使用され、配列Aのi番目の要素はA [i]と表されます。バイト文字列は、必要に応じてバイトの配列として扱われます。Xがバイト文字列の場合、X [i]はそのi番目のバイトを示し、X [0]は左端のバイトです。
If A and B are byte strings of equal length, then:
AとBが同じ長さのバイト文字列の場合、次のようになります。
o A AND B denotes the bitwise logical conjunction operation.
o A AND Bは、ビット単位の論理結合演算を示します。
o A XOR B denotes the bitwise logical exclusive disjunction operation.
o XOR Bは、ビットごとの論理排他的論理和演算を示します。
When B is a byte and i is an integer, then B >> i denotes the logical right-shift operation.
Bがバイトでiが整数の場合、B >> iは論理右シフト演算を示します。
If X is an x-byte string and Y a y-byte string, then X || Y denotes the concatenation of X and Y, with X || Y = X[0] ... X[x-1] Y[0] ... Y[y-1].
Xがxバイト文字列で、Yがyバイト文字列の場合、X || YはXとYの連結を示し、X || Y = X [0] ... X [x-1] Y [0] ... Y [y-1]。
If x and y are non-negative integers, we define Z = toByte(x, y) to be the y-byte string containing the binary representation of x in big-endian byte order.
xとyが負でない整数の場合、Z = toByte（x、y）を、ビッグエンディアンバイトオーダーでxのバイナリ表現を含むyバイト文字列として定義します。
The schemes described in this document randomize each hash function call. This means that aside from the initial message digest, a different key and different bitmask is used for each hash function call. These values are pseudorandomly generated using a pseudorandom function that takes a key SEED and a 32-byte address ADRS as input and outputs an n-byte value, where n is the security parameter. Here we explain the structure of address ADRS and propose setter methods to manipulate the address. We explain the generation of the addresses in the following sections where they are used.
このドキュメントで説明するスキームは、各ハッシュ関数呼び出しをランダム化します。つまり、最初のメッセージダイジェストは別として、ハッシュ関数の呼び出しごとに異なるキーと異なるビットマスクが使用されます。これらの値は、キーSEEDおよび32バイトのアドレスADRSを入力として受け取り、nバイトの値を出力する疑似ランダム関数を使用して疑似ランダムに生成されます。ここで、nはセキュリティパラメーターです。ここでは、アドレスADRSの構造を説明し、アドレスを操作するセッターメソッドを提案します。アドレスの生成については、以下のセクションで使用されています。
The schemes in the next two sections use two kinds of hash functions parameterized by security parameter n. For the hash tree constructions, a hash function that maps an n-byte key and 2n-byte inputs to n-byte outputs is used. To randomize this function, 3n bytes are needed -- n bytes for the key and 2n bytes for a bitmask. For the OTS scheme constructions, a hash function that maps n-byte keys and n-byte inputs to n-byte outputs is used. To randomize this function, 2n bytes are needed -- n bytes for the key and n bytes for a bitmask. Consequently, three addresses are needed for the first function and two addresses for the second one.
次の2つのセクションのスキームでは、セキュリティパラメータnでパラメータ化された2種類のハッシュ関数を使用します。ハッシュツリーの構築には、nバイトのキーと2nバイトの入力をnバイトの出力にマップするハッシュ関数が使用されます。この関数をランダム化するには、3nバイトが必要です。キーにはnバイト、ビットマスクには2nバイトです。 OTSスキームの構築では、nバイトのキーとnバイトの入力をnバイトの出力にマップするハッシュ関数が使用されます。この関数をランダム化するには、2nバイトが必要です。キーにはnバイト、ビットマスクにはnバイトです。したがって、最初の関数には3つのアドレスが必要で、2番目の関数には2つのアドレスが必要です。
There are three different types of addresses for the different use cases. One type is used for the hashes in OTS schemes, one is used for hashes within the main Merkle tree construction, and one is used for hashes in the L-trees. The latter is used to compress one-time public keys. All these types share as much format as possible. In the remainder of this section, we describe these types in detail.
さまざまなユースケースに対応する3種類のアドレスがあります。 1つのタイプはOTSスキームのハッシュに使用され、1つはメインのマークルツリー構造内のハッシュに使用され、もう1つはLツリーのハッシュに使用されます。後者は、1回限りの公開鍵の圧縮に使用されます。これらすべてのタイプは、可能な限り多くの形式を共有します。このセクションの残りの部分では、これらのタイプについて詳しく説明します。
The structure of an address complies with word borders, with a word being 32 bits long in this context. Only the tree address is too long to fit a single word, but it can fit a double word. An address is structured as follows. It always starts with a layer address of one word in the most significant bits, followed by a tree address of two words. Both addresses are needed for the multi-tree variant (see Section 4.2) and describe the position of a tree within a multi-tree. They are therefore set to zero in single-tree applications. For multi-tree hash-based signatures, the layer address describes the height of a tree within the multi-tree, starting from height zero for trees at the bottom layer. The tree address describes the position of a tree within a layer of a multi-tree starting with index zero for the leftmost tree. The next word defines the type of the address. It is set to 0 for an OTS address, to 1 for an L-tree address, and to 2 for a hash tree address. Whenever the type word of an address is changed, all following words should be initialized with 0 to prevent non-zero values in unused padding words.
アドレスの構造はワード境界に準拠しており、このコンテキストではワードは32ビット長です。ツリーのアドレスだけが長すぎて1ワードに収まりませんが、ダブルワードには適合します。アドレスは次のような構造になっています。常に最上位ビットの1ワードのレイヤーアドレスで始まり、その後に2ワードのツリーアドレスが続きます。両方のアドレスは、マルチツリーバリアント（セクション4.2を参照）に必要であり、マルチツリー内のツリーの位置を示します。したがって、それらは単一ツリーアプリケーションではゼロに設定されます。マルチツリーハッシュベースのシグネチャの場合、レイヤーアドレスはマルチツリー内のツリーの高さを表し、最下層のツリーの高さゼロから始まります。ツリーアドレスは、左端のツリーのインデックス0から始まるマルチツリーのレイヤー内のツリーの位置を示します。次の単語はアドレスのタイプを定義します。 OTSアドレスの場合は0、Lツリーアドレスの場合は1、ハッシュツリーアドレスの場合は2に設定されます。アドレスのタイプワードが変更されるときは常に、未使用のパディングワードでゼロ以外の値が発生しないように、後続のすべてのワードを0で初期化する必要があります。
We first describe the OTS address case. In this case, the type word is followed by an OTS address word that encodes the index of the OTS key pair within the tree. The next word encodes the chain address followed by a word that encodes the address of the hash function call within the chain. The last word, called keyAndMask, is used to generate two different addresses for one hash function call. The word is set to zero to generate the key. To generate the n-byte bitmask, the word is set to one.
最初にOTSアドレスのケースについて説明します。この場合、タイプワードの後には、ツリー内のOTSキーペアのインデックスをエンコードするOTSアドレスワードが続きます。次のワードはチェーンアドレスをエンコードし、その後にチェーン内のハッシュ関数呼び出しのアドレスをエンコードするワードが続きます。 keyAndMaskと呼ばれる最後の単語は、1つのハッシュ関数呼び出しに対して2つの異なるアドレスを生成するために使用されます。ワードはゼロに設定され、キーを生成します。 nバイトのビットマスクを生成するには、ワードを1に設定します。
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 0 (32 bits)|
+-------------------------+
| OTS address (32 bits)|
+-------------------------+
| chain address (32 bits)|
+-------------------------+
| hash address (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
An OTS Hash Address
OTSハッシュアドレス
We now discuss the L-tree case, which means that the type word is set to one. In that case, the type word is followed by an L-tree address word that encodes the index of the leaf computed with this L-tree. The next word encodes the height of the node being input for the next computation inside the L-tree. The following word encodes the index of the node at that height, inside the L-tree. This time, the last word, keyAndMask, is used to generate three different addresses for one function call. The word is set to zero to generate the key. To generate the most significant n bytes of the 2n-byte bitmask, the word is set to one. The least significant bytes are generated using the address with the word set to two.
次に、Lツリーの場合について説明します。これは、タイプワードが1に設定されていることを意味します。その場合、タイプワードの後には、このLツリーで計算されたリーフのインデックスをエンコードするLツリーアドレスワードが続きます。次の単語は、Lツリー内の次の計算のために入力されるノードの高さをエンコードします。次の単語は、Lツリー内のその高さにおけるノードのインデックスをエンコードします。今回は、最後の単語keyAndMaskを使用して、1つの関数呼び出しに対して3つの異なるアドレスを生成します。ワードはゼロに設定され、キーを生成します。 2nバイトのビットマスクの最上位nバイトを生成するには、ワードを1に設定します。最下位バイトは、ワードを2に設定したアドレスを使用して生成されます。
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 1 (32 bits)|
+-------------------------+
| L-tree address (32 bits)|
+-------------------------+
| tree height (32 bits)|
+-------------------------+
| tree index (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
An L-tree Address
Lツリーアドレス
We now describe the remaining type for the main tree hash addresses. In this case, the type word is set to two, followed by a zero padding of one word. The next word encodes the height of the tree node being input for the next computation, followed by a word that encodes the index of this node at that height. As for the L-tree addresses, the last word, keyAndMask, is used to generate three different addresses for one function call. The word is set to zero to generate the key. To generate the most significant n bytes of the 2n-byte bitmask, the word is set to one. The least significant bytes are generated using the address with the word set to two.
次に、メインツリーハッシュアドレスの残りのタイプについて説明します。この場合、タイプワードは2に設定され、その後に1ワードのゼロパディングが続きます。次の単語は、次の計算のために入力されるツリーノードの高さをエンコードし、その後にその高さでのこのノードのインデックスをエンコードする単語が続きます。 Lツリーアドレスについては、最後のワードkeyAndMaskを使用して、1つの関数呼び出しに対して3つの異なるアドレスを生成します。ワードはゼロに設定され、キーを生成します。 2nバイトのビットマスクの最上位nバイトを生成するには、ワードを1に設定します。最下位バイトは、ワードを2に設定したアドレスを使用して生成されます。
+-------------------------+
| layer address (32 bits)|
+-------------------------+
| tree address (64 bits)|
+-------------------------+
| type = 2 (32 bits)|
+-------------------------+
| Padding = 0 (32 bits)|
+-------------------------+
| tree height (32 bits)|
+-------------------------+
| tree index (32 bits)|
+-------------------------+
| keyAndMask (32 bits)|
+-------------------------+
A Hash Tree Address
ハッシュツリーアドレス
All fields within these addresses encode unsigned integers. When describing the generation of addresses we use setter methods that take positive integers and set the bits of a field to the binary representation of that integer of the length of the field. We furthermore assume that the setType() method sets the four words following the type word to zero.
これらのアドレス内のすべてのフィールドは、符号なし整数をエンコードします。アドレスの生成を説明するとき、正の整数を取り、フィールドのビットをフィールドの長さのその整数のバイナリ表現に設定するセッターメソッドを使用します。さらに、setType()メソッドはタイプワードに続く4つのワードをゼロに設定すると仮定します。
A byte string can be considered as a string of base w numbers, i.e., integers in the set {0, ... , w - 1}. The correspondence is defined by the function base_w(X, w, out_len) (Algorithm 1) as follows. If X is a len_X-byte string, and w is a member of the set {4, 16}, then base_w(X, w, out_len) outputs an array of out_len integers between 0 and w - 1. The length out_len is REQUIRED to be less than or equal to 8 * len_X / lg(w).
バイト文字列は、基数wの文字列、つまりセット{0、...、w-1}の整数と見なすことができます。対応は、関数base_w（X、w、out_len）（アルゴリズム1）によって次のように定義されます。 Xがlen_Xバイトの文字列で、wがセット{4、16}のメンバーである場合、base_w（X、w、out_len）は、0からw-1までのout_len整数の配列を出力します。長さout_lenが必要です8 * len_X / lg（w）以下であること。
Algorithm 1: base_w
アルゴリズム1：base_w
Input: len_X-byte string X, int w, output length out_len Output: out_len int array basew
入力：len_Xバイトの文字列X、int w、出力長out_len出力：out_len int配列basew
int in = 0;
int out = 0;
unsigned int total = 0;
int bits = 0;
int consumed;
for ( consumed = 0; consumed < out_len; consumed++ ) {
if ( bits == 0 ) {
total = X[in];
in++;
bits += 8;
}
bits -= lg(w);
basew[out] = (total >> bits) AND (w - 1);
out++;
}
return basew;
For example, if X is the (big-endian) byte string 0x1234, then
base_w(X, 16, 4) returns the array a = {1, 2, 3, 4}.
X (represented as bits)
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
X[0] | X[1]
X (represented as base 16 numbers)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
base_w(X, 16, 4)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
a[0] a[1] a[2] a[3]
base_w(X, 16, 3)
+-----------+-----------+-----------+
| 1 | 2 | 3 |
+-----------+-----------+-----------+
a[0] a[1] a[2]
base_w(X, 16, 2)
+-----------+-----------+
| 1 | 2 |
+-----------+-----------+
a[0] a[1]
Example
例
To simplify algorithm descriptions, we assume the existence of member functions. If a complex data structure like a public key PK contains a value X, then getX(PK) returns the value of X for this public key. Accordingly, setX(PK, X, Y) sets value X in PK to the value held by Y. Since camelCase is used for member function names, a value z may be referred to as Z in the function name, e.g., getZ.
アルゴリズムの説明を簡略化するために、メンバー関数の存在を想定しています。公開鍵PKなどの複雑なデータ構造に値Xが含まれている場合、getX（PK）はこの公開鍵のXの値を返します。したがって、setX（PK、X、Y）は、PKの値XをYが保持する値に設定します。キャメルケースはメンバー関数名に使用されるため、値zは、関数名でZと呼ばれることがあります（例：getZ）。
This section describes the WOTS+ system in a manner similar to that in [Huelsing13]. WOTS+ is an OTS scheme; while a private key can be used to sign any message, each private key MUST be used only once to sign a single message. In particular, if a private key is used to sign two different messages, the scheme becomes insecure.
このセクションでは、[Huelsing13]と同様の方法でWOTS +システムについて説明します。 WOTS +はOTSスキームです。秘密鍵は任意のメッセージの署名に使用できますが、各秘密鍵は1つのメッセージの署名に1回だけ使用する必要があります。特に、秘密鍵を使用して2つの異なるメッセージに署名する場合、このスキームは安全ではなくなります。
This section starts with an explanation of parameters. Afterwards, the so-called chaining function, which forms the main building block of the WOTS+ scheme, is explained. A description of the algorithms for key generation, signing, and verification follows. Finally, pseudorandom key generation is discussed.
このセクションは、パラメータの説明から始まります。その後、WOTS +スキームの主要なビルディングブロックを形成する、いわゆるチェーニング機能について説明します。鍵の生成、署名、および検証のアルゴリズムの説明を以下に示します。最後に、疑似ランダム鍵の生成について説明します。
WOTS+ uses the parameters n and w; they both take positive integer values. These parameters are summarized as follows:
WOTS +はパラメーターnおよびwを使用します。どちらも正の整数値を取ります。これらのパラメーターは次のように要約されます。
n: the message length as well as the length of a private key, public key, or signature element in bytes.
n：メッセージの長さ、および秘密鍵、公開鍵、または署名要素の長さ（バイト単位）。
w: the Winternitz parameter; it is a member of the set {4, 16}.
w：Winternitzパラメータ。セット{4、16}のメンバーです。
The parameters are used to compute values len, len_1, and len_2:
パラメータは、値len、len_1、およびlen_2を計算するために使用されます。
len: the number of n-byte string elements in a WOTS+ private key, public key, and signature. It is computed as len = len_1 + len_2, with len_1 = ceil(8n / lg(w)) and len_2 = floor(lg(len_1 * (w - 1)) / lg(w)) + 1.
len：WOTS +秘密鍵、公開鍵、および署名のnバイト文字列要素の数。これは、len = len_1 + len_2として計算され、len_1 = ceil（8n / lg（w））およびlen_2 = floor（lg（len_1 *（w-1））/ lg（w））+ 1です。
The value of n is determined by the cryptographic hash function used for WOTS+. The hash function is chosen to ensure an appropriate level of security. The value of n is the input length that can be processed by the signing algorithm. It is often the length of a message digest. The parameter w can be chosen from the set {4, 16}. A larger value of w results in shorter signatures but slower overall signing operations; it has little effect on security. Choices of w are limited to the values 4 and 16 since these values yield optimal trade-offs and easy implementation.
nの値は、WOTS +に使用される暗号化ハッシュ関数によって決定されます。ハッシュ関数は、適切なレベルのセキュリティを確保するために選択されます。 nの値は、署名アルゴリズムで処理できる入力長です。多くの場合、メッセージダイジェストの長さです。パラメータwは、セット{4、16}から選択できます。 wの値が大きいほど、署名は短くなりますが、全体的な署名操作は遅くなります。セキュリティにはほとんど影響しません。 wの選択は値4と16に制限されます。これらの値は、最適なトレードオフと簡単な実装をもたらすためです。
WOTS+ parameters are implicitly included in algorithm inputs as needed.
WOTS +パラメータは、必要に応じて暗黙的にアルゴリズム入力に含まれます。
The WOTS+ algorithm uses a keyed cryptographic hash function F. F accepts and returns byte strings of length n using keys of length n. More detail on specific instantiations can be found in Section 5. Security requirements on F are discussed in Section 9. In addition, WOTS+ uses a pseudorandom function PRF. PRF takes as input an n-byte key and a 32-byte index and generates pseudorandom outputs of length n. More detail on specific instantiations can be found in Section 5. Security requirements on PRF are discussed in Section 9.
WOTS +アルゴリズムは、キー付き暗号化ハッシュ関数Fを使用します。Fは、長さnのキーを使用して長さnのバイト文字列を受け入れて返します。特定のインスタンス化の詳細については、セクション5を参照してください。Fのセキュリティ要件については、セクション9で説明します。さらに、WOTS +は疑似ランダム関数PRFを使用します。 PRFは、nバイトのキーと32バイトのインデックスを入力として受け取り、長さがnの疑似ランダム出力を生成します。特定のインスタンス化の詳細については、セクション5を参照してください。PRFのセキュリティ要件については、セクション9で説明します。
The chaining function (Algorithm 2) computes an iteration of F on an n-byte input using outputs of PRF. It takes an OTS hash address as input. This address will have the first six 32-bit words set to encode the address of this chain. In each iteration, PRF is used to generate a key for F and a bitmask that is XORed to the intermediate result before it is processed by F. In the following, ADRS is a 32-byte OTS hash address as specified in Section 2.5 and SEED is an n-byte string. To generate the keys and bitmasks, PRF is called with SEED as key and ADRS as input. The chaining function takes as input an n-byte string X, a start index i, a number of steps s, as well as ADRS and SEED. The chaining function returns as output the value obtained by iterating F for s times on input X, using the outputs of PRF.
連鎖関数（アルゴリズム2）は、PRFの出力を使用して、nバイトの入力に対するFの反復を計算します。入力としてOTSハッシュアドレスを取ります。このアドレスには、このチェーンのアドレスをエンコードするように設定された最初の6つの32ビットワードがあります。各反復で、PRFを使用して、Fのキーと、Fで処理される前に中間結果にXORされるビットマスクを生成します。以下では、ADRSは、セクション2.5およびSEEDで指定されている32バイトのOTSハッシュアドレスです。 nバイトの文字列です。キーとビットマスクを生成するために、SEEDをキー、ADRSを入力としてPRFが呼び出されます。連鎖関数は、nバイト文字列X、開始インデックスi、ステップ数s、およびADRSとSEEDを入力として受け取ります。連鎖関数は、PRFの出力を使用して、入力Xでs回Fを繰り返して得られた値を出力として返します。
Algorithm 2: chain - Chaining Function
アルゴリズム2：チェーン-関数のチェーン
Input: Input string X, start index i, number of steps s, seed SEED, address ADRS Output: value of F iterated s times on X
入力：入力文字列X、開始インデックスi、ステップ数s、シードSEED、アドレスADRS出力：Xで反復されたs回の値
if ( s == 0 ) {
return X;
}
if ( (i + s) > (w - 1) ) {
return NULL;
}
byte[n] tmp = chain(X, i, s - 1, SEED, ADRS);
ADRS.setHashAddress(i + s - 1);
ADRS.setKeyAndMask(0);
KEY = PRF(SEED, ADRS);
ADRS.setKeyAndMask(1);
BM = PRF(SEED, ADRS);
tmp = F(KEY, tmp XOR BM);
return tmp;
The private key in WOTS+, denoted by sk (s for secret), is a length len array of n-byte strings. This private key MUST be only used to sign at most one message. Each n-byte string MUST either be selected randomly from the uniform distribution or be selected using a cryptographically secure pseudorandom procedure. In the latter case, the security of the used procedure MUST at least match that of the WOTS+ parameters used. For a further discussion on pseudorandom key generation, see Section 3.1.7. The following pseudocode (Algorithm 3) describes an algorithm for generating sk.
WOTS +の秘密鍵は、sk（秘密の場合はs）で示され、nバイト文字列の長さlenの配列です。この秘密鍵は、最大で1つのメッセージの署名にのみ使用する必要があります。各nバイト文字列は、一様分布からランダムに選択するか、暗号的に安全な疑似ランダム手順を使用して選択する必要があります。後者の場合、使用されるプロシージャのセキュリティは、使用されるWOTS +パラメータのセキュリティと少なくとも一致する必要があります。疑似ランダムキー生成の詳細については、セクション3.1.7を参照してください。次の疑似コード（アルゴリズム3）は、skを生成するアルゴリズムを示しています。
Algorithm 3: WOTS_genSK - Generating a WOTS+ Private Key
Input: No input Output: WOTS+ private key sk
入力：入力なし出力：WOTS +秘密鍵sk
for ( i = 0; i < len; i++ ) {
initialize sk[i] with a uniformly random n-byte string;
}
return sk;
A WOTS+ key pair defines a virtual structure that consists of len hash chains of length w. The len n-byte strings in the private key each define the start node for one hash chain. The public key consists of the end nodes of these hash chains. Therefore, like the private key, the public key is also a length len array of n-byte strings. To compute the hash chain, the chaining function (Algorithm 2) is used. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Please note that the SEED used here is public information also available to a verifier. The following pseudocode (Algorithm 4) describes an algorithm for generating the public key pk, where sk is the private key.
WOTS +キーペアは、長さwのlenハッシュチェーンで構成される仮想構造を定義します。秘密鍵のlen個のnバイト文字列はそれぞれ、1つのハッシュチェーンの開始ノードを定義します。公開鍵は、これらのハッシュチェーンのエンドノードで構成されます。したがって、秘密鍵と同様に、公開鍵もnバイト文字列の長さlenの配列です。ハッシュチェーンを計算するには、チェーン関数（アルゴリズム2）を使用します。 OTSハッシュアドレスADRSおよびシードSEEDは、呼び出しアルゴリズムによって提供される必要があります。このアドレスは、より大きな構造内のWOTS +鍵ペアのアドレスをエンコードします。したがって、WOTS +アルゴリズムは、最後の3つの32ビットワードを除き、ADRSのどの部分も操作してはなりません（MUST NOT）。ここで使用されているSEEDは、検証者も利用できる公開情報であることに注意してください。次の疑似コード（アルゴリズム4）は、公開鍵pkを生成するアルゴリズムを示しています。ここで、skは秘密鍵です。
Algorithm 4: WOTS_genPK - Generating a WOTS+ Public Key From a Private Key
アルゴリズム4：WOTS_genPK-秘密鍵からのWOTS +公開鍵の生成
Input: WOTS+ private key sk, address ADRS, seed SEED
Output: WOTS+ public key pk
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
}
return pk;
A WOTS+ signature is a length len array of n-byte strings. The WOTS+ signature is generated by mapping a message to len integers between 0 and w - 1. To this end, the message is transformed into len_1 base w numbers using the base_w function defined in Section 2.6. Next, a checksum is computed and appended to the transformed message as len_2 base w numbers using the base_w function. Note that the checksum may reach a maximum integer value of len_1 * (w - 1) * 2^8 and therefore depends on the parameters n and w. For the parameter sets given in Section 5, a 32-bit unsigned integer is sufficient to hold the checksum. If other parameter settings are used, the size of the variable holding the integer value of the checksum MUST be sufficiently large. Each of the base w integers is used to select a node from a different hash chain. The signature is formed by concatenating the selected nodes. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Please note that the SEED used here is public information also available to a verifier. The pseudocode for signature generation is shown below (Algorithm 5), where M is the message and sig is the resulting signature.
WOTS +署名は、nバイトの文字列の長さlenの配列です。 WOTS +署名は、メッセージを0とw-1の間のlen整数にマッピングすることによって生成されます。このために、メッセージは、2.6節で定義されているbase_w関数を使用してlen_1ベースのw番号に変換されます。次に、チェックサムが計算され、base_w関数を使用してlen_2ベースのw数として変換されたメッセージに追加されます。チェックサムが最大整数値len_1 *（w-1）* 2 ^ 8に達する可能性があるため、パラメーターnおよびwに依存することに注意してください。セクション5に示したパラメーターセットの場合、32ビットの符号なし整数でチェックサムを保持できます。他のパラメータ設定を使用する場合、チェックサムの整数値を保持する変数のサイズは十分に大きくなければなりません。ベースのw整数のそれぞれは、異なるハッシュチェーンからノードを選択するために使用されます。署名は、選択したノードを連結することによって形成されます。 OTSハッシュアドレスADRSおよびシードSEEDは、呼び出しアルゴリズムによって提供される必要があります。このアドレスは、より大きな構造内のWOTS +鍵ペアのアドレスをエンコードします。したがって、WOTS +アルゴリズムは、最後の3つの32ビットワードを除き、ADRSのどの部分も操作してはなりません（MUST NOT）。ここで使用されているSEEDは、検証者も利用できる公開情報であることに注意してください。署名生成の疑似コードを以下に示します（アルゴリズム5）。ここで、Mはメッセージで、sigは結果の署名です。
Algorithm 5: WOTS_sign - Generating a signature from a private key and a message
アルゴリズム5：WOTS_sign-秘密鍵とメッセージからの署名の生成
Input: Message M, WOTS+ private key sk, address ADRS, seed SEED
Output: WOTS+ signature sig
csum = 0;
csum = 0;
// Convert message to base w
msg = base_w(M, w, len_1);
// Compute checksum
for ( i = 0; i < len_1; i++ ) {
csum = csum + w - 1 - msg[i];
}
// Convert csum to base w
csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
}
return sig;
The data format for a signature is given below.
署名のデータ形式を以下に示します。
+---------------------------------+
| |
| sig_ots[0] | n bytes
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| sig_ots[len - 1] | n bytes
| |
+---------------------------------+
WOTS+ Signature
WOTS +署名
In order to verify a signature sig on a message M, the verifier computes a WOTS+ public key value from the signature. This can be done by "completing" the chain computations starting from the signature values, using the base w values of the message hash and its checksum. This step, called WOTS_pkFromSig, is described below in Algorithm 6. The result of WOTS_pkFromSig is then compared to the given public key. If the values are equal, the signature is accepted. Otherwise, the signature MUST be rejected. An OTS hash address ADRS and a seed SEED have to be provided by the calling algorithm. This address will encode the address of the WOTS+ key pair within a greater structure. Hence, a WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the last three 32-bit words. Please note that the SEED used here is public information also available to a verifier.
メッセージMの署名sigを検証するために、検証者は署名からWOTS +公開鍵の値を計算します。これは、メッセージハッシュのベースw値とそのチェックサムを使用して、署名値から始まるチェーン計算を「完了する」ことで実行できます。この手順は、WOTS_pkFromSigと呼ばれ、以下のアルゴリズム6で説明されています。WOTS_pkFromSigの結果は、指定された公開鍵と比較されます。値が等しい場合、署名は受け入れられます。それ以外の場合は、署名を拒否する必要があります。 OTSハッシュアドレスADRSおよびシードSEEDは、呼び出しアルゴリズムによって提供される必要があります。このアドレスは、より大きな構造内のWOTS +鍵ペアのアドレスをエンコードします。したがって、WOTS +アルゴリズムは、最後の3つの32ビットワードを除き、ADRSのどの部分も操作してはなりません（MUST NOT）。ここで使用されているSEEDは、検証者も利用できる公開情報であることに注意してください。
Algorithm 6: WOTS_pkFromSig - Computing a WOTS+ public key from a message and its signature
アルゴリズム6：WOTS_pkFromSig-メッセージとその署名からのWOTS +公開鍵の計算
Input: Message M, WOTS+ signature sig, address ADRS, seed SEED
Output: 'Temporary' WOTS+ public key tmp_pk
csum = 0;
csum = 0;
// Convert message to base w
msg = base_w(M, w, len_1);
// Compute checksum
for ( i = 0; i < len_1; i++ ) {
csum = csum + w - 1 - msg[i];
}
// Convert csum to base w
csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
for ( i = 0; i < len; i++ ) {
ADRS.setChainAddress(i);
tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
}
return tmp_pk;
Note: XMSS uses WOTS_pkFromSig to compute a public key value and delays the comparison to a later point.
注：XMSSはWOTS_pkFromSigを使用して公開鍵の値を計算し、比較を後の時点に遅らせます。
An implementation MAY use a cryptographically secure pseudorandom method to generate the private key from a single n-byte value. For example, the method suggested in [BDH11] and explained below MAY be used. Other methods MAY be used. The choice of a pseudorandom method does not affect interoperability, but the cryptographic strength MUST match that of the used WOTS+ parameters.
実装は、暗号で保護された疑似ランダム方式を使用して、単一のnバイト値から秘密鍵を生成してもよい（MAY）。たとえば、[BDH11]で提案され、以下で説明される方法が使用される場合があります。他の方法が使用される場合があります。疑似ランダム方式の選択は相互運用性に影響を与えませんが、暗号強度は使用されるWOTS +パラメーターの強度と一致する必要があります。
The advantage of generating the private key elements from a random n-byte string is that only this n-byte string needs to be stored instead of the full private key. The key can be regenerated when needed. The suggested method from [BDH11] can be described using PRF. During key generation, a uniformly random n-byte string S is sampled from a secure source of randomness. This string S is stored as private key. The private key elements are computed as sk[i] = PRF(S, toByte(i, 32)) whenever needed. Please note that this seed S MUST be different from the seed SEED used to randomize the hash function calls. Also, this seed S MUST be kept secret. The seed S MUST NOT be a low entropy, human-memorable value since private key elements are derived from S deterministically and their confidentiality is security-critical.
ランダムなnバイト文字列から秘密鍵要素を生成する利点は、完全な秘密鍵の代わりにこのnバイト文字列のみを格納する必要があることです。鍵は必要なときに再生成できます。 [BDH11]から提案された方法は、PRFを使用して記述できます。鍵の生成中、一様にランダムなnバイトの文字列Sが、安全なランダム性のソースからサンプリングされます。この文字列Sは秘密鍵として格納されます。秘密鍵要素は、必要に応じてsk [i] = PRF（S、toByte（i、32））として計算されます。このシードSは、ハッシュ関数呼び出しをランダム化するために使用されるシードSEEDとは異なる必要があることに注意してください。また、このシードSは秘密にしておく必要があります。秘密鍵要素はSから決定論的に導出され、それらの機密性がセキュリティ上重要であるため、シードSは低エントロピーで人間が記憶できる値であってはなりません。
In this section, the eXtended Merkle Signature Scheme (XMSS) is described using WOTS+. XMSS comes in two flavors: a single-tree variant (XMSS) and a multi-tree variant (XMSS^MT). Both allow combining a large number of WOTS+ key pairs under a single small public key. The main ingredient added is a binary hash tree construction. XMSS uses a single hash tree while XMSS^MT uses a tree of XMSS key pairs.
このセクションでは、拡張マークル署名方式（XMSS）について、WOTS +を使用して説明します。 XMSSには、単一ツリーバリアント（XMSS）とマルチツリーバリアント（XMSS ^ MT）の2つの種類があります。どちらも、多数のWOTS +鍵ペアを1つの小さな公開鍵の下で組み合わせることができます。追加された主な要素は、バイナリハッシュツリーの構築です。 XMSS ^ MTはXMSSキーペアのツリーを使用するのに対し、XMSSは単一のハッシュツリーを使用します。
XMSS is a method for signing a potentially large but fixed number of messages. It is based on the Merkle signature scheme. XMSS uses four cryptographic components: WOTS+ as OTS method, two additional cryptographic hash functions H and H_msg, and a pseudorandom function PRF. One of the main advantages of XMSS with WOTS+ is that it does not rely on the collision resistance of the used hash functions but on weaker properties. Each XMSS public/private key pair is associated with a perfect binary tree, every node of which contains an n-byte value. Each tree leaf contains a special tree hash of a WOTS+ public key value. Each non-leaf tree node is computed by first concatenating the values of its child nodes, computing the XOR with a bitmask, and applying the keyed hash function H to the result. The bitmasks and the keys for the hash function H are generated from a (public) seed that is part of the public key using the pseudorandom function PRF. The value corresponding to the root of the XMSS tree forms the XMSS public key together with the seed.
XMSSは、潜在的に大きいが固定数のメッセージに署名するための方法です。マークル署名方式に基づいています。 XMSSは4つの暗号化コンポーネントを使用します。OTSメソッドとしてのWOTS +、2つの追加の暗号化ハッシュ関数HおよびH_msg、および疑似ランダム関数PRF。 WOTS +を使用したXMSSの主な利点の1つは、使用されるハッシュ関数の衝突耐性に依存せず、より弱いプロパティに依存することです。各XMSS公開/秘密鍵のペアは完全なバイナリツリーに関連付けられており、そのすべてのノードにはnバイトの値が含まれています。各ツリーリーフには、WOTS +公開キー値の特別なツリーハッシュが含まれています。各非リーフツリーノードは、最初に子ノードの値を連結し、ビットマスクでXORを計算し、その結果にキー付きハッシュ関数Hを適用することによって計算されます。ハッシュ関数Hのビットマスクとキーは、疑似ランダム関数PRFを使用して、公開キーの一部である（公開）シードから生成されます。 XMSSツリーのルートに対応する値は、シードとともにXMSS公開鍵を形成します。
To generate a key pair that can be used to sign 2^h messages, a tree of height h is used. XMSS is a stateful signature scheme, meaning that the private key changes with every signature generation. To prevent one-time private keys from being used twice, the WOTS+ key pairs are numbered from 0 to (2^h) - 1 according to the related leaf, starting from index 0 for the leftmost leaf. The private key contains an index that is updated with every signature generation, such that it contains the index of the next unused WOTS+ key pair.
2 ^ hメッセージの署名に使用できるキーペアを生成するには、高さhのツリーが使用されます。 XMSSはステートフルな署名スキームです。つまり、秘密鍵は署名の生成ごとに変化します。ワンタイムプライベートキーが2回使用されるのを防ぐため、WOTS +キーペアには、関連するリーフに従って0から（2 ^ h）-1までの番号が付けられ、左端のリーフのインデックス0から始まります。秘密キーには、次の未使用のWOTS +キーペアのインデックスが含まれるように、署名の生成ごとに更新されるインデックスが含まれています。
A signature consists of the index of the used WOTS+ key pair, the WOTS+ signature on the message, and the so-called authentication path. The latter is a vector of tree nodes that allow a verifier to compute a value for the root of the tree starting from a WOTS+ signature. A verifier computes the root value and compares it to the respective value in the XMSS public key. If they match, the signature is declared valid. The XMSS private key consists of all WOTS+ private keys and the current index. To reduce storage, a pseudorandom key generation procedure, as described in [BDH11], MAY be used. The security of the used method MUST at least match the security of the XMSS instance.
署名は、使用されるWOTS +鍵ペアのインデックス、メッセージのWOTS +署名、およびいわゆる認証パスで構成されます。後者は、検証者がWOTS +署名から始まるツリーのルートの値を計算できるようにするツリーノードのベクトルです。ベリファイアはルート値を計算し、それをXMSS公開鍵のそれぞれの値と比較します。それらが一致する場合、署名は有効であると宣言されます。 XMSS秘密鍵は、すべてのWOTS +秘密鍵と現在のインデックスで構成されます。ストレージを削減するために、[BDH11]で説明されているように、擬似ランダムキー生成手順を使用できます。使用されるメソッドのセキュリティは、少なくともXMSSインスタンスのセキュリティと一致する必要があります。
XMSS has the following parameters:
XMSSには以下のパラメーターがあります。
h: the height (number of levels - 1) of the tree
h：木の高さ（レベル数-1）
n: the length in bytes of the message digest as well as each node
n：メッセージダイジェストと各ノードの長さ（バイト単位）
w: the Winternitz parameter as defined for WOTS+ in Section 3.1
w：セクション3.1でWOTS +用に定義されたWinternitzパラメータ
There are 2^h leaves in the tree.
ツリーには2 ^ hの葉があります。
For XMSS and XMSS^MT, private and public keys are denoted by SK (S for secret) and PK, respectively. For WOTS+, private and public keys are denoted by sk (s for secret) and pk, respectively. XMSS and XMSS^MT signatures are denoted by Sig. WOTS+ signatures are denoted by sig.
XMSSおよびXMSS ^ MTの場合、秘密鍵と公開鍵はそれぞれSK（秘密の場合はS）とPKで示されます。 WOTS +の場合、秘密鍵と公開鍵はそれぞれsk（秘密はs）とpkで表されます。 XMSSおよびXMSS ^ MT署名はSigで示されます。 WOTS +署名はsigで示されます。
XMSS and XMSS^MT parameters are implicitly included in algorithm inputs as needed.
XMSSおよびXMSS ^ MTパラメーターは、必要に応じてアルゴリズム入力に暗黙的に含まれます。
Besides the cryptographic hash function F and the pseudorandom function PRF required by WOTS+, XMSS uses two more functions:
暗号化ハッシュ関数FとWOTS +で必要な疑似ランダム関数PRFに加えて、XMSSはさらに2つの関数を使用します。
o A cryptographic hash function H. H accepts n-byte keys and byte strings of length 2n and returns an n-byte string.
o 暗号化ハッシュ関数H. Hは、nバイトの鍵と長さ2nのバイト文字列を受け入れ、nバイトの文字列を返します。
o A cryptographic hash function H_msg. H_msg accepts 3n-byte keys and byte strings of arbitrary length and returns an n-byte string.
o 暗号化ハッシュ関数H_msg。 H_msgは、3nバイトのキーと任意の長さのバイト文字列を受け入れ、nバイトの文字列を返します。
More detail on specific instantiations can be found in Section 5. Security requirements on H and H_msg are discussed in Section 9.
特定のインスタンス化の詳細については、セクション5を参照してください。HおよびH_msgのセキュリティ要件については、セクション9で説明します。
An XMSS private key SK contains 2^h WOTS+ private keys, the leaf index idx of the next WOTS+ private key that has not yet been used, SK_PRF (an n-byte key to generate pseudorandom values for randomized message hashing), the n-byte value root (which is the root node of the tree and SEED), and the n-byte public seed used to pseudorandomly generate bitmasks and hash function keys. Although root and SEED formally would be considered only part of the public key, they are needed (e.g., for signature generation) and hence are also required for functions that do not take the public key as input.
XMSS秘密鍵SKには、2 ^ h WOTS +秘密鍵、まだ使用されていない次のWOTS +秘密鍵のリーフインデックスidx、SK_PRF（ランダム化されたメッセージハッシュ用の擬似ランダム値を生成するnバイトの鍵）、n-バイト値ルート（ツリーとSEEDのルートノードです）、およびビットマスクとハッシュ関数キーを擬似ランダムに生成するために使用されるnバイトのパブリックシード。ルートとSEEDは正式には公開鍵の一部にすぎないと見なされますが、これらは（たとえば、署名の生成に）必要であり、したがって、公開鍵を入力として使用しない関数にも必要です。
The leaf index idx is initialized to zero when the XMSS private key is created. The key SK_PRF MUST be sampled from a secure source of randomness that follows the uniform distribution. The WOTS+ private keys MUST be generated as described in Section 3.1, or, to reduce the private key size, a cryptographic pseudorandom method MUST be used as discussed in Section 4.1.11. SEED is generated as a uniformly random n-byte string. Although SEED is public, it is critical for security that it is generated using a good entropy source. The root node is generated as described below in the section on key generation (Section 4.1.7). That section also contains an example algorithm for combined private and public key generation.
リーフインデックスidxは、XMSS秘密キーが作成されるときにゼロに初期化されます。キーSK_PRFは、一様分布に従うランダム性の安全なソースからサンプリングする必要があります。セクション3.1で説明されているようにWOTS +秘密鍵を生成する必要があります。または、秘密鍵のサイズを削減するために、セクション4.1.11で説明されているように、暗号化疑似ランダム方式を使用する必要があります。 SEEDは、一様にランダムなnバイト文字列として生成されます。 SEEDは公開されていますが、適切なエントロピーソースを使用して生成されることがセキュリティにとって重要です。ルートノードは、以下のキー生成に関するセクション（セクション4.1.7）で説明されているように生成されます。このセクションには、秘密鍵と公開鍵を組み合わせて生成するためのアルゴリズムの例も含まれています。
For the following algorithm descriptions, the existence of a method getWOTS_SK(SK, i) is assumed. This method takes as input an XMSS private key SK and an integer i and outputs the i^th WOTS+ private key of SK.
以下のアルゴリズムの説明では、メソッドgetWOTS_SK（SK、i）の存在が想定されています。このメソッドは、XMSS秘密鍵SKと整数iを入力として受け取り、SKのi番目のWOTS +秘密鍵を出力します。
To improve readability, we introduce a function RAND_HASH(LEFT, RIGHT, SEED, ADRS) (Algorithm 7) that does the randomized hashing in the tree. It takes as input two n-byte values LEFT and RIGHT that represent the left and the right halves of the hash function input, the seed SEED used as key for PRF, and the address ADRS of this hash function call. RAND_HASH first uses PRF with SEED and ADRS to generate a key KEY and n-byte bitmasks BM_0, BM_1. Then, it returns the randomized hash H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)).
読みやすさを向上させるために、ツリーでランダムなハッシュを行う関数RAND_HASH（LEFT、RIGHT、SEED、ADRS）（アルゴリズム7）を導入します。入力として、ハッシュ関数入力の左半分と右半分を表す2つのnバイト値LEFTとRIGHT、PRFのキーとして使用されるシードSEED、およびこのハッシュ関数呼び出しのアドレスADRSを受け取ります。 RAND_HASHは、最初にSEEDおよびADRSとともにPRFを使用して、キーKEYおよびnバイトのビットマスクBM_0、BM_1を生成します。次に、ランダム化されたハッシュH（KEY、（LEFT XOR BM_0）||（RIGHT XOR BM_1））を返します。
Algorithm 7: RAND_HASH
アルゴリズム7：RAND_HASH
Input: n-byte value LEFT, n-byte value RIGHT, seed SEED, address ADRS Output: n-byte randomized hash
入力：nバイトの値LEFT、nバイトの値RIGHT、シードSEED、アドレスADRS出力：nバイトのランダム化されたハッシュ
ADRS.setKeyAndMask(0);
KEY = PRF(SEED, ADRS);
ADRS.setKeyAndMask(1);
BM_0 = PRF(SEED, ADRS);
ADRS.setKeyAndMask(2);
BM_1 = PRF(SEED, ADRS);
return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
return H（KEY、（LEFT XOR BM_0）||（RIGHT XOR BM_1））;
To compute the leaves of the binary hash tree, a so-called L-tree is used. An L-tree is an unbalanced binary hash tree, distinct but similar to the main XMSS binary hash tree. The algorithm ltree (Algorithm 8) takes as input a WOTS+ public key pk and compresses it to a single n-byte value pk[0]. It also takes as input an L-tree address ADRS that encodes the address of the L-tree and the seed SEED.
バイナリハッシュツリーの葉を計算するには、いわゆるLツリーを使用します。 Lツリーは、バランスが取れていないバイナリハッシュツリーであり、別個ですが、メインのXMSSバイナリハッシュツリーに似ています。アルゴリズムltree（アルゴリズム8）は、WOTS +公開鍵pkを入力として受け取り、それを単一のnバイト値pk [0]に圧縮します。また、入力として、LツリーのアドレスとシードSEEDをエンコードするLツリーアドレスADRSを受け取ります。
Algorithm 8: ltree
アルゴリズム8：ltree
Input: WOTS+ public key pk, address ADRS, seed SEED Output: n-byte compressed public key value pk[0]
入力：WOTS +公開鍵pk、アドレスADRS、シードSEED出力：nバイトの圧縮公開鍵値pk [0]
unsigned int len' = len;
ADRS.setTreeHeight(0);
while ( len' > 1 ) {
for ( i = 0; i < floor(len' / 2); i++ ) {
ADRS.setTreeIndex(i);
pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS);
}
if ( len' % 2 == 1 ) {
pk[floor(len' / 2)] = pk[len' - 1];
}
len' = ceil(len' / 2);
ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
}
return pk[0];
For the computation of the internal n-byte nodes of a Merkle tree, the subroutine treeHash (Algorithm 9) accepts an XMSS private key SK (including seed SEED), an unsigned integer s (the start index), an unsigned integer t (the target node height), and an address ADRS that encodes the address of the containing tree. For the height of a node within a tree, counting starts with the leaves at height zero. The treeHash algorithm returns the root node of a tree of height t with the leftmost leaf being the hash of the WOTS+ pk with index s. It is REQUIRED that s % 2^t = 0, i.e., that the leaf at index s is a leftmost leaf of a sub-tree of height t. Otherwise, the hash-addressing scheme fails. The treeHash algorithm described here uses a stack holding up to (t - 1) nodes, with the usual stack functions push() and pop(). We furthermore assume that the height of a node (an unsigned integer) is stored alongside a node's value (an n-byte string) on the stack.
マークルツリーの内部nバイトノードの計算では、サブルーチンtreeHash（アルゴリズム9）は、XMSS秘密鍵SK（シードSEEDを含む）、符号なし整数s（開始インデックス）、符号なし整数t（ターゲットノードの高さ）、および包含ツリーのアドレスをエンコードするアドレスADRS。ツリー内のノードの高さについては、高さ0の葉から数え始めます。 treeHashアルゴリズムは、高さtのツリーのルートノードを返します。左端の葉は、インデックスsのWOTS + pkのハッシュです。 s％2 ^ t = 0、つまりインデックスsの葉が高さtのサブツリーの左端の葉であることが必要です。それ以外の場合、ハッシュアドレス指定スキームは失敗します。ここで説明するtreeHashアルゴリズムは、最大（t-1）個のノードを保持するスタックを使用し、通常のスタック関数push()およびpop()を使用します。さらに、ノードの高さ（符号なし整数）がノードの値（nバイトの文字列）と共にスタックに格納されると仮定します。
Algorithm 9: treeHash
アルゴリズム9：treeHash
Input: XMSS private key SK, start index s, target node height t, address ADRS Output: n-byte root node - top node on Stack
入力：XMSS秘密鍵SK、開始インデックスs、ターゲットノードの高さt、アドレスADRS出力：nバイトのルートノード-スタックの最上位ノード
if( s % (1 << t) != 0 ) return -1;
for ( i = 0; i < 2^t; i++ ) {
SEED = getSEED(SK);
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(s + i);
pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
ADRS.setType(1); // Type = L-tree address
ADRS.setLTreeAddress(s + i);
node = ltree(pk, SEED, ADRS);
ADRS.setType(2); // Type = hash tree address
ADRS.setTreeHeight(0);
ADRS.setTreeIndex(i + s);
while ( Top node on Stack has same height t' as node ) {
ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
}
Stack.push(node);
}
return Stack.pop();
The XMSS key pair is computed as described in XMSS_keyGen (Algorithm 10). The XMSS public key PK consists of the root of the binary hash tree and the seed SEED, both also stored in SK. The root is computed using treeHash. For XMSS, there is only a single main tree. Hence, the used address is set to the all-zero string in the beginning. Note that we do not define any specific format or handling for the XMSS private key SK by introducing this algorithm. It relates to requirements described earlier and simply shows a basic but very inefficient example to initialize a private key.
XMSSキーペアは、XMSS_keyGen（アルゴリズム10）の説明に従って計算されます。 XMSS公開鍵PKは、バイナリハッシュツリーのルートとシードSEEDで構成され、どちらもSKに格納されています。ルートは、treeHashを使用して計算されます。 XMSSの場合、メインツリーは1つだけです。したがって、使用されるアドレスは、最初はすべてゼロの文字列に設定されます。このアルゴリズムを導入しても、XMSS秘密鍵SKの特定の形式や処理は定義しないことに注意してください。これは前に説明した要件に関連し、秘密鍵を初期化するための基本的ではあるが非常に非効率的な例を示しています。
Algorithm 10: XMSS_keyGen - Generate an XMSS key pair
アルゴリズム10：XMSS_keyGen-XMSS鍵ペアを生成する
Input: No input Output: XMSS private key SK, XMSS public key PK
入力：入力なし出力：XMSS秘密鍵SK、XMSS公開鍵PK
// Example initialization for SK-specific contents
idx = 0;
for ( i = 0; i < 2^h; i++ ) {
wots_sk[i] = WOTS_genSK();
}
initialize SK_PRF with a uniformly random n-byte string;
setSK_PRF(SK, SK_PRF);
// Initialization for common contents
initialize SEED with a uniformly random n-byte string;
setSEED(SK, SEED);
setWOTS_SK(SK, wots_sk));
ADRS = toByte(0, 32);
root = treeHash(SK, 0, h, ADRS);
SK = idx || wots_sk || SK_PRF || root || SEED;
PK = OID || root || SEED;
return (SK || PK);
The above is just an example algorithm. It is strongly RECOMMENDED to use pseudorandom key generation to reduce the private key size. Public and private key generation MAY be interleaved to save space. Particularly, when a pseudorandom method is used to generate the private key, generation MAY be done when the respective WOTS+ key pair is needed by treeHash.
上記は一例のアルゴリズムです。疑似ランダムキー生成を使用して秘密キーのサイズを小さくすることを強くお勧めします。スペースを節約するために、公開鍵と秘密鍵の生成がインターリーブされる場合があります。特に、秘密鍵の生成に疑似ランダム方式を使用する場合、treeHashがそれぞれのWOTS +鍵ペアを必要とするときに生成が行われる場合があります。
The format of an XMSS public key is given below.
XMSS公開鍵の形式を以下に示します。
+---------------------------------+
| algorithm OID |
+---------------------------------+
| |
| root node | n bytes
| |
+---------------------------------+
| |
| SEED | n bytes
| |
+---------------------------------+
XMSS Public Key
XMSS公開鍵
An XMSS signature is a (4 + n + (len + h) * n)-byte string consisting of:
XMSSシグネチャは、（4 + n +（len + h）* n）バイトの文字列で構成されます。
o the index idx_sig of the used WOTS+ key pair (4 bytes),
o 使用されるWOTS +鍵ペアのインデックスidx_sig（4バイト）、
o a byte string r used for randomized message hashing (n bytes),
o ランダム化されたメッセージのハッシュに使用されるバイト文字列r（nバイト）、
o a WOTS+ signature sig_ots (len * n bytes), and
o WOTS +署名sig_ots（len * nバイト）、および
o the so-called authentication path 'auth' for the leaf associated with the used WOTS+ key pair (h * n bytes).
o 使用されるWOTS +鍵ペアに関連付けられたリーフのいわゆる認証パス「auth」（h * nバイト）。
The authentication path is an array of h n-byte strings. It contains
the siblings of the nodes on the path from the used leaf to the root.
It does not contain the nodes on the path itself. A verifier needs
these nodes to compute a root node for the tree from the WOTS+ public
key. A node Node is addressed by its position in the tree. Node(x,
y) denotes the y^th node on level x with y = 0 being the leftmost
node on a level. The leaves are on level 0; the root is on level h.
An authentication path contains exactly one node on every layer 0 <=
x <= (h - 1). For the i^th WOTS+ key pair, counting from zero, the
j^th authentication path node is:
Node(j, floor(i / (2^j)) XOR 1)
The computation of the authentication path is discussed in Section 4.1.9.
認証パスの計算については、セクション4.1.9で説明します。
The data format for a signature is given below.
署名のデータ形式を以下に示します。
+---------------------------------+
| |
| index idx_sig | 4 bytes
| |
+---------------------------------+
| |
| randomness r | n bytes
| |
+---------------------------------+
| |
| WOTS+ signature sig_ots | len * n bytes
| |
+---------------------------------+
| |
| auth[0] | n bytes
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| auth[h - 1] | n bytes
| |
+---------------------------------+
XMSS Signature
XMSS署名
To compute the XMSS signature of a message M with an XMSS private key, the signer first computes a randomized message digest using a random value r, idx_sig, the index of the WOTS+ key pair to be used, and the root value from the public key as key. Then, a WOTS+ signature of the message digest is computed using the next unused WOTS+ private key. Next, the authentication path is computed. Finally, the private key is updated, i.e., idx is incremented. An implementation MUST NOT output the signature before the private key is updated.
XMSS秘密鍵を使用してメッセージMのXMSS署名を計算するには、署名者はまず、ランダム値r、idx_sig、使用するWOTS +鍵ペアのインデックス、および公開鍵からのルート値を使用して、ランダム化されたメッセージダイジェストを計算しますキーとして。次に、メッセージダイジェストのWOTS +署名が、次の未使用のWOTS +秘密鍵を使用して計算されます。次に、認証パスが計算されます。最後に、秘密鍵が更新されます。つまり、idxがインクリメントされます。実装は、秘密鍵が更新される前に署名を出力してはいけません（MUST NOT）。
The node values of the authentication path MAY be computed in any way. This computation is assumed to be performed by the subroutine buildAuth for the function XMSS_sign (Algorithm 12). The fastest alternative is to store all tree nodes and set the array in the signature by copying the respective nodes. The least storage-intensive alternative is to recompute all nodes for each signature online using the treeHash algorithm (Algorithm 9). Several algorithms exist in between, with different time/storage trade-offs. For an overview, see [BDS09]. A further approach can be found in [KMN14]. Note that the details of this procedure are not relevant to interoperability; it is not necessary to know any of these details in order to perform the signature verification operation. The following version of buildAuth is given for completeness. It is a simple example for understanding, but extremely inefficient. The use of one of the alternative algorithms is strongly RECOMMENDED.
認証パスのノード値は、いかなる方法でも計算できます。この計算は、関数XMSS_sign（アルゴリズム12）のサブルーチンbuildAuthによって実行されると想定されています。最速の代替策は、すべてのツリーノードを格納し、それぞれのノードをコピーして配列を署名に設定することです。最小のストレージ集約型の代替策は、treeHashアルゴリズム（アルゴリズム9）を使用して、各署名のすべてのノードをオンラインで再計算することです。その間にいくつかのアルゴリズムが存在し、時間とストレージのトレードオフが異なります。概要については、[BDS09]を参照してください。さらなるアプローチは[KMN14]にあります。この手順の詳細は相互運用性には関係がないことに注意してください。署名検証操作を実行するために、これらの詳細を知る必要はありません。完全を期すために、次のバージョンのbuildAuthが提供されています。これは理解のための簡単な例ですが、非常に非効率的です。代替アルゴリズムの1つを使用することを強くお勧めします。
Given an XMSS private key SK, all nodes in a tree are determined. Their values are defined in terms of treeHash (Algorithm 9). Hence, one can compute the authentication path as follows:
XMSS秘密鍵SKが与えられると、ツリー内のすべてのノードが決定されます。それらの値は、treeHash（アルゴリズム9）によって定義されます。したがって、次のように認証パスを計算できます。
(Example) buildAuth - Compute the authentication path for the i^th WOTS+ key pair
（例）buildAuth-i番目のWOTS +キーペアの認証パスを計算します
Input: XMSS private key SK, WOTS+ key pair index i, ADRS Output: Authentication path auth
入力：XMSS秘密鍵SK、WOTS +鍵ペアインデックスi、ADRS出力：認証パスauth
for ( j = 0; j < h; j++ ) {
k = floor(i / (2^j)) XOR 1;
auth[j] = treeHash(SK, k * 2^j, j, ADRS);
}
We split the description of the signature generation into two main algorithms. The first one, treeSig (Algorithm 11), generates the main part of an XMSS signature and is also used by the multi-tree variant XMSS^MT. XMSS_sign (Algorithm 12) calls treeSig but handles message compression before and the private key update afterwards.
署名生成の説明を2つの主要なアルゴリズムに分割します。最初の1つであるtreeSig（アルゴリズム11）は、XMSS署名の主要部分を生成し、マルチツリーバリアントXMSS ^ MTでも使用されます。 XMSS_sign（アルゴリズム12）は、treeSigを呼び出しますが、前にメッセージ圧縮を処理し、後で秘密鍵を更新します。
The algorithm treeSig (Algorithm 11) described below calculates the WOTS+ signature on an n-byte message and the corresponding authentication path. treeSig takes as input an n-byte message M', an XMSS private key SK, a signature index idx_sig, and an address ADRS. It returns the concatenation of the WOTS+ signature sig_ots and authentication path auth.
以下で説明するアルゴリズムtreeSig（アルゴリズム11）は、nバイトのメッセージと対応する認証パスのWOTS +署名を計算します。 treeSigは、nバイトのメッセージM '、XMSS秘密鍵SK、署名インデックスidx_sig、およびアドレスADRSを入力として受け取ります。これは、WOTS +署名sig_otsと認証パスauthの連結を返します。
Algorithm 11: treeSig - Generate a WOTS+ signature on a message with corresponding authentication path
アルゴリズム11：treeSig-対応する認証パスを使用してメッセージにWOTS +署名を生成する
Input: n-byte message M', XMSS private key SK, signature index idx_sig, ADRS Output: Concatenation of WOTS+ signature sig_ots and authentication path auth
入力：nバイトのメッセージM '、XMSS秘密鍵SK、署名インデックスidx_sig、ADRS出力：WOTS +署名sig_otsと認証パスauthの連結
auth = buildAuth(SK, idx_sig, ADRS);
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(idx_sig);
sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
M', getSEED(SK), ADRS);
Sig = sig_ots || auth;
return Sig;
The algorithm XMSS_sign (Algorithm 12) described below calculates an updated private key SK and a signature on a message M. XMSS_sign takes as input a message M of arbitrary length and an XMSS private key SK. It returns the byte string containing the concatenation of the updated private key SK and the signature Sig.
以下で説明するアルゴリズムXMSS_sign（アルゴリズム12）は、更新された秘密鍵SKとメッセージMの署名を計算します。XMSS_signは、任意の長さのメッセージMとXMSS秘密鍵SKを入力として受け取ります。更新された秘密鍵SKと署名Sigの連結を含むバイト文字列を返します。
Algorithm 12: XMSS_sign - Generate an XMSS signature and update the XMSS private key
アルゴリズム12：XMSS_sign-XMSS署名を生成し、XMSS秘密鍵を更新する
Input: Message M, XMSS private key SK Output: Updated SK, XMSS signature Sig
入力：メッセージM、XMSS秘密鍵SK出力：更新されたSK、XMSS署名Sig
idx_sig = getIdx(SK);
setIdx(SK, idx_sig + 1);
ADRS = toByte(0, 32);
byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32));
byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M);
Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS);
return (SK || Sig);
An XMSS signature is verified by first computing the message digest using randomness r, index idx_sig, the root from PK and message M. Then the used WOTS+ public key pk_ots is computed from the WOTS+ signature using WOTS_pkFromSig. The WOTS+ public key in turn is used to compute the corresponding leaf using an L-tree. The leaf, together with index idx_sig and authentication path auth is used to compute an alternative root value for the tree. The verification succeeds if and only if the computed root value matches the one in the XMSS public key. In any other case, it MUST return fail.
XMSS署名は、最初にランダム性r、インデックスidx_sig、PKからのルートおよびメッセージMを使用してメッセージダイジェストを計算することによって検証されます。次に、使用されるWOTS +公開鍵pk_otsがWOTS_pkFromSigを使用してWOTS +署名から計算されます。次に、WOTS +公開鍵を使用して、Lツリーを使用して対応するリーフを計算します。葉は、インデックスidx_sigおよび認証パスauthとともに、ツリーの代替ルート値を計算するために使用されます。検証は、計算されたルート値がXMSS公開鍵のルート値と一致する場合にのみ成功します。それ以外の場合は、失敗を返す必要があります。
As for signature generation, we split verification into two parts to allow for reuse in the XMSS^MT description. The steps also needed for XMSS^MT are done by the function XMSS_rootFromSig (Algorithm 13). XMSS_verify (Algorithm 14) calls XMSS_rootFromSig as a subroutine and handles the XMSS-specific steps.
署名の生成に関しては、検証を2つの部分に分割して、XMSS ^ MT記述で再利用できるようにします。 XMSS ^ MTにも必要な手順は、関数XMSS_rootFromSig（アルゴリズム13）によって実行されます。 XMSS_verify（アルゴリズム14）は、XMSS_rootFromSigをサブルーチンとして呼び出し、XMSS固有の手順を処理します。
The main part of XMSS signature verification is done by the function XMSS_rootFromSig (Algorithm 13) described below. XMSS_rootFromSig takes as input an index idx_sig, a WOTS+ signature sig_ots, an authentication path auth, an n-byte message M', seed SEED, and address ADRS. XMSS_rootFromSig returns an n-byte string holding the value of the root of a tree defined by the input data.
XMSS署名検証の主要部分は、以下で説明する関数XMSS_rootFromSig（アルゴリズム13）によって実行されます。 XMSS_rootFromSigは、インデックスidx_sig、WOTS +署名sig_ots、認証パス認証、nバイトメッセージM '、シードSEED、およびアドレスADRSを入力として受け取ります。 XMSS_rootFromSigは、入力データで定義されたツリーのルートの値を保持するnバイトの文字列を返します。
Algorithm 13: XMSS_rootFromSig - Compute a root node from a tree signature
アルゴリズム13：XMSS_rootFromSig-ツリー署名からルートノードを計算する
Input: index idx_sig, WOTS+ signature sig_ots, authentication path auth, n-byte message M', seed SEED, address ADRS Output: n-byte root value node[0]
入力：インデックスidx_sig、WOTS +署名sig_ots、認証パス認証、nバイトメッセージM '、シードSEED、アドレスADRS出力：nバイトルート値node [0]
ADRS.setType(0); // Type = OTS hash address
ADRS.setOTSAddress(idx_sig);
pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS);
ADRS.setType(1); // Type = L-tree address
ADRS.setLTreeAddress(idx_sig);
byte[n][2] node;
node[0] = ltree(pk_ots, SEED, ADRS);
ADRS.setType(2); // Type = hash tree address
ADRS.setTreeIndex(idx_sig);
for ( k = 0; k < h; k++ ) {
ADRS.setTreeHeight(k);
if ( (floor(idx_sig / (2^k)) % 2) == 0 ) {
ADRS.setTreeIndex(ADRS.getTreeIndex() / 2);
node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS);
} else {
ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS);
}
node[0] = node[1];
}
return node[0];
The full XMSS signature verification is depicted below (Algorithm 14). It handles message compression, delegates the root computation to XMSS_rootFromSig, and compares the result to the value in the public key. XMSS_verify takes as input an XMSS signature Sig, a message M, and an XMSS public key PK. XMSS_verify returns true if and only if Sig is a valid signature on M under public key PK. Otherwise, it returns false.
XMSS署名の完全な検証を以下に示します（アルゴリズム14）。メッセージ圧縮を処理し、ルート計算をXMSS_rootFromSigに委任し、結果を公開キーの値と比較します。 XMSS_verifyは、XMSS署名Sig、メッセージM、およびXMSS公開鍵PKを入力として受け取ります。 XMSS_verifyは、Sigが公開鍵PKの下でMの有効な署名である場合にのみtrueを返します。それ以外の場合は、falseを返します。
Algorithm 14: XMSS_verify - Verify an XMSS signature using the corresponding XMSS public key and a message
アルゴリズム14：XMSS_verify-対応するXMSS公開鍵とメッセージを使用してXMSS署名を検証する
Input: XMSS signature Sig, message M, XMSS public key PK Output: Boolean
入力：XMSS署名Sig、メッセージM、XMSS公開鍵PK出力：ブール
ADRS = toByte(0, 32);
byte[n] M' = H_msg(r || getRoot(PK) || (toByte(idx_sig, n)), M);
byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M',
getSEED(PK), ADRS);
if ( node == getRoot(PK) ) {
return true;
} else {
return false;
}
An implementation MAY use a cryptographically secure pseudorandom method to generate the XMSS private key from a single n-byte value. For example, the method suggested in [BDH11] and explained below MAY be used. Other methods, such as the one in [HRS16], MAY be used. The choice of a pseudorandom method does not affect interoperability, but the cryptographic strength MUST match that of the used XMSS parameters.
実装は、暗号で保護された疑似ランダム方式を使用して、単一のnバイト値からXMSS秘密鍵を生成してもよい（MAY）。たとえば、[BDH11]で提案され、以下で説明される方法が使用される場合があります。 [HRS16]のような他の方法を使用してもかまいません。疑似ランダム方式の選択は相互運用性に影響を与えませんが、暗号強度は、使用されるXMSSパラメーターの強度と一致する必要があります。
For XMSS, a method similar to that for WOTS+ can be used. The suggested method from [BDH11] can be described using PRF. During key generation, a uniformly random n-byte string S is sampled from a secure source of randomness. This seed S MUST NOT be confused with the public seed SEED. The seed S MUST be independent of SEED, and because it is the main secret, it MUST be kept secret. This seed S is used to generate an n-byte value S_ots for each WOTS+ key pair. The n-byte value S_ots can then be used to compute the respective WOTS+ private key using the method described in Section 3.1.7. The seeds for the WOTS+ key pairs are computed as S_ots[i] = PRF(S, toByte(i, 32)) where i is the index of the WOTS+ key pair. An advantage of this method is that a WOTS+ key can be computed using only len + 1 evaluations of PRF when S is given.
XMSSの場合、WOTS +と同様の方法を使用できます。 [BDH11]から提案された方法は、PRFを使用して記述できます。鍵の生成中、一様にランダムなnバイトの文字列Sが、安全なランダム性のソースからサンプリングされます。このシードSをパブリックシードシードと混同しないでください。シードSはSEEDから独立している必要があり、主な秘密であるため、秘密にしておく必要があります。このシードSは、各WOTS +鍵ペアのnバイト値S_otsを生成するために使用されます。次に、nバイトの値S_otsを使用して、セクション3.1.7で説明されている方法を使用して、それぞれのWOTS +秘密鍵を計算できます。 WOTS +キーペアのシードは、S_ots [i] = PRF（S、toByte（i、32））として計算されます。ここで、iはWOTS +キーペアのインデックスです。この方法の利点は、Sが指定されている場合、PRFのlen + 1評価のみを使用してWOTS +鍵を計算できることです。
Some applications might require working with partial private keys or copies of private keys. Examples include load balancing and delegation of signing rights or proxy signatures. Such applications MAY use their own key format and MAY use a signing algorithm different from the one described above. The index in partial private keys or copies of a private key MAY be manipulated as required by the applications. However, applications MUST establish means that guarantee that each index, and thereby each WOTS+ key pair, is used to sign only a single message.
一部のアプリケーションでは、部分的な秘密鍵または秘密鍵のコピーを処理する必要があります。例としては、負荷分散、署名権限またはプロキシ署名の委任などがあります。このようなアプリケーションは、独自のキー形式を使用してもよいし（MAY）、上記のものとは異なる署名アルゴリズムを使用してもよい（MAY）。部分的な秘密鍵のインデックスまたは秘密鍵のコピーは、アプリケーションの必要に応じて操作できます。ただし、アプリケーションは、各インデックス、つまり各WOTS +キーペアが単一のメッセージのみに署名するために使用されることを保証する手段を確立する必要があります。
XMSS^MT is a method for signing a large but fixed number of messages. It was first described in [HRB13]. It builds on XMSS. XMSS^MT uses a tree of several layers of XMSS trees, a so-called hypertree. The trees on top and intermediate layers are used to sign the root nodes of the trees on the respective layer below. Trees on the lowest layer are used to sign the actual messages. All XMSS trees have equal height.
XMSS ^ MTは、大量ではあるが一定数のメッセージに署名するための方法です。 [HRB13]で最初に説明されました。 XMSS上に構築されます。 XMSS ^ MTは、XMSSツリーのいくつかのレイヤーのツリー、いわゆるハイパーツリーを使用します。最上層と中間層のツリーは、下の各層のツリーのルートノードに署名するために使用されます。最下層のツリーは、実際のメッセージに署名するために使用されます。すべてのXMSSツリーの高さは同じです。
Consider an XMSS^MT tree of total height h that has d layers of XMSS trees of height h / d. Then, layer d - 1 contains one XMSS tree, layer d - 2 contains 2^(h / d) XMSS trees, and so on. Finally, layer 0 contains 2^(h - h / d) XMSS trees.
高さh / dのXMSSツリーのd層を持つ全高さhのXMSS ^ MTツリーを考えます。次に、レイヤーd-1には1つのXMSSツリーが含まれ、レイヤーd-2には2 ^（h / d）XMSSツリーが含まれます。最後に、レイヤー0には2 ^（h-h / d）XMSSツリーが含まれています。
In addition to all XMSS parameters, an XMSS^MT system requires the number of tree layers d, specified as an integer value that divides h without remainder. The same tree height h / d and the same Winternitz parameter w are used for all tree layers.
すべてのXMSSパラメーターに加えて、XMSS ^ MTシステムには、hを剰余なしで割る整数値として指定されたツリーレイヤーの数dが必要です。同じ木の高さh / dと同じWinternitzパラメータwがすべての木のレイヤーに使用されます。
All the trees on higher layers sign root nodes of other trees, with the root nodes being n-byte strings. Hence, no message compression is needed, and WOTS+ is used to sign the root nodes themselves instead of their hash values.
上位層のすべてのツリーは他のツリーのルートノードに署名し、ルートノードはnバイトの文字列です。したがって、メッセージの圧縮は不要であり、ハッシュ値の代わりにルートノード自体の署名にWOTS +が使用されます。
An XMSS^MT private key SK_MT (S for secret) consists of one reduced XMSS private key for each XMSS tree. These reduced XMSS private keys just contain the WOTS+ private keys corresponding to that XMSS key pair; they do not contain a pseudorandom function key, index, public seed, or root node. Instead, SK_MT contains a single n-byte pseudorandom function key SK_PRF, a single (ceil(h / 8))-byte index idx_MT, a single n-byte seed SEED, and a single root value root (which is the root of the single tree on the top layer). The index is a global index over all WOTS+ key pairs of all XMSS trees on layer 0. It is initialized with 0. It stores the index of the last used WOTS+ key pair on the bottom layer, i.e., a number between 0 and 2^h - 1.
XMSS ^ MT秘密鍵SK_MT（秘密の場合はS）は、XMSSツリーごとに1つの縮小されたXMSS秘密鍵で構成されます。これらの縮小されたXMSS秘密鍵には、そのXMSS鍵ペアに対応するWOTS +秘密鍵のみが含まれます。疑似ランダム関数キー、インデックス、パブリックシード、またはルートノードは含まれていません。代わりに、SK_MTには、単一のnバイトの疑似ランダム関数キーSK_PRF、単一の（ceil（h / 8））バイトのインデックスidx_MT、単一のnバイトのシードSEED、および単一のルート値ルート（これは、最上層の単一ツリー）。インデックスは、レイヤー0のすべてのXMSSツリーのすべてのWOTS +キーペアに対するグローバルインデックスです。0で初期化されます。これは、最後のレイヤーで最後に使用されたWOTS +キーペアのインデックス、つまり0〜2の数値を格納します^ h-1。
The reduced XMSS private keys MUST either be generated as described in Section 4.1.3 or be generated using a cryptographic pseudorandom method as discussed in Section 4.2.6. As for XMSS, the PRF key SK_PRF MUST be sampled from a secure source of randomness that follows the uniform distribution. SEED is generated as a uniformly random n-byte string. Although SEED is public, it is critical for security that it is generated using a good entropy source. The root is the root node of the single XMSS tree on the top layer. Its computation is explained below. As for XMSS, root and SEED are public information and would classically be considered part of the public key. However, as both are needed for signing, which only takes the private key, they are also part of SK_MT.
縮小されたXMSS秘密鍵は、セクション4.1.3で説明されているように生成されるか、セクション4.2.6で説明されているように、暗号化疑似ランダム方式を使用して生成される必要があります。 XMSSの場合と同様に、PRFキーSK_PRFは、一様分布に従うランダム性の安全なソースからサンプリングする必要があります。 SEEDは、一様にランダムなnバイト文字列として生成されます。 SEEDは公開されていますが、適切なエントロピーソースを使用して生成されることがセキュリティにとって重要です。ルートは、最上層の単一のXMSSツリーのルートノードです。その計算を以下に説明します。 XMSSに関しては、ルートとSEEDは公開情報であり、古典的には公開鍵の一部と見なされます。ただし、両方とも署名に必要であり、秘密鍵のみを使用するため、これらもSK_MTの一部です。
This document does not define any specific format for the XMSS^MT private key SK_MT as it is not required for interoperability. Algorithms 15 and 16 use a function getXMSS_SK(SK, x, y) that outputs the reduced private key of the x^th XMSS tree on the y^th layer.
このドキュメントでは、XMSS ^ MT秘密キーSK_MTの特定の形式を定義していません。相互運用性には必要ないためです。アルゴリズム15と16は、関数getXMSS_SK（SK、x、y）を使用して、y ^ thレイヤーのx ^ th XMSSツリーの縮小秘密鍵を出力します。
The XMSS^MT public key PK_MT contains the root of the single XMSS tree on layer d - 1 and the seed SEED. These are the same values as in the private key SK_MT. The pseudorandom function PRF keyed with SEED is used to generate the bitmasks and keys for all XMSS trees. XMSSMT_keyGen (Algorithm 15) shows example pseudocode to generate SK_MT and PK_MT. The n-byte root node of the top-layer tree is computed using treeHash. The algorithm XMSSMT_keyGen outputs an XMSS^MT private key SK_MT and an XMSS^MT public key PK_MT. The algorithm below gives an example of how the reduced XMSS private keys can be generated. However, any of the above mentioned ways is acceptable as long as the cryptographic strength of the used method matches or supersedes that of the used XMSS^MT parameter set.
XMSS ^ MT公開鍵PK_MTには、レイヤーd-1の単一のXMSSツリーのルートとシードSEEDが含まれています。これらは、秘密鍵SK_MTと同じ値です。 SEEDでキー付けされた疑似ランダム関数PRFは、すべてのXMSSツリーのビットマスクとキーを生成するために使用されます。 XMSSMT_keyGen（アルゴリズム15）は、SK_MTおよびPK_MTを生成する疑似コードの例を示しています。最上層ツリーのnバイトのルートノードは、treeHashを使用して計算されます。アルゴリズムXMSSMT_keyGenは、XMSS ^ MT秘密鍵SK_MTおよびXMSS ^ MT公開鍵PK_MTを出力します。以下のアルゴリズムは、削減されたXMSS秘密鍵を生成する方法の例を示しています。ただし、使用されるメソッドの暗号強度が、使用されるXMSS ^ MTパラメーターセットの暗号強度と一致するか、それよりも優先される限り、上記の方法のいずれかを使用できます。
Algorithm 15: XMSSMT_keyGen - Generate an XMSS^MT key pair
Input: No input
Output: XMSS^MT private key SK_MT, XMSS^MT public key PK_MT
// Example initialization
idx_MT = 0;
setIdx(SK_MT, idx_MT);
initialize SK_PRF with a uniformly random n-byte string;
setSK_PRF(SK_MT, SK_PRF);
initialize SEED with a uniformly random n-byte string;
setSEED(SK_MT, SEED);
// Generate reduced XMSS private keys
ADRS = toByte(0, 32);
for ( layer = 0; layer < d; layer++ ) {
ADRS.setLayerAddress(layer);
for ( tree = 0; tree <
(1 << ((d - 1 - layer) * (h / d)));
tree++ ) {
ADRS.setTreeAddress(tree);
for ( i = 0; i < 2^(h / d); i++ ) {
wots_sk[i] = WOTS_genSK();
}
setXMSS_SK(SK_MT, wots_sk, tree, layer);
}
}
SK = getXMSS_SK(SK_MT, 0, d - 1);
setSEED(SK, SEED);
root = treeHash(SK, 0, h / d, ADRS);
setRoot(SK_MT, root);
PK_MT = OID || root || SEED;
return (SK_MT || PK_MT);
The above is just an example algorithm. It is strongly RECOMMENDED to use pseudorandom key generation to reduce the private key size. Public and private key generation MAY be interleaved to save space. In particular, when a pseudorandom method is used to generate the private key, generation MAY be delayed to the point that the respective WOTS+ key pair is needed by another algorithm.
上記は一例のアルゴリズムです。疑似ランダムキー生成を使用して秘密キーのサイズを小さくすることを強くお勧めします。スペースを節約するために、公開鍵と秘密鍵の生成がインターリーブされる場合があります。特に、疑似ランダム方式を使用して秘密鍵を生成する場合、生成は、それぞれのWOTS +鍵ペアが別のアルゴリズムで必要になる点まで遅延してもよい（MAY）。
The format of an XMSS^MT public key is given below.
XMSS ^ MT公開鍵の形式を以下に示します。
+---------------------------------+
| algorithm OID |
+---------------------------------+
| |
| root node | n bytes
| |
+---------------------------------+
| |
| SEED | n bytes
| |
+---------------------------------+
XMSS^MT Public Key
XMSS ^ MT公開鍵
An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) + n + (h + d * len) * n). It consists of:
XMSS ^ MT署名Sig_MTは、長さのバイト文字列（ceil（h / 8）+ n +（h + d * len）* n）です。それはで構成されています：
o the index idx_sig of the used WOTS+ key pair on the bottom layer (ceil(h / 8) bytes),
o 最下層で使用されているWOTS +鍵ペアのインデックスidx_sig（ceil（h / 8）バイト）、
o a byte string r used for randomized message hashing (n bytes), and
o ランダム化されたメッセージのハッシュに使用されるバイト文字列r（nバイト）、および
o d reduced XMSS signatures ((h / d + len) * n bytes each).
o dはXMSS署名を削減しました（（h / d + len）*それぞれnバイト）。
The reduced XMSS signatures only contain a WOTS+ signature sig_ots and an authentication path auth. They contain no index idx and no byte string r.
削減されたXMSS署名には、WOTS +署名sig_otsと認証パスauthのみが含まれます。インデックスidxとバイト文字列rは含まれていません。
The data format for a signature is given below.
署名のデータ形式を以下に示します。
+---------------------------------+
| |
| index idx_sig | ceil(h / 8) bytes
| |
+---------------------------------+
| |
| randomness r | n bytes
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (bottom layer 0) |
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (layer 1) |
| |
+---------------------------------+
| |
~ .... ~
| |
+---------------------------------+
| |
| (reduced) XMSS signature Sig | (h / d + len) * n bytes
| (layer d - 1) |
| |
+---------------------------------+
XMSS^MT Signature
XMSS ^ MT署名
To compute the XMSS^MT signature Sig_MT of a message M using an XMSS^MT private key SK_MT, XMSSMT_sign (Algorithm 16) described below uses treeSig as defined in Section 4.1.9. First, the signature index is set to idx_sig. Next, PRF is used to compute a pseudorandom n-byte string r. This n-byte string, idx_sig, and the root node from PK_MT are then used to compute a randomized message digest of length n. The message digest is signed using the WOTS+ key pair on the bottom layer with absolute index idx. The authentication path for the WOTS+ key pair and the root of the containing XMSS tree are computed. The root is signed by the parent XMSS tree. This is repeated until the top tree is reached.
XMSS ^ MT秘密鍵SK_MTを使用してメッセージMのXMSS ^ MT署名Sig_MTを計算するには、以下で説明するXMSSMT_sign（アルゴリズム16）は、セクション4.1.9で定義されているtreeSigを使用します。最初に、署名インデックスがidx_sigに設定されます。次に、PRFを使用して、擬似ランダムnバイト文字列rを計算します。次に、このnバイト文字列idx_sigとPK_MTからのルートノードを使用して、長さnのランダム化されたメッセージダイジェストを計算します。メッセージダイジェストは、絶対インデックスidxで最下層のWOTS +キーペアを使用して署名されます。 WOTS +キーペアの認証パスと、それを含むXMSSツリーのルートが計算されます。ルートは、親XMSSツリーによって署名されています。これは、トップツリーに到達するまで繰り返されます。
Algorithm 16: XMSSMT_sign - Generate an XMSS^MT signature and update
the XMSS^MT private key
Input: Message M, XMSS^MT private key SK_MT Output: Updated SK_MT, signature Sig_MT
入力：メッセージM、XMSS ^ MT秘密鍵SK_MT出力：更新されたSK_MT、署名Sig_MT
// Init
ADRS = toByte(0, 32);
SEED = getSEED(SK_MT);
SK_PRF = getSK_PRF(SK_MT);
idx_sig = getIdx(SK_MT);
// Update SK_MT
setIdx(SK_MT, idx_sig + 1);
// Message compression
byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32));
byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
// Sign
Sig_MT = idx_sig;
unsigned int idx_tree
= (h - h / d) most significant bits of idx_sig;
unsigned int idx_leaf = (h / d) least significant bits of idx_sig;
SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF
|| toByte(0, n) || SEED;
ADRS.setLayerAddress(0);
ADRS.setTreeAddress(idx_tree);
Sig_tmp = treeSig(M', SK, idx_leaf, ADRS);
Sig_MT = Sig_MT || r || Sig_tmp;
for ( j = 1; j < d; j++ ) {
root = treeHash(SK, 0, h / d, ADRS);
idx_leaf = (h / d) least significant bits of idx_tree;
idx_tree = (h - j * (h / d)) most significant bits of idx_tree;
SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF
|| toByte(0, n) || SEED;
ADRS.setLayerAddress(j);
ADRS.setTreeAddress(idx_tree);
Sig_tmp = treeSig(root, SK, idx_leaf, ADRS);
Sig_MT = Sig_MT || Sig_tmp;
}
return SK_MT || Sig_MT;
Algorithm 16 is only one method to compute XMSS^MT signatures. Time-memory trade-offs exist that allow reduction of the signing time to less than the signing time of an XMSS scheme with tree height h / d. These trade-offs 1) prevent certain values from being recomputed several times by keeping a state and 2) distribute all computations over all signature generations. Details can be found in [Huelsing13a].
アルゴリズム16は、XMSS ^ MT署名を計算する唯一の方法です。ツリーの高さがh / dのXMSSスキームの署名時間よりも署名時間を短縮できる時間メモリのトレードオフが存在します。これらのトレードオフは、1）状態を維持することによって特定の値が数回再計算されるのを防ぎ、2）すべての計算をすべての署名生成に分散します。詳細は[Huelsing13a]にあります。
XMSS^MT signature verification (Algorithm 17) can be summarized as d XMSS signature verifications with small changes. First, the message is hashed. The XMSS signatures are then all on n-byte values. Second, instead of comparing the computed root node to a given value, a signature on this root node is verified. Only the root node of the top tree is compared to the value in the XMSS^MT public key. XMSSMT_verify uses XMSS_rootFromSig. The function getXMSSSignature(Sig_MT, i) returns the ith reduced XMSS signature from the XMSS^MT signature Sig_MT. XMSSMT_verify takes as input an XMSS^MT signature Sig_MT, a message M, and a public key PK_MT. XMSSMT_verify returns true if and only if Sig_MT is a valid signature on M under public key PK_MT. Otherwise, it returns false.
XMSS ^ MT署名検証（アルゴリズム17）は、小さな変更を加えたd XMSS署名検証として要約できます。まず、メッセージがハッシュされます。 XMSS署名はすべてnバイトの値になります。次に、計算されたルートノードを指定された値と比較する代わりに、このルートノードの署名が検証されます。最上位ツリーのルートノードのみが、XMSS ^ MT公開キーの値と比較されます。 XMSSMT_verifyはXMSS_rootFromSigを使用します。関数getXMSSSignature（Sig_MT、i）は、XMSS ^ MT署名Sig_MTからi番目の縮小されたXMSS署名を返します。 XMSSMT_verifyは、XMSS ^ MT署名Sig_MT、メッセージM、および公開鍵PK_MTを入力として受け取ります。 XMSSMT_verifyは、Sig_MTが公開鍵PK_MTの下でMの有効な署名である場合にのみtrueを返します。それ以外の場合は、falseを返します。
Algorithm 17: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a
message M using an XMSS^MT public key PK_MT
Input: XMSS^MT signature Sig_MT, message M, XMSS^MT public key PK_MT Output: Boolean
入力：XMSS ^ MT署名Sig_MT、メッセージM、XMSS ^ MT公開鍵PK_MT出力：ブール値
idx_sig = getIdx(Sig_MT);
SEED = getSEED(PK_MT);
ADRS = toByte(0, 32);
byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT)
|| (toByte(idx_sig, n)), M);
unsigned int idx_leaf
= (h / d) least significant bits of idx_sig;
unsigned int idx_tree
= (h - h / d) most significant bits of idx_sig;
Sig' = getXMSSSignature(Sig_MT, 0);
ADRS.setLayerAddress(0);
ADRS.setTreeAddress(idx_tree);
byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
getAuth(Sig'), M', SEED, ADRS);
for ( j = 1; j < d; j++ ) {
idx_leaf = (h / d) least significant bits of idx_tree;
idx_tree = (h - j * h / d) most significant bits of idx_tree;
Sig' = getXMSSSignature(Sig_MT, j);
ADRS.setLayerAddress(j);
ADRS.setTreeAddress(idx_tree);
node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
getAuth(Sig'), node, SEED, ADRS);
}
if ( node == getRoot(PK_MT) ) {
return true;
} else {
return false;
}
Like for XMSS, an implementation MAY use a cryptographically secure pseudorandom method to generate the XMSS^MT private key from a single n-byte value. For example, the method explained below MAY be used. Other methods, such as the one in [HRS16], MAY be used. The choice of a pseudorandom method does not affect interoperability, but the cryptographic strength MUST match that of the used XMSS^MT parameters.
XMSSの場合と同様に、実装は、暗号で保護された疑似ランダムメソッドを使用して、単一のnバイト値からXMSS ^ MT秘密鍵を生成できます（MAY）。たとえば、以下で説明する方法を使用できます。 [HRS16]のような他の方法を使用してもかまいません。疑似ランダム方式の選択は相互運用性に影響を与えませんが、暗号強度は使用されるXMSS ^ MTパラメーターの強度と一致する必要があります。
For XMSS^MT, a method similar to that for XMSS and WOTS+ can be used. The method uses PRF. During key generation, a uniformly random n-byte string S_MT is sampled from a secure source of randomness. This seed S_MT is used to generate one n-byte value S for each XMSS key pair. This n-byte value can be used to compute the respective XMSS private key using the method described in Section 4.1.11. Let S[x][y] be the seed for the x^th XMSS private key on layer y. The seeds are computed as S[x][y] = PRF(PRF(S, toByte(y, 32)), toByte(x, 32)).
XMSS ^ MTの場合、XMSSおよびWOTS +の場合と同様の方法を使用できます。この方法ではPRFを使用します。鍵の生成中に、一様にランダムなnバイトの文字列S_MTが、安全なランダム性のソースからサンプリングされます。このシードS_MTは、XMSS鍵ペアごとに1つのnバイト値Sを生成するために使用されます。このnバイトの値は、セクション4.1.11で説明されている方法を使用して、それぞれのXMSS秘密鍵を計算するために使用できます。 S [x] [y]をレイヤーyのx番目のXMSS秘密鍵のシードとします。シードは、S [x] [y] = PRF（PRF（S、toByte（y、32））、toByte（x、32））として計算されます。
The content of Section 4.1.12 also applies to XMSS^MT.
セクション4.1.12の内容はXMSS ^ MTにも適用されます。
This section provides basic parameter sets that are assumed to cover most relevant applications. Parameter sets for two classical security levels are defined. Parameters with n = 32 provide a classical security level of 256 bits. Parameters with n = 64 provide a classical security level of 512 bits. Considering quantum-computer-aided attacks, these output sizes yield post-quantum security of 128 and 256 bits, respectively.
このセクションでは、ほとんどの関連アプリケーションをカバーすると想定される基本的なパラメーターセットを提供します。 2つの従来のセキュリティレベルのパラメータセットが定義されています。 n = 32のパラメーターは、256ビットの従来のセキュリティレベルを提供します。 n = 64のパラメーターは、512ビットの従来のセキュリティレベルを提供します。量子コンピュータ支援攻撃を考慮すると、これらの出力サイズは、それぞれ128ビットおよび256ビットのポスト量子セキュリティをもたらします。
While this document specifies several parameter sets, an implementation is only REQUIRED to provide support for verification of all REQUIRED parameter sets. The REQUIRED parameter sets all use SHA2-256 to instantiate all functions. The REQUIRED parameter sets are only distinguished by the tree height parameter h (which determines the number of signatures that can be done with a single key pair) and the number of layers d (which defines a trade-off between speed and signature size). An implementation MAY provide support for signature generation using any of the proposed parameter sets. For convenience, this document defines a default option for XMSS (XMSS_SHA2_20_256) and XMSS^MT (XMSSMT-SHA2_60/3_256). These are supposed to match the most generic requirements.
このドキュメントではいくつかのパラメーターセットを指定していますが、実装はすべての必須パラメーターセットの検証をサポートするためにのみ必須です。 REQUIREDパラメータセットはすべて、SHA2-256を使用してすべての関数をインスタンス化します。必須パラメーターセットは、ツリーの高さパラメーターh（単一のキーペアで実行できる署名の数を決定する）とレイヤーの数d（速度と署名サイズのトレードオフを定義する）によってのみ区別されます。実装は、提案されたパラメータセットのいずれかを使用した署名生成のサポートを提供する場合があります。便宜上、このドキュメントでは、XMSS（XMSS_SHA2_20_256）およびXMSS ^ MT（XMSSMT-SHA2_60 / 3_256）のデフォルトオプションを定義しています。これらは、最も一般的な要件に一致するはずです。
For the n = 32 setting, we give parameters that use SHA2-256 as defined in [FIPS180] and other parameters that use the SHA3/Keccak-based extendable-output function SHAKE-128 as defined in [FIPS202]. For the n = 64 setting, we give parameters that use SHA2-512 as defined in [FIPS180] and other parameters that use the SHA3/Keccak-based extendable-output functions SHAKE-256 as defined in [FIPS202]. The parameter sets using SHA2-256 are mandatory for deployment and therefore MUST be provided by any implementation. The remaining parameter sets specified in this document are OPTIONAL.
n = 32設定の場合、[FIPS180]で定義されているSHA2-256を使用するパラメーターと、[FIPS202]で定義されているSHA3 / Keccakベースの拡張可能出力関数SHAKE-128を使用する他のパラメーターを指定します。 n = 64設定の場合、[FIPS180]で定義されているSHA2-512を使用するパラメーターと、[FIPS202]で定義されているSHA3 / Keccakベースの拡張可能出力関数SHAKE-256を使用する他のパラメーターを指定します。 SHA2-256を使用するパラメーターセットは展開に必須であるため、実装によって提供する必要があります。このドキュメントで指定されている残りのパラメータセットはオプションです。
SHA2 does not provide a keyed-mode itself. To implement the keyed hash functions, the following is used for SHA2 with n = 32:
SHA2自体にはキーモードはありません。キー付きハッシュ関数を実装するには、n = 32のSHA2に以下を使用します。
F: SHA2-256(toByte(0, 32) || KEY || M),
F：SHA2-256（toByte（0、32）|| KEY || M）、
H: SHA2-256(toByte(1, 32) || KEY || M),
H：SHA2-256（toByte（1、32）|| KEY || M）、
H_msg: SHA2-256(toByte(2, 32) || KEY || M), and
PRF: SHA2-256(toByte(3, 32) || KEY || M).
教授：S2-258（タビヤテ（3、32）|| Kiy || M）。
Accordingly, for SHA2 with n = 64 we use:
したがって、n = 64のSHA2の場合、次を使用します。
F: SHA2-512(toByte(0, 64) || KEY || M),
F：SHA2-512（toByte（0、64）|| KEY || M）、
H: SHA2-512(toByte(1, 64) || KEY || M),
H：SHA2-512（toByte（1、64）|| KEY || M）、
H_msg: SHA2-512(toByte(2, 64) || KEY || M), and
PRF: SHA2-512(toByte(3, 64) || KEY || M).
教授：S2-512（Tabiyate（3、64）|| Kiy || M）。
The n-byte padding is used for two reasons. First, it is necessary that the internal compression function takes 2n-byte blocks, but keys are n and 3n bytes long. Second, the padding is used to achieve independence of the different function families. Finally, for the PRF, no full-fledged Hash-Based Message Authentication Code (HMAC) is needed as the message length is fixed, meaning that standard length extension attacks are not a concern here. For that reason, the simpler construction above suffices.
nバイトのパディングが使用される理由は2つあります。まず、内部圧縮関数は2nバイトのブロックを取る必要がありますが、キーの長さはnバイトと3nバイトです。次に、パディングを使用して、さまざまな関数ファミリーの独立性を実現します。最後に、PRFの場合、メッセージ長が固定されているため、本格的なハッシュベースのメッセージ認証コード（HMAC）は必要ありません。つまり、標準長の拡張攻撃はここでは問題になりません。そのため、上記の単純な構造で十分です。
Similar constructions are used with SHA3. To implement the keyed hash functions, the following is used for SHA3 with n = 32:
SHA3でも同様の構造が使用されています。キー付きハッシュ関数を実装するには、n = 32のSHA3に以下を使用します。
F: SHAKE128(toByte(0, 32) || KEY || M, 256),
F：SHAKE128（toByte（0、32）|| KEY || M、256）、
H: SHAKE128(toByte(1, 32) || KEY || M, 256),
H：SHAKE128（toByte（1、32）|| KEY || M、256）、
H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256),
H_msg：SHAKE128（toByte（2、32）|| KEY || M、256）、
PRF: SHAKE128(toByte(3, 32) || KEY || M, 256).
PRF：SHAKE128（toByte（3、32）|| KEY || M、256）。
Accordingly, for SHA3 with n = 64, we use:
したがって、n = 64のSHA3の場合、次を使用します。
F: SHAKE256(toByte(0, 64) || KEY || M, 512),
F：SHAKE256（toByte（0、64）|| KEY || M、512）、
H: SHAKE256(toByte(1, 64) || KEY || M, 512),
H：SHAKE256（toByte（1、64）|| KEY || M、512）、
H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512),
H_msg：SHAKE256（toByte（2、64）|| KEY || M、512）、
PRF: SHAKE256(toByte(3, 64) || KEY || M, 512).
PRF：SHAKE256（toByte（3、64）|| KEY || M、512）。
As for SHA2, an initial n-byte identifier is used to achieve independence of the different function families. While a shorter identifier could be used in case of SHA3, we use n bytes for consistency with the SHA2 implementations.
SHA2に関しては、異なる関数ファミリーの独立を達成するために、最初のnバイトの識別子が使用されます。 SHA3の場合は短い識別子を使用できますが、SHA2実装との一貫性を保つためにnバイトを使用しています。
To fully describe a WOTS+ signature method, the parameters n and w, as well as the functions F and PRF, MUST be specified. The following table defines several WOTS+ signature systems, each of which is identified by a name. Naming follows this convention: WOTSP-[Hashfamily]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16. Values for len are provided for convenience.
WOTS +署名方式を完全に説明するには、パラメーターnとw、および関数FとPRFを指定する必要があります。次の表は、いくつかのWOTS +署名システムを定義しています。それぞれのシステムは名前で識別されます。命名は次の規則に従います：WOTSP- [ハッシュファミリ] _ [ビット単位のn]。このドキュメントのすべてのパラメーターセットはw = 16を使用するため、命名にはwは含まれません。 lenの値は便宜上提供されています。
+-----------------+----------+----+----+-----+
| Name | F / PRF | n | w | len |
+-----------------+----------+----+----+-----+
| REQUIRED: | | | | |
| | | | | |
| WOTSP-SHA2_256 | SHA2-256 | 32 | 16 | 67 |
| | | | | |
| OPTIONAL: | | | | |
| | | | | |
| WOTSP-SHA2_512 | SHA2-512 | 64 | 16 | 131 |
| | | | | |
| WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 | 67 |
| | | | | |
| WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 |
+-----------------+----------+----+----+-----+
Table 1
表1
The implementation of the single functions is done as described above. External Data Representation (XDR) formats for WOTS+ are listed in Appendix A.
単一機能の実装は、上記のように行われます。 WOTS +の外部データ表現（XDR）形式は、付録Aにリストされています。
To fully describe an XMSS signature method, the parameters n, w, and h, as well as the functions F, H, H_msg, and PRF, MUST be specified. The following table defines different XMSS signature systems, each of which is identified by a name. Naming follows this convention: XMSS-[Hashfamily]_[h]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16.
XMSS署名メソッドを完全に説明するには、パラメーターn、w、およびh、および関数F、H、H_msg、およびPRFを指定する必要があります。次の表は、さまざまなXMSS署名システムを定義しています。それぞれのシステムは名前で識別されます。命名は、XMSS- [ハッシュファミリ] _ [h] _ [ビット単位のn]という規則に従います。このドキュメントのすべてのパラメーターセットはw = 16を使用するため、命名にはwは含まれません。
+-------------------+-----------+----+----+-----+----+
| Name | Functions | n | w | len | h |
+-------------------+-----------+----+----+-----+----+
| REQUIRED: | | | | | |
| | | | | | |
| XMSS-SHA2_10_256 | SHA2-256 | 32 | 16 | 67 | 10 |
| | | | | | |
| XMSS-SHA2_16_256 | SHA2-256 | 32 | 16 | 67 | 16 |
| | | | | | |
| XMSS-SHA2_20_256 | SHA2-256 | 32 | 16 | 67 | 20 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| XMSS-SHA2_10_512 | SHA2-512 | 64 | 16 | 131 | 10 |
| | | | | | |
| XMSS-SHA2_16_512 | SHA2-512 | 64 | 16 | 131 | 16 |
| | | | | | |
| XMSS-SHA2_20_512 | SHA2-512 | 64 | 16 | 131 | 20 |
| | | | | | |
| XMSS-SHAKE_10_256 | SHAKE128 | 32 | 16 | 67 | 10 |
| | | | | | |
| XMSS-SHAKE_16_256 | SHAKE128 | 32 | 16 | 67 | 16 |
| | | | | | |
| XMSS-SHAKE_20_256 | SHAKE128 | 32 | 16 | 67 | 20 |
| | | | | | |
| XMSS-SHAKE_10_512 | SHAKE256 | 64 | 16 | 131 | 10 |
| | | | | | |
| XMSS-SHAKE_16_512 | SHAKE256 | 64 | 16 | 131 | 16 |
| | | | | | |
| XMSS-SHAKE_20_512 | SHAKE256 | 64 | 16 | 131 | 20 |
+-------------------+-----------+----+----+-----+----+
Table 2
表2
The XDR formats for XMSS are listed in Appendix B.
XMSSのXDR形式は、付録Bにリストされています。
In contrast to traditional signature schemes like RSA or Digital Signature Algorithm (DSA), XMSS has a tree height parameter h that determines the number of messages that can be signed with one key pair. Increasing the height allows using a key pair for more signatures, but it also increases the signature size and slows down key generation, signing, and verification. To demonstrate the impact of different values of h, the following table shows signature size and runtimes. Runtimes are given as the number of calls to F and H when the BDS algorithm is used to compute authentication paths for the worst case. The last column shows the number of messages that can be signed with one key pair. The numbers are the same for the XMSS-SHAKE instances with same parameters h and n.
RSAやデジタル署名アルゴリズム（DSA）などの従来の署名方式とは異なり、XMSSには、1つの鍵ペアで署名できるメッセージの数を決定するツリーの高さパラメーターhがあります。高さを大きくすると、より多くの署名にキーペアを使用できますが、署名のサイズが大きくなり、キーの生成、署名、および検証が遅くなります。 hのさまざまな値の影響を示すために、次の表に署名のサイズと実行時間を示します。最悪の場合の認証パスを計算するためにBDSアルゴリズムが使用される場合、ランタイムはFおよびHへの呼び出し数として与えられます。最後の列は、1つの鍵ペアで署名できるメッセージの数を示しています。数値は、同じパラメーターhおよびnを持つXMSS-SHAKEインスタンスの場合と同じです。
+------------------+-------+------------+--------+--------+-------+
| Name | |Sig| | KeyGen | Sign | Verify | #Sigs |
+------------------+-------+------------+--------+--------+-------+
| REQUIRED: | | | | | |
| | | | | | |
| XMSS-SHA2_10_256 | 2,500 | 1,238,016 | 5,725 | 1,149 | 2^10 |
| | | | | | |
| XMSS-SHA2_16_256 | 2,692 | 79*10^6 | 9,163 | 1,155 | 2^16 |
| | | | | | |
| XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 | 1,159 | 2^20 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| XMSS-SHA2_10_512 | 9,092 | 2,417,664 | 11,165 | 2,237 | 2^10 |
| | | | | | |
| XMSS-SHA2_16_512 | 9,476 | 155*10^6 | 17,867 | 2,243 | 2^16 |
| | | | | | |
| XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 | 2,247 | 2^20 |
+------------------+-------+------------+--------+--------+-------+
Table 3
表3
As a default, users without special requirements should use option XMSS-SHA2_20_256, which allows signing of 2^20 messages with one key pair and provides reasonable speed and signature size. Users that require more signatures per key pair or faster key generation should consider XMSS^MT.
デフォルトでは、特別な要件のないユーザーはオプションXMSS-SHA2_20_256を使用する必要があります。これにより、1つのキーペアで2 ^ 20メッセージの署名が可能になり、妥当な速度と署名サイズが提供されます。キーペアごとにさらに多くの署名を必要とするユーザー、またはより速いキー生成を必要とするユーザーは、XMSS ^ MTを検討する必要があります。
To fully describe an XMSS^MT signature method, the parameters n, w, h, and d, as well as the functions F, H, H_msg, and PRF, MUST be specified. The following table defines different XMSS^MT signature systems, each of which is identified by a name. Naming follows this convention: XMSSMT-[Hashfamily]_[h]/[d]_[n in bits]. Naming does not include w as all parameter sets in this document use w=16.
XMSS ^ MT署名メソッドを完全に説明するには、パラメーターn、w、h、およびd、ならびに関数F、H、H_msg、およびPRFを指定する必要があります。次の表は、それぞれが名前で識別されるさまざまなXMSS ^ MT署名システムを定義しています。命名は次の規則に従います：XMSSMT- [ハッシュファミリ] _ [h] / [d] _ [nビット単位]。このドキュメントのすべてのパラメーターセットはw = 16を使用するため、命名にはwは含まれません。
+------------------------+-----------+----+----+-----+----+----+
| Name | Functions | n | w | len | h | d |
+------------------------+-----------+----+----+-----+----+----+
| REQUIRED: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_256 | SHA2-256 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_256 | SHA2-256 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_256 | SHA2-256 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_256 | SHA2-256 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_256 | SHA2-256 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_256 | SHA2-256 | 32 | 16 | 67 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_256 | SHA2-256 | 32 | 16 | 67 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_256 | SHA2-256 | 32 | 16 | 67 | 60 | 12 |
| | | | | | | |
| OPTIONAL: | | | | | | |
| | | | | | | |
| XMSSMT-SHA2_20/2_512 | SHA2-512 | 64 | 16 | 131 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHA2_20/4_512 | SHA2-512 | 64 | 16 | 131 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/2_512 | SHA2-512 | 64 | 16 | 131 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHA2_40/4_512 | SHA2-512 | 64 | 16 | 131 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHA2_40/8_512 | SHA2-512 | 64 | 16 | 131 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHA2_60/3_512 | SHA2-512 | 64 | 16 | 131 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHA2_60/6_512 | SHA2-512 | 64 | 16 | 131 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHA2_60/12_512 | SHA2-512 | 64 | 16 | 131 | 60 | 12 |
| | | | | | | |
| XMSSMT-SHAKE_20/2_256 | SHAKE128 | 32 | 16 | 67 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_20/4_256 | SHAKE128 | 32 | 16 | 67 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/2_256 | SHAKE128 | 32 | 16 | 67 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_40/4_256 | SHAKE128 | 32 | 16 | 67 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/8_256 | SHAKE128 | 32 | 16 | 67 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHAKE_60/3_256 | SHAKE128 | 32 | 16 | 67 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHAKE_60/6_256 | SHAKE128 | 32 | 16 | 67 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHAKE_60/12_256 | SHAKE128 | 32 | 16 | 67 | 60 | 12 |
| | | | | | | |
| XMSSMT-SHAKE_20/2_512 | SHAKE256 | 64 | 16 | 131 | 20 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_20/4_512 | SHAKE256 | 64 | 16 | 131 | 20 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/2_512 | SHAKE256 | 64 | 16 | 131 | 40 | 2 |
| | | | | | | |
| XMSSMT-SHAKE_40/4_512 | SHAKE256 | 64 | 16 | 131 | 40 | 4 |
| | | | | | | |
| XMSSMT-SHAKE_40/8_512 | SHAKE256 | 64 | 16 | 131 | 40 | 8 |
| | | | | | | |
| XMSSMT-SHAKE_60/3_512 | SHAKE256 | 64 | 16 | 131 | 60 | 3 |
| | | | | | | |
| XMSSMT-SHAKE_60/6_512 | SHAKE256 | 64 | 16 | 131 | 60 | 6 |
| | | | | | | |
| XMSSMT-SHAKE_60/12_512 | SHAKE256 | 64 | 16 | 131 | 60 | 12 |
+------------------------+-----------+----+----+-----+----+----+
Table 4
表4
XDR formats for XMSS^MT are listed in Appendix C.
XMSS ^ MTのXDR形式は、付録Cにリストされています。
In addition to the tree height parameter already used for XMSS, XMSS^MT has the parameter d that determines the number of tree layers. XMSS can be understood as XMSS^MT with a single layer, i.e., d=1. Hence, the choice of h has the same effect as for XMSS. The number of tree layers provides a trade-off between signature size on the one side and key generation and signing speed on the other side. Increasing the number of layers reduces key generation time exponentially and signing time linearly at the cost of increasing the signature size linearly. Essentially, an XMSS^MT signature contains one WOTSP signature per layer. Speed roughly corresponds to d-times the speed for XMSS with trees of height h/d.
XMSS ^ MTには、XMSSですでに使用されている木の高さパラメーターに加えて、木の層の数を決定するパラメーターdがあります。 XMSSは、単層、つまりd = 1のXMSS ^ MTとして理解できます。したがって、hの選択はXMSSの場合と同じ効果があります。ツリーレイヤーの数は、一方の署名サイズと、もう一方の鍵生成および署名速度の間のトレードオフを提供します。層の数を増やすと、キーの生成時間が指数関数的に減少し、署名時間が線形に増加する代わりに、署名時間が線形に減少します。基本的に、XMSS ^ MTシグニチャには、レイヤごとに1つのWOTSPシグニチャが含まれています。速度は、高さh / dの木があるXMSSの速度のおよそd倍に相当します。
To demonstrate the impact of different values of h and d, the following table shows signature size and runtimes. Runtimes are given as the number of calls to F and H when the BDS algorithm and distributed signature generation are used. Timings are worst-case times. The last column shows the number of messages that can be signed with one key pair. The numbers are the same for the XMSS- SHAKE instances with same parameters h and n. Due to formatting limitations, only the parameter part of the parameter set names are given, omitting the name "XMSSMT".
hとdの異なる値の影響を示すために、次の表に署名のサイズと実行時間を示します。ランタイムは、BDSアルゴリズムと分散署名生成が使用されている場合のFとHの呼び出し数として与えられます。タイミングは最悪の場合です。最後の列は、1つの鍵ペアで署名できるメッセージの数を示しています。数値は、同じパラメーターhおよびnを持つXMSS- SHAKEインスタンスの場合と同じです。フォーマットの制限により、パラメーターセット名のパラメーター部分のみが指定され、「XMSSMT」という名前は省略されています。
+----------------+---------+------------+--------+--------+-------+
| Name | |Sig| | KeyGen | Sign | Verify | #Sigs |
+----------------+---------+------------+--------+--------+-------+
| REQUIRED: | | | | | |
| | | | | | |
| SHA2_20/2_256 | 4,963 | 2,476,032 | 7,227 | 2,298 | 2^20 |
| | | | | | |
| SHA2_20/4_256 | 9,251 | 154,752 | 4,170 | 4,576 | 2^20 |
| | | | | | |
| SHA2_40/2_256 | 5,605 | 2,535*10^6 | 13,417 | 2,318 | 2^40 |
| | | | | | |
| SHA2_40/4_256 | 9,893 | 4,952,064 | 7,227 | 4,596 | 2^40 |
| | | | | | |
| SHA2_40/8_256 | 18,469 | 309,504 | 4,170 | 9,152 | 2^40 |
| | | | | | |
| SHA2_60/3_256 | 8,392 | 3,803*10^6 | 13,417 | 3,477 | 2^60 |
| | | | | | |
| SHA2_60/6_256 | 14,824 | 7,428,096 | 7,227 | 6,894 | 2^60 |
| | | | | | |
| SHA2_60/12_256 | 27,688 | 464,256 | 4,170 | 13,728 | 2^60 |
| | | | | | |
| OPTIONAL: | | | | | |
| | | | | | |
| SHA2_20/2_512 | 18,115 | 4,835,328 | 14,075 | 4,474 | 2^20 |
| | | | | | |
| SHA2_20/4_512 | 34,883 | 302,208 | 8,138 | 8,928 | 2^20 |
| | | | | | |
| SHA2_40/2_512 | 19,397 | 4,951*10^6 | 26,025 | 4,494 | 2^40 |
| | | | | | |
| SHA2_40/4_512 | 36,165 | 9,670,656 | 14,075 | 8,948 | 2^40 |
| | | | | | |
| SHA2_40/8_512 | 69,701 | 604,416 | 8,138 | 17,856 | 2^40 |
| | | | | | |
| SHA2_60/3_512 | 29,064 | 7,427*10^6 | 26,025 | 6,741 | 2^60 |
| | | | | | |
| SHA2_60/6_512 | 54,216 | 14,505,984 | 14,075 | 13,422 | 2^60 |
| | | | | | |
| SHA2_60/12_512 | 104,520 | 906,624 | 8,138 | 26,784 | 2^60 |
+----------------+---------+------------+--------+--------+-------+
Table 5
表5
As a default, users without special requirements should use option XMSSMT-SHA2_60/3_256, which allows signing of 2^60 messages with one key pair (this is a virtually unbounded number of signatures). At the same time, signature size and speed are well balanced.
デフォルトでは、特別な要件のないユーザーはオプションXMSSMT-SHA2_60 / 3_256を使用する必要があります。これにより、1つのキーペアで2 ^ 60メッセージの署名が可能になります（これは実質的に無制限の数の署名です）。同時に、署名のサイズと速度のバランスが取れています。
The goal of this note is to describe the WOTS+, XMSS, and XMSS^MT algorithms based on the scientific literature. The description is done in a modular way that allows basing a description of stateless hash-based signature algorithms like SPHINCS [BHH15] on it.
このノートの目的は、科学文献に基づいてWOTS +、XMSS、およびXMSS ^ MTアルゴリズムを説明することです。説明は、SPHINCS [BHH15]のようなステートレスハッシュベースの署名アルゴリズムの説明を基にできるモジュール方式で行われます。
This note slightly deviates from the scientific literature by using a tweak that prevents multi-user and multi-target attacks against H_msg. To this end, the public key as well as the index of the used one-time key pair become part of the hash function key. Thereby, we achieve a domain separation that forces an attacker to decide which hash value to attack.
このメモは、H_msgに対するマルチユーザーおよびマルチターゲットの攻撃を防ぐ微調整を使用することにより、科学文献からわずかに逸脱しています。この目的のために、公開鍵と使用されたワンタイムキーペアのインデックスがハッシュ関数キーの一部になります。これにより、攻撃者に攻撃するハッシュ値を決定させるドメイン分離を実現します。
For the generation of the randomness used for randomized message hashing, we apply a PRF, keyed with a secret value, to the index of the used one-time key pair instead of the message. The reason is that this requires processing the message only once instead of twice. For long messages, this improves speed and simplifies implementations on resource-constrained devices that cannot hold the entire message in storage.
ランダム化されたメッセージのハッシュに使用されるランダム性を生成するために、秘密の値でキーイングされたPRFを、メッセージの代わりに使用されるワンタイムキーペアのインデックスに適用します。これは、メッセージの処理が2回ではなく1回だけで済むためです。長いメッセージの場合、これにより速度が向上し、メッセージ全体をストレージに保持できないリソースに制約のあるデバイスでの実装が簡素化されます。
We give one mandatory set of parameters using SHA2-256. The reasons are twofold. On the one hand, SHA2-256 is part of most cryptographic libraries. On the other hand, a 256-bit hash function leads to parameters that provide 128 bits of security even against quantum-computer-aided attacks. A post-quantum security level of 256 bits seems overly conservative. However, to prepare for possible cryptanalytic breakthroughs, we also provide OPTIONAL parameter sets using the less widely supported SHA2-512, SHAKE-256, and SHAKE-512 functions.
SHA2-256を使用して1つの必須パラメーターセットを指定します。理由は2つあります。一方では、SHA2-256はほとんどの暗号化ライブラリの一部です。一方、256ビットのハッシュ関数は、量子コンピューター支援攻撃に対しても128ビットのセキュリティを提供するパラメーターにつながります。 256ビットのポスト量子セキュリティレベルは非常に保守的です。ただし、暗号解読の可能性に備えるために、あまり広くサポートされていないSHA2-512、SHAKE-256、およびSHAKE-512関数を使用したOPTIONALパラメーターセットも提供しています。
We suggest the value w = 16 for the Winternitz parameter. No bigger values are included since the decrease in signature size then becomes less significant. Furthermore, the value w = 16 considerably simplifies the implementations of some of the algorithms. Please note that we do allow w = 4 but limit the specified parameter sets to w = 16 for efficiency reasons.
Winternitzパラメータには値w = 16をお勧めします。シグネチャサイズの減少はそれほど重要ではなくなるため、大きな値は含まれません。さらに、値w = 16は、一部のアルゴリズムの実装を大幅に簡略化します。 w = 4は許可されますが、効率上の理由から、指定されたパラメーターセットをw = 16に制限することに注意してください。
The signature and public key formats are designed so that they are easy to parse. Each format starts with a 32-bit enumeration value that indicates all of the details of the signature algorithm and hence defines all of the information that is needed in order to parse the format.
署名と公開鍵の形式は、解析しやすいように設計されています。各フォーマットは、署名アルゴリズムのすべての詳細を示す32ビットの列挙値で始まり、フォーマットを解析するために必要なすべての情報を定義します。
For testing purposes, a reference implementation in C is available. The code contains a basic implementation that closely follows the pseudocode in this document and an optimized implementation that uses the BDS algorithm [BDS08] to compute authentication paths and distributed signature generation as described in [HRB13] for XMSS^MT.
テスト目的で、Cのリファレンス実装が利用可能です。コードには、このドキュメントの疑似コードに厳密に従う基本的な実装と、XMSS ^ MTの[HRB13]で説明されているように、BDSアルゴリズム[BDS08]を使用して認証パスと分散署名生成を計算する最適化された実装が含まれます。
The code is permanently available at <https://github.com/joostrijneveld/xmss-reference>.
コードは<https://github.com/joostrijneveld/xmss-reference>で永続的に利用できます。
The Internet Assigned Numbers Authority (IANA) has created three registries: one for WOTS+ signatures (as defined in Section 3), one for XMSS signatures (as defined in Section 4), and one for XMSS^MT signatures (as defined in Section 4). For the sake of clarity and convenience, the first collection of WOTS+, XMSS, and XMSS^MT parameter sets is defined in Section 5. Additions to these registries require that a specification be documented in an RFC or another permanent and readily available reference in sufficient detail as defined by the "Specification Required" policy described in [RFC8126] to make interoperability between independent implementations possible. Each entry in these registries contains the following elements:
Internet Assigned Numbers Authority（IANA）は、3つのレジストリを作成しました。1つはWOTS +署名（セクション3で定義）、XMSS署名（セクション4で定義）、およびXMSS ^ MT署名（セクション4で定義）です。 ）。明確さと利便性のために、WOTS +、XMSS、およびXMSS ^ MTパラメータセットの最初のコレクションはセクション5で定義されています。これらのレジストリへの追加は、仕様がRFCまたは別の永続的ですぐに利用可能な参照で十分に文書化されていることを要求します独立した実装間の相互運用性を可能にするために、[RFC8126]で説明されている "Specification Required"ポリシーで定義されている詳細。これらのレジストリの各エントリには、次の要素が含まれています。
o a short name, such as "XMSS_SHA2_20_256",
o 「XMSS_SHA2_20_256」などの短い名前
o a positive number, and
o 正の数、および
o a reference to a specification that completely defines the signature method test cases or provides a reference implementation that can be used to verify the correctness of an implementation (or a reference to such an implementation).
o 署名メソッドのテストケースを完全に定義する仕様への参照、または実装の正しさを検証するために使用できる参照実装（またはそのような実装への参照）を提供します。
Requests to add an entry to these registries MUST include the name and the reference. The number is assigned by IANA. These number assignments SHOULD use the smallest available positive number. Submitters MUST have their requests reviewed and approved. Designated Experts for this task as requested by the "Specification Required" policy defined by [RFC8126] will be assigned by the Internet Engineering Steering Group (IESG). The IESG can be contacted at iesg@ietf.org. Interested applicants that are unfamiliar with IANA processes should visit <http://www.iana.org>.
これらのレジストリにエントリを追加するリクエストには、名前と参照を含める必要があります。番号はIANAによって割り当てられます。これらの番号割り当ては、利用可能な最小の正数を使用する必要があります（SHOULD）。提出者は、その要求をレビューして承認する必要があります。 [RFC8126]によって定義された「Specification Required」ポリシーによって要求されたこのタスクの指定エキスパートは、インターネットエンジニアリングステアリンググループ（IESG）によって割り当てられます。 IESGはiesg@ietf.orgに連絡できます。 IANAプロセスに慣れていない興味のある申請者は、<http://www.iana.org>にアクセスしてください。
The number 0x00000000 (decimal 0) is Reserved. The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF (decimal 4,294,967,295) inclusive will not be assigned by IANA and are Reserved for Private Use; no attempt will be made to prevent multiple sites from using the same value in different (and incompatible) ways [RFC8126].
数値0x00000000（10進数の0）は予約済みです。 0xDDDDDDDD（10進数の3,722,304,989）から0xFFFFFFFF（10進数の4,294,967,295）までの数値はIANAによって割り当てられず、私用に予約されています。複数のサイトが異なる（互換性のない）方法で同じ値を使用することを防ぐ試みは行われません[RFC8126]。
The "WOTS+ Signatures" registry is as follows.
「WOTS + Signatures」レジストリは以下の通りです。
+--------------------+-----------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+-----------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | WOTSP-SHA2_256 | Section 5.2 |
| | | |
| 0x00000002 | WOTSP-SHA2_512 | Section 5.2 |
| | | |
| 0x00000003 | WOTSP-SHAKE_256 | Section 5.2 |
| | | |
| 0x00000004 | WOTSP-SHAKE_512 | Section 5.2 |
+--------------------+-----------------+-------------+
Table 6
表6
The "XMSS Signatures" registry is as follows.
「XMSS Signatures」レジストリは次のとおりです。
+--------------------+-------------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+-------------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | XMSS-SHA2_10_256 | Section 5.3 |
| | | |
| 0x00000002 | XMSS-SHA2_16_256 | Section 5.3 |
| | | |
| 0x00000003 | XMSS-SHA2_20_256 | Section 5.3 |
| | | |
| 0x00000004 | XMSS-SHA2_10_512 | Section 5.3 |
| | | |
| 0x00000005 | XMSS-SHA2_16_512 | Section 5.3 |
| | | |
| 0x00000006 | XMSS-SHA2_20_512 | Section 5.3 |
| | | |
| 0x00000007 | XMSS-SHAKE_10_256 | Section 5.3 |
| | | |
| 0x00000008 | XMSS-SHAKE_16_256 | Section 5.3 |
| | | |
| 0x00000009 | XMSS-SHAKE_20_256 | Section 5.3 |
| | | |
| 0x0000000A | XMSS-SHAKE_10_512 | Section 5.3 |
| | | |
| 0x0000000B | XMSS-SHAKE_16_512 | Section 5.3 |
| | | |
| 0x0000000C | XMSS-SHAKE_20_512 | Section 5.3 |
+--------------------+-------------------+-------------+
Table 7
表7
The "XMSS^MT Signatures" registry is as follows.
「XMSS ^ MT Signatures」レジストリは次のとおりです。
+--------------------+------------------------+-------------+
| Numeric Identifier | Name | Reference |
+--------------------+------------------------+-------------+
| 0x00000000 | Reserved | this RFC |
| | | |
| 0x00000001 | XMSSMT-SHA2_20/2_256 | Section 5.4 |
| | | |
| 0x00000002 | XMSSMT-SHA2_20/4_256 | Section 5.4 |
| | | |
| 0x00000003 | XMSSMT-SHA2_40/2_256 | Section 5.4 |
| | | |
| 0x00000004 | XMSSMT-SHA2_40/4_256 | Section 5.4 |
| | | |
| 0x00000005 | XMSSMT-SHA2_40/8_256 | Section 5.4 |
| | | |
| 0x00000006 | XMSSMT-SHA2_60/3_256 | Section 5.4 |
| | | |
| 0x00000007 | XMSSMT-SHA2_60/6_256 | Section 5.4 |
| | | |
| 0x00000008 | XMSSMT-SHA2_60/12_256 | Section 5.4 |
| | | |
| 0x00000009 | XMSSMT-SHA2_20/2_512 | Section 5.4 |
| | | |
| 0x0000000A | XMSSMT-SHA2_20/4_512 | Section 5.4 |
| | | |
| 0x0000000B | XMSSMT-SHA2_40/2_512 | Section 5.4 |
| | | |
| 0x0000000C | XMSSMT-SHA2_40/4_512 | Section 5.4 |
| | | |
| 0x0000000D | XMSSMT-SHA2_40/8_512 | Section 5.4 |
| | | |
| 0x0000000E | XMSSMT-SHA2_60/3_512 | Section 5.4 |
| | | |
| 0x0000000F | XMSSMT-SHA2_60/6_512 | Section 5.4 |
| | | |
| 0x00000010 | XMSSMT-SHA2_60/12_512 | Section 5.4 |
| | | |
| 0x00000011 | XMSSMT-SHAKE_20/2_256 | Section 5.4 |
| | | |
| 0x00000012 | XMSSMT-SHAKE_20/4_256 | Section 5.4 |
| | | |
| 0x00000013 | XMSSMT-SHAKE_40/2_256 | Section 5.4 |
| | | |
| 0x00000014 | XMSSMT-SHAKE_40/4_256 | Section 5.4 |
| | | |
| 0x00000015 | XMSSMT-SHAKE_40/8_256 | Section 5.4 |
| | | |
| 0x00000016 | XMSSMT-SHAKE_60/3_256 | Section 5.4 |
| | | |
| 0x00000017 | XMSSMT-SHAKE_60/6_256 | Section 5.4 |
| | | |
| 0x00000018 | XMSSMT-SHAKE_60/12_256 | Section 5.4 |
| | | |
| 0x00000019 | XMSSMT-SHAKE_20/2_512 | Section 5.4 |
| | | |
| 0x0000001A | XMSSMT-SHAKE_20/4_512 | Section 5.4 |
| | | |
| 0x0000001B | XMSSMT-SHAKE_40/2_512 | Section 5.4 |
| | | |
| 0x0000001C | XMSSMT-SHAKE_40/4_512 | Section 5.4 |
| | | |
| 0x0000001D | XMSSMT-SHAKE_40/8_512 | Section 5.4 |
| | | |
| 0x0000001E | XMSSMT-SHAKE_60/3_512 | Section 5.4 |
| | | |
| 0x0000001F | XMSSMT-SHAKE_60/6_512 | Section 5.4 |
| | | |
| 0x00000020 | XMSSMT-SHAKE_60/12_512 | Section 5.4 |
+--------------------+------------------------+-------------+
Table 8
表8
An IANA registration of a signature system does not constitute an endorsement of that system or its security.
署名システムのIANA登録は、そのシステムまたはそのセキュリティの推奨を構成するものではありません。
A signature system is considered secure if it prevents an attacker from forging a valid signature. More specifically, consider a setting in which an attacker gets a public key and can learn signatures on arbitrary messages of its choice. A signature system is secure if, even in this setting, the attacker cannot produce a new message/signature pair of his choosing such that the verification algorithm accepts.
攻撃者が有効な署名を偽造するのを防ぐ場合、署名システムは安全であると見なされます。より具体的には、攻撃者が公開鍵を取得し、選択した任意のメッセージの署名を学習できる設定について考えます。この設定でも、検証アルゴリズムが受け入れるように攻撃者が選択した新しいメッセージ/署名のペアを生成できない場合、署名システムは安全です。
Preventing an attacker from mounting an attack means that the attack is computationally too expensive to be carried out. There are various estimates for when a computation is too expensive to be done. For that reason, this note only describes how expensive it is for an attacker to generate a forgery. Parameters are accompanied by a bit security value. The meaning of bit security is as follows. A parameter set grants b bits of security if the best attack takes at least 2^(b - 1) bit operations to achieve a success probability of 1/2. Hence, to mount a successful attack, an attacker needs to perform 2^b bit operations on average. The given values for bit security were estimated according to [HRS16].
攻撃者が攻撃を仕掛けることを防ぐということは、その攻撃が計算上高すぎて実行できないことを意味します。計算が高すぎて実行できない場合には、さまざまな見積もりがあります。そのため、このメモでは、攻撃者が偽造を生成することのコストについてのみ説明しています。パラメータにはビットセキュリティ値が付属しています。ビットセキュリティの意味は以下の通りです。最善の攻撃が少なくとも2 ^（b-1）ビット演算を実行して1/2の成功確率を達成する場合、パラメータセットはbビットのセキュリティを付与します。したがって、攻撃を成功させるためには、攻撃者は平均で2 ^ bビットの操作を実行する必要があります。ビットセキュリティの所定の値は、[HRS16]に従って推定されました。
A full security proof for all schemes described in this document can be found in [HRS16]. This proof shows that an attacker has to break at least one out of certain security properties of the used hash functions and PRFs to forge a signature in any of the described schemes. The proof in [HRS16] considers an initial message compression different from the randomized hashing used here. We comment on this below. For the original schemes, these proofs show that an attacker has to break certain minimal security properties. In particular, it is not sufficient to break the collision resistance of the hash functions to generate a forgery.
このドキュメントで説明されているすべてのスキームの完全なセキュリティ証明は、[HRS16]にあります。この証明は、説明されたスキームのいずれかで署名を偽造するために、攻撃者が使用されるハッシュ関数とPRFの特定のセキュリティプロパティから少なくとも1つを破る必要があることを示しています。 [HRS16]の証明では、ここで使用されるランダム化されたハッシュとは異なる初期メッセージ圧縮を考慮しています。以下でこれについてコメントします。元のスキームでは、これらの証拠は、攻撃者が特定の最小限のセキュリティプロパティを破らなければならないことを示しています。特に、偽造を生成するためにハッシュ関数の衝突耐性を破るだけでは不十分です。
More specifically, the requirements on the used functions are that F and H are post-quantum multi-function multi-target second-preimage resistant keyed functions, F fulfills an additional statistical requirement that roughly says that most images have at least two preimages, PRF is a post-quantum pseudorandom function, and H_msg is a post-quantum multi-target extended target collision-resistant keyed hash function. For detailed definitions of these properties see [HRS16]. To give some intuition: multi-function multi-target second-preimage resistance is an extension of second-preimage resistance to keyed hash functions, covering the case where an adversary succeeds if it finds a second preimage for one out of many values. The same holds for multi-target extended target collision resistance, which just lacks the multi-function identifier as target collision resistance already considers keyed hash functions. The proof in [HRS16] splits PRF into two functions. When PRF is used for pseudorandom key generation or generation of randomness for randomized message hashing, it is still considered a pseudorandom function. Whenever PRF is used to generate bitmasks and hash function keys, it is modeled as a random oracle. This is due to technical reasons in the proof, and an implementation using a pseudorandom function is secure.
より具体的には、使用される関数の要件は、FとHがポスト量子多機能マルチターゲットの第2プリイメージ耐性キー関数であり、Fが追加の統計的要件を満たしているということです。はポスト量子擬似ランダム関数で、H_msgはポスト量子マルチターゲット拡張ターゲット衝突耐性キー付きハッシュ関数です。これらのプロパティの詳細な定義については、[HRS16]を参照してください。いくつかの直感を与えるために：マルチファンクションマルチターゲットの第2プリイメージ耐性は、キー付きハッシュ関数に対する第2プリイメージ耐性の拡張であり、敵が多くの値から1つの第2プリイメージを見つけた場合に成功するケースをカバーします。マルチターゲット拡張ターゲットコリジョンレジスタンスについても同じことが言えます。ターゲットコリジョンレジスタンスはすでにキー付きハッシュ関数を考慮しているため、マルチファンクションIDが欠けているだけです。 [HRS16]の証明は、PRFを2つの機能に分割します。 PRFが疑似ランダムキーの生成またはランダム化されたメッセージハッシュのランダム性の生成に使用される場合でも、疑似ランダム関数と見なされます。 PRFを使用してビットマスクとハッシュ関数キーを生成する場合は常に、ランダムオラクルとしてモデル化されます。これは証明の技術的な理由によるものであり、疑似乱数関数を使用した実装は安全です。
The proof in [HRS16] considers classical randomized hashing for the initial message compression, i.e., H(r, M) instead of H(r || getRoot(PK) || index, M). This classical randomized hashing allows getting a security reduction from extended target collision resistance [HRS16], a property that is conjectured to be strictly weaker than collision resistance. However, it turns out that in this case, an attacker could still launch a multi-target attack even against multiple users at the same time. The reason is that the adversary attacking u users at the same time learns u * 2^h randomized hashes H(r_i_j || M_i_j) with signature index i in [0, 2^h - 1] and user index j in [0, u]. It suffices to find a single pair (r*, M*) such that H(r* || M*) = H(r_i_u || M_i_u) for one out of the u * 2^h learned hashes. Hence, an attacker can do a brute-force search in time 2^n / u * 2^h instead of 2^n.
[HRS16]の証明では、初期メッセージ圧縮に従来のランダム化ハッシュ、つまりH（r || getRoot（PK）|| index、M）ではなくH（r、M）を考慮しています。この古典的なランダム化ハッシュにより、拡張ターゲット衝突抵抗[HRS16]からセキュリティを削減できます。これは、衝突抵抗よりも厳密に弱いと推測されるプロパティです。ただし、この場合、攻撃者は同時に複数のユーザーに対してもマルチターゲット攻撃を仕掛けることができることがわかりました。その理由は、u人のユーザーを同時に攻撃する攻撃者が、[0、2 ^ h-1]の署名インデックスiと[0、 u]。 u * 2 ^ hの学習されたハッシュのうちの1つに対して、H（r * || M *）= H（r_i_u || M_i_u）のような単一のペア（r *、M *）を見つけることで十分です。したがって、攻撃者は2 ^ nではなく2 ^ n / u * 2 ^ hでブルートフォース検索を実行できます。
The indexed randomized hashing H(r || getRoot(PK) || toByte(idx, n), M) used in this work makes the hash function calls position- and user-dependent. This thwarts the above attack because each hash function evaluation during an attack can only target one of the learned randomized hash values. More specifically, an attacker now has to decide which index idx and which root value to use for each query. If one assumes that the used hash function is a random function, it can be shown that a multi-user existential forgery attack that targets this message compression has a complexity of 2^n hash function calls.
この作業で使用されるインデックス付きランダム化ハッシュH（r || getRoot（PK）|| toByte（idx、n）、M）は、ハッシュ関数呼び出しを位置とユーザーに依存させます。攻撃中の各ハッシュ関数の評価は、学習したランダム化されたハッシュ値の1つのみを対象にすることができるため、これは上記の攻撃を阻止します。具体的には、攻撃者は各クエリに使用するインデックスidxとルート値を決定する必要があります。使用されているハッシュ関数がランダム関数であると想定すると、このメッセージ圧縮を標的とするマルチユーザー存在型偽造攻撃は、2 ^ nハッシュ関数呼び出しの複雑さを持っていることがわかります。
The given bit security values were estimated based on the complexity of the best-known generic attacks against the required security properties of the used hash and pseudorandom functions, assuming conventional and quantum adversaries. At the time of writing, generic attacks are the best-known attacks for the parameters suggested in the classical setting. Also, in the quantum setting, there are no dedicated attacks known that perform better than generic attacks. Nevertheless, the topic of quantum cryptanalysis of hash functions is not as well understood as in the classical setting.
与えられたビットセキュリティ値は、使用されるハッシュ関数と疑似ランダム関数の必要なセキュリティプロパティに対する最もよく知られている一般的な攻撃の複雑さに基づいて推定され、従来の攻撃者と量子攻撃者を想定しています。これを書いている時点では、一般的な攻撃は、古典的な設定で提案されているパラメータに対する最もよく知られている攻撃です。また、クォンタムの設定では、一般的な攻撃よりもパフォーマンスが高い既知の専用攻撃はありません。それにもかかわらず、ハッシュ関数の量子暗号解読のトピックは、古典的な設定ほどよく理解されていません。
The assumptions one has to make to prove security of the described schemes are minimal in the following sense. Any signature algorithm that allows arbitrary size messages relies on the security of a cryptographic hash function, either on collision resistance or on extended target collision resistance if randomized hashing is used for message compression. For the schemes described here, this is already sufficient to be secure. In contrast, common signature schemes like RSA, DSA, and Elliptic Curve Digital Signature Algorithm (ECDSA) additionally rely on the conjectured hardness of certain mathematical problems.
記述されたスキームのセキュリティを証明するために行わなければならない仮定は、次の意味で最小限です。任意のサイズのメッセージを許可するすべての署名アルゴリズムは、暗号化ハッシュ関数のセキュリティに依存します。これは、衝突耐性またはランダム化ハッシュがメッセージ圧縮に使用されている場合は拡張ターゲット衝突耐性に依存します。ここで説明するスキームの場合、これはすでに安全に十分です。対照的に、RSA、DSA、楕円曲線デジタル署名アルゴリズム（ECDSA）などの一般的な署名方式は、特定の数学的問題の推測される硬さにさらに依存しています。
A post-quantum cryptosystem is a system that is secure against attackers with access to a reasonably sized quantum computer. At the time of writing this note, whether or not it is feasible to build such a machine is an open conjecture. However, significant progress was made over the last few years in this regard. Hence, we consider it a matter of risk assessment to prepare for this case.
ポスト量子暗号システムは、適度なサイズの量子コンピューターにアクセスできる攻撃者に対して安全なシステムです。このノートを書いている時点では、そのようなマシンを構築することが可能であるかどうかは、オープンな推測です。しかし、この点で過去数年間で大きな進歩がありました。したがって、このケースに備えることはリスク評価の問題であると考えます。
In contrast to RSA, DSA, and ECDSA, the described signature systems are post-quantum-secure if they are used with an appropriate cryptographic hash function. In particular, for post-quantum security, the size of n must be twice the size required for classical security. This is in order to protect against quantum square-root attacks due to Grover's algorithm. [HRS16] shows that variants of Grover's algorithm are the optimal generic attacks against the security properties of hash functions required for the described schemes.
RSA、DSA、およびECDSAとは対照的に、説明されている署名システムは、適切な暗号化ハッシュ関数と共に使用された場合、量子後安全です。特に、量子化後のセキュリティでは、nのサイズは従来のセキュリティに必要なサイズの2倍でなければなりません。これは、グローバーのアルゴリズムによる量子平方根攻撃から保護するためです。 [HRS16]は、Groverのアルゴリズムのバリアントが、説明したスキームに必要なハッシュ関数のセキュリティプロパティに対する最適な一般的な攻撃であることを示しています。
As stated above, we only consider generic attacks here, as cryptographic hash functions should be deprecated as soon as dedicated attacks that perform significantly better exist. This also applies to the quantum setting. As soon as dedicated quantum attacks against the used hash function that can perform significantly better than the described generic attacks exist, these hash functions should not be used anymore for the described schemes, or the computation of the security level has to be redone.
上記のように、ここでは一般的な攻撃のみを考慮します。暗号化ハッシュ関数は、パフォーマンスが大幅に向上する専用の攻撃が存在するようになるとすぐに廃止されるはずです。これは、クォンタム設定にも適用されます。記述された一般的な攻撃よりもはるかに優れた使用可能なハッシュ関数に対する専用の量子攻撃が存在するようになるとすぐに、これらのハッシュ関数は、記述されたスキームではもう使用されないか、セキュリティレベルの計算をやり直す必要があります。
[FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, August 2015.
[FIPS180]米国国立標準技術研究所、「Secure Hash Standard（SHS）」、FIPS PUB 180-4、DOI 10.6028 / NIST.FIPS.180-4、2015年8月。
[FIPS202] National Institute of Standards and Technology, "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202, August 2015.
[FIPS202]米国国立標準技術研究所、「SHA-3標準：順列ベースのハッシュと拡張可能な出力関数」、FIPS PUB 202、DOI 10.6028 / NIST.FIPS.202、2015年8月。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.
[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するキーワード」、BCP 14、RFC 2119、DOI 10.17487 / RFC2119、1997年3月、<https://www.rfc-editor.org/info/ rfc2119>。
[RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <https://www.rfc-editor.org/info/rfc4506>.
[RFC4506] Eisler、M。、編、「XDR：外部データ表現標準」、STD 67、RFC 4506、DOI 10.17487 / RFC4506、2006年5月、<https://www.rfc-editor.org/info/rfc4506 >。
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>.
[RFC8126]コットン、M。、レイバ、B。、およびT.ナルテン、「RFCでIANAの考慮事項セクションを作成するためのガイドライン」、BCP 26、RFC 8126、DOI 10.17487 / RFC8126、2017年6月、<https：// www .rfc-editor.org / info / rfc8126>。
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8174] Leiba、B。、「RFC 2119キーワードの大文字と小文字のあいまいさ」、BCP 14、RFC 8174、DOI 10.17487 / RFC8174、2017年5月、<https://www.rfc-editor.org/info/ rfc8174>。
[BDH11] Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions", Lecture Notes in Computer Science, Volume 7071, Post-Quantum Cryptography, DOI 10.1007/978-3-642-25405-5_8, 2011.
[BDH11] Buchmann、J.、Dahmen、E。、およびA. Huelsing、「XMSS-最小限のセキュリティ仮定に基づく実用的なフォワードセキュア署名方式」、コンピュータサイエンスの講義ノート、ボリューム7071、ポスト量子暗号、DOI 10.1007 / 978-3-642-25405-5_8、2011。
[BDS08] Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree Traversal Revisited", Lecture Notes in Computer Science, Volume 5299, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88403-3_5, 2008.
[BDS08] Buchmann、J.、Dahmen、E。、およびM. Schneider、「Merkle Tree Traversal Revisited」、Lecture Notes in Computer Science、Volume 5299、Post-Quantum Cryptography、DOI 10.1007 / 978-3-540-88403- 3_5、2008。
[BDS09] Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based Digital Signature Schemes", Book chapter, Post-Quantum Cryptography, DOI 10.1007/978-3-540-88702-7_3, 2009.
[BDS09] Buchmann、J.、Dahmen、E。、およびM. Szydlo、「ハッシュベースのデジタル署名方式」、本の章、ポスト量子暗号、DOI 10.1007 / 978-3-540-88702-7_3、2009。
[BHH15] Bernstein, D., Hopwood, D., Huelsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical Stateless Hash-Based Signatures", Lecture Notes in Computer Science, Volume 9056, Advances in Cryptology - EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15, 2015.
[BHH15]バーンスタイン、D。、ホップウッド、D。、ヒューリング、A。、ランゲ、T。、ニーダーハーゲン、R。、パパクリストドゥロウ、L。、シュナイダー、M。、シュヴァーブ、P.、Z。ウィルコックスO 'ハーン、「SPHINCS：実用的なステートレスハッシュベースの署名」、コンピュータサイエンスの講義ノート、第9056巻、暗号学の進歩-EUROCRYPT、DOI 10.1007 / 978-3-662-46800-5_15、2015年。
[HRB13] Huelsing, A., Rausch, L., and J. Buchmann, "Optimal Parameters for XMSS^MT", Lecture Notes in Computer Science, Volume 8128, CD-ARES, DOI 10.1007/978-3-642-40588-4_14, 2013.
[HRB13] Huelsing、A.、Rausch、L。、およびJ. Buchmann、「XMSS ^ MTの最適パラメータ」、コンピュータサイエンスの講義ノート、8128巻、CD-ARES、DOI 10.1007 / 978-3-642-40588 -4_14、2013。
[HRS16] Huelsing, A., Rijneveld, J., and F. Song, "Mitigating Multi-Target Attacks in Hash-based Signatures", Lecture Notes in Computer Science, Volume 9614, Public-Key Cryptography - PKC, DOI 10.1007/978-3-662-49384-7_15, 2016.
[HRS16] Huelsing、A.、Rijneveld、J。、およびF. Song、「ハッシュベースの署名におけるマルチターゲット攻撃の緩和」、コンピュータサイエンスの講義ノート、9614巻、公開鍵暗号-PKC、DOI 10.1007 / 978-3-662-49384-7_15、2016。
[Huelsing13] Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based Signature Schemes", Lecture Notes in Computer Science, Volume 7918, Progress in Cryptology - AFRICACRYPT, DOI 10.1007/978-3-642-38553-7_10, 2013.
[Huelsing13] Huelsing、A.、 "W-OTS +-Shorter Signatures for Hash-Based Signature Schemes"、Lecture Notes in Computer Science、Volume 7918、Progress in Cryptology-AFRICACRYPT、DOI 10.1007 / 978-3-642-38553-7_10 、2013。
[Huelsing13a] Huelsing, A., "Practical Forward Secure Signatures using Minimal Security Assumptions", PhD thesis TU Darmstadt, 2013, <http://tuprints.ulb.tu-darmstadt.de/3651/1/Thesis.pdf>.
[Huelsing13a] Huelsing、A.、「最小限のセキュリティ仮定を使用した実用的なフォワードセキュア署名」、PhD論文TU Darmstadt、2013、<http://tuprints.ulb.tu-darmstadt.de/3651/1/Thesis.pdf>。
[KMN14] Knecht, M., Meier, W., and C. Nicola, "A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm", Computing Research Repository (CoRR), arXiv:1409.4081, 2014.
[KMN14] Knecht、M.、Meier、W。、およびC. Nicola、「スペース効率と時間効率の高いマークルツリートラバーサルアルゴリズムの実装」、コンピューティング研究リポジトリ（CoRR）、arXiv：1409.4081、2014。
[MCF18] McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based Signatures", Work in Progress, draft-mcgrew-hash-sigs-11, April 2018.
[MCF18] McGrew、D.、Curcio、M。、およびS. Fluhrer、「ハッシュベースの署名」、Work in Progress、draft-mcgrew-hash-sigs-11、2018年4月。
[Merkle83] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Computer Science Series, UMI Research Press, ISBN: 9780835713849, 1983.
[Merkle83]マークル、R。、「秘密、認証、および公開鍵システム」、コンピューターサイエンスシリーズ、UMI Research Press、ISBN：9780835713849、1983。
Appendix A. WOTS+ XDR Formats
付録A.WOTS + XDR形式
The WOTS+ signature and public key formats are formally defined using XDR [RFC4506] in order to provide an unambiguous, machine readable definition. Though XDR is used, these formats are simple and easy to parse without any special tools. Note that this representation includes all optional parameter sets. The same applies for the XMSS and XMSS^MT formats below.
WOTS +署名と公開鍵の形式は、明確な機械可読な定義を提供するために、XDR [RFC4506]を使用して正式に定義されています。 XDRが使用されますが、これらの形式はシンプルで、特別なツールを使用しなくても簡単に解析できます。この表現には、すべてのオプションのパラメーターセットが含まれることに注意してください。以下のXMSSおよびXMSS ^ MTフォーマットにも同じことが適用されます。
WOTS+ parameter sets are defined using XDR syntax as follows:
WOTS +パラメータセットは、XDR構文を使用して次のように定義されます。
/* ots_algorithm_type identifies a particular
signature algorithm */
enum ots_algorithm_type {
wotsp_reserved = 0x00000000,
wotsp-sha2_256 = 0x00000001,
wotsp-sha2_512 = 0x00000002,
wotsp-shake_256 = 0x00000003,
wotsp-shake_512 = 0x00000004,
};
WOTS+ signatures are defined using XDR syntax as follows:
WOTS +署名は、XDR構文を使用して次のように定義されます。
/* Byte strings */
typedef opaque bytestring32[32];
typedef opaque bytestring64[64];
union ots_signature switch (ots_algorithm_type type) {
case wotsp-sha2_256:
case wotsp-shake_256:
bytestring32 ots_sig_n32_len67[67];
case wotsp-sha2_512: case wotsp-shake_512: bytestring64 ots_sig_n64_len18[131];
case wotsp-sha2_512：case wotsp-shake_512：bytestring64 ots_sig_n64_len18 [131];
default:
void; /* error condition */
};
WOTS+ public keys are defined using XDR syntax as follows:
WOTS +公開鍵は、XDR構文を使用して次のように定義されます。
union ots_pubkey switch (ots_algorithm_type type) {
case wotsp-sha2_256:
case wotsp-shake_256:
bytestring32 ots_pubk_n32_len67[67];
case wotsp-sha2_512: case wotsp-shake_512: bytestring64 ots_pubk_n64_len18[131];
case wotsp-sha2_512：case wotsp-shake_512：bytestring64 ots_pubk_n64_len18 [131];
default:
void; /* error condition */
};
XMSS parameter sets are defined using XDR syntax as follows:
XMSSパラメータセットは、XDR構文を使用して次のように定義されます。
/* Byte strings */
typedef opaque bytestring4[4];
typedef不透明なバイト文字列4 [4];
/* Definition of parameter sets */
enum xmss_algorithm_type { xmss_reserved = 0x00000000,
列挙型xmss_algorithm_type {xmss_reserved = 0x00000000、
/* 256 bit classical security, 128 bit post-quantum security */
xmss-sha2_10_256 = 0x00000001, xmss-sha2_16_256 = 0x00000002, xmss-sha2_20_256 = 0x00000003,
xmss-sha2_10_256 = 0 xxx 0000001、xmss-sha2_16_256 = 0 xms 0000002、xmss-sha2_20_256 = 0 x 0000003、
/* 512 bit classical security, 256 bit post-quantum security */
xmss-sha2_10_512 = 0x00000004, xmss-sha2_16_512 = 0x00000005, xmss-sha2_20_512 = 0x00000006,
xmss-sha2_10_512 = 0 xxx 00000004、xmss-sha2_16_512 = 0 xmsssha2_20_512 = 0 x 00000006、
/* 256 bit classical security, 128 bit post-quantum security */
xmss-shake_10_256 = 0x00000007, xmss-shake_16_256 = 0x00000008, xmss-shake_20_256 = 0x00000009,
xmss-shake_10_256 = 0x00000007、xmss-shake_16_256 = 0x00000008、xmss-shake_20_256 = 0x00000009、
/* 512 bit classical security, 256 bit post-quantum security */
xmss-shake_10_512 = 0x0000000A, xmss-shake_16_512 = 0x0000000B, xmss-shake_20_512 = 0x0000000C, };
xmss-shake_10_512 = 0x0000000A、xmss-shake_16_512 = 0x0000000B、xmss-shake_20_512 = 0x0000000C、};
XMSS signatures are defined using XDR syntax as follows:
XMSS署名は、XDR構文を使用して次のように定義されます。
/* Authentication path types */
union xmss_path switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-shake_10_256:
bytestring32 path_n32_t10[10];
case xmss-sha2_16_256: case xmss-shake_16_256: bytestring32 path_n32_t16[16];
case xmss-sha2_16_256：case xmss-shake_16_256：bytestring32 path_n32_t16 [16];
case xmss-sha2_20_256: case xmss-shake_20_256: bytestring32 path_n32_t20[20];
case xmss-sha2_20_256：case xmss-shake_20_256：bytestring32 path_n32_t20 [20];
case xmss-sha2_10_512: case xmss-shake_10_512: bytestring64 path_n64_t10[10];
case xmss-sha2_10_512：case xmss-shake_10_512：bytestring64 path_n64_t10 [10];
case xmss-sha2_16_512: case xmss-shake_16_512: bytestring64 path_n64_t16[16];
case xmss-sha2_16_512：case xmss-shake_16_512：bytestring64 path_n64_t16 [16];
case xmss-sha2_20_512: case xmss-shake_20_512: bytestring64 path_n64_t20[20];
case xmss-sha2_20_512：case xmss-shake_20_512：bytestring64 path_n64_t20 [20];
default:
void; /* error condition */
};
/* Types for XMSS random strings */
union random_string_xmss switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 rand_n32;
case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 rand_n64;
case xmss-sha2_10_512：case xmss-sha2_16_512：case xmss-sha2_20_512：case xmss-shake_10_512：case xmss-shake_16_512：case xmss-shake_20_512：bytestring64 rand_n64;
default:
void; /* error condition */
};
/* Corresponding WOTS+ type for given XMSS type */
union xmss_ots_signature switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
wotsp-sha2_256;
case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: wotsp-sha2_512;
case xmss-sha2_10_512：case xmss-sha2_16_512：case xmss-sha2_20_512：wotsp-sha2_512;
case xmss-shake_10_256: case xmss-shake_16_256: case xmss-shake_20_256: wotsp-shake_256;
case xmss-shake_10_256：case xmss-shake_16_256：case xmss-shake_20_256：wotsp-shake_256;
case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: wotsp-shake_512;
case xmss-shake_10_512：case xmss-shake_16_512：case xmss-shake_20_512：wotsp-shake_512;
default:
void; /* error condition */
};
/* XMSS signature structure */
struct xmss_signature {
/* WOTS+ key pair index */
bytestring4 idx_sig;
/* Random string for randomized hashing */
random_string_xmss rand_string;
/* WOTS+ signature */
xmss_ots_signature sig_ots;
/* authentication path */
xmss_path nodes;
};
XMSS public keys are defined using XDR syntax as follows:
XMSS公開鍵は、XDR構文を使用して次のように定義されます。
/* Types for bitmask seed */
union seed switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 seed_n32;
case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 seed_n64;
case xmss-sha2_10_512：case xmss-sha2_16_512：case xmss-sha2_20_512：case xmss-shake_10_512：case xmss-shake_16_512：case xmss-shake_20_512：bytestring64 seed_n64;
default:
void; /* error condition */
};
/* Types for XMSS root node */
union xmss_root switch (xmss_algorithm_type type) {
case xmss-sha2_10_256:
case xmss-sha2_16_256:
case xmss-sha2_20_256:
case xmss-shake_10_256:
case xmss-shake_16_256:
case xmss-shake_20_256:
bytestring32 root_n32;
case xmss-sha2_10_512: case xmss-sha2_16_512: case xmss-sha2_20_512: case xmss-shake_10_512: case xmss-shake_16_512: case xmss-shake_20_512: bytestring64 root_n64;
case xmss-sha2_10_512：case xmss-sha2_16_512：case xmss-sha2_20_512：case xmss-shake_10_512：case xmss-shake_16_512：case xmss-shake_20_512：bytestring64 root_n64;
default:
void; /* error condition */
};
/* XMSS public key structure */
struct xmss_public_key {
xmss_root root; /* Root node */
seed SEED; /* Seed for bitmasks */
};
Appendix C. XMSS^MT XDR Formats
付録C. XMSS ^ MT XDR形式
XMSS^MT parameter sets are defined using XDR syntax as follows:
XMSS ^ MTパラメータセットは、XDR構文を使用して次のように定義されます。
/* Byte strings */
typedef opaque bytestring3[3];
typedef opaque bytestring5[5];
typedef opaque bytestring8[8];
/* Definition of parameter sets */
enum xmssmt_algorithm_type { xmssmt_reserved = 0x00000000,
列挙型xmssmt_algorithm_type {xmssmt_reserved = 0x00000000、
/* 256 bit classical security, 128 bit post-quantum security */
xmssmt-sha2_20/2_256 = 0x00000001, xmssmt-sha2_20/4_256 = 0x00000002, xmssmt-sha2_40/2_256 = 0x00000003, xmssmt-sha2_40/4_256 = 0x00000004, xmssmt-sha2_40/8_256 = 0x00000005, xmssmt-sha2_60/3_256 = 0x00000006, xmssmt-sha2_60/6_256 = 0x00000007, xmssmt-sha2_60/12_256 = 0x00000008,
xmssmt-sha2_20 / 2_256 = 0x00000001、xmssmt-sha2_20 / 4_256 = 0x00000002、xmssmt-sha2_40 / 2_256 = 0x00000003、xmssmt-sha2_40 / 4_256t = 0x00000004、xmssmt-sha2_40 / 8_256 = 8_256_x_ms_40_ms_x_ms_40_ms_x_ms_40_ms_x0_ms_ms_40_ms_x0_ms_ms_ms_ms_40_0000_x0_ms_ms_ms_ms_40_xs_ms_40_0000_xs_ms_ms_ms_ms_ms40_ms_40 sha2_60 / 6_256 = 0x00000007、xmssmt-sha2_60 / 12_256 = 0x00000008、
/* 512 bit classical security, 256 bit post-quantum security */
xmssmt-sha2_20/2_512 = 0x00000009, xmssmt-sha2_20/4_512 = 0x0000000A, xmssmt-sha2_40/2_512 = 0x0000000B, xmssmt-sha2_40/4_512 = 0x0000000C, xmssmt-sha2_40/8_512 = 0x0000000D, xmssmt-sha2_60/3_512 = 0x0000000E, xmssmt-sha2_60/6_512 = 0x0000000F, xmssmt-sha2_60/12_512 = 0x00000010,
xmssmt-sha2_20 / 2_512 = 0x00000009、xmssmt-sha2_20 / 4_512 = 0x0000000A、xmssmt-sha2_40 / 2_512 = 0x0000000B、xmssmt-sha2_40 / 4_512 = 0x0000000C、xmssmt-sha2_40 / 8D0_5xD0_5xD0_x0_0x00x00x00x00x00x00x0x0x0x0x0x0x0x0x0x0x00m0x000000 sha2_60 / 6_512 = 0x0000000F、xmssmt-sha2_60 / 12_512 = 0x00000010、
/* 256 bit classical security, 128 bit post-quantum security */
xmssmt-shake_20/2_256 = 0x00000011, xmssmt-shake_20/4_256 = 0x00000012, xmssmt-shake_40/2_256 = 0x00000013, xmssmt-shake_40/4_256 = 0x00000014, xmssmt-shake_40/8_256 = 0x00000015, xmssmt-shake_60/3_256 = 0x00000016, xmssmt-shake_60/6_256 = 0x00000017, xmssmt-shake_60/12_256 = 0x00000018,
xmssmt-shake_20 / 2_256 = 0x00000011、xmssmt-shake_20 / 4_256 = 0x00000012、xmssmt-shake_40 / 2_256 = 0x00000013、xmssmt-shake_40 / 4_256 = 0x00000014、xmssmt-shake_40 / 8_256 = 0x00000015、xmssmt_sh_mt_sh_mt_sh_mt_sh shake_60 / 6_256 = 0x00000017、xmssmt-shake_60 / 12_256 = 0x00000018、
/* 512 bit classical security, 256 bit post-quantum security */
xmssmt-shake_20/2_512 = 0x00000019,
xmssmt-shake_20/4_512 = 0x0000001A,
xmssmt-shake_40/2_512 = 0x0000001B,
xmssmt-shake_40/4_512 = 0x0000001C,
xmssmt-shake_40/8_512 = 0x0000001D,
xmssmt-shake_60/3_512 = 0x0000001E,
xmssmt-shake_60/6_512 = 0x0000001F,
xmssmt-shake_60/12_512 = 0x00000020,
};
XMSS^MT signatures are defined using XDR syntax as follows:
XMSS ^ MT署名は、XDR構文を使用して次のように定義されます。
/* Type for XMSS^MT key pair index */
/* Depends solely on h */
union idx_sig_xmssmt switch (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
bytestring3 idx3;
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
bytestring5 idx5;
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring8 idx8;
default:
void; /* error condition */
};
union random_string_xmssmt switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
bytestring32 rand_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring64 rand_n64;
default:
void; /* error condition */
};
/* Type for reduced XMSS signatures */
union xmss_reduced (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_60/6_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_60/6_256:
bytestring32 xmss_reduced_n32_t77[77];
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/12_256:
bytestring32 xmss_reduced_n32_t72[72];
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_60/3_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_60/3_256:
bytestring32 xmss_reduced_n32_t87[87];
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_60/6_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_60/6_512:
bytestring64 xmss_reduced_n32_t141[141];
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/12_512:
bytestring64 xmss_reduced_n32_t136[136];
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_60/3_512:
bytestring64 xmss_reduced_n32_t151[151];
default:
void; /* error condition */
};
/* xmss_reduced_array depends on d */
union xmss_reduced_array (xmss_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/2_512:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/2_512:
xmss_reduced xmss_red_arr_d2[2];
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/3_512:
xmss_reduced xmss_red_arr_d3[3];
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/4_512:
case xmssmt-shake_20/4_256:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/4_512:
xmss_reduced xmss_red_arr_d4[4];
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/6_512:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/6_512:
xmss_reduced xmss_red_arr_d6[6];
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_40/8_512:
case xmssmt-shake_40/8_256:
case xmssmt-shake_40/8_512:
xmss_reduced xmss_red_arr_d8[8];
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_60/12_256:
case xmssmt-shake_60/12_512:
xmss_reduced xmss_red_arr_d12[12];
default:
void; /* error condition */
};
/* XMSS^MT signature structure */
struct xmssmt_signature {
/* WOTS+ key pair index */
idx_sig_xmssmt idx_sig;
/* Random string for randomized hashing */
random_string_xmssmt randomness;
/* Array of d reduced XMSS signatures */
xmss_reduced_array;
};
XMSS^MT public keys are defined using XDR syntax as follows:
XMSS ^ MT公開鍵は、XDR構文を使用して次のように定義されます。
/* Types for bitmask seed */
union seed switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/12_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_60/3_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/12_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_60/3_256:
bytestring32 seed_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/12_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_60/3_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/12_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_60/3_512:
bytestring64 seed_n64;
default:
void; /* error condition */
};
/* Types for XMSS^MT root node */
union xmssmt_root switch (xmssmt_algorithm_type type) {
case xmssmt-sha2_20/2_256:
case xmssmt-sha2_20/4_256:
case xmssmt-sha2_40/2_256:
case xmssmt-sha2_40/4_256:
case xmssmt-sha2_40/8_256:
case xmssmt-sha2_60/3_256:
case xmssmt-sha2_60/6_256:
case xmssmt-sha2_60/12_256:
case xmssmt-shake_20/2_256:
case xmssmt-shake_20/4_256:
case xmssmt-shake_40/2_256:
case xmssmt-shake_40/4_256:
case xmssmt-shake_40/8_256:
case xmssmt-shake_60/3_256:
case xmssmt-shake_60/6_256:
case xmssmt-shake_60/12_256:
bytestring32 root_n32;
case xmssmt-sha2_20/2_512:
case xmssmt-sha2_20/4_512:
case xmssmt-sha2_40/2_512:
case xmssmt-sha2_40/4_512:
case xmssmt-sha2_40/8_512:
case xmssmt-sha2_60/3_512:
case xmssmt-sha2_60/6_512:
case xmssmt-sha2_60/12_512:
case xmssmt-shake_20/2_512:
case xmssmt-shake_20/4_512:
case xmssmt-shake_40/2_512:
case xmssmt-shake_40/4_512:
case xmssmt-shake_40/8_512:
case xmssmt-shake_60/3_512:
case xmssmt-shake_60/6_512:
case xmssmt-shake_60/12_512:
bytestring64 root_n64;
default:
void; /* error condition */
};
/* XMSS^MT public key structure */
struct xmssmt_public_key {
xmssmt_root root; /* Root node */
seed SEED; /* Seed for bitmasks */
};
Acknowledgements
謝辞
We would like to thank Johannes Braun, Peter Campbell, Florian Caullery, Stephen Farrell, Scott Fluhrer, Burt Kaliski, Adam Langley, Marcos Manzano, David McGrew, Rafael Misoczki, Sean Parkinson, Sebastian Roland, and the Keccak team for their help and comments.
Johannes Braun、Peter Campbell、Florian Caullery、Stephen Farrell、Scott Fluhrer、Burt Kaliski、Adam Langley、Marcos Manzano、David McGrew、Rafael Misoczki、Sean Parkinson、Sebastian Roland、およびKeccakチームの支援とコメントに感謝します。
Authors' Addresses
著者のアドレス
Andreas Huelsing TU Eindhoven P.O. Box 513 Eindhoven 5600 MB The Netherlands
Andreas Huelsing TUアイントホーフェンP.O.ボックス513アイントホーフェン5600 MBオランダ
Email: ietf@huelsing.net
Denis Butin TU Darmstadt Hochschulstrasse 10 Darmstadt 64289 Germany
Denis Butin TU Darmstadt Hochschulstrasse 10ダルムシュタットドイツ
Email: dbutin@cdc.informatik.tu-darmstadt.de
Stefan-Lukas Gazdag genua GmbH Domagkstrasse 7 Kirchheim bei Muenchen 85551 Germany
Stefan-Lukas Gazdag genua GmbH Domagkstrasse 7キルヒハイムバイミュンヘン85551ドイツ
Email: ietf@gazdag.de
Joost Rijneveld Radboud University Toernooiveld 212 Nijmegen 6525 EC The Netherlands
Joost Rijneveld Radboud University Tournament field 212 Nijmegen 6525 ECオランダ
Email: ietf@joostrijneveld.nl
Aziz Mohaisen University of Central Florida 4000 Central Florida Blvd Orlando, FL 32816 United States of America
Aziz Mohaisen University of Central Florida 4000 Central Florida Blvd Orlando、FL 32816アメリカ合衆国
Phone: +1 407 823-1294
Email: mohaisen@ieee.org