XMSS 哈希地址方案

方案使得每个hash函数调用随机化，除了原始消息摘要，还需要额外的key和不同的bitmask给到每一个hash函数调用。

输入：密钥种子，32字节ADRS
输出：n字节（n是安全参数）

下面是ADRS的结构说明（三种不同类型的地址，对应Type字段）

OTS哈希地址

Type = 0

keyAndMask：用于为一个哈希函数调用生成两个不同地址
生成密钥：keyAndMask <—— 0
生成掩码（n Byte）：keyAndMask <—— 1

L-树哈希地址

作用：压缩一次性公钥

Type = 1

keyAndMask：用于为一个函数调用生成三个不一样的地址
生成密钥：keyAndMask <—— 0
生成掩码（n Byte）：keyAndMask <—— 1 （最高有效n字节）
生成掩码（n Byte）：keyAndMask <—— 2 （最高次有效n字节）

哈希树地址

type = 2
Padding = 0

keyAndMask：用于为一个函数调用生成三个不一样的地址
生成密钥：keyAndMask <—— 0
生成掩码（n Byte）：keyAndMask <—— 1 （最高有效n字节）
生成掩码（n Byte）：keyAndMask <—— 2 （最高次有效n字节）

基w数的字符串

一个字节字符串可以看作是以w为基数的字符串，即集合{0，1，..，w-1}中整数

成员函数

WOTS+

One-Time Signatures

每个私钥只能用于对单个消息进行一次签名。特别是，如果使用私钥对两条不同的消息进行签名，则该方案将变得不安全。

WOTS+ 参数

n：消息长度以及私钥、公钥或签名元素的长度（以字节为单位）。

w：Winternitz参数；它是集合{4，16}的一个成员。

w值越大，签名越短，但总体签名操作越慢；它对安全几乎没有影响。w的选择仅限于值4和16，因为这些值产生最佳的权衡和易于实现。

WOTS+伪随机函数

WOTS+算法使用密钥加密哈希函数F。F使用长度为n的密钥接受并返回长度为n的字节字符串。有关特定实例化的更多详细信息，请参见第5节。第9节讨论了F的安全要求。此外，WOTS+使用伪随机函数PRF。PRF采用一个n字节的键和一个32字节的索引作为输入，并生成长度为n的伪随机输出。有关特定实例化的更多详细信息，请参见第5节。第9节讨论了PRF的安全要求。

WOTS+链接函数

链接函数F（算法2）使用PRF的输出的n字节作为输入，进行迭代。它以一个OTS哈希地址作为输入。此地址将设置前6个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: 链-链函数

输入：
X，输入字符串
i，开始索引
s，步数
SEED，种子
ADRS，地址
输出：
F，X上迭代s次的值

WOTS+私钥

WOTS+中的私钥由sk表示（s表示secret），是一个长度为len的n字节字符串数组。此私钥最多只能用于签署一封邮件。每个n字节字符串必须从均匀分布中随机选择，或者使用加密安全伪随机过程选择。

Algorithm 3: WOTS生成私钥

输入：无输入
输出：WOTS+私钥sk

     for ( i = 0; i < len; i++ ) {
       initialize sk[i] with a uniformly random n-byte string;
     }
     return sk;

WOTS+公钥

WOTS+密钥对定义了一个虚拟结构，该结构由长度为w的len散列链组成。私钥中的lenn字节字符串分别定义一个哈希链的起始节点。公钥由这些散列链的末端节点组成。因此，与私钥一样，公钥也是一个长度为len的n字节字符串数组。为了计算散列链，使用链接函数（算法2）。OTS哈希地址ADR和种子必须由调用算法提供。该地址将在更大的结构中对WOTS+密钥对的地址进行编码。因此，除最后三个32位字外，WOTS+算法不得操纵ADR的任何部分。请注意，此处使用的种子是公开信息，也可供验证人使用。以下伪代码（算法4）描述了用于生成公钥pk的算法，其中sk是私钥。

Algorithm 4: WOTS私钥生成公钥

Input:
sk, WOTS+ private key
ADRS, address
SEED，seed
Output:
pk，WOTS+ public key

     for ( i = 0; i < len; i++ ) {
       ADRS.setChainAddress(i);
       pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
     }
     return pk;

WOTS+签名生成

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+算法不得操纵该算法的任何部分

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

Algorithm 5: WOTS签名

Input:
M, Message
sk, WOTS+ private key
ADRS, address
SEED, seed
Output:
sig, WOTS+ signature

csum = 0;

 // Convert message to base w
 msg = base_w(M, w, len_1);

 // Compute checksum
 for ( i = 0; i < len_1; i++ ) {
       csum = csum + w - 1 - msg[i];
 }

 // Convert csum to base w
 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
 msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
 for ( i = 0; i < len; i++ ) {
      ADRS.setChainAddress(i);
      sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
 }
 return sig;

签名的数据格式：

WOTS+签名验证

为了验证消息M上的签名sig，验证器从签名计算WOTS+公钥值。这可以通过使用消息散列的基w值及其校验和，从签名值开始“完成”链计算来完成。该步骤称为WOTS_pkFromSig，在算法6中描述如下。然后将WOTS_pkFromSig的结果与给定的公钥进行比较。如果值相等，则接受签名。否则，必须拒绝签名。OTS哈希地址ADR和种子必须由调用算法提供。该地址将在更大的结构中对WOTS+密钥对的地址进行编码。因此，除最后三个32位字外，WOTS+算法不得操纵ADR的任何部分。请注意，此处使用的种子是公开信息，也可供验证人使用。

算法6:WOTS从消息及其签名计算WOTS+公钥

Input:
M, Message
sig, WOTS+ signature
ADRS, address
SEED，seed
Output:
tmp_pk，'Temporary' WOTS+ public key

csum=0；

 // Convert message to base w
 msg = base_w(M, w, len_1);

 // Compute checksum
 for ( i = 0; i < len_1; i++ ) {
       csum = csum + w - 1 - msg[i];
 }

 // Convert csum to base w
 csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
 len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
 msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
 for ( i = 0; i < len; i++ ) {
      ADRS.setChainAddress(i);
      tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
 }
 return tmp_pk;

伪随机密钥生成

种子seed随机，保密