Flexible Signatures

2019/10/28 密码学

本文主要描述Lamport-Diffie一次性签名与Merkle认证树结合的签名方案,并探讨如何结合两者创建一个灵活的签名方案(flexible signatures)。

一次性签名方案

下面是关于一次性签名方案的定义。

一次性签名是至多能签一个消息的签名方案。如果签多个消息,敌手就可以伪造签名。

Lamport’s One-Time Signature Scheme

Lamport签名方案的思路很简单,以消息长度为3比特的情况为例子:

假设是一个单向函数,在的值域内公钥由6个元素组成,分别是

私钥包含对应的原像,分别是

这些公私钥对可以看作是一个二维数组。对于消息(3个比特)

其中是一个比特位,签名由三个值组成,以消息011为例,生成的签名为:(如上图所示)

验证过程是显然的,对于消息的签名,对于时,当且仅当满足

时予以接受。

敌手攻击

敌手无法对单向函数求出原像,但是如果敌手知道多个签名,那么就可以伪造签名。例如敌手知道了消息011和101的签名,那么攻击者可以构造出消息111和001的签名。因此该方案至多能签一个消息。

灵活的Lamport方案(Flexible)

Duc V.Le、Mahimna Kelkar等学者提出了灵活的Lamport方案,其中密钥生成函数、签名算法与原方案一致,修改了验证部分。

Flexible Verification Algorithm:算法的输入是消息、公钥、签名、可选参数,输出是对该签名的验证结果。下图是该方案的完整描述:

注意到,该验证方案并没有像原来方案一样对每个位都进行验证,而是验证了r比特,这意味着敌手的攻击成功概率会高一些。

基于Merkle树的签名

上面的Lamport方案只能对一个消息进行签名,而结合Merkle树则可以对多个消息进行签名。

Merkle树

Merkle树是一类基于哈希值的二叉树或多叉树,其叶子节点上的值通常为数据块的哈希值,而非叶子节点上的值。以下图为例,父节点的值是左右孩子的值结合的哈希。

Merkle树大多用来进行完整性验证处理,特别是分布式环境下,Merkle树会大大减少数据的传输量以及计算的复杂度。比特币的轻量级节点所采用的SPV验证就是利用Merkle树这一优点。

Merkle Signature Scheme

最初Merkle树的目的是高效处理Lamport one-time signatures只能签名一条消息的问题,这种方法形成了一种高效的数字签名框架Merkle Signature Scheme。

在Merkle Signature Scheme中,签名包含四个部分,分别是签名状态S、一次性签名算法、一次性公钥PK、一组认证节点Auth。

以上图为例,对于消息010的签名,其认证节点是。验证者使用公钥生成,然后用生成,以此类推溯源到根节点root,判断是否与S相同。

灵活的Merkle树的签名(Flexible)

上面的Merkle树签名方案有一个特点是,验证过程需要从叶子节点溯源到root节点,这是一个线性过程。Duc V.Le、Mahimna Kelkar等学者提出了灵活的Merkle方案,使验证过程可以随机化、多线程处理。

还是以上面的图为例,原版的签名中包含一组认证节点Auth(也就是红色高亮的节点),改进的签名是多增加一组认证节点Auth_c,对应的是蓝色高亮的节点。此时验证者可以随机对任意一层的节点进行认证,而无需按照原来的线性过程逐步溯源。

性能分析

灵活的Merkle树的签名方案相比于其他的签名方案,在时间上速度更快。

参考文献

  1. Flexible Signatures: Making Authentication Suitable for Real-Time Environments
  2. Introduction to Modern Cryptography Section 12.5 Lamport’s One-Time Signature Scheme
  3. Introduction to Modern Cryptography Section 12.6.2 “Tree-Based” Signatures

Search

    Table of Contents