回首近几年，我有幸经历了两个相互冲突、却又令人着迷的时代潮流变迁。第一个潮流变迁是：专家学者们耗费四十年设计的密码学，终于派上用场；从信息加密、电话安全、到加密数字货币，我们可以在生活的方方面面发现使用密码学的例子。
第二个潮流变迁是：所有密码学家已经做好准备，迎接以上美好的幻灭。
正文开始之前我得重申一下，本文所讲的不是所谓量子计算启示录（末日预言），也不是要讲 21 世纪密码学的成功。我们要谈论的是另一件未成定局的事情——密码学有史以来最简单的（也是最酷炫的）技术之一：基于散列函数的签名。
在 20 世纪 70 年代末，Leslie Lamport 发明了基于哈希函数（Hash Function，又称散列函数）的签名 ，并经过 Ralph Merkle 等人进一步改进。而后的很多年，这被视为密码学领域一滩有趣的“死水”，因为除了相应地产生冗长的（对比其他复杂方案）签名，基于哈希函数的签名好像没有什么作用。然而近几年来，这项技术似乎有了复苏的迹象。这很大程度归因于它的特性——不同于其他基于RSA或离散对数假设的签名，哈希函数签名被视为可以抵抗量子计算攻击（如 Shor's 算法）。
首先，我们进行一些背景介绍。
背景：哈希函数和签名方法
在正式介绍哈希函数签名之前，首先你得知道密码学中的哈希函数是什么。哈希函数可以接受一串字符（任意长度）作为输入，经过“消化”后，产生固定长度的输出。常见的密码学哈希运算，像是 SHA2、SHA3 或 Blake2 等，经运算会产生长度介于 256 ~ 512 位的输出。
一个函数 H(.) 要被称作“密码学”哈希函数，必须满足一些安全性的要求。这些要求有很多，不过我们主要聚焦在以下三个方面：
抗-原像攻击 Pre-image resistance （或俗称“单向性”）：给定输出 Y=H(X)，想要找到对应的输入 X 使得 H(X)=Y 是一件“极度费时”的工作。（这里当然存在许多例外，但最棒的部分在于，不论 X 属于什么分布，找到 X 的时间成本和暴力搜寻相同。）
抗-次原像攻击：这和前者有些微的差别。给定输入 X，对于攻击者来说，要找到另一个 X' 使得 H(X)=H(X') 是非常困难的。
抗-碰撞：很难找到两个输入 X1, X2，使得 H(X1)=H(X2)。要注意的是，这个假设的条件比 抗-次原像攻击还要严苛。因为攻击者可以从无垠的选择中寻找任意两个输入。
我们相信所有本文提到的哈希函数示例都能提供上述的所有特性。换言之，没有任何可行的（甚至是概念上的）方法能破解它。当然这种情况也是会变的，如果破解的方法被找到，我们当然会立即停用哈希函数（稍后会讨论关于量子计算攻击的特例）。
我们的目标是使用哈希函数构造数字签名方案，因此简要回顾数字签名这个词能带来很大的帮助。
数字签名方法源于公钥的使用，使用者（签署人）生成一对密钥：公钥和私钥。使用者自行保管私钥，并能够用私钥“签署”任何消息，从而产生相应的数字签名。任何一个持有公钥的人都能验证该消息正确性和相关签名。
从安全的角度来说，我们希望签名是不可伪造的，或是说“存在不可伪造性”。这意味着攻击者（没有私钥控制权的人）无法在某段消息上伪造你的签名。
Lamport 一次性签名
在 1979 年，一位名叫 Leslie Lamport 的数学家发明了世界上第一个基于哈希函数的签名。Lamport 发现只要使用简单的哈希函数，或是单向函数，就可以构建出非常强大的数字签名方法。
强大的前提是，用户只需要做一次签名的动作就能保证安全性！后续会做更详细的阐述。
为了更好的讨论，我们假设以下条件：一个哈希函数，它能接受 256 位的输入并产生 256 位的输出； SHA256 哈希函数就是个绝佳的示范工具；我们也需要能产生随机输入的方法。
假设我们的目标是对 256 位的消息进行签名。要得到我们需要的密钥，首先需要生成随机的 512 个位字符串，每个位字符串长度为 256 位。为了便于理解，我们将这些字串列为两个独立的表，并以符号代指：
sk0= sk10, sk20, ...,sk2560
sk1= sk11, sk21, ...,sk2561
我们以列表 (sk~0~, sk~1~) 表示用来签名的 密钥。接下来为了生成公钥，我们将随机的位字符串通过 H(.) 进行哈希运算，得到公钥如下表：
pk0= H(sk10), H(sk20), ...,H(sk2560)
pk1= H(sk11), H(sk21), ...,H(sk2561)
现在我们可以将公钥 (pk~0~,pk~1~) 公布给所有人知道。比如说，我们可以把公钥发给朋友，嵌入证书中，或是发布在 Keybase 上。
接着我们使用密钥对 256 位消息 M 进行签名。首先我们得将消息 M 重现为独立的 256 位元（Bit，又称“比特”）：
M1, M2, ..., M256 ∈ {0, 1}
签名算法的其余部分非常简单。我们从消息 M 的第 1 位至第 256 位，逐一相应在密钥列表中的其中一个密钥上取出字符串。而所选密钥取决于我们要签名的消息每一位（bit）的值。
具体一点地说，对于 i = [1,256]，如果第 i 位的消息位元 Mi = 0，我们会从 sk0 表中选择第 i 个字符 (ski0) ，作为我们签名的一部分；如果第 i 位的消息位元 Mi = 1，我们则从 sk1 表进行前述过程（即，如果我们要对消息 M 中的第 3 位进行签名，而该位值为 0，则使用 sk0 中的第三位，sk03，作为我们签名的一部分）。对每个消息位元完成此操作后，我们将选中的字符串连接，得到签名。
过程如图示说明，因为部分过程化简，密钥和消息长度只有 8 个 bit（位元）。要注意的是，每个色块代表的都是不同的随机 256 位字符串。