Hash to Obtain Random Subset (HORS)

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。

这里，我们一般要求 $8\mid \tau$，也就是 $\tau$ 应该是 $8$ 的倍数。

通过 $PRG$ 生成 $t$ 个随机数，构成私钥：

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

对每一个随机数进行哈希，得到公钥

$$\begin{aligned}
pk &= (pk_0, pk_1, \dotsm, pk_{t-1}) \\ &= (hash(sk_0), hash(sk_1), \dotsm, hash(sk_{t-1}))
\end{aligned}$$

图示：

消息签名($SIG$)

$$ \sigma(M) \leftarrow SIG(M, sk)$$

对消息 $M\in \{0, 1\}^*$ 进行哈希，得到摘要 $m$。

将 $m$ 进行分割，分成 $k$ 份，每一份 $\tau = \log_2t$ bits，这里如果 $8|\tau$，那么编写程序的时候会得到极大的简化。

$$m = (m_0, m_1, \dotsm, m_{k-1})$$

将每一份转换成对应的整数，比如每份 $16$ bits 时：

$$\begin{aligned}
0001\_0010\_1111\_1000_2 = 4856_{10}
\end{aligned}$$

则签名为

$$\begin{aligned}
\sigma
&= (\sigma_0, \sigma_1, \dotsm, \sigma_{k-1}) \\
&= (sk_{m_0}, sk_{m_1}, \dotsm, sk_{m_{k-1}})
\end{aligned} $$

其中有可能
$$ \exists \ i, j \in [0, k-1], i \ne j, \sigma_i = \sigma_j $$

图示：

消息校验($VER$)

$$ false/true \leftarrow VER(M, \sigma(M), pk) $$

同样，将 $M$ 进行哈希之后，转换成 $k$ 个 $\tau$ bits 的整数

$$m = (m_0, m_1, \dotsm, m_{k-1})$$

计算出

$$ pk^\prime = (pk^\prime_{m_0}, pk^\prime_{m_1}, \dotsm, pk^\prime_{m_{k-1}}) $$

对于 $i \in [0,k-1]$，如果 $hash(\sigma_i) = pk^\prime_i$ 均成立，则校验成功，返回 $true$，否则校验失败，返回 $false$。

图示：