《A Graduate Course in Applied Cryptography》Chapter 14 Fast hash-based signatures

- 日理万妓 2022-08-28 03:56 19阅读 0赞

原文教材 与 参考资料：

Boneh Dan , Shoup Victor . A Graduate Course in Applied Cryptography\[J\].

该书项目地址（可以免费获取）：http://toc.cryptobook.us/

博客为对该书的学习笔记，并非原创知识，仅帮助理解，整理思路。

## 14.0 Fast hash-based signatures ##

在13章中介绍的基于陷门函数构造的数字签名协议，往往需要较慢的签名时间以及较长签名长度存储空间，但是其安全性是基于大整数因子分解困难问题的。如果敌手具备访问量子计算机的能力，那么该类签名方案都是不安全的。

基于哈希的签名方案其签名长度比RSA的更长，但是安全性更高。考虑到完美保密的定义，这里给出一次性签名（one-time sigantures）, 该签名方案对于一条消息只能签名一次，如果使用相同的密钥对另外一个消息重复签名，那么该方案将立即失去安全性。不失一般性，可以将一次性签名推广到多次签名（q-time signature）即为该算法可以签名q次，即为该签名算法最多可以对q个消息进行签名，超过q次签名该方案将不在安全。q = 1, 就表示的是one-time signature协议，下面给出出一个形式化的 q-time signature 安全性定义：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16][]

根据经典的签名强安全定义，可以直接推广出一个强安全的q-time signature 协议：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

该书在这里首先使用单向函数构造了一个一次性签名协议，并描述了相关的应用场景，然后从该一次性签名协议出发构造了一个基本的多次签名协议。

## 14.1  Basic  Lamport signatures ##

这里给出一个最为简单的一次性签名方案，每次签名一个比特，该方案构造使用一个单向函数f。

该方案的具体构造如下：

私钥sk为两个随机数x1, x2， 设置公钥为pk:\{ f(x1), f(x2) \}。

当收到一个需要签名的消息m时，此处定义m为一个比特值。

如果m = 0, 那么签名就是x1。  如果m = 1, 那签名就是x2。

当收到签名x1或者x2时，直接使用单向函数 f 进行运算，计算f(xi), 然后比较公钥和计算结果。

如果f(xi) == f(x1) 那么就是意味着是对m = 0的签名。

如果f(xi) == f(x2) 那么就是意味着是对m = 1的签名。

函数f是一个单向函数，敌手无法从公钥获得其输入的秘密值xi。那么敌手就无法伪造对1比特签名，且明文消息不能帮助敌手伪造一个签名，下面给出该方案的安全性定理：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

**Basic Lamport Signatures :**

**       **   如果要对长度为v的消息进行签名，那么我们只要重复运行v次签名协议即可，即为每1位比特都有两个对应的签名结果，根据该比特的不同，将会输出不同的结果作为其签名结果。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

公钥的空间为y^2v，私钥的空间亦为x^2v，随机的选择2V个值作为私钥（签名）。然后使用单向函数 f（）计算对应的公钥，对一个消息m的签名结果如下：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

其中阴影部分就是对应的消息m的签名结果，任何人都可以使用消息m和签名结果以及单向函数f，公钥PK，来测定该签名是不是正确的签名。

需要注意的点：

（1）减少私钥长度，上述方案的私钥是一个二维随机数向量，这需要较长的存储空间，如果使用PRF来迭代生成私钥，那么将会使用较少的存储空间，但是增加了签名时的计算时间消耗。

（2）减少公钥长度，与私钥（签名）相同，该签名的公钥存储空间也是非常大的，可以通过增加签名的长度来减少公钥的长度。

## 14.2  A general Lamport framework ##

为了能够进一步的减少签名的长度，降低开销，这里从一个框架来展开：

此处直接给出通用的框架 ：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

G：首先产生一个随机数K，并生成n个公钥，私钥的长度通过PRF来降低，仅仅保存seed即可。

S：使用一个单射函数P，将明文消息m映射到n长的私钥空间上（为子集），然后根据映射的结果（子集，长度为l, l <= n）使用单向函数F，得到签名结果（对应的私钥）。

V：对明文使用单射P，将明文映射到n元素的子集(l)。 然后根据该子集的下标，如果该下标等于签名的的下标（正确的情况下是的确是相等的），使用单向函数f() 以签名结果作为输入，输出正正确的情况下应当与对应下标的公钥相等。然后，迭代进行验证直到结束。

这个框架最为重要的是P函数：考虑这样一种情况，如果对M进行签名，那么P（M）可以获得一个映射的序列，假设我们从该序列中选取一个子集，该子集对应另一个随机的消息M\`, 那么这里我们即可以在不知道私钥的情况下得到一个合法的M\`的签名。因此，要求映射P不能将两个不同的消息m1, m2映射成P(m1) 是 P(m2)子集的情形，称之为containment free。下面给出该属性的形式化定义：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

这里挑选满足该属性的函数P是容易的，要求P是一个单射函数，并且总是输出一个固定长度的子集。因为输出集合的长度相等，那么不存在谁是谁的子集的问题。举例，对于n = 2v, 设定P函数总是输出长度为v，下面给出该通用方案的安全性定理：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

因为敌手可以获得n个签名与公钥对，所以这里等价是进行了一个 t - repeat One-way 攻击游戏。我们可以构造一个算法B调用敌手A来赢得one-way 游戏。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 9][]

A输出一个签名，由于P是containment free的，所以m为n-1个签名中的一个原像，即为一个OW实例的解。

## 14.3  Winternitz one-time signatures ##

Winternitz 一次性签名方案亦是从Lamport 框架而来，极大的降低了签名和公钥的长度，但是该签名的验证时间被延长，这里使用一个哈希链来构造该方案，下面给出Hash chains 的定义：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 10][]

**The Winternitz scheme**:

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 11][]

形象的描述如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 12][]

如上图所示：阴影的节点即为签名结果（对于某一个P(m) = (2,1,2,3,2,1,0,2,1)).

这里需要注意私钥空间为n元素向量，d为签名的向量，即P的作用是将明文映射到从私钥空间中选择n个d长集合，然后从每个d长集合中输出一个确定的签名。这里n为P的输出长度，d为n长子集的每个元素的集合。

这里与containment free性质类似，为了防止敌手可以从一个消息M的合法签名S转化成为一个消息M\`的合法签名S\`，这里称之为domination free属，该属性描述如下：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 13][]

不论是containment free 还是 domination free性质，本质上是在防止这样一种情况：敌手可以将一个消息M1的合法签名S1，转换成为一个消息M2和合法签名S2，即使这个消息M2可能是随机的，并不具备实际语义意义的。

另外针对上述方案，还有一个单向函数的安全性定义，即多次重复迭代计算单向函数, 敌手不能攻破该单向函数，攻击游戏描述如下：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 14][]

##  14.4  HORS：short Lamport signature ##

HORS 亦是Lamport签名的变体，进一步降低了签名长度在不增加验证时间的情况下。这扩展了公钥，但是我们将会展示使用Merkle tree来降低公钥长度。

HORS的全称为Hash to obtain a random subset，简称HORS。从上文的方案中可以看出P函数生成签名子集下标，这里使用哈希来生成随机的子集，然后使用Merkle tree结构来降低公钥长度，描述如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 15][]

## ** 14.5  Applications of one-time signatures** ##

这里只有一个需要关注的内容，就是Online/offline 签名系统：将一个签名方案分成两个部分，第一部分为offline 阶段，该阶段在签名之前进行预计算，然后再Online进行签名计算，这是针对一些特殊场景的，比如CA每天需要进行大量的签名运算，并且有访问的高峰期，这里完全可以将计算复杂量大的部分放到线下阶段，然后把计算较快的部分放到Online上。

下面给出一个基本的方案：思路：使用RSA对根公钥进行验证，然后使用一次性签名方案对需要签名的消息进行签名。RSA签名较慢，一次性签名较快，可以适用于上述Online、Offline场景。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 16][]

##  14.6 From one-time signatures  to many-time signatures ##

使用一次签名构造多次签名这是一个非常符合直觉的构造，最简单的情况，多次使用一次性签名即可生成一个多次签名方案：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 17][]

方案描述如上图，是比较容易理解的，这里不在描述过程。

## 14.7 总结 ##

本节的所有描述内容都是围绕一次性签名展开，这种签名是可以抗量子攻击的，所有的讨论内容都是在围绕如何降低one-time signature的公钥长度，私钥长度，签名长度而展开的。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/add1da7ffc424e2a992154e71ff7f83d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/12b208700b044f1fada25cf0e43d748b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/f847ebe2959f4bcc9a8304dedaedd304.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/430b3d9c55ec42baabb4dfab7066be12.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/74f1323e43f4463c8c371ad7ee5ef486.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/63bdfd49e3a04117bba75bcdd8d90126.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/5e23cd4503234d7cb76286d996871c26.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/07e8d408284c41678413947f0b223bb9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/726b1e0bff3741dda5200dd79e77ec81.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/af70edf4c3b1460294d457fa671b07e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/6ebd784083474baab1d71ffc7bf6af48.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/984d4d4cae334f379b2ef40237440bee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/3aa8a1d41b35448e9df20e0e3e269699.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/134db277c9c24cd28d7beaaecfdc847c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/d019336432614383846628daae7ff13d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/7c8f89f3dd8b475582137133df25dcb2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/6e20d5aeb3884d88aa68817c03a7bdfd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAem1ybGludXg_size_20_color_FFFFFF_t_70_g_se_x_16 17]: /images/20220828/435e394c6f1f4218b8a4eabe79e28e2b.png