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
        
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:扩展的Merkle签名方案

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.

本说明描述了扩展Merkle签名方案(XMSS),这是一种基于哈希的数字签名系统,基于科学文献中现有的描述。本说明指定了Winternitz一次性签名加(WOTS+),一种一次性签名方案;XMSS,一种单树方案;以及XMSS^MT,XMSS的多树变体。XMSS和XMSS^MT都使用WOTS+作为主要构建块。XMSS提供加密数字签名,而不依赖于推测的数学问题的难度。事实证明,它只依赖于加密哈希函数的属性。XMS提供了强大的安全保证,甚至在底层哈希函数的抗冲突性被破坏时也是安全的。它适用于紧凑的实现,实现相对简单,并且自然地抵抗侧通道攻击。与大多数其他签名系统不同,基于哈希的签名到目前为止可以抵抗使用量子计算机的已知攻击。

Status of This Memo

关于下段备忘

This document is not an Internet Standards Track specification; it is published for informational purposes.

本文件不是互联网标准跟踪规范;它是为了提供信息而发布的。

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.

本文件是互联网研究工作组(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.

版权所有(c)2018 IETF信托基金和确定为文件作者的人员。版权所有。

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
        
   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
        
   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
        
1. Introduction
1. 介绍

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)方案允许使用密钥对安全地对一条消息进行签名。多次签名(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.

1979年,Merkle提出了OTS方案以及由它们组成的MTS方案[Merkle83]。它们在20世纪90年代得到了很好的研究,并从21世纪中期开始重新引起人们的兴趣,因为它们能够抵抗量子计算机辅助的攻击。这些类型的签名方案称为基于哈希的签名方案,因为它们是由加密哈希函数构建的。基于散列的签名方案通常具有较小的私钥和公钥以及快速的签名生成和验证;但是,它们还具有签名大和密钥生成相对较慢的特点。此外,它们适合于紧凑的实现,有利于各种应用程序,并且自然能够抵抗大多数类型的侧通道攻击。

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提出了扩展Merkle签名方案(XMSS)[BDH11],该方案比Merkle的原始方案具有更好的效率,并且在标准模型中提供了现代安全性证明。McGrew、Curcio和Fluhrer编写了一份互联网草案[MCF18],详细说明了Leighton-Micali签名(LMS)方案,该方案建立在Lamport、Diffie、Winternitz和Merkle的开创性著作的基础上,采用了与XMS不同的方法,完全依赖随机oracle模型中的安全参数。最近,引入了基于无状态散列的签名方案SPHINCS[BHH15],目的是更易于在当前应用程序中部署。引入基于散列的签名的合理下一步是完成基本算法的规范——LMS、XMSS、括约肌和/或变体。

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.

扩展Merkle签名方案(XMSS)[BDH11]是最新的基于状态哈希的签名方案。它具有此类方案中最小的签名,并带有多树变体,解决了密钥生成缓慢的问题。此外,可以证明XMSS是安全的,只对底层的哈希函数作了轻微的假设。特别是,对于XMS的安全性,不要求加密哈希函数具有抗冲突性。如[HRS16]所述,对XMS的改进是本说明的一部分。

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的单树和多树变体。它还描述了WOTS+,这是[Huelsing13]中引入的XMSS使用的Winternitz OTS方案的一个变体。这些方案的描述具有足够的特殊性,以确保实现之间的互操作性。

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节中的扩展Merkle签名方案(XMSS)和第4.2节中的多树变体(XMSS^MT)。第5节介绍了参数集。第6节描述了本说明中选择的理由。第7节给出了有关参考代码的信息。第8节介绍了这些签名系统的IANA注册。最后,第9节介绍了安全注意事项。

1.1. CFRG Note on Post-Quantum Cryptography
1.1. 关于后量子密码术的CFRG注记

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.

加密论坛研究小组(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:

此外,对于XMS:

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.

在新邮件上伪造签名是可行的。这是一个大多数开发人员都不熟悉的新属性,需要仔细处理密钥。开发人员不应使用此处描述的方案,除非在防止重用密钥状态的系统中。

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必须允许返回更新的密钥状态。

1.2. Conventions Used in This Document
1.2. 本文件中使用的公约

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.

本文件中的关键词“必须”、“不得”、“必需”、“应”、“不应”、“建议”、“不建议”、“可”和“可选”在所有大写字母出现时(如图所示)应按照BCP 14[RFC2119][RFC8174]所述进行解释。

2. Notation
2. 符号
2.1. Data Types
2.1. 数据类型

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.

字节和字节字符串是基本的数据类型。字节是由八位组成的序列。单个字节表示为一对十六进制数字,前导为“0x”。字节字符串是零个或多个字节的有序序列,表示为带前导“0x”的十六进制字符的有序序列。例如,0xe534f0是长度为3的字节字符串。字节字符串数组是一个有序的索引集,从索引0开始,其中所有字节字符串的长度都相同。对于任何数据类型或结构,我们都采用大端表示法。

2.2. Functions
2.2. 功能

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.

下限(x):返回小于或等于x的最大整数。

lg(x): returns the logarithm to base 2 of x.

lg(x):返回x以2为底的对数。

2.3. Operators
2.3. 操作员

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表示a提升到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表示a与非零b的商。

% : 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为非负,即楼层(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和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]。

2.4. Integer-to-Byte Conversion
2.4. 整数到字节转换

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)定义为y字节字符串,其中包含以大端字节顺序表示的x的二进制表示。

2.5. Hash Function Address Scheme
2.5. 哈希函数地址方案

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.

本文档中描述的方案使每个哈希函数调用随机化。这意味着,除了初始消息摘要之外,每个哈希函数调用都使用不同的键和不同的位掩码。这些值是使用伪随机函数伪随机生成的,该函数以密钥种子和32字节地址ADRS作为输入,并输出n字节值,其中n是安全参数。在这里,我们解释了地址ADR的结构,并提出了操作地址的setter方法。我们将在下面使用地址的部分中解释地址的生成。

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.

接下来两部分中的方案使用两种由安全参数n参数化的哈希函数。对于哈希树构造,使用了一个哈希函数,该函数将一个n字节键和2n字节输入映射到n字节输出。要使此函数随机化,需要3n个字节——n个字节用于键,2n个字节用于位掩码。对于OTS方案构造,使用了将n字节键和n字节输入映射到n字节输出的哈希函数。要使此函数随机化,需要2n个字节——n个字节用于密钥,n个字节用于位掩码。因此,第一个函数需要三个地址,第二个函数需要两个地址。

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.

对于不同的用例,有三种不同类型的地址。一种类型用于OTS方案中的散列,一种用于主Merkle树结构中的散列,另一种用于L树中的散列。后者用于压缩一次性公钥。所有这些类型共享尽可能多的格式。在本节的其余部分中,我们将详细描述这些类型。

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

地址的结构符合字边框,在此上下文中,字的长度为32位。只有树地址太长,无法容纳单个单词,但它可以容纳两个单词。地址的结构如下所示。它总是以最重要位中的一个字的层地址开始,然后是两个字的树地址。这两个地址都是multi-tree variant(参见第4.2节)所需的,并描述了树在multi-tree中的位置。因此,在单树应用程序中,它们被设置为零。对于

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.

基于多树哈希的签名,层地址描述了多树中树的高度,从底层树的高度0开始。树地址描述了一棵树在一个多层树的层中的位置,最左边的树从索引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用于为一个哈希函数调用生成两个不同的地址。将单词设置为零以生成密钥。要生成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)|
                     +-------------------------+
        
                     +-------------------------+
                     | 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用于为一个函数调用生成三个不同的地址。将单词设置为零以生成密钥。要生成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)|
                     +-------------------------+
        
                     +-------------------------+
                     | 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.

现在我们描述主树散列地址的剩余类型。在本例中,类型字设置为两个,后跟一个字的零填充。下一个单词编码为下一次计算输入的树节点的高度,后面是一个单词,该单词编码该高度处该节点的索引。对于L树地址,最后一个字keyAndMask用于为一个函数调用生成三个不同的地址。将单词设置为零以生成密钥。要生成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)|
                     +-------------------------+
        
                     +-------------------------+
                     | 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.

这些地址中的所有字段都编码无符号整数。在描述地址的生成时,我们使用setter方法,该方法采用正整数,并将字段的位设置为该字段长度整数的二进制表示形式。我们进一步假设setType()方法将类型字后面的四个字设置为零。

2.6. Strings of Base w Numbers
2.6. 基w数的字符串

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}中的整数。对应关系由函数基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;
        
       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 ( 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}.
        
   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 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     |
         +-----------+-----------+-----------+-----------+
        
                 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, 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, 3)
         +-----------+-----------+-----------+
         |     1     |     2     |     3     |
         +-----------+-----------+-----------+
             a[0]        a[1]        a[2]
        
                          base_w(X, 16, 2)
         +-----------+-----------+
         |     1     |     2     |
         +-----------+-----------+
             a[0]        a[1]
        
                          base_w(X, 16, 2)
         +-----------+-----------+
         |     1     |     2     |
         +-----------+-----------+
             a[0]        a[1]
        

Example

实例

2.7. Member Functions
2.7. 成员函数

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所持有的值。由于camelCase用于成员函数名,因此值z在函数名中可以称为z,例如getZ。

3. Primitives
3. 原语
3.1. WOTS+: One-Time Signatures
3.1. WOTS+:一次性签名

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方案;虽然私钥可以用于对任何消息进行签名,但每个私钥只能用于对单个消息进行一次签名。特别是,如果使用私钥对两条不同的消息进行签名,则该方案将变得不安全。

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+方案的主要构建块。下面介绍密钥生成、签名和验证的算法。最后,讨论了伪随机密钥的生成。

3.1.1. WOTS+ Parameters
3.1.1. 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+参数根据需要隐式包含在算法输入中。

3.1.1.1. WOTS+ Functions
3.1.1.1. 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节。第9节讨论了F的安全要求。此外,WOTS+使用伪随机函数PRF。PRF采用一个n字节的键和一个32字节的索引作为输入,并生成长度为n的伪随机输出。有关特定实例化的更多详细信息,请参见第5节。第9节讨论了PRF的安全要求。

3.1.2. WOTS+ Chaining Function
3.1.2. WOTS+链接功能

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哈希地址作为输入。此地址将设置前六个32位字来编码此链的地址。在每次迭代中,PRF用于为F生成一个键和一个位掩码,该位掩码在F处理中间结果之前异或到中间结果。在下文中,ADRS是第2.5节中指定的32字节OTS哈希地址,SEED是一个n字节字符串。为了生成密钥和位掩码,调用PRF,以种子作为密钥,ADR作为输入。链函数将n字节字符串X、开始索引i、若干步骤s以及adr和SEED作为输入。链函数使用PRF的输出,将F在输入X上迭代s次得到的值作为输出返回。

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,种子,地址ADRS输出:X上迭代s次的F值

     if ( s == 0 ) {
       return X;
     }
     if ( (i + s) > (w - 1) ) {
       return NULL;
     }
     byte[n] tmp = chain(X, i, s - 1, SEED, ADRS);
        
     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);
        
     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;
        
     tmp = F(KEY, tmp XOR BM);
     return tmp;
        
3.1.3. WOTS+ Private Key
3.1.3. WOTS+私钥

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表示secret),是一个长度为len的n字节字符串数组。此私钥最多只能用于签署一封邮件。每个n字节字符串必须从均匀分布中随机选择,或者使用加密安全伪随机过程选择。在后一种情况下,所用程序的安全性必须至少与所用WOTS+参数的安全性相匹配。有关伪随机密钥生成的进一步讨论,请参见第3.1.7节。下面的伪代码(算法3)描述了生成sk的算法。

   Algorithm 3: WOTS_genSK - Generating a WOTS+ Private Key
        
   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;
        
     for ( i = 0; i < len; i++ ) {
       initialize sk[i] with a uniformly random n-byte string;
     }
     return sk;
        
3.1.4. WOTS+ Public Key
3.1.4. WOTS+公钥

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散列链组成。私钥中的lenn字节字符串分别定义一个哈希链的起始节点。公钥由这些散列链的末端节点组成。因此,与私钥一样,公钥也是一个长度为len的n字节字符串数组。为了计算散列链,使用链接函数(算法2)。OTS哈希地址ADR和种子必须由调用算法提供。该地址将在更大的结构中对WOTS+密钥对的地址进行编码。因此,除最后三个32位字外,WOTS+算法不得操纵ADR的任何部分。请注意,此处使用的种子是公开信息,也可供验证人使用。以下伪代码(算法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
        
     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;
        
     for ( i = 0; i < len; i++ ) {
       ADRS.setChainAddress(i);
       pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
     }
     return pk;
        
3.1.5. WOTS+ Signature Generation
3.1.5. WOTS+签名生成

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

WOTS+签名是由n字节字符串组成的长度为len的数组。WOTS+签名是通过将消息映射到0和w-1之间的len整数生成的。为此,使用第2.6节中定义的base_w函数将消息转换为len_1 base w编号。接下来,使用base_w函数计算校验和,并将其作为len_2 base w数附加到转换后的消息中。注意,校验和可能达到len_1*(w-1)*2^8的最大整数值,因此取决于参数n和w。对于第5节中给出的参数集,32位无符号整数足以保存校验和。如果使用其他参数设置,则保存校验和整数值的变量的大小必须足够大。每个基w整数用于从不同的哈希链中选择节点。签名是通过连接所选节点形成的。OTS哈希地址ADR和种子必须由调用算法提供。该地址将在更大的结构中对WOTS+密钥对的地址进行编码。因此,WOTS+算法不得操纵该算法的任何部分

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.

除最后三个32位字外的ADR。请注意,此处使用的种子是公开信息,也可供验证人使用。用于生成签名的伪码如下所示(算法5),其中M是消息,sig是结果签名。

Algorithm 5: WOTS_sign - Generating a signature from a private key and a message

算法5:WOTS_签名-从私钥和消息生成签名

     Input: Message M, WOTS+ private key sk, address ADRS, seed SEED
     Output: WOTS+ signature sig
        
     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);
        
     // 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];
     }
        
     // 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;
        
     // 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
             |                                 |
             +---------------------------------+
        
             +---------------------------------+
             |                                 |
             |           sig_ots[0]            |    n bytes
             |                                 |
             +---------------------------------+
             |                                 |
             ~              ....               ~
             |                                 |
             +---------------------------------+
             |                                 |
             |          sig_ots[len - 1]       |    n bytes
             |                                 |
             +---------------------------------+
        

WOTS+ Signature

WOTS+签名

3.1.6. WOTS+ Signature Verification
3.1.6. 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哈希地址ADR和种子必须由调用算法提供。该地址将在更大的结构中对WOTS+密钥对的地址进行编码。因此,除最后三个32位字外,WOTS+算法不得操纵ADR的任何部分。请注意,此处使用的种子是公开信息,也可供验证人使用。

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
        
     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);
        
     // 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];
     }
        
     // 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;
        
     // 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计算公钥值,并将比较延迟到稍后的时间点。

3.1.7. Pseudorandom Key Generation
3.1.7. 伪随机密钥生成

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字节值生成私钥。例如,可使用[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不能是低熵、人类记忆值,因为私钥元素是从S确定地派生的,并且它们的机密性是安全关键的。

4. Schemes
4. 计划

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.

在本节中,使用WOTS+描述扩展Merkle签名方案(XMSS)。XMSS有两种风格:单树变体(XMSS)和多树变体(XMSS^MT)。两者都允许在单个小公钥下组合大量WOT+密钥对。添加的主要成分是二进制哈希树结构。XMSS使用单个哈希树,而XMSS^MT使用XMSS密钥对树。

4.1. XMSS: eXtended Merkle Signature Scheme
4.1. XMSS:扩展的Merkle签名方案

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

XMSS是一种对可能较大但数量固定的消息进行签名的方法。它基于Merkle签名方案。XMSS使用四个加密组件:WOTS+作为OTS方法、两个额外的加密哈希函数H和H_msg以及一个伪随机函数PRF。使用WOTS+的XMS的主要优点之一是,它不依赖于所用哈希函数的抗冲突性,而是依赖于较弱的属性。每个XMSS公钥/私钥对都与一个完美的二叉树相关联,二叉树的每个节点都包含一个n字节的值。每个树叶包含一个WOTS+公钥值的特殊树哈希。每个非叶树节点首先通过连接其子节点的值来计算,使用位掩码计算异或,并对结果应用键控哈希函数H。哈希函数H的位掩码和键是从

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

(公共)作为使用伪随机函数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是一个有状态签名方案,意味着私钥随着签名的生成而变化。为了防止一次性私钥被使用两次,WOTS+密钥对根据相关叶从索引0(最左边的叶)开始从0到(2^h)-1进行编号。私钥包含一个索引,该索引随着每次签名生成而更新,因此它包含下一个未使用的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私钥由所有WOT+私钥和当前索引组成。为了减少存储,可以使用伪随机密钥生成过程,如[BDH11]中所述。所用方法的安全性必须至少与XMSS实例的安全性匹配。

4.1.1. XMSS Parameters
4.1.1. 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.

树上有两片叶子。

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表示secret)和PK表示。对于WOTS+,私钥和公钥分别用sk(s表示secret)和pk表示。XMSS和XMSS^MT签名由Sig表示。WOTS+签名由sig表示。

XMSS and XMSS^MT parameters are implicitly included in algorithm inputs as needed.

XMSS和XMSS^MT参数根据需要隐式包含在算法输入中。

4.1.2. XMSS Hash Functions
4.1.2. XMSS散列函数

Besides the cryptographic hash function F and the pseudorandom function PRF required by WOTS+, XMSS uses two more functions:

除了WOTS+所需的加密哈希函数F和伪随机函数PRF外,XMSS还使用了两个函数:

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接受长度为2n的n字节密钥和字节字符串,并返回一个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节。第9节讨论了H和H_msg的安全要求。

4.1.3. XMSS Private Key
4.1.3. XMSS私钥

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字节值根(即树和种子的根节点),以及用于伪随机生成位掩码和哈希函数键的n字节公共种子。虽然root和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.

创建XMSS私钥时,叶索引idx初始化为零。密钥SK_PRF必须从遵循均匀分布的安全随机性源中采样。必须按照第3.1节所述生成WOTS+私钥,或者,为了减小私钥大小,必须使用第4.1.11节所述的加密伪随机方法。种子作为统一的随机n字节字符串生成。虽然种子是公开的,但使用良好的熵源生成种子对安全性至关重要。根节点的生成如下文密钥生成部分(第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+私钥。

4.1.4. Randomized Tree Hashing
4.1.4. 随机树散列

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),它在树中进行随机散列。它将两个n字节的值LEFT和RIGHT作为输入,这两个值分别表示哈希函数输入的左半部和右半部、用作PRF键的种子以及此哈希函数调用的地址ADR。RAND_HASH首先使用带有SEED和adr的PRF生成密钥和n字节位掩码BM_0、BM_1。然后,它返回随机散列H(KEY,(左XOR BM_0)| |(右XOR BM_1))。

Algorithm 7: RAND_HASH

算法7:随机散列

Input: n-byte value LEFT, n-byte value RIGHT, seed SEED, address ADRS Output: n-byte randomized hash

输入:左n字节值,右n字节值,种子种子,地址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);
        
     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));

返回H(键,(左XOR BM_0)| |(右XOR BM_1));

4.1.5. L-Trees
4.1.5. L-树

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-树地址ADRS作为输入,ADRS对L-树和种子的地址进行编码。

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,地址ADR,种子输出: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];
        
     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];
        
4.1.6. TreeHash
4.1.6. 树灰

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.

为了计算Merkle树的内部n字节节点,子例程treeHash(算法9)接受XMSS私钥SK(包括种子种子)、无符号整数s(起始索引)、无符号整数t(目标节点高度)和编码包含树地址的地址ADRS。对于树中节点的高度,计数从高度为零的树叶开始。treeHash算法返回高度为t的树的根节点,最左边的叶子是索引为s的WOTS+pk的散列。要求s%2^t=0,即索引s处的叶是高度为t的子树的最左侧叶。否则,哈希寻址方案将失败。这里描述的treeHash算法使用最多容纳(t-1)个节点的堆栈,以及常用的堆栈函数push()和pop()。此外,我们假设节点的高度(无符号整数)与堆栈上的节点值(n字节字符串)一起存储。

Algorithm 9: treeHash

算法9:树灰

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();
        
     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();
        
4.1.7. XMSS Key Generation
4.1.7. XMSS密钥生成

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_keyGen(算法10)中的描述计算XMSS密钥对。XMSS公钥PK由二进制哈希树的根和种子组成,两者都存储在SK中。根使用treeHash计算。对于XMS,只有一个主树。因此,使用的地址在开始时设置为全零字符串。注意,通过引入此算法,我们没有为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);
        
     // 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);
        
     // 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);
        
     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需要相应的wot+密钥对时进行生成。

The format of an XMSS public key is given below.

XMSS公钥的格式如下所示。

            +---------------------------------+
            |          algorithm OID          |
            +---------------------------------+
            |                                 |
            |            root node            |     n bytes
            |                                 |
            +---------------------------------+
            |                                 |
            |              SEED               |     n bytes
            |                                 |
            +---------------------------------+
        
            +---------------------------------+
            |          algorithm OID          |
            +---------------------------------+
            |                                 |
            |            root node            |     n bytes
            |                                 |
            +---------------------------------+
            |                                 |
            |              SEED               |     n bytes
            |                                 |
            +---------------------------------+
        

XMSS Public Key

XMSS公钥

4.1.8. XMSS Signature
4.1.8. 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+签名信号(len*n字节),以及

o the so-called authentication path 'auth' for the leaf associated with the used WOTS+ key pair (h * n bytes).

o 与所用WOTS+密钥对(h*n字节)关联的叶的所谓身份验证路径“auth”。

   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:
        
   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)
        
      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
             |                                 |
             +---------------------------------+
        
             +---------------------------------+
             |                                 |
             |          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签名

4.1.9. XMSS Signature Generation
4.1.9. 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被递增。在更新私钥之前,实现不得输出签名。

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

可以以任何方式计算认证路径的节点值。假定此计算由函数XMSS_sign的子例程buildAuth执行(算法12)。最快的替代方法是存储所有树节点,并通过复制各自的节点在签名中设置数组。存储密集度最低的替代方案是为每个签名重新计算所有节点

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.

在线使用treeHash算法(算法9)。在这两者之间存在几种算法,它们具有不同的时间/存储权衡。有关概述,请参见[BDS09]。可在[KMN14]中找到进一步的方法。注意,本程序的细节与互操作性无关;为了执行签名验证操作,不需要知道这些细节中的任何一个。以下版本的buildAuth是完整的。这是一个简单的理解示例,但效率极低。强烈建议使用一种替代算法。

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);
     }
        
     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.

我们将签名生成的描述分为两个主要算法。第一个是treeSig(算法11),它生成XMSS签名的主要部分,也被多树变量XMSS^MT使用。XMSS_签名(算法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+签名签名和身份验证路径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 = 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;
        
     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);
        
     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);
        
4.1.10. XMSS Signature Verification
4.1.10. XMSS签名验证

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.

通过首先使用随机性r、索引idx_sig、来自PK的根和消息M计算消息摘要来验证XMSS签名。然后使用WOTS_pkFromSig从WOTS+签名计算所使用的WOTS+公钥PK_ots。WOTS+公钥依次用于使用L-树计算相应的叶。叶与索引idx_sig和身份验证路径auth一起用于计算树的可选根值。当且仅当计算的根值与XMSS公钥中的根值匹配时,验证才会成功。在任何其他情况下,它必须返回fail。

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.

至于签名生成,我们将验证分为两部分,以允许在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、身份验证路径auth、n字节消息M',种子种子和地址adr作为输入。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,身份验证路径auth,n字节消息M',种子种子,地址ADRS输出:n字节根值节点[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];
        
     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

完整的XMSS签名验证描述如下(算法14)。它处理消息压缩,将根计算委托给XMSS_rootFromSig,并将结果与公钥中的值进行比较。XMSS_verify将XMSS签名Sig作为输入

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.

消息M和XMSS公钥PK。当且仅当Sig是公钥PK下M上的有效签名时,XMSS_verify返回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);
        
     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;
     }
        
     byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M',
                                     getSEED(PK), ADRS);
     if ( node == getRoot(PK) ) {
       return true;
     } else {
       return false;
     }
        
4.1.11. Pseudorandom Key Generation
4.1.11. 伪随机密钥生成

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私钥。例如,可使用[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用于为每个WOTS+密钥对生成n字节值S_ots。然后,可以使用第3.1.7节中描述的方法,使用n字节值S_ots计算相应的WOT+私钥。WOTS+密钥对的种子被计算为S_ots[i]=PRF(S,toByte(i,32)),其中i是WOTS+密钥对的索引。该方法的一个优点是,当给定S时,可以仅使用PRF的len+1求值来计算WOTS+密钥。

4.1.12. Free Index Handling and Partial Private Keys
4.1.12. 自由索引处理和部分私钥

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.

某些应用程序可能需要使用部分私钥或私钥副本。示例包括负载平衡和签名权或代理签名的委托。这些应用程序可以使用它们自己的密钥格式,并且可以使用与上述不同的签名算法。部分私钥或私钥副本中的索引可根据应用程序的要求进行操作。然而,应用程序必须建立一种方法,以保证每个索引以及每个WOTS+密钥对仅用于对单个消息进行签名。

4.2. XMSS^MT: Multi-Tree XMSS
4.2. XMSS^MT:多树XMSS

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]中首次对其进行了描述。它建立在XMS之上。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的XMSS MT树,该树具有高度H/D的XMSS树的D层。然后,层d-1包含一个XMSS树,层d-2包含2^(h/d)个XMSS树,依此类推。最后,层0包含2^(h-h/d)XMSS树。

4.2.1. XMSS^MT Parameters
4.2.1. XMSS^MT参数

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系统还需要树层数d,指定为不带余数除以h的整数值。所有树层使用相同的树高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+用于对根节点本身进行签名,而不是对其哈希值进行签名。

4.2.2. XMSS^MT Key Generation
4.2.2. XMSS^MT密钥生成

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

XMSS^MT私钥SK_MT(S表示机密)由每个XMSS树的一个简化的XMSS私钥组成。这些缩减的XMSS私钥仅包含与该XMSS密钥对相对应的WOTS+私钥;它们不包含伪随机函数键、索引、公共种子或根节点。相反,SK_MT包含单个n字节伪随机函数键SK_PRF、单个(ceil(h/8))字节索引idx_MT、单个n字节种子和单个根值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.

(它是顶层上单个树的根)。该索引是层0上所有XMSS树的所有WOT+密钥对的全局索引。它是用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节所述的加密伪随机方法生成。对于XMS,PRF密钥SK_PRF必须从遵循均匀分布的安全随机性源中采样。种子作为统一的随机n字节字符串生成。虽然种子是公开的,但使用良好的熵源生成种子对安全性至关重要。根是顶层单个XMSS树的根节点。其计算说明如下。对于XMS,根和种子是公共信息,通常被视为公钥的一部分。但是,由于签名只需要私钥,所以这两个密钥都是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层上第x^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树的根和种子。这些值与私钥SK_MT中的值相同。使用种子键控的伪随机函数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
        
   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
        
     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);
        
     // 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);
        }
     }
        
     // 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);
        
     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);
        
     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.

以上只是一个示例算法。强烈建议使用伪随机密钥生成来减小私钥大小。公钥和私钥生成可以交叉进行以节省空间。具体地,当使用伪随机方法来生成私钥时,生成可以延迟到另一算法需要相应的wot+密钥对的点。

The format of an XMSS^MT public key is given below.

XMSS^MT公钥的格式如下所示。

            +---------------------------------+
            |          algorithm OID          |
            +---------------------------------+
            |                                 |
            |            root node            |     n bytes
            |                                 |
            +---------------------------------+
            |                                 |
            |              SEED               |     n bytes
            |                                 |
            +---------------------------------+
        
            +---------------------------------+
            |          algorithm OID          |
            +---------------------------------+
            |                                 |
            |            root node            |     n bytes
            |                                 |
            +---------------------------------+
            |                                 |
            |              SEED               |     n bytes
            |                                 |
            +---------------------------------+
        

XMSS^MT Public Key

XMSS^MT公钥

4.2.3. XMSS^MT Signature
4.2.3. 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+签名签名和身份验证路径认证。它们不包含索引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)          |
           |                                 |
           +---------------------------------+
        
           +---------------------------------+
           |                                 |
           |          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签名

4.2.4. XMSS^MT Signature Generation
4.2.4. 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\u sign(算法16)使用第4.1.9节中定义的treeSig。首先,签名索引设置为idx_sig。接下来,PRF用于计算伪随机n字节字符串r。然后使用这个n字节字符串idx_sig和PK_MT的根节点来计算长度为n的随机消息摘要。消息摘要使用底层的WOTS+密钥对和绝对索引idx进行签名。计算WOTS+密钥对的身份验证路径和包含XMSS树的根。根由父XMSS树签名。重复此操作,直到到达最上面的树为止。

   Algorithm 16: XMSSMT_sign - Generate an XMSS^MT signature and update
   the XMSS^MT private key
        
   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);
        
     // 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);
        
     // 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);
        
     // 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;
        
     // 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]。

4.2.5. XMSS^MT Signature Verification
4.2.5. XMSS^MT签名验证

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
        
   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\u MT,消息M,XMSS^MT公钥PK\u MT输出:布尔值

     idx_sig = getIdx(Sig_MT);
     SEED = getSEED(PK_MT);
     ADRS = toByte(0, 32);
        
     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);
        
     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);
        
     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;
     }
        
     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;
     }
        
4.2.6. Pseudorandom Key Generation
4.2.6. 伪随机密钥生成

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.

与XMS类似,实现可以使用加密安全的伪随机方法从单个n字节值生成XMSS^MT私钥。例如,可以使用下面解释的方法。可以使用其他方法,例如[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密钥对生成一个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))。

4.2.7. Free Index Handling and Partial Private Keys
4.2.7. 自由索引处理和部分私钥

The content of Section 4.1.12 also applies to XMSS^MT.

第4.1.12节的内容也适用于XMSS^MT。

5. Parameter Sets
5. 参数集

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.

本节提供基本参数集,假设这些参数集涵盖大多数相关应用。定义了两个经典安全级别的参数集。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.

虽然本文档指定了多个参数集,但只需要实现为验证所有必需参数集提供支持。所需参数集均使用SHA2-256实例化所有函数。所需的参数集仅通过树高参数h(它决定了可以使用单个密钥对完成的签名数量)和层数d(它定义了速度和签名大小之间的权衡)来区分。一种实现可以使用所提议的任何参数集来提供对签名生成的支持。为方便起见,本文档为XMSS(XMSS_SHA2_20_256)和XMSS^MT(XMSSMT-SHA2_60/3_256)定义了一个默认选项。这些应该与最通用的需求相匹配。

5.1. Implementing the Functions
5.1. 履行职能

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(托拜特(0,32)| | |键| | M),

H: SHA2-256(toByte(1, 32) || KEY || M),

H:SHA2-256(托拜特(1,32)| | | |键| | M),

      H_msg: SHA2-256(toByte(2, 32) || KEY || M), and
        
      H_msg: SHA2-256(toByte(2, 32) || KEY || M), and
        

PRF: SHA2-256(toByte(3, 32) || KEY || M).

PRF:SHA2-256(托拜特(3,32)| | |键| | M)。

Accordingly, for SHA2 with n = 64 we use:

因此,对于n=64的SHA2,我们使用:

F: SHA2-512(toByte(0, 64) || KEY || M),

F:SHA2-512(托拜特(0,64)| | | |键| | M),

H: SHA2-512(toByte(1, 64) || KEY || M),

H:SHA2-512(托拜特(1,64)| | |键| | M),

      H_msg: SHA2-512(toByte(2, 64) || KEY || M), and
        
      H_msg: SHA2-512(toByte(2, 64) || KEY || M), and
        

PRF: SHA2-512(toByte(3, 64) || KEY || M).

PRF:SHA2-512(托拜特(3,64)| | |键| | 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字节填充有两个原因。首先,内部压缩函数必须使用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(托拜特(0,32)| | | |键| | 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|u 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(托拜特(0,64)| | | |键| | M,512),

H: SHAKE256(toByte(1, 64) || KEY || M, 512),

H:SHAKE256(托拜特(1,64)| | | |键| | M,512),

H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512),

H|u msg:SHAKE256(托拜特(2,64)| | | |键| | M,512),

PRF: SHAKE256(toByte(3, 64) || KEY || M, 512).

PRF:SHAKE256(托拜特(3,64)| | | |键| | 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个字节。

5.2. WOTS+ Parameters
5.2. WOTS+参数

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-[Hashfamily]\un(以位为单位)。命名不包括w,因为本文档中的所有参数集都使用w=16。为方便起见,提供了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 |
              +-----------------+----------+----+----+-----+
        
              +-----------------+----------+----+----+-----+
              | 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。

5.3. XMSS Parameters
5.3. XMSS参数

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-[Hashfamily]\uh]\un(以位为单位)。命名不包括w,因为本文档中的所有参数集都使用w=16。

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

XMS的XDR格式在附录B中列出。

5.3.1. Parameter Guide
5.3.1. 参数指南

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

与RSA或数字签名算法(DSA)等传统签名方案不同,XMSS有一个树高参数h,该参数确定可以使用一个密钥对签名的消息数。增加高度允许使用密钥对进行更多签名,但也会增加签名大小,并减慢密钥生成、签名和验证的速度。为了演示不同h值的影响,下表显示了签名大小和运行时。当BDS算法用于计算身份验证路径时,运行时作为对F和H的调用数给出

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.

最坏的情况。最后一列显示可以使用一个密钥对签名的消息数。参数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 |
    +------------------+-------+------------+--------+--------+-------+
        
    +------------------+-------+------------+--------+--------+-------+
    | 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,该选项允许使用一个密钥对对2^20消息进行签名,并提供合理的速度和签名大小。需要每个密钥对更多签名的用户或更快的密钥生成应该考虑XMSS ^ MT。

5.4. XMSS^MT Parameters
5.4. 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-[Hashfamily].[h]/[d].[n位]。命名不包括w,因为本文档中的所有参数集都使用w=16。

     +------------------------+-----------+----+----+-----+----+----+
     | 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 |
        
     +------------------------+-----------+----+----+-----+----+----+
     | 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 |
     +------------------------+-----------+----+----+-----+----+----+
        
     |                        |           |    |    |     |    |    |
     | 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中列出。

5.4.1. Parameter Guide
5.4.1. 参数指南

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的树高参数外,XMSS^MT还有一个确定树层数量的参数d。XMSS可以理解为具有单层的XMSS^MT,即d=1。因此,h的选择具有与XMS相同的效果。树层的数量在一侧的签名大小与另一侧的密钥生成和签名速度之间提供了一种折衷。增加层数以指数方式减少密钥生成时间,以线性增加签名大小为代价线性减少签名时间。基本上,XMSS^MT签名每层包含一个WOTSP签名。速度大致相当于高度为h/d的树的XMS速度的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-

为了演示h和d的不同值的影响,下表显示了签名大小和运行时。当使用BDS算法和分布式签名生成时,运行时是F和H的调用次数。时间是最糟糕的时刻。最后一列显示可以使用一个密钥对签名的消息数。XMS的编号相同-

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和n的抖动实例。由于格式限制,仅给出参数集名称的参数部分,省略名称“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 |
    +----------------+---------+------------+--------+--------+-------+
        
    +----------------+---------+------------+--------+--------+-------+
    | 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,该选项允许使用一个密钥对对2^60条消息进行签名(这实际上是一个无限数量的签名)。同时,签名的大小和速度也很好地平衡了。

6. Rationale
6. 根本原因

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算法。描述是以模块化的方式完成的,允许基于无状态散列的签名算法(如括约肌[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,用一个秘密值进行键控。原因是这只需要处理一次消息,而不是两次。对于长消息,这可以提高速度并简化在资源受限的设备上的实现,这些设备无法将整个消息保存在存储器中。

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给出了一组必需的参数。原因有两方面。一方面,SHA2-256是大多数加密库的一部分。另一方面,256位散列函数产生的参数即使在量子计算机辅助攻击下也能提供128位的安全性。256位的后量子安全级别似乎过于保守。然而,为了准备可能的密码分析突破,我们还提供了可选的参数集,使用不太广泛支持的SHA2-512、SHAKE-256和SHAKE-512函数。

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位枚举值开始,该值指示签名算法的所有细节,并因此定义解析格式所需的所有信息。

7. Reference Code
7. 参考代码

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语言的参考实现。该代码包含一个基本实现,该实现密切遵循本文档中的伪代码,以及一个优化实现,该实现使用BDS算法[BDS08]计算XMSS^MT的认证路径和分布式签名生成,如[HRB13]所述。

The code is permanently available at <https://github.com/joostrijneveld/xmss-reference>.

该代码在以下位置永久可用:<https://github.com/joostrijneveld/xmss-reference>.

8. IANA Considerations
8. IANA考虑

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:

互联网分配号码管理局(IANA)创建了三个注册中心:一个用于WOTS+签名(定义见第3节)、一个用于XMSS签名(定义见第4节)和一个用于XMSS^MT签名(定义见第4节)。为清晰方便起见,第5节定义了WOTS+、XMSS和XMSS^MT参数集的第一个集合。对这些注册中心的补充要求规范记录在RFC或另一个永久且随时可用的参考文件中,详细程度由[RFC8126]中描述的“所需规范”政策定义,以使独立实现之间的互操作性成为可能。这些注册表中的每个条目都包含以下元素:

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

向这些注册表添加条目的请求必须包括名称和引用。号码由IANA分配。这些数字分配应使用最小的可用正数。提交者的请求必须经过审查和批准。根据[RFC8126]定义的“所需规范”政策的要求,该任务的指定专家将由

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

互联网工程指导小组(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(十进制0)。0xDDDD(十进制3722304989)和0xFFFFFFFF(十进制4294967295)之间的数字将不由IANA分配,并保留供私人使用;不会试图阻止多个站点以不同(且不兼容)的方式使用相同的值[RFC8126]。

The "WOTS+ Signatures" registry is as follows.

“WOTS+签名”注册表如下所示。

          +--------------------+-----------------+-------------+
          | 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 |
          +--------------------+-----------------+-------------+
        
          +--------------------+-----------------+-------------+
          | 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签名”注册表如下所示。

         +--------------------+-------------------+-------------+
         | 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 |
         +--------------------+-------------------+-------------+
        
         +--------------------+-------------------+-------------+
         | 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签名”注册表如下所示。

       +--------------------+------------------------+-------------+
       | 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 |
        
       +--------------------+------------------------+-------------+
       | 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 |
       +--------------------+------------------------+-------------+
        
       |                    |                        |             |
       |     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注册不构成对该系统或其安全性的认可。

9. Security Considerations
9. 安全考虑

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

阻止攻击者发起攻击意味着攻击在计算上过于昂贵,无法执行。当计算过于昂贵而无法完成时,有各种各样的估计。因此,本说明仅描述攻击者生成伪造文件的成本。参数带有位安全值。比特安全性的含义如下。如果最佳攻击至少需要2^(b-1)位操作才能获得成功概率,则参数集授予b位安全性

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

1/2. 因此,要成功发起攻击,攻击者平均需要执行2^b位的操作。比特安全性的给定值根据[HRS16]进行估计。

9.1. Security Proofs
9.1. 安全证明

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的某些安全属性中的至少一个,才能在所描述的任何方案中伪造签名。[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是后量子多功能多目标第二前像抗键控函数,F满足额外的统计要求,大致上说,大多数图像至少有两个前像,PRF是后量子伪随机函数,H_msg是一个后量子多目标扩展目标抗冲突键控哈希函数。有关这些属性的详细定义,请参见[HRS16]。直观地说:多功能多目标第二个前映像阻力是第二个前映像阻力对键控哈希函数的扩展,涵盖了对手在多个值中的一个找到第二个前映像时成功的情况。多目标扩展目标冲突抵抗也是如此,它只是缺少多功能标识符,因为目标冲突抵抗已经考虑了键控哈希函数。[HRS16]中的证明将PRF分解为两个函数。当PRF用于伪随机密钥生成或随机消息散列的随机性生成时,它仍然被视为伪随机函数。每当使用PRF生成位掩码和散列函数键时,它都被建模为随机oracle。这是由于证明中的技术原因,并且使用伪随机函数的实现是安全的。

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

[HRS16]中的证明考虑了初始消息压缩的经典随机哈希,即H(r,M)而不是H(r | | | getRoot(PK)| index,M)。这种经典的随机散列允许从扩展的目标冲突抵抗[HRS16]中获得安全性降低,该属性被推测为严格弱于冲突抵抗。然而,事实证明,在这种情况下,即使同时针对多个用户,攻击者仍然可以发起多目标攻击。原因是攻击u用户的对手同时学习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.

签名索引i在[0,2^H-1]中,用户索引j在[0,u]中的随机散列H(r|i|j | M|i|j)。对于u*2^H中的一个学习哈希,只需找到一对(r*,M*),使得H(r*| M*)=H(r|i|u | M|u)。因此,攻击者可以在2^n/u*2^h而不是2^n的时间内进行暴力搜索。

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)使得散列函数调用位置和用户相关。这阻止了上述攻击,因为攻击期间的每个哈希函数计算只能针对一个已学习的随机哈希值。更具体地说,攻击者现在必须决定每个查询使用哪个索引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.

给定的比特安全值是根据针对所用散列函数和伪随机函数所需安全属性的最著名的通用攻击的复杂性来估计的,假设存在常规和量子对手。在撰写本文时,对于经典设置中建议的参数,泛型攻击是最著名的攻击。此外,在quantum设置中,没有已知的专用攻击比一般攻击性能更好。然而,哈希函数的量子密码分析的主题并不像在经典环境中那样容易理解。

9.2. Minimal Security Assumptions
9.2. 最小安全性假设

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)还依赖于某些数学问题的推测难度。

9.3. Post-Quantum Security
9.3. 后量子安全

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的大小必须是经典安全性所需大小的两倍。这是为了防止Grover算法引起的量子平方根攻击。[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.

如上所述,我们只考虑这里的通用攻击,因为加密哈希函数应该在执行显著更好的专用攻击时被弃用。这也适用于量程设置。一旦存在针对所使用的哈希函数的专用量子攻击,且该攻击的性能明显优于所描述的通用攻击,则不应再将这些哈希函数用于所描述的方案,或者必须重新计算安全级别。

10. References
10. 工具书类
10.1. Normative References
10.1. 规范性引用文件

[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]国家标准与技术研究所,“安全哈希标准(SHS)”,FIPS PUB 180-4,DOI 10.6028/NIST.FIPS.180-42015年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]艾斯勒,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]Cotton,M.,Leiba,B.,和T.Narten,“在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>.

10.2. Informative References
10.2. 资料性引用

[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树遍历”,计算机科学课堂讲稿,第5299卷,后量子密码学,DOI 10.1007/978-3-540-88403-3_52008。

[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]Bernstein,D.,Hopwood,D.,Huelsing,A.,Lange,T.,Niederhagen,R.,Papchristodoulou,L.,Schneider,M.,Schwabe,P.,和Z.Wilcox-O'Hearn,“括约肌:实用的无状态散列签名”,计算机科学讲稿,第9056卷,密码学进展-欧密码,DOI 10.1007/978-3-662-46800-5,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収,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+短签名”,《计算机科学讲稿》,第7918卷,密码学进展-非洲密码,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.“使用最小安全假设的实用前向安全签名”,博士论文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,“Merkle树遍历算法的时空高效实现”,计算研究存储库(CoRR),arXiv:1409.40812014。

[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,“基于哈希的签名”,正在进行的工作,草稿-McGrew-Hash-sigs-112018年4月。

[Merkle83] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Computer Science Series, UMI Research Press, ISBN: 9780835713849, 1983.

[Merkle83]Merkle,R.,“保密、认证和公钥系统”,计算机科学系列,UMI研究出版社,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格式。

A.1. WOTS+ Parameter Sets
A.1. WOTS+参数集

WOTS+ parameter sets are defined using XDR syntax as follows:

WOTS+参数集使用XDR语法定义如下:

      /* ots_algorithm_type identifies a particular
         signature algorithm */
        
      /* 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,
      };
        
      enum ots_algorithm_type {
        wotsp_reserved  = 0x00000000,
        wotsp-sha2_256  = 0x00000001,
        wotsp-sha2_512  = 0x00000002,
        wotsp-shake_256 = 0x00000003,
        wotsp-shake_512 = 0x00000004,
      };
        
A.2. WOTS+ Signatures
A.2. WOTS+签名

WOTS+ signatures are defined using XDR syntax as follows:

WOTS+签名使用XDR语法定义如下:

      /* Byte strings */
        
      /* Byte strings */
        
      typedef opaque bytestring32[32];
      typedef opaque bytestring64[64];
        
      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];
        
      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];

案例wotsp-sha2_512:案例wotsp-shake_512:bytestring64 ots_sig_n64_len18[131];

        default:
          void;   /* error condition */
      };
        
        default:
          void;   /* error condition */
      };
        
A.3. WOTS+ Public Keys
A.3. WOTS+公钥

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];
        
      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];

案例wotsp-sha2_512:案例wotsp-shake_512:通过测试64 ots_pubk_n64_len18[131];

        default:
          void;   /* error condition */
      };
        
        default:
          void;   /* error condition */
      };
        
Appendix B. XMSS XDR Formats
附录B.XMSS XDR格式
B.1. XMSS Parameter Sets
B.1. XMSS参数集

XMSS parameter sets are defined using XDR syntax as follows:

XMSS参数集使用XDR语法定义,如下所示:

      /* Byte strings */
        
      /* Byte strings */
        

typedef opaque bytestring4[4];

typedef不透明bytestring4[4];

      /* Definition of parameter sets */
        
      /* Definition of parameter sets */
        

enum xmss_algorithm_type { xmss_reserved = 0x00000000,

枚举xmss_算法_类型{xmss_reserved=0x00000000,

        /* 256 bit classical security, 128 bit post-quantum security */
        
        /* 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=0x00000001,xmss-sha2_16_256=0x00000002,xmss-sha2_20_256=0x00000003,

        /* 512 bit classical security, 256 bit post-quantum security */
        
        /* 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=0x00000004,xmss-sha2_16_512=0x00000005,xmss-sha2_20_512=0x00000006,

        /* 256 bit classical security, 128 bit post-quantum security */
        
        /* 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 */
        
        /* 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,};

B.2. XMSS Signatures
B.2. XMSS签名

XMSS signatures are defined using XDR syntax as follows:

XMSS签名使用XDR语法定义如下:

      /* Authentication path types */
        
      /* 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];
        
      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];

案例xmss-sha2_16_256:案例xmss-shake_16_256:bytestring32 path_n32_t16[16];

case xmss-sha2_20_256: case xmss-shake_20_256: bytestring32 path_n32_t20[20];

案例xmss-sha2_20_256:案例xmss-shake_20_256:bytestring32 path_n32_t20[20];

case xmss-sha2_10_512: case xmss-shake_10_512: bytestring64 path_n64_t10[10];

案例xmss-sha2_10_512:案例xmss-shake_10_512:bytestring64 path_n64_t10[10];

case xmss-sha2_16_512: case xmss-shake_16_512: bytestring64 path_n64_t16[16];

案例xmss-sha2_16_512:案例xmss-shake_16_512:bytestring64 path_n64_t16[16];

case xmss-sha2_20_512: case xmss-shake_20_512: bytestring64 path_n64_t20[20];

案例xmss-sha2_20_512:案例xmss-shake_20_512:bytestring64 path_n64_t20[20];

        default:
          void;     /* error condition */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* Types for XMSS random strings */
        
      /* 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;
        
      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;

案例xmss-sha2_10_512:案例xmss-sha2_16_512:案例xmss-sha2_20_512:案例xmss-shake_10_512:案例xmss-shake_16_512:案例xmss-shake_20_512:bytestring64 rand_n64;

        default:
          void;     /* error condition */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* Corresponding WOTS+ type for given XMSS type */
        
      /* 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;
        
      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;

案例xmss-sha2_10_512:案例xmss-sha2_16_512:案例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;

案例xmss-shake_10_256:案例xmss-shake_16_256:案例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;

案例xmss-shake_10_512:案例xmss-shake_16_512:案例xmss-shake_20_512:wotsp-shake_512;

        default:
          void;     /* error condition */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* XMSS signature structure */
        
      /* 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;
      };
        
      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;
      };
        
B.3. XMSS Public Keys
B.3. XMSS公钥

XMSS public keys are defined using XDR syntax as follows:

XMSS公钥使用XDR语法定义如下:

      /* Types for bitmask seed */
        
      /* 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;
        
      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;

案例xmss-sha2_10_512:案例xmss-sha2_16_512:案例xmss-sha2_20_512:案例xmss-shake_10_512:案例xmss-shake_16_512:案例xmss-shake_20_512:bytestring64 seed_n64;

        default:
          void;     /* error condition */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* Types for XMSS root node */
        
      /* 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;
        
      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;

案例xmss-sha2_10_512:案例xmss-sha2_16_512:案例xmss-sha2_20_512:案例xmss-shake_10_512:案例xmss-shake_16_512:案例xmss-shake_20_512:bytestring64 root_n64;

        default:
          void;     /* error condition */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* XMSS public key structure */
        
      /* XMSS public key structure */
        
      struct xmss_public_key {
        xmss_root root;  /* Root node */
        seed SEED;  /* Seed for bitmasks */
      };
        
      struct xmss_public_key {
        xmss_root root;  /* Root node */
        seed SEED;  /* Seed for bitmasks */
      };
        

Appendix C. XMSS^MT XDR Formats

附录C.XMSS^MT XDR格式

C.1. XMSS^MT Parameter Sets
C.1. XMSS^MT参数集

XMSS^MT parameter sets are defined using XDR syntax as follows:

XMSS^MT参数集使用XDR语法定义如下:

      /* Byte strings */
        
      /* Byte strings */
        
      typedef opaque bytestring3[3];
      typedef opaque bytestring5[5];
      typedef opaque bytestring8[8];
        
      typedef opaque bytestring3[3];
      typedef opaque bytestring5[5];
      typedef opaque bytestring8[8];
        
      /* Definition of parameter sets */
        
      /* Definition of parameter sets */
        

enum xmssmt_algorithm_type { xmssmt_reserved = 0x00000000,

枚举xmssmt_算法_类型{xmssmt_reserved=0x00000000,

        /* 256 bit classical security, 128 bit post-quantum security */
        
        /* 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\U 20/2\U 256=0x00000001,xmssmt-sha2\U 20/4\U 256=0x00000002,xmssmt-sha2\U 40/2\U 256=0x00000003,xmssmt-sha2\U 40/4\U 256=0x00000004,xmssmt-sha2\U 40/8\U 256=0x00000005,xmssmt-sha2\U 60/3\U 256=0x00000006,xmssmt-sha2\U 60/6\U 256=0x00000007,xmssmt-sha2\U 60/12\0x00000008,

        /* 512 bit classical security, 256 bit post-quantum security */
        
        /* 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\U 20/2\U 512=0x00000009,xmssmt-sha2\U 20/4\U 512=0x0000000A,xmssmt-sha2\U 40/2\U 512=0x0000000B,xmssmt-sha2\U 40/4\U 512=0x0000000C,xmssmt-sha2\U 40/8\U 512=0x0000000D,xmssmt-sha2\U 60/3\U 512=0x0000000E,xmssmt-sha2\U 60/6\U 512=0x0000000F,xmssmt-sha2\U=0x00000010,

        /* 256 bit classical security, 128 bit post-quantum security */
        
        /* 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\U 20/2\U 256=0x00000011,xmssmt-shake\U 20/4\U 256=0x00000012,xmssmt-shake\U 40/2\U 256=0x00000013,xmssmt-shake\U 40/4\U 256=0x00000014,xmssmt-shake\U 40/8\U 256=0x00000015,xmssmt-shake\U 60/3\U 256=0x00000016,xmssmt-shake\U 60/6\U=256 0x00000017,xmssmt-shake\U 60/12\U 256=0x00000018,

        /* 512 bit classical security, 256 bit post-quantum security */
        
        /* 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,
      };
        
        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,
      };
        
C.2. XMSS^MT Signatures
C.2. XMSS^MT签名

XMSS^MT signatures are defined using XDR syntax as follows:

XMSS^MT签名使用XDR语法定义如下:

      /* Type for XMSS^MT key pair index */
      /* Depends solely on h */
        
      /* 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;
        
      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_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;
        
        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 */
      };
        
        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;
        
      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;
        
        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 */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* Type for reduced XMSS signatures */
        
      /* 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];
        
      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_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_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/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_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];
        
        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 */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* xmss_reduced_array depends on d */
        
      /* 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];
        
      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_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_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_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_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];
        
        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 */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* XMSS^MT signature structure */
        
      /* 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;
      };
        
      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;
      };
        
C.3. XMSS^MT Public Keys
C.3. XMSS^MT公钥

XMSS^MT public keys are defined using XDR syntax as follows:

XMSS^MT公钥使用XDR语法定义如下:

      /* Types for bitmask seed */
        
      /* 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;
        
      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;
        
        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 */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* Types for XMSS^MT root node */
        
      /* 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;
        
      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:

案例xmssmt-sha2\U 20/2\U 512:案例xmssmt-sha2\U 20/4\U 512:案例xmssmt-sha2\U 40/2\U 512:案例xmssmt-sha2\U 40/4\U 512:案例xmssmt-sha2\U 40/8\U 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;
        
        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 */
      };
        
        default:
          void;     /* error condition */
      };
        
      /* XMSS^MT public key structure */
        
      /* XMSS^MT public key structure */
        
      struct xmssmt_public_key {
        xmssmt_root root;  /* Root node */
        seed SEED;  /* Seed for bitmasks */
      };
        
      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.

我们要感谢约翰内斯·布劳恩、彼得·坎贝尔、弗洛里安·考勒里、斯蒂芬·法雷尔、斯科特·弗洛勒、伯特·卡利斯基、亚当·兰利、马科斯·曼扎诺、大卫·麦格雷夫、拉斐尔·米索茨基、肖恩·帕金森、塞巴斯蒂安·罗兰和凯卡团队的帮助和评论。

Authors' Addresses

作者地址

Andreas Huelsing TU Eindhoven P.O. Box 513 Eindhoven 5600 MB The Netherlands

Andreas Huelsing TU Eindhoven邮政信箱513 Eindhoven 5600 MB荷兰

   Email: ietf@huelsing.net
        
   Email: ietf@huelsing.net
        

Denis Butin TU Darmstadt Hochschulstrasse 10 Darmstadt 64289 Germany

Denis Butin TU Darmstadt Hochschulstrasse 10 Darmstadt 64289德国

   Email: dbutin@cdc.informatik.tu-darmstadt.de
        
   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 Kirchheim bei Muenchen 85551德国

   Email: ietf@gazdag.de
        
   Email: ietf@gazdag.de
        

Joost Rijneveld Radboud University Toernooiveld 212 Nijmegen 6525 EC The Netherlands

荷兰托尔努埃尔德托尔努埃尔德212奈梅根6525欧共体Joost Rijneveld Radboud大学

   Email: ietf@joostrijneveld.nl
        
   Email: ietf@joostrijneveld.nl
        

Aziz Mohaisen University of Central Florida 4000 Central Florida Blvd Orlando, FL 32816 United States of America

阿齐兹·莫哈森中佛罗里达大学4000佛罗里达中部奥兰多,佛罗里达州美利坚合众国32816

   Phone: +1 407 823-1294
   Email: mohaisen@ieee.org
        
   Phone: +1 407 823-1294
   Email: mohaisen@ieee.org