基于强变色龙Hash函数的紧致安全签名通用构造

李 飞 高 伟 王贵林 谢冬青 唐春明

1(鲁东大学数学与统计科学学院 山东烟台 264025) 2(广东省信息安全技术重点实验室(广州大学) 广州 510006) 3(华为新加坡研究所谢尔德实验室 新加坡 117674) (miss＿lifei@163．com)

2017-06-10；

2017-07-28

国家自然科学基金项目(61202475)；广东省信息安全技术重点实验室开放课题(GDXXAQ2016-02)；山东省统计科研重点课题(KT16022)；鲁东大学博士人才科研基金项目(2017) This work was supported by the National Natural Science Foundation of China (61202475), the Open Project of Guangdong Provincial Key Laboratory of Information Security Technology (GDXXAQ2016-02), the Shandong Provincial Statistics Key Project (KT16022), and the Ludong University Research Foundation for Doctoral Talents (2017).

基于强变色龙Hash函数的紧致安全签名通用构造

李 飞1,2高 伟1,2王贵林3谢冬青2唐春明2

1(鲁东大学数学与统计科学学院 山东烟台 264025)2(广东省信息安全技术重点实验室(广州大学) 广州 510006)3(华为新加坡研究所谢尔德实验室 新加坡 117674) (miss＿lifei@163．com)

可证明安全性已经成为构造和分析密码方案的一个基本要求.研究可证明安全密码学领域的一个经典问题，即如何在随机预言模型下构造可证明安全的数字签名方案，而且其安全性可紧致地规约为某个基础数学问题的困难性.首先提出一种新密码原型，称作强变色龙Hash函数;然后基于强变色龙Hash函数，给出紧致安全数字签名方案的一般化构造框架及其变形，分别对应带状态和无状态2种情形;接着证明了这2种通用方案的安全性均可规约为底层强变色龙Hash函数的抗碰撞性.利用 RSA,CDH,IF等具体假设下的强变色龙Hash函数，通过所提出的一般化构造技术，可以模块化地构造相应的具体的紧致安全签名方案.2类经典的紧致安全签名方案构造范式，即Fiat-Shamir(FS)类和Full-Domain-Hash(FDH)类，可大致统一在所提出的构造框架中，而且本框架可将FDH类紧致安全签名方案解释为相应FS类紧致签名方案的优化形式.

数字签名；可证明安全；紧致安全性；随机预言模型；变色龙Hash函数；全域Hash签名

在现代密码学中具备可证明安全性[1]是公钥加密[2]、数字签名[3]、密钥交换[4]等公钥密码方案设计的最基本原则之一.紧致安全性则是可证明安全性要求的进一步提升[1].本文力图发展一种新的通用框架，可以基于某种底层困难问题通过模块化方式构造紧致安全的数字签名方案，代替传统的仅能实现松散安全性归约的先Hash后求逆的构造签名框架.进一步地，这个框架所基于的底层困难问题应该是一个非常基础且具有高度概括性的密码原型，最好是能在陷门置换的基础上增加一些最必要的密码学性质，而这些密码学性质恰恰又是使得安全性证明达到紧致要求的必要条件.事实上，这就是本文所提出一种新型密码原型，称作强变色龙Hash函数.本文结合实例作了相关比较及分析，从而说明本文所给出的紧致安全签名的一般性构造框架具有高度概括性，既可导出具体的FDH类[5]紧致安全签名方案，又可导出具体的FS类[6]紧致安全签名方案.特别值得注意是，FDH类签名方案和FS类签名方案，在密码学的相关研究领域中通常被认为是2类相互独立的一般性签名构造框架.本文结果表明，至少在紧致安全签名构造方面，二者是统一的：本文的统一框架下，FDH紧致签名方案基本可以看作是对应的FS类签名方案的优化结果.

本文的主要贡献包括3个方面：

1) 作为理论基础，本文提出了一种新的密码原型，称作强变色龙Hash函数，既可以看作经典变色龙Hash函数概念的推广，又可看作陷门置换的推广，从而兼具这2种重要密码原型的基本密码性质.特别需要指出的是，强变色龙Hash函数的可逆性在传统变色龙Hash函数的相关研究中极少提到，这主要是因为变色龙Hash函数的原有应用环境只是需要该密码原型的抗碰撞性和“变色龙”性质.然而强变色龙Hash函数的可逆性在本文签名方案的构造中起到了不可或缺的基础性作用.

2) 本文提出一种可证明安全签名方案的一般性构造框架，而且安全性归约达到了紧致性要求.这个基础型可证明安全签名框架是带状态的，即要求签名者记录所有签名历史，避免对同一个消息产生2种不同的签名.因此，本文给出了这种一般性签名方案的改进方法，可以非常容易地实现不带状态的紧致安全签名方案.

3) 作为上述一般性签名框架的应用，本文以基于RSA的签名方案为例，给出了3个紧致安全的RSA签名方案，并将这些具体签名方案与现有的FS类和FDH类签名方案进行比较，从而表明以上理论框架可以导出FS类签名方案和FDH类签名方案，其技术水平与直接构造的同类紧致安全签名方案持平.同时，这一理论结果也在某种程度上“否定”了FS类紧致安全签名方案的构造，这是因为在本文的理论框架下，FDH类签名方案可以看作对应FS类数字签名方案的优化结果.

1 研究背景与相关工作

1988年，Goldwasser等人[7]以形式化方式给出了数字签名的经典定义，此定义使用了渐进安全性(asymptotic security)的描述方法：所谓一个安全性证明就是一个归约算法，它调用一个多项式时间复杂度的签名伪造算法构造出一个解决底层困难问题的多项式时间算法，进而由反证法得出安全性证明.渐进安全性证明在理论上讲是很好的，但是其实际应用却存在很大局限.当需要评估一个数字签名方案在给定的具体安全参数和具体攻击资源等条件下的实际安全性时，渐进安全性就不再适用.

受实际应用环境对数字签名安全强度精确化要求的驱动，Bellare和Rogaway[5]在1996年提出了具体安全性(concrete security)的概念，其特点是力图给出伪造签名的困难程度与解决底层数学问题的困难程度之间的精确关系.在具体安全性框架下，可以进一步考虑安全归约的紧致性(tightness).在文献[8]中提到，如果伪造签名的难度与攻击底层数学问题的难度非常接近，则称该归约是紧致的，否则称该归约是松散的.换句话说，对于紧致安全归约来说，签名伪造算法的成功概率和运行时间与解决底层困难问题的成功概率和运行时间可看作是大致相同.通过本文后面所给数字签名方案的安全性归约，可以更加具体地认识和理解安全性归约的“渐进”、“具体”、“紧致”、“松散”等抽象概念的含义.

就数字签名方案的安全性证明是否依赖随机预言假设，可证明安全数字签名方案可分为随机预言模型下安全类和标准模型下安全类.所谓随机预言假设[9]是在密码方案的安全性证明中，把某个密码学意义下Hash函数理想化为一个完全随机函数，也就是假设存在一个各方均可访问的随机预言机，对于每次询问所返回的Hash值都是完全随机的，而且同一个数值的Hash值总是相同的.通常认为，Hash函数仅有抗碰撞性，随机预言模型假设该函数具有完全随机性，而函数的随机性是密码学对函数性质的最高要求，可见随机预言假设是一个非常强的假设.因此，在可证明安全密码学研究领域，有一派研究是致力于标准安全密码方案的构造.目前，人们已经构造了不少标准模型下安全的数字签名方案，例如文献[10-13]所给出的签名方案.与随机预言模型下安全的数字签名方案相比，这些标准安全的数字签名方案往往效率较低，实际应用中受到很大限制.本文主要考虑随机预言模型下安全数字签名的构造问题，重点关注这些签名方案安全性归约的紧致性.随机预言模型下安全的数字签名方案基本分为2类:

1) FDH类，即全域Hash类签名方案基本都是按照以下框架构造的.令f是一个陷门置换函数，其陷门(即函数f的逆变换)记作f-1.令RO是一个随机预言机，可将定义域{0,1}*的值映射到函数f的值域中的一个随机值.对于全域Hash签名方案[5,9]，消息m的签名形式为σ=f-1(RO(m))，其签名验证是看等式f(σ)=RO(m)是否成立.令(ε,t)分别是伪造签名算法的成功概率和运行时间，而(ε′,t′)分别是解决底层困难问题的算法的成功概率和运行时间，这里解决底层问题的算法即是安全性证明的归约算法，是调用签名伪造算法作子函数来构造的.对于一个可证明安全数字签名方案及其安全归约来说，所谓归约(或者说安全性)紧致通常是指ε≈c1ε′,t≈c2t′,其中c1,c2均是较小常数.所谓归约松散，往往是指这些系数是归约算法中某些参数的函数，如系数是敌手访问随机预言机次数的二次多项式.系数c1,c2有时称作(概率、时间)紧致系数.

当陷门置换函数f是RSA函数时，即f(x)=xemodn，得到了具体的FDH签名方案，记作RSA-FDH.对于RSA-FDH，Bellare和Rogway[5]在 1996年分析了具体安全性，但是所给出归约非常松散，即t≈t′,ε≈(qs+qh)ε′,此处，qs和qh分别表示在定义安全性的游戏过程中敌手所作签名询问次数和随机预言机询问次数.2000年，Coron[14]给出了更加紧致的安全性归约(也就是更加紧致的安全性证明)，所给出的概率关系式为t≈t′,ε≈qsε′,即系数中不再含有随机预言机访问次数qh.其安全性归约的紧致性得以提升的关键是利用了RSA函数的随机自归约性质(random self-reducibility)[15].为了进一步提升归约紧致性，即去掉上式系数中的qs，Bellare和Rogway[5]提出RSA-FDH签名方案的一种改进形式，称作PSS，并指出其安全性归约是紧致的，即ε≈ε′.文献[5]的核心思想是对签名过程进行随机化，即在签名中引入一个随机因子r.在2002年，Coron[16]作了进一步分析，在保证归约紧致性基本不变的情况下，可以进一步优化随机因子r的长度.2002年，Dodis和Reyzin[15]对以上结果进行了系统的理论化整理，所依赖的基本密码原型为无爪置换(claw-free permutations)：

① 如果作为构建模块的陷门置换函数f仅仅是一个黑盒形式的陷门置换，即仅考虑函数的陷门性质，不考虑其他具体的特殊性质，如文献[14-15]所提到的RSA函数的随机自归约性，那么相应的FDH签名所能达到的归约紧致性只能是ε≈(qs+qh)ε′.

② 如果陷门函数f可以看作是无爪置换所诱导的，那么FDH签名的归约紧致性可以进一步优化为ε≈qsε′.

③ 在陷门函数f由无爪置换诱导，且签名中引入随机因子r的情况下，随机化后的FDH签名的归约紧致性可以再进一步优化为ε≈ε′，此时的签名形式为σ=(f-1(RO(m,r)),r).

2003年，Katz和Wang[17]改进了FDH类签名方案，其改进后的签名形式为σ=(f-1(RO(m,b)),b)，其归约紧致性基本达到最优，即ε≈ε′，而随机因子b只需 1比特.其代价是：所给的基础签名方案是带状态的，即需要签名者记录所有已经签过的消息及签名，以免对同一个消息产生2个不同的签名.同时，他们还给出了一般性转换方法，可以将此带状态的签名方案转换为不带状态形式.

借鉴以上基于陷门置换构造FDH类签名方案的思想及实现紧致安全性的技术框架，基于BLS短签名[18]，同样可以构造出相应的变形方案且实现紧致安全性[17].值得注意的是BLS签名及其紧致安全的变形方案所依赖的底层困难问题是CDH假设，这并不是陷门置换.如何给出一个比陷门置换更具概括性的密码原型，并进一步扩展类似于随机自归约的性质，并分析这些性质与紧致归约之间的理论联系是紧致安全签名方案构造理论的一个重要方面，也是本文的一个理论性目标.

2) FS类签名方案开始于Fiat和Shamir[6]，可以看作是与FDH类签名并列的另外一种签名构造框架.FS类签名包括了基于离散对数的签名方案，而离散对数问题并不存在陷门.前面介绍的FDH类签名所依托的困难问题则必须有陷门.下面首先给出FS类签名的一般性构造框架.

一个经典身份认证方案由3个操作过程构成：

步骤1. 证明方发送承诺值Y给验证方，通常Y的计算需要用到保密的随机串y;

步骤2. 验证方发送随机选取的一个足够长度的挑战值c给验证方;

步骤3. 证明方利用其私钥及之前的内部随机信息y计算并发送一个应答值z给验证方，验证方检验对话副本(Y,c,z)是否合法.

1999年，Micali和Reyzi[8]提出了一种称作SWAP的通用型转化框架，可以模块化地构造具有紧致安全性的FS类签名方案.SWAP转换框架与以上Fiat-Shamir转换框架在形式上类似，可看作Fiat-Shamir转换的变形，因此也将其归为FS类签名.SWAP转换框架对于底层的典型身份认证方案提出了特殊要求：证明方在不需要知晓y(计算承诺时所选择的随机秘密值)的条件下，可以直接由承诺Y和挑战c计算出应答值z.在SWAP转换框架中，签名形式为(c,z).若(Y,c,z)是合法的协议副本，则(c,z)就是合法签名，此处Y=H(c,m)，H是密码学意义下的Hash函数(在安全性证明中需理想化为随机预言机).Micali和Reyzin[8]利用SWAP转换构造了一种基于整数分解难题的签名方案，其安全性归约关系为ε≈ε′，其中ε′表示归约算法解决整数分解问题的成功概率.

2016年，Abdalla等人[22]提出了所谓的损耗性身份认证方案，并证明了针对这类损耗性身份认证方案应用Fiat-Shamir转换，可以得到紧致安全的数字签名方案.分别基于理想格上的最短向量问题、c确定型离散对数问题(c-decisional discrete logarithm)和子集和问题(subset sum)等数学难题，Abdalla等人给出3种具体的损耗性身份认证方案[22]及对应的紧致安全签名方案.大致来说，在一个损耗性身份认证方案中，证明方的公钥可以采用2种不可区分形式中的任何一种，分别称为正常型(normal)和损耗型(lossy).对于文献[22]所给出的数字签名方案来说，安全性归约的关系式表示为ε≈ε′，此处ε′是敌手成功攻破损耗性身份认证方案的密钥不可区分性质的概率，ε仍然是伪造签名算法的成功概率，可见此类签名方案也达到了紧致安全性.值得注意的是，一般来说，损耗性身份认证方案的密钥不可区分性质往往与确定性(decisional)困难问题相关.从这类签名所依赖的具体困难问题来看，其应用范围具有很大限制性.

2016年Bellare等人[23]研究了由身份认证方案到紧致安全签名的一般化构造框架，这是FS转换框架的改进模式.Bellare等人首先给出了身份认证方案的安全性定义框架，而这一框架又细分出4种具体形式，然后给出了3种FS类转换框架并分析、比较了这些框架的相关指标.需要指出的是身份认证方案并不是最底层的密码方案，其安全性定义及安全性分析是非常复杂的.从密码学理论角度看，把紧致安全签名方案的构造归为某类更加简练的密码原型的构造(例如作为一种底层构造模块，本文给出的强变色龙Hash函数就比身份认证方案更为简练)是需要进一步研究的理论课题.

另外，Goh和Jarecki在2003年提出了一种基于CDH困难问题的FS类签名方案[24]，之后针对该方案又作了进一步的改进[25].这2个FS类签名方案的安全性归约均基本达到了最优紧致性，即ε≈ε′，此处ε′是归约算法解决CDH困难问题的成功概率，而ε仍然是伪造签名算法的成功概率.在文献[17]中，Katz和Wang还提出了一种基于DDH困难问题 (decisional Diffie-Hellman)的FS类签名，其安全性可紧致地归约为DDH问题的困难性，在签名长度和计算效率方面均优于文献[24-25]所给的基于CDH困难问题的FS类签名方案.

2 预备知识

本节介绍数字签名语法定义及安全性定义[5,7].

定义1. 一个数字签名方案

DS=(S.Gen,S.Sign,S.Vrf)

由3个概率多项式时间算法组成：

1) (pk,sk)←S.Gen(1λ).这是密钥生成算法.输入安全参数 1λ，输出公钥pk和私钥sk.

2)σ←S.Sign(sk,m).这是数字签名生成算法.输入待签名消息m和私钥sk，输出签名σ.

3)b←S.Vrf(pk,m,σ).这是数字签名验证算法.输入消息m、签名σ和公钥pk，输出一个比特b，表示σ是否合法.

定义2. 称一个数字签名方案在选择消息攻击下是(t,ε) 不可伪造的，如果对于任何的运行时间不超过t的伪造者A，下述概率不等式总成立：

Pr[S.Vrf(pk,m*,σ*)=1∧m*∉S*|

(sk,pk)←RS.Gen(1k);

(σ*,m*)←RAOS ign()(pk)]<ε,

此处S*表示伪造者已经索得签名的所有消息集合，即不存在伪造算法满足运行时间小于等于t，成功概率大于等于ε.

3 强变色龙Hash函数

本节提出强变色龙Hash函数的定义，并给出3个具体方案.

3.1强变色龙Hash函数定义

定义3. 一个强变色龙Hash函数(族):

SCH=(H.Gen,H.Hash,H.Ivt)

由3个概率多项式时间算法组成：

1) (hk,itd)←H.Gen(1λ).该算法为密钥生成算法，其输入为安全参数λ，其输出是Hash密钥hk和求逆陷门itd.Hash密钥hk决定了消息集合S、随机种子集合R和Hash值集合H.每个Hash密钥都确定了变色龙Hash函数(族)中的一个具体变色龙Hash函数.在不产生歧义的情况下，一个Hash函数可以指一个Hash函数族，也可以指一个具体的Hash函数.

2) (h,r)←H.Hash(hk,s).该算法为强变色龙Hash函数的Hash算法.对于待Hash消息s∈RS及Hash密钥hk，选择一个随机数r∈RR，然后计算Hash值h←Hashh k(s,r)∈H，最后返回Hash值及随机种子(h,r).此处，明确区分了随机化算法H.Hash(hk,s)和确定算法Hashh k(s,r).二者本质上没有区别，只是为了相关叙述的方便.

3)r←H.Ivt(hk,itd,h,s).此算法称作强变色龙Hash函数的求逆算法.对于给定的Hash值h和被Hash消息s，该算法计算随机种子r∈RR使得h=Hashh k(s,r).该算法的存在性正是强变色龙Hash函数的“强变色性”的形式化描述.也就是说，借助陷门itd，该算法能够提供相应的随机值r，从而可以将任意Hash值h解读为任意消息s的Hash值，特别是此时不需要知道h的另外原象.

抗碰撞性：称强变色龙Hash函数(族)是抗碰撞的，如果对于任何运行时间不超过的概率多项式时间敌手A，下面过程的成功概率总满足：

即不存在碰撞算法满足运行时间小于等于t，成功概率大于等于ε.

为了更好地理解这一新概念,对于上述形式化定义,下面分析强变色龙Hash函数与其他相关密码学概念之间的关系.

1) 强变色龙Hash函数和传统变色龙Hash函数[26]二者之间的关系.对于强变色龙Hash函数来说，其陷门可以用来对任意的Hash值h，求出原象对(s′,r′)；而对于传统变色龙Hash函数来说，其陷门可以用来对任意的原象对(s,r)，求出第二原象对(s′,r′).换句话说，用强变色龙Hash函数的陷门可以任意求逆(从多个符合条件的原象中，选择一个)，而传统变色龙Hash函数，其陷门可以计算碰撞.通常，求逆算法必定可以平凡地导出求碰撞算法，反之则不然.因此，以上定义称为强变色龙Hash函数.需要特别指出的是，有些具体的变色龙Hash函数本身也是强变色龙Hash函数，但是当时应用环境并未牵涉到“强”变色性，因此并未明确提出该性质.

2) 作为一种底层的密码原型概念，强变色龙Hash函数可以看作陷门单向函数概念的拓展.事实上，在函数Hashh k(s,r)和H.Ivt(hk,itd,h,s)中固定变量s，将会自然诱导出一个陷门单向函数f及其逆函数g:

fh k,s(r)=Hashh k(s,r)，r∈R，

gh k,s,itd(h)=H.Ivt(hk,itd,h,s)，h∈H.

3) 作为一种基础密码原型，强变色龙Hash函数可以看作无爪置换(claw-free permutations)[15]的一种扩展.事实上，对于函数Hashh k(s,r)，分别给变量s不同的赋值s=s0,s=s1，将会自然诱导出相应的一对函数:

fh k,s0(r)=Hashh k(s0,r)，r∈R，

fh k,s1(r)=Hashh k(s1,r)，r∈R.

对于上述函数对，根据抗碰撞性质，计算r0,r1使得fh k,s0(r0)=fh k,s1(r1) 在计算上是不可行的.从而,{(fi:R→H,gi:R→H)|fi(r)=fh k,s0(r),fi(r)=fh k,s1(r),r∈R}构成了一个无爪置换族[15].简言之，无爪置换族是强变色龙族Hash函数的简化形式.特别地，当s的取值集合S只有2个元素，自然得出无爪置换族.

3.2强变色龙Hash函数的具体方案

本节给出强变色龙Hash函数的3个具体构造，分别基于CDH,RSA和IF等常见困难问题.通过这些具体构造，容易得出初步结论：

1) 从刻划密码学概念的角度来讲，强变色龙Hash函数是对传统变色龙Hash函数的加强，而且强化后的性质将在后续签名方案构造中发挥重要作用.

2) 从方案构造角度来说，以往的某些变色龙Hash函数本身具有“强变色”的性质，只是由于缺乏该性质的应用背景驱动，而没有提出“强变色”性质的抽象概念.

本节只是给出函数的方案描述，各相关性质易于验证，其证明不作赘述.

3.2.1SCH-CDH: 基于双线性对的强变色龙Hash函数构造

根据文献[27]中基于双线性对的无密钥泄漏变色龙Hash函数，容易得出强变色龙Hash函数：

1)H.Gen(1λ).选取2个乘法群G,GT及相关双线性对e:G×G→GT，随机选择α,β←Rq，并计算其中G=〈g〉，|G|=q，q是素数.令Hash密钥和求逆陷门为

hk=(g,gα,gβ)，

itd=α.

2)H.Hash(hk,s).对于给定的Hash密钥hk=(g,gα,gβ)，待Hash消息s∈q，随机选择γ←Rq，并计算r=(gαγ,gγ)，然后计算Hash值:

h=Hashg,gα,gβ(s,r)=(gβ)sgγ.

之后返回Hash值h及随机信息r=(gα γ,gγ).只有当h=(gβ)sgγ和e(g,r′)=e(r″,gα)(此式用于保证的确存在γ使得r=(r′,r″)=(gαγ,gγ))同时成立时，才认为h为s的Hash值.

3)H.Ivt(hk,itd,h,s).对于给定的Hash值h和被Hash消息s，计算：

r″=h(gβ)-s,

r′=r″α.

最后输出r=(r′,r″).输出值的正确性为

Hashg,gα,gβ(s,r)=(gβ)sgγ=(gβ)sh(gβ)-s=h，
e(g,r′)=e(r″,gα).

3.2.2SCH-RSA: 基于RSA困难问题的强变色龙Hash函数构造

根据文献[28]中基于RSA的无密钥泄漏变色龙Hash函数，容易得出强变色龙Hash函数：

1)H.Gen(1λ).根据输入的安全参数λ，选择同样长度的不同素数p,q，并计算n=pq;然后，选择足够大的素数e>l，此处参数l保证e足够大;接着计算d，使得ed=1 mod (p-1)(q-1);最后，随机选择x←Rq，并计算求逆陷门和Hash密钥:

itd=d,

hk=(n,e,xe).

2)H.Hash(hk,s).给定Hash密钥hk和被Hash消息s∈e，该算法选择r←R*n，计算Hash值为

h=Hashh k(s,r)=(xe)sremodn.

之后，返回Hash值及随机信息(h,r).

3)H.Ivt(hk,itd,h,s).对于给定的Hash值h和被Hash消息s，利用陷门信息itd=d，计算随机种子：

r=(h(xe)-s)dmodn.

该输出值的正确性为

Hashh k(s,r)=(xe)sremodn=

(xe)s(h(xe)-s)d emodn=hmodn.

3.2.3SCH-IF: 基于整数分解难题的强变色龙Hash函数构造

根据文献[29]中基于IF的无密钥泄漏变色龙Hash函数，容易得出强变色龙Hash函数：

1)H.Gen(1λ).首先随机选择同样长度的不同素数p,q，使得p,q=3 mod 4，计算n=pq，确定一个辅助的整数型参数τ.如此形式的RSA模n通常称作Blum-Williams整数或Blum整数[1,23].随机选择x∈QRn，令Hash密钥hk和求逆陷门itd分别为

hk=(n,τ,x2τ),itd=(p,q).

2)H.Hash(hk,s).给定待Hash消息s∈R2τ和Hash密钥hk，随机选择r←R*n，然后计算Hash值：

h=Hashh k(s,r)=(x2τ)sr2τmodn.

之后，输出Hash值h及随机信息r.

3)H.Ivt(hk,itd,h,s).对于Hash值h和被Hash消息s，该算法利用陷门信息itd=(p,q)，计算与之对应的随机信息：

r=(h×(x2τ)-s)modn.

该输出值的正确性为

Hashh k(s,r)=(x2τ)sr2τmodn=

(x2τ)s(h(x2τ)-s)modn=hmodn.

4 带状态的紧致安全签名方案

本节提出由强变色龙Hash函数构造紧致安全签名方案的2种一般性框架，分别对应带状态和不带状态2种情形，并在随机预言模型下分析其紧致安全性.

4.1带状态的紧致安全签名方案

给定任意一个强变色龙Hash函数族SCH=(H.Gen,H.Hash,H.Ivt)，可以构造如下带状态的数字签名方案，记作SCH-2-DS0:

1)S.Gen(1λ).首先，运行强变色龙Hash函数的密钥生成算法(hk,itd)←RH.Gen(1λ)，令签名公钥和私钥分别为

pk=hk,

sk=itd.

2)S.Sign(sk,m).对于待签名的消息m∈M，首先检查该消息是否已经签过.如果是，则返回之前的签名;否则，根据签名的公钥pk=hk和私钥sk=itd，计算

h←H1(m),

r←H.Ivt(hk,itd,h,s).

然后返回签名σ←(s,r).同时，记录此次的消息及其签名.注意，每次签名前需要检查之前的签名，且在签名后作记录，就是所谓的带状态性(stateful).简言之，该签名方案就是对消息的普通Hash值进行变色龙Hash函数的求逆.这种数字签名构造框架与最通常的Full-Domain-Hash签名[9,14]非常相似.

3)S.Vrf(pk,m,σ).对于给定的公钥pk=hk，验证σ=(s,r)是否为消息m的合法签名，即验证是否成立:

H1(m)=Hashh k(s,r).

定理1. 如果底层的强变色龙Hash函数SCH=(H.Gen,H.Hash,H.Ivt)是(t′,ε′)抗碰撞的，那么上述签名方案:

SCH-2-DS0=(S.Gen,S.Hash,S.Vrf)

就是(t,ε)存在性不可伪造的，其中:

t′=t+qHash×tHash,

其中，qHash表示敌手访问随机预言机OH1(·)的次数，而tHash表示H.Hash(·)的运行时间.

证明. 证明采用反证法.对于签名方案SCH-2-DS0，假设存在一个存在性伪造算法F，其运行时间为t，其概率为ε，敌手攻击签名方案的具体过程在定义2已经给出.下面构造一个针对底层强变色龙Hash函数SCH的寻找碰撞算法，记作C，其概率为ε′，其运行时间约为t′.算法C模拟签名安全性定义中的挑战者，以子程序形式调用伪造算法F，最后给出一对碰撞.

首先，作为强变色龙Hash函数的攻击者，C从它自己的挑战者处获得Hash密钥hk，令签名公钥为pk=hk，并把该公钥pk及其相关的辅助性公开参数发送给F.C初始化一个计数器f=0，用来跟踪记录在整个游戏期间各方访问随机预言机OH1(·)的次数，对重复消息的Hash函数值(随机预言机返回的值)只计一次.

C按照如下方式来模拟签名预言机.不失一般性，我们假设所有提供给签名预言机OS ign(·)的待签名消息各不相同.为了模拟签名OS ign(m)，C首先访问随机预言机OH1(·)，获得Hash值H1(m)，此处的随机预言机也是由C本身模拟.根据上述对于随机预言机OH1(·)的模拟过程，存在(s,r)使得H1(m)=Hashh k(s,r)，而(s,r)正是由C本身选取.因此，C知晓(s,r)，可直接把消息m的签名定为σ←(s,r)，并将σ作为应答返回给伪造者F.上述模拟与实际的签名算法完全一致.

最后，敌手F返回消息m*及其伪造签名σ*.如S.Vrf(pk,σ*,m*)≠1，C则中断算法执行，宣布失败;如果S.Vrf(pk,σ*,m*)=1，根据方案SCH-2-DS0中S.Vrf的算法描述，可以知道h*=Hashh k(s*,r*)，此处σ*=(s*,r*).根据H1(m*)的随机预言机模拟过程，C知道另外一对碰撞值(s*′,r*′)使得:

Hashh k(s*,r*)=Hashh k(s*′,r*′).

C把(s*′,r*′)和(s*,r*)作为一对碰撞传给他本身的挑战者.如此以来，只要(s*′,r*′)≠(s*,r*)，那么C就攻破了强变色龙Hash函数的抗碰撞性质.

再来分析C的运行时间.C的运行时间包括伪造算法F的运行时间和C模拟签名预言机和随机预言机的时间.其中，一次签名预言机的模拟主要就是一次随机预言机的模拟，而随机预言机的一次模拟就是一次Hash函数Hashh k(s,r)的计算，其运行时间记作tHash.同时，对于C中的一些琐碎的计算不予考虑，如某些结果的记录和查询.因此，C的运行时间为t′=t+qHash×tHash.因此，所构造算法C是一个运行时间为t′、成功概率为ε′的计算碰撞算法，这与变色龙Hash函数的(t′,ε′)抗碰撞性矛盾.

证毕.

4.2不带状态的紧致安全签名方案

基于以上的带状态紧致安全签名方案SCH-2-DS0，作如下修改可以得到一个不带状态的紧致安全签名方案，记作SCH-2-DS1.

在签名算法中，将操作h←H1(m)改为

h←H1(m,s,s′)，

在验证算法S.Vrf(pk,m,σ)中，根据以上密钥生成算法和签名算法中的改动作相应的修改.鉴于这些修改的平凡性，此处不作赘述.

定理2. 如果底层的强变色龙Hash函数

SCH=(H.Gen,H.Hash,H.Ivt)

是(t′,ε′)抗碰撞的，那么上述签名方案

SCH-2-DS1=(S.Gen,S.Hash,S.Vrf)

就是(t,ε)存在性不可伪造的，其中:

t′=t+qHash×tHash,

其中，qHash表示敌手访问随机预言机OH1(·)的次数，而tHash表示H.Hash(·)的运行时间.

证明. 与定理1的证明类似，此处从略.

证毕.

4.3紧致安全签名方案实例

本节以基于RSA难题的强变色龙Hash函数为例，首先设计一个基于RSA的具体签名方案，然后考虑这一签名方案的变形，并比较这些方案与现有的相关方案.借此说明，上述基于强变色龙Hash函数的一般化签名方案具有良好的理论概括性和实际应用价值.

对于前面提出的基于RSA假设的强变色龙Hash函数SCH-RSA，应用上述的数字签名构造框架SCH-2-DS0，得到带状态数字签名方案DS-RSA：

1)S.Gen(1λ).本方案相关符号与前面强变色龙Hash函数SCH-RSA一致，公钥和私钥分别为

pk=(n,e,xe),

sk=(x,d),

2)S.Sign(sk,m).假设消息m之前未曾签过，计算签名

σ=(H1(m)d×x-s,s)，

3)S.Vrf(pk,m,σ).为了验证σ=(s,r)是否为消息m的签名，只需验证是否成立等式:

H1(m)=(xe)sremodn.

上述签名是直接套用签名框架SCH-2-DS0的结果，因此具有带状态的缺点.利用不带状态的签名框架SCH-2-DS1，并作适当优化，可以构造出如下2个基于RSA假设的不带状态签名方案.

σ=(H1(m,s,s′)d×x-s,s,s′)，

σ=(H1(m,s′)d,s′)，

由以上2式显然可见，在计算上讲，只是有一次模乘法的差别，这与d次模幂运算相比，基本可以忽略.因此，计算差别可以忽略.在签名长度上看，二者的签名长度只有1比特的差别，考虑到紧致性方面的极细微差别，1比特的差别基本可以忽略.

σ=(H1(m,s)d×x-s,s),

此处s←Re.以上签名形式与文献[8]中基于RSA的紧致安全签名方案完全一致，该方案是把文献[8]的一般化签名框架(称之为SWAP转换)应用在GQ身份认证方案[30]而得到的.注意:SWAP提出的背景是为了解决Fiat-Shamir类签名方案的紧致安全性问题.事实上，一般的Fiat-Shamir类签名方案都不具有紧致安全性.SWAP转换是Fiat-Shamir转换的一种变形，仅适用于一类特殊的身份认证方案，可以将其转化为紧致安全的FS类签名方案.

4.4紧致安全签名构造框架的理论意义

通过4.3节具体例子，对于本文提出的基于强变色龙Hash的一般化签名方案的构造框架，作4项探讨：

1) 根据4.3节基于RSA难题的3个具体签名方案，同样可以模块化地构造出基于双线性群上CDH 难题的具体签名方案和基于整数分解难题的具体签名方案，既包含FDH类紧致安全签名，又包括FS类紧致安全签名.

2) 本文所提出的基于强变色龙Hash函数的紧致安全签名的框架，在理论上统一了FDH类和FS类 这2类紧致安全签名方案，从而指出了紧致安全签名方案要求底层密码原型所必须具有的最关键性质.事实上，在数字签名构造理论领域，人们通常把FS类签名和FDH类签名看作2类独立的签名构造技术.

3) 在本文所提出的框架下，FS类紧致安全签名[8]和PDH类紧致安全签名，可以看作是以不同方式调整框架中的相关参数而形成的不同的特殊结果.特别是，FDH类签名方案可以看作是比相应的FS类签名方案更为优化的形式.从这层意义上讲，本文的一般性理论结果粗略地否定了FS类紧致安全签名研究分支[3]的研究意义.

4) 本文所提出的框架具有非常高的概括性，从而具有广泛的应用性，其根本原因是最为底层的密码原型具有很高抽象性和概括性.事实上，它可以诱导出陷门置换、无爪置换[15]等非常基础的密码原型.

5 结 论

本文研究了可证明安全密码学领域的一个经典问题，即如何由底层困难问题出发，高效且直观地构造紧致安全数字签名方案.首先扩展了传统变色龙Hash函数的概念，提出了强变色龙Hash函数的密码原型，用作底层困难问题的抽象模型，力图刻划底层困难问题的基础密码性质，而这些性质又是实现紧致安全签名的关键所在.进而提出了一种直观、简练的转换框架，可将强变色龙Hash函数转换为带状态的紧致安全签名方案.进一步给出了对应的不带状态紧致安全签名方案变形，并指出所提出的通用构造框架在某种程度上统一了FS类和FDH类2种经典的数字签名构造框架(就紧致安全签名的情况来说)，而之前密码学领域通常认为它们是互相独立的2种签名构造范式.同时在本文所给的一般性框架下，FDH类紧致签名还可以看作相应FS类紧致签名的优化变形.

[1] Feng Dengguo. Research on theory and approach of provable security[J]. Journal on Software, 16(10): 1743-1756 (in Chinese)

(冯登国. 可证明安全性理论与方法研究[J]. 软件学报, 2005, 16(10): 1743-1756)

[2] Xu Peng, Cui Guohua, Lei Fengyu. An efficient and provably secure IBE scheme without bilinear pairing[J]. Journal on Computer Research and Development, 2008, 45(10): 1687-1695 (in Chinese )

(徐鹏, 崔国华, 雷凤宇. 非双线性映射下一种实用的和可证明安全的IBE方案[J]. 计算机研究与发展, 2008, 45(10): 1687-1695)

[3] Chen Ming, Yuan Shaoliang. Provably secure identiy-based multi-proxy signature scheme in standard model[J]. Journal of Computer Research and Development, 2016, 53(8): 1879-1892 (in Chinese )

(陈明, 袁少良. 标准模型下可证明安全的基于身份多代理签名[J]. 计算机研究与发展, 2016, 53(8): 1879-1892)

[4] Wen Weiqiang, Wang Libin. A strongly secure lattice-based key exchange protocol[J]. Journal of Computer Research and Development, 2015, 52(10): 2258-2269 (in Chinese)

(温伟强, 王立斌. 基于格问题的强安全密钥交换协议[J]. 计算机研究与发展, 2015, 52(10): 2258-2269)

[5] Bellare M, Rogaway P. The exact security of digital signatures-how to sign with RSA and Rabin[G] //LNCS 1070: Advances in Cryptology (EUROCRYPT 1996). Berlin: Springer, 1996: 399-416

[6] Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems[G] //LNCS 263: Advances in Cryptology (CRYPTO’86). Berlin: Springer, 1987: 186-194

[7] Goldwasser S, Micali S, Rivest R. A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM Journal on Computing, 1988, 17(2): 281-308

[8] Micali S, Reyzin L. Improving the exact security of digital signature schemes[J]. Journal of Cryptology, 1999, 15(1): 1-18

[9] Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C] //Proc of ACM Conf on Computer & Communication Security. New York: ACM, 1993: 62-73

[10] Cramer R, Shoup V. Signature schemes based on the strong RSA assumption[J]. ACM Trans on Information & System Security, 1999, 3(3): 161-185

[11] Gennaro R, Halevi S, Rabin T. Secure Hash-and-sign signatures without the random oracle[G] //LNCS 1592: Advances in Cryptology (EUROCRYPT’99). Berlin: Springer, 1999: 123-139

[12] Hohenberger S, Waters B. Short and stateless signatures from the RSA assumption[G] //LNCS 5677: Advances in Cryptology (CRYPTO 2009). Berlin: Springer, 2009: 654-670

[13] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[J]. Journal of Cryptology, 2012, 25(4): 601-639

[14] Coron J S. On the exact security of full domain Hash[G] //LNCS 1880: Advances in Cryptology (CRYPTO 2000). Berlin: Springer, 2000: 229-235

[15] Dodis Y, Reyzin L. On the power of claw-free permutation[G] //LNCS 2576: Proc of the 3rd Int Conf on Security in Communication Networks. Berlin: Springer, 2002: 55-73

[16] Coron J S. Optimal security proofs for PSS and other signature schemes[G] //LNCS 2332: Advances in Cryptology (EUROCRYPT 2002). Berlin: Springer, 2002: 272-287

[17] Katz J, Wang Nan. Efficiency improvements for signature schemes with tight security reductions[C] //Proc of the 10th ACM Conf on Computer and Communications Security. New York: ACM, 2003: 155-164

[18] Boneh D, Lynn B, Shacham H. Short signatures from the weil pairing[J]. Journal of Cryptology, 2004, 17(4): 297-319

[19] Bellare M, Palacio A. GQ and schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks[G] //LNCS 2442: Advances in Cryptology (CRYPTO’02). Berlin: Springer, 2002: 162-177

[20] Pointcheval D, Stern J. Security arguments for digital signatures and blind signatures[J]. Journal of Cryptology, 2000,13(3): 361-396

[21] Schnorr C P. Efficient signature generation by smart cards[J]. Journal of Cryptology, 1991, 4(3): 161-174

[22] Abdalla M, Fouque P A, Lyubashevsky V, et al. Tightly-secure signatures from lossy identification schemes[J]. Journal of Cryptology, 2016, 29(3): 597-631

[23] Bellare M, Poettering B, Stebila D. From identification to signatures, tightly: A framework and generic transforms[G] //LNCS 10032: Advances in Cryptology (Asiacrypt 2016). Berlin: Springer, 2017: 435-464

[24] Goh E J, Jarecki S. A signature scheme as secure as the Diffie-Hellman problem[G] //LNCS 2656: Advances in Cryptology (EUROCRYPT 2003). Berlin: Springer, 2003: 401-415

[25] Goh E J, Jarecki S, Katz J, et al. Efficient signature schemes with tight reductions to the Diffie-Hellman problems[J]. Journal of Cryptology, 2007, 20(4): 493-514

[26] Krawczyk H, Rabin T. Chameleon signatures[C] //Proc of Network and Distributed System Security Symposium (NDSS 2000). Reston, VA: Internet Society, 2000: 143-154

[27] Chen Xiaofeng, Zhang Fangguo, Tian Haibo, et al. Discrete logarithm based chameleon hashing and signatures without key exposure[J]. Computers & Electrical Engineering, 2011, 37(4): 614-623

[28] Ateniese G, Medeiros B. On the key exposure problem in chameleon hashes[G] //LNCS 3352: Proc of Security in Communication Networks (SCN 2004). Berlin: Springer, 2004: 165-179

[29] Gao Wei, Wang Xueli, Xie Dongqing. Chameleon hashes without key exposure based on factoring[J]. Journal of Computer Science and Technology, 2007, 22(1): 109-113

[30] Quisquater J J, Guillou L C. A paradoxical identity-based signature scheme resulting from zero-knowledge[G] //LNCS 403: Advances in Cryptolgy (CRYPTO’88). Berlin: Springer, 1988: 216-231

GenericTightlySecureSignatureSchemesfromStrongChameleonHashFunctions

Li Fei1,2, Gao Wei1,2, Wang Guilin3, Xie Dongqing2, and Tang Chunming2

1(SchoolofMathematicsandStatistics,LudongUniversity,Yantai,Shandong264025)2(GuangdongProvincialKeyLaboratoryofInformationSecurityTechnology(GuangzhouUniversity),Guangzhou510006)3(ShieldLaboratory,SingaporeResearchCenterofHuawei,Singapore117674)

Provable security has become one basic requirement for constructing and analyzing cryptographic schemes. This paper studies the classical issue in the field of provable security, namely how to construct provably secure digital signature schemes with tight security reduction from certain basic mathematical hard problems in the random oracle model. This paper first proposes a new cryptographic primitive called a strong chameleon Hash function. Based on a strong chameleon Hash function, we present a generic framework and its variant respectively for constructing a stateful and stateless digital signature scheme with tight security. We prove that these generic digital signature schemes are both secure under the assumption that the underlying chameleon Hash function is collision resistant in the random oracle model. By applying these generic construction methods to some concrete chameleon Hash functions under common mathematical assumptions such as RSA, CDH and IF (integer factorization), the corresponding digital signature schemes with tight security can be modularly obtained. The two existing classic paradigms to generically construct tightly secure signature schemes, i.e. Fiat-Shamir signatures and Full-Domain-Hash signatures, can be roughly unified by our generic frameworks. Furthermore, under our generic frameworks, a tightly secure signature scheme following the Fiat-Shamir methodology can be seen as the optimized variant of the corresponding tightly secure signature scheme following the Full-Domain-Hash framework.

digital signature; provable security; tight security; random oracle model; chameleon Hash function;full domain Hash signature

TP309

LiFei, born in 1977. PhD from Guangzhou University. Her main research interests include public key cryptography, algebra, and number theory.

GaoWei, born in 1978. PhD from Hunan University. Associate professor. His main research interests include public key cryptography, cloud security and applied mathematics (mygaowei@163.cm).

WangGuilin, born in 1968. PhD from Institute of Software, Chinese Academy of Sciences. Senior researcher. His main research interests include public key cryptography, cloud security and network security (Wang.Guilin@huawei.com).

XieDongqing, born in 1965. PhD from Hunan University. Professor. Member of CCF. His main research interests include applied cryptography, cloud security and network security (dongqing_xie@hotmail.com).

TangChunming, born in 1972. PhD. Professor. His main research interests include applied cryptography, cloud security and applied mathematics (ctang@gzhu.edu.cn).