一种具有CDH问题安全性基于身份的签名方案

陈辉焱, ,

(1.北京电子科技学院 信息安全系,北京 100070; 2.西安电子科技大学 通信工程学院,西安 710071)

0 概述

在实践中使用公钥密码学,最主要的问题是如何提供一种安全的方式将用户与他们的公钥连接起来。目前,解决上述问题的方案是建立一个公钥基础设施,其中由可信实体颁发证书来确定公钥属于某个确定的用户,证书通常包括用户的身份、公钥以及可信的实体签名。若需要安全的通信,2个用户间首先要交换证书。为了减少实际应用中对用户证书的需求,文献[1]提出基于身份密码学的观点,其思想是用户的公钥可以从任意字符串(邮件地址、连接用户姓名的IP地址、社会安全号等)中导出,它以一种明确的方式来验证其身份。这种密码体系需要一种被称为私钥生成器(Private Key Generator,PKG)的可信机构来完成,PKG的任务是从用户的身份信息中计算用户的私钥。

1984年以来,许多基于身份的签名(Identity-based Signature,IBS)方案[2-3]被提出。目前,有两种通用的IBS构造方法:一种由文献[4]提出,它表明之前提出的大量方案都是其通用构造的实例;另外一种由文献[5]提出,对于签名知识的证明,该方法需要有效的零知识协议,这使得其构造仅仅适用于一部分方案,如RSA-FDH和BLS[6]。

IBS的安全证明一般都是通过演示一个规约来进行,这种规约证明了如果攻击者A能够有效地破解某个IBS,那么就可以构造出一种算法来破解这种困难问题,这种评估安全性的技术就是安全性规约。规约质量由敌手抗IBS方案破解潜在的棘手问题成功的概率决定。当敌手在时间t内运行成功的概率大约等于相同时间内解决潜在困难问题的概率时,则认为安全规约是严格的,否则就认为它是近似规约。

严格的安全证明需要较短的安全参数和更高的效率。针对那些在随机预言机模型下是安全的密码方案或由它们变形[7-8]所得的一些密码方案,为其提供新的安全证明,以及利用严格的安全规约构造新的方案[9-10],已经成为可证明安全领域的一个研究热点。然而,目前在设计具有严格安全规约的IBS方案方面还没有明显的进步。文献[11]在Diffie-Hellman假设下对方案在严格安全规约范围内通过Pointcheval和斯特恩分叉引理给出了证明。文献[12-13]在Diffie-Hellman假设下对方案在严格安全规约范围内通过文献[14]的“ID规约技术”给出了证明。文献[4]针对IBS方案的大家族定义了一个框架来提供安全性证明,但是该框架不能提供严格的安全界。文献[5]演示了从任何满足确定条件的数字签名方案到IBS方案的转换,并对所得的IBS方案给出安全性证明,尽管该安全性证明避免了分叉技术的使用,但它的规约条件仍然比较宽松。

尽管可计算的Diffie-Hellman (Computational Diffie-Hellman,CDH)假设在技术上比离散对数假设强,但对于各种已被研究的密码群来说,目前并不知道如何通过解决离散对数问题[15]来更快地解决Diffie-Hellman问题。此外,一些理论表明在某些群中CDH假设与离散对数假设[15]等价。

基于以上问题,本文提出一种新的IBS方案IDSSTR。该方案的签名过程是确定的:用户使用他的部分密钥通过Schnorr[16]签名方案在消息上计算签名。在随机预言机模型下,IDSSTR的安全性与CDH假设密切相关。此外,不需要额外的信息将IDSSTR转换成离线/在线版本。为缩短签名消息的总长度,本文也给出具有消息恢复功能的IDSSTR修改版本。

1 预备知识

1.1 IBS方案

IBS方案由下列4个步骤组成:

1)系统参数建立。该算法通过PKG运行,输入安全参数,生成方案的公共参数params和主密钥。PKG公布公共参数,自己保存主密钥。

2)私钥提取。给出身份ID、主密钥和公共参数params,该算法生成ID的私钥dID。主实体将使用该算法针对参与方案的所有实体来生成私钥,并通过安全渠道将私钥分发给其主人。

3)签名。给出消息m、身份ID、私钥dID和公共参数params,该算法在m上生成ID的签名σ。具有身份ID的实体将使用该算法用于签名。

4)验证。给出签名σ、消息m、身份ID和公共参数params,如果σ对于身份ID在m上是有效的签名,则该算法输出“接受”;否则,输出“拒绝”。

IBS方案安全性已知的最普遍概念是在自适应性选择消息攻击时存在伪造安全,在该模型中,敌手可以让签名者签署除了输出以外的任何消息,如果敌手最终输出一对有效的消息和签名,则敌手赢得游戏。

敌手和挑战者之间的游戏如下:

1)系统参数建立。挑战者运行系统参数建立算法,得到公共参数params和主私钥sk。敌手可以得到公共参数params,但主私钥sk由挑战者保管。

2)查询。敌手自适应地制作大量不同的查询给挑战者。每个查询可以是下列中的一种:

(1)哈希查询:挑战者针对请求的输入计算哈希函数值并将该值发送给敌手。

(2)私钥提取查询:敌手可以询问任何身份ID的私钥。挑战者通过运行私钥提取算法生成与ID对应的私钥dID,将dID作为应答发送给敌手。

(3)签名查询:敌手可以针对身份ID和某个消息m对挑战者进行签名查询。挑战者首先运行私钥提取算法产生与ID对应的私钥dID,再利用dID运行签名算法生成消息m的签名σ,将σ作为应答发送给敌手。

3)伪造。敌手最终对消息m*和身份ID*输出一个伪造的签名σ*。如果下列条件均成立,则敌手成功:

(1)Verify(params,ID*,m*,σ*)=accept。

(2)敌手在ID*上没有制造提取查询。

(3)敌手在(ID*,m*)上没有制造签名查询。

在上面的游戏中敌手A的优势被定义为:

AdvSigA=Pr[A succeeds]

(1)

其中,概率是挑战者和敌手在各种能遇到的情况下得到的。

定义1如果敌手在时间t内最多制造qs个签名查询,qH个哈希函数查询,qe个私钥提取查询,且AdvSigA至少为ε,则敌手就可以破解该签名方案。如果一个签名方案在可适应选择消息条件下没有伪造者可以破解它,则认为该签名方案是不可伪造的。

1.2 双线性配对和复杂性假设

为简单起见,令G1=G2。对于条件G1=G2,可以修改结合超级椭圆曲线的Weil和Tate配对来创造这样的双线性。

定义3如果不存在一个概率多项式时间算法在时间t内,以至少ε的概率解决群G上的CDH问题,则认为(t,ε)-CDH假设成立。

CDH问题的困难性被广泛地认为与离散对数问题的困难性密切相关。此外,对于离散对数问题是困难的一类群来说,通过文献[15]的结果,可以直接将本文方案与离散对数问题的困难性相联系。

1.3 密码哈希函数

密码哈希函数是具有特定安全属性的哈希函数,适合在各种信息安全应用中作为原语使用,例如身份验证和消息完整性。对于密码哈希函数H,存在与密码观点相关的3个基本属性。

1)原像抵抗性。给出一个哈希值h,很难找到一个消息m使得H(m)=h。缺乏这种属性的密码哈希函数对于原像攻击是很脆弱的。

2)第二原像抵抗性。给出一个输入m1,很难找到不同的输入m2使得H(m2)=H(m1)。缺乏这种属性的密码哈希函数对于第2种原像攻击是很脆弱的。

3)抗碰撞性。很难找到2条不同的消息m1和m2使得H(m1)=H(m2),如m1和m2这样的一对值被称为密码哈希碰撞。

2 具有严格安全性规约的IBS

本文的签名方案IDSSTR运行过程如下:

1)系统参数建立。给出安全参数n,算法运行如下:

2)私钥提取。给定用户的身份ID∈{0,1}*,算法运行如下:

(2)计算h=H(v,ID)和f=hx。

(3)计算r=H0(f,ID)。

(4)计算y=t+rxmodp。

(5)将对应身份ID的私钥dID设置为dID=(f,y)。

3)签名。给出身份ID、dID和消息m∈{0,1}*,算法运行如下:

(2)计算c=H1(v0,m)和w=gy。

(3)计算s=k+cymodp。

(4)消息m和身份ID上的签名σ=(f,w,s,c)。

4)验证。给出身份ID和消息m上的签名σ=(f,w,s,c),算法运行如下:

(1)计算r=H0(f,ID)。

(2)计算h=H(wu-r,ID)。

2.1 安全性证明

首先,证明不可伪造性。

定理1假设H1是密码哈希函数,它具有原像抵抗性,H和H0作为随机预言机。如果阶为素数p的群G上的CDH假设成立,则该方案在自适应选择消息攻击下是安全的,如果在qH个随机预言机查询、qe个提取预言机查询和qs个签名预言机查询的条件下满足:

ε≤ε′+(qsig+qe)(qH+qH0+2qe+2qs)/p+

(2+qH+qe+qs)/p

(2)

t≈t′-O(4qe+6qs+qH)T

(3)

则该签名方案是不可伪造的。其中,T是G中求幂的最大时间。

证明:F是一个伪造者,(t,qH,qH0,qe,qs,ε)破坏本文的构造。

构造一个模拟算法S,它可以将(G,g,p)和(ga,gb)作为输入。算法S使用F算法在t′步内以ε′的概率计算CDHg,p(ga,gb)函数,其中:

ε≤ε′+(qs+qe)(qH+qH0+2qe+2qs)/p+

(2+qH+qe+qs)/p

(4)

t≈t′-O(4qe+6qs+qH)T

(5)

算法S对伪造者F模拟运行上述签名方案。算法S回答F的哈希函数查询、私钥提取查询、签名预言机查询,并将F可能的伪造(m,σ)转化为CDHg,p(ga,gb)函数的答案。算法S通过提供(G,g,p)开始模拟,公钥u=ga作为F的输入。算法S回应F的查询如下:

(1)S检查L。如果存在条目(v,ID,d)∈L,S返回gbgd到F。

(2)否则,S检查L′。L′通过提取预言机和签名预言机生成。如果存在条目(v,ID,d)∈L′,S返回gd到F。

(1)S检查L0。如果存在条目(f,ID,r)∈L0,S返回r到F。

(2)否则,S检查L0′。L0′通过提取预言机和签名预言机生成。如果存在条目(f,ID,r)∈L0′,S返回r到F。

(1)S检查LE,如果存在条目(ID,f,y)∈LE,S返回(f,y)到F。

4)签名查询。假设伪造者F要求身份ID∈{0,1}*和消息m∈{0,1}*上的签名,算法S在不知道主密钥的情况下必须创建一个有效的签名组。在这个过程中,S定义了哈希函数H和H0的若干值并为签名查询生成了一些私钥。因此,算法S得到列表LE、L′和L0′。模拟过程如下:

(1)S检查LE。如果存在条目(ID,f,y)∈LE,S跳到过程(5)。

(4)设置H(v,ID)=h,H0(f,ID)=r。如果H(v,ID)或H0(f,ID)已经被设置,则S终止;否则,在身份ID上生成私钥dID=(f,y),并分别将(f,ID,y)、(v,ID,d)、(f,ID,r)放到LE、L′和L0′中。

(6)S计算c=H1(v0,m)和s=k+cy,生成一个有效的签名σ=(f,w,s,c)并将其返回到F。

5)伪造。A输出(m*,ID*,σ*=(f*,w*,s*,c*))使得σ*在消息m*和身份ID*上是一个有效的签名,要求(m*,ID*)未曾在之前的签名预言机查询中被查询过,ID*未曾在之前的提取预言机查询中被查询过。其中,如果H0(f*,ID*)没有被攻击者查询到H0预言机中或通过签名预言机和提取预言机设置,则模拟查询到H0预言机自身。如果r*=H0(f*,ID*),H(w*u-r*)没有被攻击者查询到H预言机中或通过签名预言机和提取预言机设置,则模拟查询到H预言机自身。

需要注意的是,S为F提供模拟器,它的分布与F在含有签名者的真实交互中的分布相同。为了更清楚地说明这点,本文给出下列解释:

1)H0预言机和H预言机的模拟器较好。

解决CDH问题时假设伪造者F返回一个有效的消息、身份和签名组(m*,ID*,σ*=(f*,w*,s*,c*)),(m*,ID*)和ID*都未曾在之前的私钥提取查询和签名查询中被查询过。在有效的伪造签名(m*,ID*,σ*=(f*,w*,s*,c*))中,需要考虑下列情形:

情形1ID*出现在签名预言机查询中,但存在满足(ID*,f′,gy′)=(ID*,f*,w*)的(ID*,f′,gy′)∈LE。假设A选择gk并计算c*=H1(gk,m*),为了得到s*,A必须计算DLg(gk(w*)c*)。假设A选择c*,为了生成一个有效的伪造签名(m*,ID*,σ*=(f*,w*,s*,c*)),A必须找到满足H1(gs*(w*)c*,m*)=c*的s*。如果s*以不可忽略的概率被找到,则密码哈希函数H1就会很容易受到原像攻击,这与原像抵抗性的概念发生矛盾。因此,这种情况下A生成有效伪造签名的概率是可以忽略的。

情形2ID*出现在签名预言机查询中,但存在满足(ID*,f′,gy′)≠(ID*,f*,w*)的(ID*,f′,y′)∈LE。假设r*=H0(f*,ID*),r′=H0(f′,ID*),可以得到w*ur*≠w′ur′。否则,通过w*ur*=w′ur′得到h*=H(w*ur*,ID*)=H(w′ur′,ID*)=h′,f*=(h*)a=(h′)a=f′,r*=H0(f*,ID*)=H0(f′,ID*)=r′,w*=w′。因此,在这种情况下,(w*ur*,ID*,h*)不能出现在L′中。

综上所述,ID*不能出现在签名预言机查询中。

如果上面的情况均不发生,则(v*,ID*)存储在L中并且h*=H(v*,ID*)=gbgd对于模拟器S中的某些d成立。

用算法S解决CDH问题的概率计算过程如下:

3)NH0代表伪造者F不能在(f*,ID*)上查询H0预言机这一事件,NH0是伪造者的一部分输出。NH代表伪造者F不能在(v*,ID*)上查询H预言机这一事件,NH是伪造者的一部分输出。其中r*=H0(f*,m*),v*=H0(w*u-r*)。计算概率Pr[NH∨NH0]的上界(Pr[NH∨NH0]=Pr[NH∧NH0]+Pr[NH0])过程如下:

(1)Pr[NH∧NH0]的上界:假设r*=H0(f*,m*),计算v*=w*u-r*。如果模拟器在(v*,ID*)上查询H预言机本身并得到h=H(v*,ID*),h满足ha=f*的概率最多为1/p。

(2)Pr[NH0]的上界:模拟器S在(f*,ID*)上查询H0预言机本身并得到r*=H0(f*,ID*),H(v*,ID*)的概率被设置为最大(qH+qe+qs)/p,其中v*=w*u-r*。如果H(v*,ID*)的概率没有被设置,它将通过模拟器被查询且模拟器得到h=H(v*)。h满足ha=f*的概率为1/p,则Pr[NH0]的概率最大值为(1+qH+qe+qs)/p。

将上面的概率相加,得出模拟器S最小以ε-(qs+qe)(qH+qH0+2qe+2qs)/p-(2+qH+qe+qs)/p的概率解决CDH问题。

2.2 效率分析

表1 2种方案在循环群G上的计算成本比较

2.3 离线/在线分析

本质上通过做离线的所有工作有可能使得上述方案瞬间在线签名。本文的签名方案主要分为以下2步:

(2)计算w=gy。

(3)输出(v0,m)。

2)在线签名。给出签名消息m∈{0,1}*。

(1)计算c=H1(v0,m)。

(2)计算s=k+cymodp。

(3)签名为σ=(f,w,s,c)。

验证过程与前述相同。这一属性较有用,因为它允许签名者重新计算f进而快速地在线签名,即通过一个模乘运算和模加运算就可以运行一个哈希函数。

3 有限的消息恢复

在带宽有限的环境中,缩短原始消息M附加签名σ的总长度是可行的。缩短签名消息总长度的通用技术是在签名过程中只对消息的一部分进行编码,利用这种技术得到的方案称为具有消息恢复功能的签名方案。现有的具有消息恢复功能的数字签名可以分为2种:基于RSA的方案[14]和基于离散对数的方案[18]。本节给出IDSSTR的一种修改版本,并根据文献[18]提出的技术使其具有消息恢复功能。

IDSSTR修改版本构造过程如下:

1)系统参数建立。给出安全参数n,算法运行如下:

2)私钥提取。对于给出的身份串ID∈{0,1}*,算法运行如下:

(2)计算h=H(v,ID)和f=hx。

(3)计算r=H0(f,ID)。

(4)计算y=t+rxmodp。

(5)将对应身份ID的私钥dID设置为dID=(f,y)。

3)签名。给出身份ID、dID和消息m∈{0,1}l,算法运行如下:

(2)计算m′=F1(m)‖F2(F1(m))⊕m和w=gy。

(3)计算c=H1(v0)⊕m′。

(4)计算c′=H2(c)。

(5)计算s=k+c′ymodp。

(6)消息m和身份ID上的签名σ=(f,w,s,c)。

4)验证。给出身份ID和消息m上的签名σ=(f,w,s,c),算法运行如下:

(1)计算r=H0(f,ID)。

(2)计算h=H(wu-r,ID)。

(3)计算c′=H2(c)。

(4)计算v0=gsw-c′。

(5)计算m′=H1(v0)⊕c。

(6)计算m=[m′]l⊕F2([m′]l)。

其中,[m′]l表示m′中最重要的l位,[m′]l表示m′中次重要的l位,a⊕b表示字符串a和b的异或计算(XOR)。

备注 为了在身份ID上签名一个较长的消息m(|m|>l),m应该分为m1和m2两部分,且|m2|=l,m=m1‖m2,m1‖m2表示字符串m1和m2的级联。

签名者生成(f,w,s,c)过程如下:

2)计算m′=F1(m2)‖F2(F1(m2))⊕m2和w=gy。

3)计算c=H1(v0)⊕m′。

4)计算c′=H2(c‖m1)。

5)计算s=k+c′ymodp。

6)消息m和身份ID上的签名σ=(f,w,s,c)。

对于上面的方案,假设H1、H2、F1、F2是密码哈希函数,H和H0是可以给出类似于IDSSTR安全证明的随机预言机。

4 结束语

本文提出一种具有严格安全性规约的IBS新方案IDSSTR。IDSSTR在线时自然有效,离线阶段不需要额外的条件,验证过程也不变。为了缩短原消息M和附加签名σ的总长度,本文同时也提出了一种具有部分消息恢复功能的IDSSTR修改版本。因为CDH问题的困难性被广泛地认为与离散对数问题的困难性密切相关,因此,本文提出的IDSSTR为其提供了安全保证。下一步将对一些基于身份的密码方案提供新的安全证明以及利用严格的安全规约来构造更实用的方案。

[1] ADI S.Identity-based cryptosystems and signature schemes[J].Lecture Notes in Computer Science,1984,21(2):47-53.

[2] XUN Yi.An identity-based signature scheme from the weil pairing[J].IEEE Communications Letters,2003,7(2):76-78.

[3] BARRETO P S L M,MCCULLAGH N,QUISQUATER J J.Efficient and provably-secure identity-based signatures and signcryption from bilinear maps[C]//Proceedings of International Conference on Theory and Application of Cryptology and Information Security.Washington D.C.,USA:IEEE Press,2005:515-532.

[4] BELLARE M,NAMPREMPRE C,NEVEN G.Security proofs for identity-based identification and signature schemes[M].Berlin,Germany:Springer,2004.

[5] KUROSAWA K,HENG S H.From digital signature to ID-based identification/signature[C]//Proceedings of International Workshop on Public Key Cryptography.Berlin,Germany:Springer,2004:248-261.

[6] DAN B,BEN L,HOVAV S.Short signatures from the weil paring[J].Journal of Cryptology,2004,17(4):297-319.

[7] CORON J S.Optimal security proofs for PSS and other signature schemes[C]//Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2002:272-287.

[8] GE S.Tight proofs for signature schemes without random Oracles[C]//Proceedings of International Conference on Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2011:189-206.

[9] 卢 超,钱海峰.标准模型下的在线/离线多签名方案[J].计算机应用研究,2010,27(9):3514-3517.

[10] 胡国政,洪 帆.标准模型中可证安全的签名方案[J].武汉理工大学校报,2009,31(15):130-134.

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

[12] 刘振华,张襄松,田绪安,等.标准模型下基于身份的具有部分消息恢复功能的签名方案[J].北京工业大学学报,2010,36(5):654-658.

[13] WANG Z,CHEN H.Emerging directions in embedded and ubiquitous somputing[M].Berlin,Germany:Springer,2007.

[14] BELLARE M,ROGAWAY P.The exact security of digital signatures:how to sign with RSA and Rabin[C]//Proceedings of International Conference on Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,1996:399-416.

[15] MAURER U M,WOLF S.The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms[J].SIAM Journal on Computing,1998,28(5):1689-1721.

[16] SCHNORR C P.Efficient identification and signatures for smart cards[M].Berlin,Germany:Springer,1989.

[17] LIBERT B,QUISQUATER J J.The exact security of an identity based signature and its applications[EB/OL].[2016-11-25].https://eprint.iacr.org/2004/102.pdf.

[18] ABE M,OKAMOTO T.A signature scheme with message recovery as secure as discrete logarithm[J].IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences,2001,84(1):197-204.