SPHINCS 于 2015 年由 Bernstein, Daniel J., Daira Hopwood, Andreas Hülsing 等人提出，具体的论文见 SPHINCS: practical stateless hash-based signatures。

SPHINCS 是一个无状态的签名系统。有状态指的是每次签名时需要记录系统的信息，比如是第几次签名，在验证的时候需要使用该参数，而无状态的签名系统则不需要保存这些信息。相对于有状态的签名系统，无状态的签名系统不需要记录签名的状态，符合标准的 API 且方便在不同主机上移植，无状态的签名系统是更好的选择。

SPNHICS 基于多种签名算法，比如 WOTS+, HORST 等，如果不了解相关内容，建议先参考之前的文章。

本文建立在 WOTS 签名系统基础上，若还尚不熟悉该签名系统，可参考另一篇文章 Winternitz One Time Signature，论文见 W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes，该算法产生的一对密钥只能签名一条消息。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定 $w$ 参数该参数决定哈希私钥多少次构造公钥，此外还需确定哈希之后摘要的长度 $m$ ，或者可以认为是采用的哈希函数族，$n$ 为其他哈希值长度。

HORST 属于 FTS，由 HORS 改进而来，相比较 HORS 而言，牺牲了运行时间，但是减少了公钥的大小，同时算法中引入了掩码的计算。

HORST 中的公钥是二叉哈希树 (binary hash tree) 的根节点，叶子节点是 HOSR 公钥的 $(t=2^\tau)$ 个 $block$ 。

本文的介绍建立在 HORS 之上，若还尚未了解 HORS 签名系统机制，可以参考另一篇文章 Hash to Obtain Random Subset (HORS)，此外，提出 HORST 的论文见 SPHINCS: practical stateless hash-based signatures。

概念

Merkle Tree 又称 Hash Tree，实现一般为二叉树，当然也可以用多叉树实现，本质是一样的，WiKi 上也有相关介绍，点击这里传送。

树的叶子节点处存放数据的哈希值，其他的非叶子节点通过子节点进行构造，按照下方公式：

$$node_i = hash(node_{2i+1} || node_{2i+2})$$

其中，节点 $i$ 是节点 $2i+1$ 和 $2i+2$ 的父结点，$||$ 表示串接，或者简单的说拼接，比如 $a = 0001_2, b = 1100_2$ 则
$$ c = a || b = 00011100_2$$

HORS(Hash to Obtain Random Subset)属于 FTS, 其生成的公私钥对，可以多次用来签名消息，但是每一次签名之后，系统的安全性会降低，签名能够被伪造的概率上升。论文可见 Better than BiBa: Short One-time Signatures with Fast Signing and Verifying。

下面以三元组 $(GEN, SIG, VER)$ 对 HORS 签名系统进行介绍。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定参数 $k$ 和 $t = 2^\tau$，哈希函数输出的摘要长度为 $n = k \times \log_2t = k \times \tau$ bits。

1979 年 Ralph C. Merkle 提出了 Winternitz-OTS，其中运用了哈希链(hash chain)的结构，论文见 A Certified Digital Signature ，更加详细的算法描述见 Hash-based Digital Signature Schemes，该算法产生的一对密钥也只能签名一条消息。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先，我们需要确定 $w$ 参数该参数决定哈希私钥多少次构造公钥，此外还需确定哈希之后摘要的长度 $n$ ，或者可以认为是采用的哈希函数族。

Lamport 是第一个 OTS(One Time Signature) 算法，由 Leslie Lamport 于 1979 年提出，论文可见 Constructing Digital Signatures from One Way Function ，一对密钥只能签名一次，不能重复使用。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先我们需要确定安全参数 $k$，不过实际操作中我们一般只需要确定输出的摘要长度 $n$。

通过随机数生成器(PRG, Pseudo Random Generator)，生成 $n$ 对随机数，每一对包含两个随机数，每一个随机数 $n$ bits，总共 $2\times n\times n$ bits，此为私钥。

对每一个随机数进行哈希，生成 $2\times n$ 个摘要，每一个 $n$ bits，也是 $2 \times n \times n$ bits，此为公钥。

形式化表示为：

$$sk = (sk_{0,0}, sk_{0,1}, \dotsm, sk_{n-1, 0}, sk_{n-1, 1}) \\
pk = (pk_{0,0}, pk_{0,1}, \dotsm, pk_{n-1, 0}, pk_{n-1, 1})$$

定义

任意的签名算法都可以用一个三元组表示: ($GEN, SIG, VER$)，可以说是组成签名系统的三个算法。

• $GEN$: 密钥生成算法
• $SIG$: 消息签名算法
• $VER$: 消息校验算法

定义一个接口表示：

1
2
3
4
5
6
7
8

type Signature interface {
	// GenerateKey generates secret key and public key
	GenerateKey() (sk []byte, pk []byte)
	// Sign computes signature of message using secret key
	Sign(message []byte, sk []byte) []byte
	// Verify check if the signature is valid
	Verify(message []byte, pk []byte, signature []byte) bool
}

下面详细说说这三个算法。

概念

什么是哈希函数？

定义其实很简单，哈希函数其实就是一种映射关系，它可以把任意长度的数据映射为固定长度的数据，输出一般称为摘要(digest) ，就比如常见的 md5 算法，可以将输入映射成 128 bits。

$$\{0, 1\}^* \overset{map}{\longrightarrow} \{0,1\}^n$$

同时，也正因为说，哈希函数将任意长度的输入映射成固定长度的输出，因为输入空间远大于输出空间，所以必然会存在冲突，比如下面的这种情景。不过，在实际使用的时候，必须要求哈希函数具备一定的安全性。