WOTS+

本文建立在 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$ 为其他哈希值长度。

一般情况下，我们要求：$w|m , w | 8$ ， 这将极大的简化之后的代码编写。

计算：

$$ l_1 = \lceil \frac{m}{w}\rceil,\ l_2 = \lfloor \frac{\log(l_1(2^w-1))}{w} \rfloor + 1 ,\ l = l_1 + l_2 $$

定义 $c^i(x, \boldsymbol{r})$ 运算：

$$
c^i(x,\boldsymbol{r}) =
\begin{cases}
& x, & i = 0 \\
& \mathcal{F}(c^{i-1}(x,\boldsymbol{r})\oplus r_i), & i \gt 0
\end{cases}
$$

其中
$$\begin{aligned}
& x \in \{0,1\}^n
\\
& \mathcal{F}: \{0,1\}^n \rightarrow \{0,1\}^n
\\
& \boldsymbol{r} = (r_1, r_2, \dotsm, r_{2^w-1}) \in \{0,1\}^{n\times (2^w-1)}
\end{aligned}
$$

定义

$$\boldsymbol{r}_{a,b} =
\begin{cases}
&(r_a, r_{a+1}, \dotsm, r_b), & a \ge b
\\
& \emptyset , & a < b
\end{cases}$$

注：原文中使用 $c^i_k(x,\boldsymbol{r})$ 含有参数 $k$，用来确定使用的哈希函数，这里为了简单和方便理解，不再暴露该参数。在实现中，通常我们会指定特定的哈希函数，不会使用参数 $k$。

通过 $PRG$ 生成 $l+2^w-1$ 个 $n$ bits 的随机数，前 $l$ 个随机数即为私钥：

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

后 $2^w-1$ 个为掩码

$$\boldsymbol{r} = (r_1, r_2, \dotsm, r_{2^w-1})$$

公钥包括 $l+1$ 个 $blocks$，第一个 $block$ 为掩码 $\boldsymbol{r}$。后 $l$ 个通过 $sk$ 进行转换：

$$pk_i = c^{2^w-1}(sk_{i-1},\boldsymbol{r}), i \in [1,l]$$

最终，公钥为

$$\begin{aligned}
pk &= (pk_0, pk_1, \dotsm, pk_l) \\
&= (\boldsymbol{r}, c^{2^w-1}(sk_0, \boldsymbol{r}), \dotsm, c^{2^w-1}(sk_{l-1}, \boldsymbol{r}))
\end{aligned}
\tag{2}
$$

图示：

消息签名($SIG$)

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

使用哈希函数

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

计算消息 $M \in \{0, 1\}^*$ 的摘要 $m \in \{0,1\}^m$，这 $m$ bits 分成 $l_1$ 份，每一份 $w$ bits。

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

上述的每 $w$ bits 表示的 $m_i, i \in [0, l_1-1]$ 等价于一个整数。

接下来计算校验和(Checksum)

$$C = \sum^{l_1}_{i=1}(2^w-1-m_i) \le l_1(2^w-1)$$

将 $C$ 同样表示每部分 $w$ bits，或者说转换成以 $w$ 为基的数字。

$$c = (c_0, c_1, \dotsm, c_{l_2-1})$$

设
$$b = (b_0, b_1, \dotsm, b_{l-1}) = m || c$$

即 $b$ 为 $m$ 和 $c$ 的串接。

则签名

$$\begin{aligned}
\sigma &= (\sigma_0, \sigma_1, \dotsm, \sigma_{l-1}) \\
&= (\mathcal{F}^{b_0}(sk_0, \boldsymbol{r}), \mathcal{F}^{b_1}(sk_1,\boldsymbol{r}), \dotsm, \mathcal{F}^{b_{l-1}}(sk_{l-1},\boldsymbol{r}))
\end{aligned}$$

图示：

消息校验($VER$)

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

通过上述同样的方式将消息 $M$ 转换成

$$b = (b_0, b_1, \dotsm, b_{l-1})$$

将传递过来的签名
$$\sigma = (\sigma_0, \sigma_1, \dotsm, \sigma_{l-1})$$

进行如下处理，得到 $pk^\prime$

$$\begin{aligned}
pk^\prime &= (\boldsymbol{r}, pk^\prime_1, pk^\prime_2, \dotsm, pk ^\prime_{l}) \\
&= (\boldsymbol{r}, \mathcal{F}^{2^w-1-b_0}(\sigma_0), \mathcal{F}^{2^w-1-b_1}(\sigma_1), \dotsm,\mathcal{F}^{2^w-1-b_{l-1}}(\sigma_{l-1}))
\end{aligned}$$

和公钥

$$pk = (\boldsymbol{r},pk_1, pk_2, \dotsm, pk_{l})$$

进行匹配，如果 $pk = pk^\prime$ 则校验通过，返回 $true$，否则返回 $false$。

图示：