本文建立在 WOTS 签名系统基础上，若还尚不熟悉该签名系统，可参考另一篇文章 Winternitz One Time Signature，论文见 W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes，该算法产生的一对密钥只能签名一条消息。
下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。
$$(pk, sk) \leftarrow GEN(1^k)$$
首先，我们需要确定 $w$ 参数该参数决定哈希私钥多少次构造公钥，此外还需确定哈希之后摘要的长度 $m$ ，或者可以认为是采用的哈希函数族，$n$ 为其他哈希值长度。
1979 年 Ralph C. Merkle 提出了 Winternitz-OTS，其中运用了哈希链(hash chain)的结构，论文见 A Certified Digital Signature ，更加详细的算法描述见 Hash-based Digital Signature Schemes，该算法产生的一对密钥也只能签名一条消息。
下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。
$$(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)$ 三元组描述该算法。
$$(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})$$