HORS with trees (HORST)

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。

下面按照三元组 $(GEN, SIG, VER)$ 介绍该签名算法。

密钥生成 (GEN)

$$pk \leftarrow GEN(\mathcal{S}, \mathcal{Q})$$

首先，我们需要确定参数 $t = 2^\tau$ 和 $k$，且 $t \times k = m$，$m$ 为消息哈希之后的长度，使用哈希函数 $\mathcal{H}$，$n$ 为树中的哈希值长度，使用哈希函数 $\mathcal{F}$。然后求出使得 $k(\tau -x +1) + 2^x$ 最小的 $x$，如果 $x$ 有两个解，取较大的那个。

在 $SPHINCS-256$ 中

$$t = 2^{16}, k = 32, m = 512, n = 256, x = 6 $$

下面设

$$\mathcal{H}: \{0,1\}^* \rightarrow \{0,1\}^m$$

$$\mathcal{F}: \{0,1\}^* \rightarrow \{0,1\}^n$$

密钥对的生成需要两个输入，一个是随机数种子 $\mathcal{S}\in \{0,1\}^n$，另一个是掩码 $\mathcal{Q} \in \{0,1\}^{2n\times \log t}$。 其中 $\mathcal{Q}$ 可以表示为

$$ \mathcal{Q} = (\mathcal{Q}_{0,0}, \mathcal{Q}_{0,1}, \dotsm, \mathcal{Q}_{\log t-1,0}, \mathcal{Q}_{\log t-1,1}) $$

首先，随机生成 $t$ 个随机数，作为私钥：

$$sk = (sk_0, sk_1, \dotsm, sk_{t-1}) \leftarrow G_t(\mathcal{S}) $$

然后计算

$$L_i = \mathcal{F}(sk_i)$$

作为哈希树的叶子节点，计算出树的根节点，作为公钥，这样的计算公式和 Merkle Tree 不太一样，因为需要计算掩码。 $\mathcal{Q}$ 一共是 $2 \log t$ 个，每一个 $n$ bits，每一层对应一对掩码 $(\mathcal{Q}_{i,0}, \mathcal{Q}_{i,1})$。

$$node_i = \mathcal{F}(node_{2i}\oplus \mathcal{Q}_{i,0}|| node_{2i+1}\oplus \mathcal{Q}_{i,1})$$

左节点使用 $\mathcal{Q}_{i,0}$ 进行异或操作，右结点则使用 $\mathcal{Q}_{i,1}$。

图示：

消息签名 (SIG)

$$(\sigma, pk) \leftarrow (M, \mathcal{S}, \mathcal{Q})$$

对于输入的任意消息，首先使用哈希函数 $\mathcal{H}$ 转换成 $M \in \{0,1\}^m$，然后将 $M$ 分成 $k$ 份，每一份 $\log t$ bits。

$$M = (M_0, M_1, \dotsm, M_{k-1})$$

每一份 $M_i, i \in [0, k-1]$ 对应一个整数。

与 HORS 不同的是，HORST 签名 $\sigma$ 包含 $k+1$ 个 $blocks$：

$$\sigma = (\sigma_0, \sigma_1, \dotsm, \sigma_k)$$

对于 $i \in [0,k-1], \sigma_i = (sk_{M_i}, Auth_{M_i})$，其中 $sk_{M_i}$ 的选择方法和 HORS 中一致， $Auth_{M_i}$ 是叶子节点到 $\boldsymbol{\tau -x}$ 层的 认证路径，而不是根节点。

对于 $i=k$，$\sigma_k$ 为 $\tau -x$ 层的$2^x$ 个所有节点值：

$$\sigma_k = (N_{0,\tau-x},N_{1,\tau-x},,\dotsm, N_{2^x-1,\tau-x})$$

图示：

消息校验 (VER)

$$pk^\prime \leftarrow (M, \sigma, \mathcal{Q})$$

根据上述处理，得到
$$M = (M_0, M_1, \dotsm, M_{k-1})$$

对于 $i \in [0, k-1], y_i = \lfloor \frac{M_i}{2^\tau}-x\rfloor$，通过 $L_{M_i} = \mathcal{F}(\sigma^1_i)$ 和 $Auth_{M_i} = \sigma^2_i$ 计算出 $N^\prime_{y_i, \tau-x}$，和 $\sigma_k$ 中对应的进行比较，如果全部匹配，则返回根节点 $pk$，否则返回 $fail$。

其中 $\sigma_i^1$ 表示签名第 $i$ 个 $block$ 的第一部分内容，也就是私钥内容，$\sigma_i^1$ 表示签名第 $i$ 个 $block$ 的认证路径。

图示：