基于动态变色龙认证树的一次签名方案

2024年3月16日发(作者：卜维勤)

密码学报 ISSN 2095-7025 CN 10-1195/TN E-mail: jcr@

Journal of Cryptologic Rearch,2016,3(6):607–618

©《密码学报》编辑部版权所有. Tel/Fax: +86-10-82789618

基于动态变色龙认证树的一次签名方案*

王红伟1, 徐 剑1, 倪 盼2, 周福才1

1. 东北大学 软件学院, 沈阳 110169

2. 东北大学 计算机科学与工程学院, 沈阳 110169

通讯作者: 周福才, E-mail: fczhou@

摘 要: 一次签名是数字签名的一种，主要使用单向函数对消息进行签名. 一次签名相对于公钥签名更加高效, 因而在传感器网络等轻量级计算环境中有着很好的应用前景. 然而, 为了保障安全性, 一对密钥只能用于对一条消息的签名, 为不同的消息生成不同的密钥造成了密钥管理过程过于复杂. 已有的一次签名方案只能支持有限数量的一次签名, 且代价开销较大. 因此, 构建了一种基于动态变色龙认证树的一次签名方案. 首先, 将可扩展的动态变色龙认证树与一次签名结合, 给出了方案的形式化定义, 包括密钥生成算法、签名算法和验证算法, 并且介绍了每个算法的详细设计，同时对方案的构建过程进行了详细描述; 其次, 在动态变色龙认证树的结构保持性和单向性定义的基础上, 对方案的安全性进行分析, 所构造的方案在适应性选择明文攻击下是不可伪造的; 最后, 将本方案与已有方案进行比较, 结果表明该方案不仅支持无上限数量的一次签名, 同时, 方案的平均签名长度更短, 密钥生成、签名以及验证的效率更高.

关键词: 一次签名; 变色龙哈希函数; 动态变色龙认证树

中图法分类号: TP309.7 文献标识码: A DOI: 10.13868/.000156

中文引用格式: 王红伟, 徐剑, 倪盼, 周福才. 基于动态变色龙认证树的一次签名方案[J]. 密码学报, 2016, 3(6):

607–618.

英文引用格式: WANG H W, XU J, NI P, ZHOU F C. One-time signature scheme bad on dynamic chameleon

authentication tree[J].

Journal of Cryptologic Rearch, 2016, 3(6): 607–618.

One-time Signature Scheme Bad on Dynamic Chameleon Authentication Tree

WANG Hong-Wei1, XU Jian1, NI Pan2, ZHOU Fu-Cai1

1.

Software College, Northeastern University, Shenyang 110169, China

2. School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China

Corresponding author: ZHOU Fu-Cai, E-mail: fczhou@

Abstract: One-time signature is a special kind of digital signature, which mainly us one-way function to sign

messages. One-time signature is more efficient than public key signature, hence it has a good application prospect

in the lightweight computing environment such as nsor networks. However, each pair of keys can only be ud

to sign one message in order to ensure the curity. Creating different keys for different messages caus the key

management process extremely complex. Existing one-time signature schemes can only support a limited number

of signatures, and their overhead is relatively expensive. Therefore, a one-time signature scheme bad on



基金项目: 国家自然科学基金(61440014); 辽宁省博士启动基金(20141012); 中央高校基本科研业务费项目(N151704002);

沈阳市科技计划(F14-231-1-08)

收稿日期: 2016-03-29 定稿日期: 2016-08-23

608 Journal of Cryptologic Rearch 密码学报 Vol.3, No.6, Dec. 2016

dynamic chameleon authentication tree is constructed. First of all, the scheme combines dynamic chameleon

authentication tree with one-time signature. The formalization definition of the scheme includes key generation

algorithm, signature algorithm and verification algorithm. A detailed description of each algorithm is given and

the scheme construction process is described in detail. Secondly, the curity of the scheme is analyzed bad on

the structure-prerving property and one-wayness of the dynamic chameleon authentication tree. The propod

scheme is proved to be unforgeable under adaptive chon message attacks. Finally, compared with existing

schemes, the propod scheme supports unlimited number of one-time signature, and it has a shorter signature

length on average. The propod scheme is more efficient in terms of key generation, signature and

authentication.

Key words: one-time signature; chameleon Hash function; dynamic chameleon authentication tree

1 引言

近年来,

由于一次签名方案的高效性,

使其在智能电网中的多播认证[1,2]、无线传感器网络中的广播认证[3,4]等方面得到广泛应用.

一次签名是一种特殊的数字签名,

其基本思想是利用单向函数对消息进行签名,

相对基于陷门函数的公钥签名而言,

一次签名的生成与验证更高效.

但一次签名会在签名过程中暴露部分私钥,

因此为保证签名的安全性,

每对密钥只能使用一次.

一次签名方案最初由Lamport[5]提出,

因其用来签名和验证的密钥数量很大,

相对应的签名的数据量也很大.

一次签名具有时效性但空间复杂性较高,

既满足时效性高又满足空间复杂性低的方案很少.

Kalach等人[6]给出了一种基于抗碰撞哈希函数的抗量子一次签名方案,

能够适用于资源受限的设备.

此外,

一次签名方案需要满足较强的安全性. Abe等人[7]提出了一种基于线性决策假设并满足结构保持性的一次签名方案,

在每个签名中加入一个新的随机标签,

使用旧标签对新消息生成有效签名是困难的,

其方案满足了签名的强不可伪造性. Buchmann等人[8]证明了Winternitz一次签名方案的在是适应性选择消息攻击下是不可伪造的.

为降低一次签名方案的空间复杂性并解决密钥管理复杂问题,

基于Merkle树的改进方案最具典型性.

Merkle[9]将Merkle树结构与一次签名方案结合,

能够以较高的效率管理公钥和验证签名. Shoufan等人利用了Merkle加密处理器,

将基于Winternitz一次签名的Merkle树构造集成到硬件中[10],

提高了一次签名方案的性能.

基于Merkle树的一次签名方案虽然对原有方案进行了改进,

但仍存在以下问题:

第一,

在初始化过程中,

需预先计算所有叶子节点的值,

并依此构造Merkle树,

因此初始化时的计算和存储开销较大;

第二,

多数方案支持有限数量的一次签名,

能支持签名数量无上限的方案较少且难以在实际环境中应用.

传统的基于Merkle树的一次签名方案有着上述缺陷,

不能很好地进行实际应用,

所以引入变色龙哈希函数[11]这一概念来解决Merkle树存在的问题.

变色龙哈希函数是一种带陷门的单向哈希函数,

最初由Krawczyk和Rabin提出. “变色龙”的含义是陷门拥有者可以在不改变函数输出的前提下,

任意改变函数的输入,

使用陷门很容易计算出碰撞.

变色龙哈希函数的构造可基于因式分解的困难性、离散对数难题、格理论等.

Schröder等人[12]首次将变色龙哈希函数与Merkle树结合构造了变色龙认证树(chameleon authentication

tree, CAT),

并将CAT与一次签名方案相结合,

使得初始化阶段不需要预先计算出所有一次签名密钥对.

当CAT深度为D时,

一个CAT能处理的叶子节点数量为2D,

其签名大小最坏情况下由D个变色龙哈希值和一个一次签名组成.

然而, CAT结构虽支持最多2D数量的一次签名,

但在初始化时同样需要预先设定深度,

且后续每个叶子节点的认证路径长度都为深度D.

若初始化为满足需求中较大的深度D,

则会增加一次签名长度、签名及认证时间、空间等开销;

若初始化为较小的D,

当一次签名数量大于2D时,

又要重新构造更大的CAT,

重建CAT的开销会更大.

鉴于CAT存在的上述问题, 2013年Schröder和Simkin[13]首次给出了全动态变色龙认证树(fully dynamic

王红伟 等: 基于动态变色龙认证树的一次签名方案 609

chameleon authentication tree, f-CAT)和t界动态变色龙认证树(t-bounded dynamic chameleon authentication

tree, t-CAT)的概念,

并于2015年发布了f-CAT和t-CAT的正式版本[14]. 2014年陈科结合f-CAT和t-CAT的思想提出了动态变色龙认证树[15](dynamic chameleon authentication tree, DCAT).

相比f-CAT和t-CAT的验证根节点使用变色龙哈希函数计算哈希值, DCAT使用普通哈希函数计算验证根节点哈希值开销较小.

此外, f-CAT扩展树的规模时对验证根节点的更新需要用到变色龙哈希函数的可逆性, t-CAT为保证更强安全性而避免使用变色龙哈希函数的可逆性,

初始化时便限制了t-CAT的规模. DCAT不需要初始化树的深度,

能够根据需要动态扩展树的规模.

因此, DCAT在上述方面优于f-CAT和t-CAT.

为解决基于CAT的一次签名方案存在的问题,

本文将DCAT应用到一次签名方案中,

当向DCAT中插入一次签名公钥时,

其认证路径的长度、计算存储开销等与当前所支持的签名数量呈对数级增长.

2 预备知识

2.1 一次签名

一次签名是数字签名的一种,

一个公/私钥对只能对一条消息签名,

否则签名容易被伪造.

其优势是签名的生成与验证高效,

适用于计算复杂度较低的芯片.

其中,

密钥生成算法为Gen,

签名生成算法为Sig,签名验证算法为Ver,

消息为m,

签名为,

私钥为SK,公钥为PK.定义1为一次签名相关算法的描述.

定义1(一次签名)[5]

OTSGen,Sig,Ver为一次签名方案,

算法描述如下:

1.

Gen1k:

密钥生成算法输入安全参数1k,生成公私钥对(PK,SK)并输出.

2.

Sig(m,SK):

签名算法输入消息m和私钥SK,

生成消息m的一次签名,

输出.

3.

Verm,,PK:

验证签名算法输入消息m,

签名和公钥PK,

使用PK验证的是否正确.

一次签名满足完整性[3]和适应性选择消息的不可伪造性[16].

下面给出完整性的形式化描述.

完整性[3]:

对于一对正确的消息签名对m,,

验证签名算法Verm,,PK输出为错误的概率是可忽k略的.

即ProbVerm,,PK0:PK,SKGen1,Sigm,SKnegl.

本文方案的安全性基于一次签名的存在不可伪造性,

下面给出标准一次签名的存在不可伪造游戏[17].

Setup:

挑战者B运行Gen算法,

然后把生成的公钥PK发送给敌手A,

保留私钥SK.

Sign queries:

敌手A只对一系列消息m1,m2,,mq发起签名质询,

对于每个mi,

挑战者B运行Sig生成mi的签名i并将i发送给A.

A可以对任意mi进行调整使得mi依赖于m1,m2,,mi1,

即自适应选择明文攻击.

Output:

敌手A输出一对消息签名对m,.

如果是消息m的合法签名,即可以通过Ver算法的验证,

并且不属于Sign Queries阶段所询问过的消息mi(1iq),

则敌手A获胜.

将敌手A的优势定义为赢得游戏的概率.

定义2(适应性选择消息攻击下是不可伪造性)

对于一个一次签名方案,如果敌手A在可以进行q次适应性选择消息m1,m2,,mq的签名查询的条件下,

能够伪造一个新消息m的签名的概率是可忽略的,

那么称此签名方案在适应性选择消息攻击下是不可伪造的.

2.2

变色龙哈希函数

变色龙哈希函数是非标准的抗碰撞哈希函数,

它包含一对公私钥对,

分别用cpk和csk(陷门信息)表示.

定义2为变色龙哈希函数的相关描述.

定义3(变色龙哈希函数)[11]

变色龙哈希函数可以由概率多项式时间算法组成的元组

610 Journal of Cryptologic Rearch

密码学报 Vol.3, No.6, Dec. 2016

CHchamGen,Ch,Col来表示,

关键算法描述如下:

1.

chamGen1:

密钥生成算法输入安全参数1,

生成公私钥对cpk,csk,

其中csk和cpk与安全参数1多项式相关.

in2.

Chcpk,m,r:

哈希计算算法输入公钥cpk,

消息m0,1和随机数r0,1.

计算哈希值Chcpk,m,r{0,1}out.

3.

Colcsk,m,r,m:

碰撞计算算法输入私钥csk,

消息m,

随机数r和需要匹配碰撞的消息m.

根据rColcsk,m,r,m计算出与m匹配的随机数r,

满足Chcpk,m,rChcpk,m,r,

那么m,r和m,r一对碰撞.

安全的变色龙哈希具有抗碰撞性和语义安全性2个性质[11,17].

抗碰撞性[11,17]:

敌手在不知道陷门信息csk的条件下,

对于给定的m,r和m,

输出随机数r满足Chcpk,m,rChcpk,m,r的概率是可忽略的.

语义安全性[11,17]:

对于任意两条消息m和m,哈希值Chcpk,m,r和Chcpk,m,r的概率分布在计算上是不可区分的.

特别的,

对于随机选择的r,

从Chcpk,m,r无法得到有关m的任何消息.

2.3

动态变色龙认证树

动态变色龙认证树在初始化阶段不需要确定树的规模,

在数据插入的过程中能够自适应地扩展规模,

更适合一次签名数量未知的应用.

keykeykeykeychkeychkey0(1)key0(2)ch1key0ch1(3)h2dkey0ch1(4)h2ch3keykeychkeychhdkey0ch1h2ch3(5)h4d……

图1 动态变色龙认证树结构

Figure 1 The structure of DCAT

王红伟 等:

基于动态变色龙认证树的一次签名方案 611

DCAT结构以及动态扩展的状态如图1所示,

虚线划分出了DCAT

不同规模时的状态,

每个状态下的DCAT结构都能保持一致性. DCAT节点分4种类型:

key为验证根节点,

ch为变色龙节点,

h为普通节点,

d为虚拟节点.

右节点为变色龙节点,

构造过程中根据需要预先生成的变色龙节点为虚拟节点;

左节点为普通节点;

每一个规模下的DCAT根节点为验证根节点. DCAT根节点使用普通哈希函数计算哈希值,

这充分考虑到树结构的扩展,

扩展时需保持结构的一致性.

2.3.1 DCAT形式化定义

定义4(动态变色龙认证树)[14] DCAT可以由概率多项式时间算法所组成的元组来表示,

即DCATdcatGen,dcatInrt,dcatQuery,dcatVerify.

算法的详细描述如下:

1.

dcatGen1:

初始化算法输入安全参数1,

调用变色龙哈希函数的初始化算法生成公私钥cpk,cskchamGen1,

将树的结构信息dcatStruct初始化为空,

回公私钥pk,sk.

dcatStruct中包括树的容量capacity、当前数据总量size及树的深度depth,

设置DCAT的公钥pkcpk,

私钥skcsk,dcatStruct.

最后,

返2.

dcatInrtsk,data:

插入数据算法.

使用私钥sk将数据data插入到DCAT中.

首先,

将私钥sk解析为csk,dcatStruct;

然后检查size是否等于capacity,

若size等于capacity,

当前树已经饱和,

需要将原来树结构作为扩展后的左子树,

原根节点变为新的验证根节点的左孩子;

最后插入数据data.

返回数据的索引i,

认证路径auth,

更新结构信息dcatStruct,

将私钥更新为sk.

3.

dcatQueryi:

查询DCAT中的第i个元素di.

若查询成功,

返回数据di及其对应的认证路径authi;

若查询失败则输出0.

4.

dcatVerifypk,i,data:

首先查询第i个元素,

即dcatQueryidi,authi,验证di与data是否一致,

然后使用pk和authi验证data是否为DCAT中的第i个元素,

即验证根节点值与计算结果是否匹配.

2.3.2 DCAT安全性定义

DCAT的安全性包括结构保持性和单向性两方面.

下面首先给出结构保持性与单向性游戏,

然后分别给出两者的形式化定义.

挑战者生成公私钥对pk,sk,

将公钥pk交给敌手A.

令q:q为敌手所能查询的签名数量的上限.敌手A可以适应性地发送q个数据d1,d2,,dq()给挑战者,

挑战者将q个数据依次插入DCAT中,

返回数据元素所对应的认证路径(证据)auth1,auth2,,authq().

敌手A试图破坏DCAT的结构结构保持性或者单向性,

输出未曾插入到DCAT中的伪造数据及其认证路径.

下面通过挑战者和敌手间的交互游戏对结构保持性和单向性进行描述.

Setup:

挑战者运行dcatGen1来计算私钥sk,

和公钥pk,

然后将公钥pk发送给敌手A.

Running:

敌手A适应性地发送数据di1iq给挑战者,

挑战者运行dcatInrtsk,di将数据插入到DCAT中,

然后运行authidcatQueryi,

将数据及对应的认证路径发送给敌手A.

查询应答序列表示为Q:d1,1,auth1,d2,2,auth2,,dq(),q,authq().

Output:

敌手A获胜分两种情况.

情况1(结构保持性),

敌手A输出数据d*,索引i*和认证路径auth*,

**********即d,i,auth.

若满足1iq,

l,i,authQ并且dcatVerifypk,i,d,auth1,

则敌手A破坏***了DCAT的结构保持性,

敌手A获胜.

情况2(单向性),

敌手A输出d,i,auth,

如果qi并且*

612 Journal of Cryptologic Rearch

密码学报 Vol.3, No.6, Dec. 2016

dcatVerifypk,i*,d*1,

则敌手A破坏了DCAT的单向性,

敌手A获胜.

定义5(结构保持性)

任意多项式时间算法的敌手A试图通过改变叶子节点顺序或者修改替换叶子节点,

输出伪造的数据及其认证路径,

如果敌手A获胜概率是可忽略的,

则认为DCAT具有结构保持性.

定义6(单向性)

任意多项式时间算法的敌手A试图插入新数据到DCAT中,

并输出新数据及其认证路径,

如果敌手A获胜的概率是可忽略的,

则DCAT具有单向性.

3 基于动态变色龙认证树的一次签名方案

基于动态变色龙认证树的一次签名方案(one-time signature scheme bad on dynamic chameleon

authentication tree, OTS-DCAT)的基本设计思想是将多个一次签名的密钥存储在DCAT的叶子节点,

管理用户未知数量的一次签名的公钥,

提高查询和验证一次签名的效率. DCAT具有可扩展性,

能很好地支持未知数量的一次签名查询与验证.

3.1

形式化定义

下面给出方案的形式化定义及其详细描述.

定义7(OTS-DCAT) OTS-DCAT可以由密钥生成算法dGen,

签名算法dSig以及验证算法dVer所构成的元组OTS-DCATdGen,dSig,dVer来表示,

详细描述如下.

1.

dGen1:

密钥生成算法生成DCAT公私钥对pk,skdcatGen1,

返回私钥sk和对应的公钥pk.

2.

dSigsk,m:

签名算法对给定的消息m0,1进行一次签名,

并将一次签名公钥插入到DCAT中.

首先,

一次签名的密钥生成算法生成签名所需密钥对SK,PKGen1,

签名算法对消息m进行一次OTS公钥PK进行签名,

即0Sigm,SK.

然后,

将一次签名公钥PK插入DCAT中,

调用DCAT的插入算法,

即sk,i,authdcatInrtsk,PK,

设置认证路径1i,auth,

其中1用于对第i个验证.

最后,

返回最终的签名为0,1,PK.

3.

dVerm,,pk:

验证算法首先解析消息m的签名,

对m的一次签名及其公钥进行验证.

首先,

解析签名包含消息m的一次签名0,

公钥PK和用于验证PK的1;

然后,

对1进行解析,

包含PK在DCAT中的索引i和PK的认证路径auth,

解析完成.

最后,

运行DCAT的验证算法dcatVerifypk,i,PK验证一次签名公钥PK,

成功输出1,

否则输出0并终止操作;

再运行OTS的验证算法Verm,0,PK,

使用公钥PK验证消息m的签名0.

3.2

安全性定义

定义8(OTS-DCAT安全性)

若OTS-DCAT满足以下性质,

则认为该OTS-DCAT方案是不可伪造的:

1.

敌手不能破坏DCAT的结构保持性.

意味着敌手A试图通过改变叶子节点顺序或者修改替换叶子节点,

输出伪造的数据及其认证路径,

A获胜概率是可忽略的;

2.

敌手不能破坏DCAT的单向性.

敌手A试图插入新数据到DCAT中,

输出新数据及其认证路径,

敌手A获胜的概率是可忽略的;

3.

敌手不能伪造一个正确的一次签名.

即敌手A适应性选择消息的签名查询条件下,

能够伪造一个新消息的签名的概率是可忽略的.

王红伟 等:

基于动态变色龙认证树的一次签名方案 613

3.3

方案详细设计

本小节将给出方案的具体算法设计和方案结构描述.

3.3.1

密钥生成算法

dGen1:

该算法用于方案的初始化,

生成密钥,

需要取足够长,

如128 bit,

这样才能有效阻止蛮力攻击.

算法主要步骤如下:

1.

cpk,cskchamGen1 //生成变色龙哈希函数的公私钥

2.

rootNULL

4. depth0

//设置根节点为空

//设置当前签名总数为0, DCAT的容量为0

//设置DCAT深度为0

//令DCAT的结构为空

//私钥sk包括变色龙哈希函数私钥和DCAT的结构信息

//公钥即变色龙哈希函数的公钥

3. size0,capacity0

5. dcatStructNULL

6.

DBNULL

7.

skcsk,dcatStruct

8.

pkcpk

9. returnpk,sk

3.3.2

签名算法

dSigsk,m:

该算法用于对用户的消息生成签名.

主要步骤如下:

1.

SK,PKGen1

2.

0Sigm,SK

//生成一次签名的公私钥对

//使用一次签名的私钥对消息m生成签名0

//存储数据的数据库为空

//返回公私钥

3.

将一次签名的公钥PK插入到DCAT中

a. ifsizecapacity extendFlag1 //当DCAT饱和时,

需要扩展;

否则从第h步向下执行

b. depthdepth1 //若进行扩展,

树的深度增加1

//从空树扩展容量为1 c. ifcapacity0 capacity1

d. elcapacitycapacity2

e. newRootnewKeyHashNode

f.

ildroot

g.

rootnewRoot

h.

updateNodePK

//容量扩展为原来的2倍

//生成新的验证根节点

//将原来的树结构作为扩展后树的左子树

//将新的根节点作为根节点,

扩展完成

//插入PK到正确的叶子节点位置,

更新认证路径中节点

//若进行了扩展,

对根节点进行数字签名

//将一次签名公钥PK加入到数据库DB中

//设置一次签名总数加1

//更新DCAT结构信息

i. ifextendFlag1 

j.

PK

k. sizesize1

l.

dcatStructcapacity,size,depth

4.

设置认证路径1i,auth

5.

返回最终的签名0,1,PK

3.3.3

验证签名算法

dVerm,,pk:

用户使用公钥验证消息的签名是否合法.

主要步骤如下:

614 Journal of Cryptologic Rearch

密码学报 Vol.3, No.6, Dec. 2016

1.

解析签名为0,1,PK

2.

将1解析为i,auth

3.

用i,auth验证一次签名公钥PK

a.

if.verify1 //验证认证路径auth中的验证根节点的数字签名

b.

iftIndexi1&&tRootHash //判断推算出的元素位置tIndex是

否正确,

同时验证计算出来的根节点哈希值tRootHash,

与认证路径中的根节点哈希值是否匹配

c.

return1orreturn0

4.

用PK验证消息m的签名0

3.3.4 OTS-DCAT结构

//验证成功,

返回1;

验证失败,

返回0

OTS-DCAT的结构示意图如图2所示.

其中,

验证根节点为Hi,

将验证根节点的值存储在可信的公共存储库中,

用于验证一次签名公钥的真实性.

叶子节点为一次签名公钥YiOTS.

中间节点为一些辅助验证的节点,

并通过对孩子节点计算哈希得到父节点的值.

这些中间节点又包括两种,

其中使用变色龙哈希函数CH计算哈希值的节点称为变色龙节点CHi;

使用普通抗碰撞哈希函数H计算哈希值的节点称为普通节点Hi,

验证根节点Hi为普通节点的一种.

H4H3CH47H2CH23H45CH67H1CH1H2CH3H4CH5H6CH7Y0OTSY1OTSY2OTSY3OTSY4OTSY5OTSY6OTSY7OTS

图2

OTS-DCAT结构

Figure 2 The structure of OTS-DCAT

由于DCAT的结构可扩展,

树的结构会根据一次签名数量逐渐扩展,

level表示树的层次,

2level1为树所能容纳的最大签名数量.

若当前树的规模小于一次签名公钥数量时,

需扩展树的规模,

扩展规模即为树的深度D增1,

同时所能容纳的叶子节点数量扩展一倍.

初始level为0,

当向树中插入第一个OTS公钥Y0OTS时level增1,

插入第2个OTS公钥Y1OTS时扩展规模level增至2,

当插入Y2OTS时继续扩展至level为

王红伟 等:

基于动态变色龙认证树的一次签名方案 615

3,

当插入Y4OTS时扩展至level为4,

以此类推.

对于给定的层次level,

最多可对2level1条消息进行签名,

即DCAT叶子节点最多能插入2level1数量的一次签名密钥.

图3中共包含8个一次签名验证密钥Y0OTS,,Y7OTS,

因此可对8条消息进行签名.

OTSOTS根据节点类型,

选择不同的哈希函数计算哈希值,

即H1HY0,

CH1Chcsk,Y1,r1,

H4HH3||CH47;

若要插入Y4OTS,

首先为当前不存在的变色龙节点CH67生成两个随机数v67和r67,

然后计算哈希值CH67Chcsk,v67,r67;

若继续插入Y6OTS时,

同理生成随机数计算出CH7,

对CH67计算碰撞r67Colcsk,v67,r67,H6||CH7.

认证路径包括从叶子到验证根节点的路径上所有节点的兄弟节点以及路径上变色龙节点的随机数.

认证路径与一次签名、一次签名公钥、叶子节点的索引一同发送给用户,

用于用户对签名进行验证.

当i1时,

验证根节点Hi可验证2i12i2个叶子节点,

例如H4验证Y4OTS,Y5OTS,Y6OTS,Y7OTS这4个节点.

4 安全性分析

定理1(OTS-DCAT安全性)

如果OTS是存在不可伪造的一次签名方案, DCAT是一个满足结构保持性和单向性的动态变色龙认证树,

那么OTS-DCAT的构造在适应性选择明文攻击下是不可伪造的.

证明思路:

任意敌手最多向签名预言机发出q次质询,

之后敌手尝试对新消息m*输出有效签名***0,1*,PK*.

1*用于验证一次签名公钥PK*是否为DCAT中的叶子节点,

PK*用于验证0是否为消息m*的有效签名.

敌手猜测PK*的索引是否大于q:

*1.

如果索引小于等于q,

敌手对方案的攻击仍有2种情况: (1)

i1,,q且PK*PKi; (2)对任意的i*1,,q都有PK*PKi.

其中,

若PK*PKi,

意味着敌手伪造出了有效的一次签名,

若PK*PKi,

意味着PK*能够通过认证,

PK*的认证路径与DCAT已有的任何一条认证路径都不相同,

敌手破坏了DCAT的结构保持性.

2.

如果索引大于q,

即i*q1,

敌手破坏了DCAT的单向性.

证明:

反证法.

如果定义7中构造的OTS-DCAT是不安全的.

那么存在一个概率多项式时间敌手A向****签名预言机最多请求q:q次消息的签名.

A对新的消息m*尝试输出合法的签名0,1,PK,

该签名*不同于请求得到的任何一个签名.

下面需根据1中的索引划分敌手类型,

若1i*q即为敌手A,

反之i*q1即为敌手A.

*根据返回的伪造结果对敌手A进一步区分: (1)

i1,,q且PKPKi,

敌手的类型为ASig; (2)

*i1,,q且PK*PKi,

敌手类型为ADCAT.

下面对如何构造一个有效的敌手A使用AOTS破坏一次签名方案或者使用ADCAT来破坏DCAT的结构保持性进行分析.

多项式时间的模拟器B随机猜测敌手类型(ADCAT或AOTS).

1.

一次签名方案攻击:

B获取一个一次签名公钥PK,

然后访问签名预言机并均匀随机地猜测出一个*索引i1,,q.

B运行初始化算法sk,pkdcatGen1初始化DCAT的密钥.

B模拟ASig的运行,

ASig输入pk.

当ASig向签名预言机质询消息mi的签名时,

B对ii*的质询作如下回应:

首先计算新的一次签名密钥对PKi,SKiGen1i,

在本地对消息mi进行签名0SigSKi,mi,

然后运行

616 Journal of Cryptologic Rearch

密码学报 Vol.3, No.6, Dec. 2016

sk,i,authdcatInrtsk,PKi将一次签名的公钥PKi插入到DCAT中,

置认证路径1ii,auth,

返回ii最终的签名i0,1,PKi.

对于ii*的情况,

B向签名预言机质询消息mi的签名,

得到mi的签名i*,

运行sk,i,authdcatInrtsk,PK将一次签名公钥PK插入到DCAT中,

设置认证路径0*ii1ii,auth,

返回签名i0,1,PK.

最终,

ASig停止运行,

输出一个伪造的签名m*,*,

其中*****0,1*,PK*.

若PK*PK,

B输出m*,0;

否则,

B退出.

以上过程,

若ASig以不可忽略的概率1输出一个伪造的签名,

满足存在一个索引i使PK*PK.

那么B正确猜出索引i的概率为1q,

那么B成功的概率11q也是不可忽略的,

那么根据定义2可知B破坏了一次签名的不可伪造性.

2.

结构保持性攻击:

首先,

B随机生成q个一次签名密钥对PKi,SKiGen1,输出PK1,,PKq.

然后,

B获得DCAT公钥pk和q个一次签名公钥的认证路径i,authii1.

B初始化计数器c0,

模拟运行ADCAT,

pk作为输入.

当敌手ADCAT质询某个消息mc的签名时,

B设置c的值,

对消息进行签名q0SigSKc,m并返回签名0,1,PKc,

其中1c,authc.

最终,

ADCAT输出m*,*,

其中***0,1*,PK*,

1*i*,auth*.

如果1i*q且PKPKi*,

那么B输出PK*,1*,

否则B退出.

***当ADCAT成功,

那么ADCAT返回合法的m,满足1i*q且任意i1,,q,PKPKi.

假设ADCAT以不可忽略的概率2获胜,

那么B获胜概率与ADCAT一样,

即22,

那么根据定义5可知,

B破坏了DCAT的结构保持性.

3.

单向性攻击:

假设B能够访问敌手A,

A能输出满足q1i*的伪造的m*,*.

B破坏单向性的过程如下:

首先,

B随机生成q对一次签名的密钥PKi,SKiGen(1)并输出PK1,,PKq.

然后,

B获得公钥pk和q个一次签名公钥的认证路径i,authii1.

B初始化计数器c0,

模拟运行A,

pk为输入.

如果A质询消息mi的签名i,

那么B置0SigSKi,mi,

设置c的值,

返回签名qi0,1,PKc,

其中1c,authc.

最终,

A尝试输出一个合法的伪造m*,*,

其中签名为**0,1*,PK*,

认证路径为1*i*,auth*.

若q1i*,

B输出PK*,1*;

否则B退出.

由于B为概率多项式时间的模拟器,

A是有效的.

由于B模拟运行了A,

因此当A获胜的时候B获胜,

用0表示获胜概率,

根据定义6可知若0是不可忽略的,

那么B破坏了DCAT的单向性.

根据证明思路中对敌手类型的区分,

可以知道B获胜的概率包括2方面PPP2,

其中PPsig+PDCAT1+2,P0.B总体获胜的概率为

Pwin21

01201222q2由上述证明可知,

0、1和2都是不可忽略的,

因此Pwin是不可忽略的,

那么B获胜的概率是不可忽略的,

然而这与假设中一次签名是不可伪造的或者与DCAT的结构保持性或单向性相矛盾.

因此,

OTS-DCAT的构造在适应性选择明文攻击下是不可伪造的.

王红伟 等:

基于动态变色龙认证树的一次签名方案 617

5 代价分析与比较

将本方案OTS-DCAT与文献[12]中的方案进行开销比较,

比较结果如表1所示.

表1 与已有方案的开销对比

Table 1 Overhead comparison with previous solution

对比项

支持的签名数量

密钥生成时间

签名大小

签名时间

验证时间

tGen2D

2trtch

文献[12] OTS-DCAT

无上限

tGen

lOTSlevellhlch2

lOTSDlhlch2

toKgtColOD

Dthtch2toVf

toKgtColOlevel

levelthtch2toVf

表1中的符号说明如下:

tGen为变色龙哈希函数密钥生成时间;

tr为随机数生成时间;

tch为变色龙哈希计算时间;

tCol为碰撞计算时间;

toKg为一次签名密钥生成时间;

toVf为一次签名验证时间;

D为MTS-CAT中初始化的深度;

level为OTS-DCAT中满足当前一次签名数量的最小规模;

lOTS为一次签名长度;

lh为普通抗碰撞哈希输出的长度;

lch为变色龙哈希函数输出的长度.

整体来看, OTS-DCAT可以根据实际需要动态扩展树的规模,

能支持无上限的一次签名数量,

优于文献[12]中支持签名数量为2D的方案.

其次,

初始化OTS-DCAT时不需要预先构造深度为D的树结构,

节省初始化阶段的计算开销,

更灵活实用.

此外,

签名由一次签名、一次签名公钥和一次签名密钥在树结构中的认证路径组成,

在树的规模相同的情况下, OTS-DCAT能大大缩短平均的认证路径,

也意味着签名与验证操作更加高效.

(1)

密钥生成: OTS-DCAT的密钥生成算法只生成变色龙哈希的密钥对,

不用初始化树的深度D,

不需随机生成根节点值及其随机数,

不需预先计算验证根节点值,

在密钥生成阶段更高效.

(2)

签名与验证开销:

签名与验证阶段的开销与当前已有元素个数2level相关,

2level远远小于上限2D.

虽然平均来看, OTS-DCAT与文献[12]方案签名操作开销相当,

但OTS-DCAT更稳定.

6 结束语

本文分析了一次签名方案存在的问题,

现有的方案最多支持指数级的一次签名数量,

密钥生成阶段开销较大,

不能根据需求动态地生成,

签名与验证的效率不高.

因而,

本文将动态变色龙认证树与一次签名相结合,

提出了一种基于动态变色龙认证树的一次签名方案,

并对方案的安全性进行分析,

最后从效率方面与已有方案进行对比,

具有密钥生成阶段开销小、签名和验证阶段的计算复杂度低等优点.

References

[1] KATTI R S, SULE R, KAVASSERI R G. Multicast authentication in the smart grid with one-time signatures from

sigma-protocols[J]. Proceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems. ACM, 2013:

239–239.

[2] QINGHUA L, GUOHONG C. Multicast authentication in the smart grid with one-time signature[J]. IEEE Transactions on

Smart Grid. 2011, 2(4): 686–696.

[3] ZHANG J W, MA J F, WEN X Z. Universally composable one-time signature and broadcast authentication[J]. Science China:

Information Science, 2010, 40(2): 272–284.

张俊伟, 马建峰, 文相在. 通用可组合的一次签名和广播认证[J]. 中国科学: 信息科学, 2010, 40(2): 272–284.

[4] GROZA B, MURVAY S. Secure broadcast with one-time signatures in controller area networks[C]. In: Proceedings of the

2011 Sixth International Conference on Availability, Reliability and Security (ARES). IEEE, 2011: 371–376.

618 Journal of Cryptologic Rearch

密码学报 Vol.3, No.6, Dec. 2016

[5] LAMPORT L. Constructing digital signatures from a one-way function[R]. Technical Report, Technical Report CSL-98, SRI

International, 1979.

[6] KALACH K, SAFAVI-NAINI R. An efficient post-quantum one-time signature scheme[C]. In: International Conference on

Selected Areas in Cryptography. Springer International Publishing, 2015: 331–351.

[7] ABE M, DAVID B, KOHLWEISS M, et al. Tagged one-time signatures: Tight curity and optimal tag size[C]. In:

International Workshop on Public Key Cryptography. Springer Berlin Heidelberg, 2013: 312–331.

[8] BUCHMANN J, DAHMEN E, ERETH S, et al. On the curity of the Winternitz one-time signature scheme[C]. In:

International Conference on Cryptology in Africa. Springer Berlin Heidelberg, 2011: 363–378.

[9] MERKLE R. A digital signature bad on a conventional encryption function[C]. In: Advances in Cryptology— CRYPTO

1987: Springer Berlin Heidelberg. 1988: 369–378.

[10] SHOUFAN A, HUBER N, MOLTER H G. A novel cryptoprocessor architecture for chained Merkle signature scheme[J].

Microprocessors and Microsystems, 2011, 35(1): 34–47.

[11] KRAWCZYK H, RABIN T. Chameleon hashing and signatures[J]. IACR Cryptology ePrint Archive, 1998, 1998: 10.

[12] SCHROEDER D, SCHROEDER H. Verifiable data streaming[C]. In: Proceedings of the 2012 ACM Conference on

Computer and Communications Security. ACM, 2012: 953–964.

[13] SCHÖDER D, SIMKIN M. Boosting verifiable data streaming[C]. In: Grande Region Security & Reliability Day. ACM,

2013.

[14] CHEN K. Rearch and application of verifiable data streaming bad on dynamic chameleon authentication tree[D].

Shenyang: Northeastern University, 2014.

陈科. 基于动态变色龙认证树的流式数据完整性验证研究与应用[D]. 沈阳: 东北大学, 2014.

[15] SCHÖDER D, SIMKIN M. VeriStream—a framework for verifiable data streaming[C]. In: International Conference on

Financial Cryptography and Data Security. Springer Berlin Heidelberg, 2015: 548–566.

[16] HE D Y. On the strongly unforgeable digital signatures in the standard model[D]. East China Normal University, 2009.

何定彦. 标准模型下强不可伪造数字签名研究[D]. 华东师范大学, 2009.

[17] CHEN X, ZHANG F, KIM K. Chameleon hashing without key exposure[C]. In: International Conference on Information

Security. Springer Berlin Heidelberg, 2004: 87–98.

作者信息

王红伟(1992–), 河北唐山人, 硕士. 主要研究领域为信息安全.

E-mail: 1499298276@

徐剑(1978–), 辽宁沈阳人, 副教授.

主要研究领域为密码学与网络安全,

云计算安全及大数据隐私保护.

E-mail: xuj@

倪盼(1990–), 辽宁沈阳人, 博士生. 主要研究领域为加密数据的分析分类.

E-mail: 1510414@

周福才(1964–), 吉林长春人, 教授,博士生导师. 主要研究领域为网络与信息安全, 可信计算.

E-mail: fczhou@