节点文献
数字签名算法的研究与设计
The Research on Digital Signature Schemes
【作者】 王少辉;
【作者基本信息】 山东大学 , 信息安全, 2008, 博士
【摘要】 随着计算机网络通信技术和软件技术的迅猛发展,以及因特网的广泛应用,如何保证及加强信息安全性,保证电子信息的完整性已成为国际社会普遍关心的重大问题。数字签名算法应运而生。数字签名是公钥密码学领域最重要的发展方向之一,是在电子传输中提供数据的认证性、完整性和不可否认性的重要技术和理论保障,因而是信息安全的核心技术之一,也是实现安全电子商务和安全电子政务的关键技术之一。数字签名是计算机通信网信息安全的基本内容之一,对它的研究有着重要的理论和实际意义。本文针对密码学数字签名领域的几个热点问题,研究并设计了一些有效并安全的数字签名方案,具体成果如下。1.标准模型下有效群签名方案效率和安全性是评估一个密码算法的两个重要指标。直到1999年,所有可证明安全的有效签名算法都基于随机预言模型(Random Oracle Model)[11]。而标准模型下签名方案因采用树结构,其可证明安全性以严重的牺牲效率作为代价,因此只具有重要的理论意义而不实用。在随机预言模型中,假定任何用户(合法用户和攻击者)都能访问某个理想化的随机预言机以获得一个随机数,但是这个理想的预言机在现实世界中并不存在,而通常以hash函数代替。文献[33]设计了这样的方案,其在随机预言模型下是安全的,但是在hash函数替代预言机后,方案却是不安全的。从而,满足标准模型下可证明安全的有效签名方案的设计仍是当前研究的热点和难点。群签名[15]是一种可撤销匿名性的数字签名技术,具有如下的特点:(1)只有特定群的成员可以签署消息;(2)验证者能够验证签名的合法性但是不能获知签名者的身份;(3)在有纠纷的情况下,签名者的身份可以由群管理员打开。群签名在管理,军事,政治以及经济等多个方面有着广泛的应用。目前,已提出的标准模型下可证明安全的群签名主要有:Bellare,Micciancio和Warinschi[39]提出了第一个标准模型下可证明安全的群签名,但方案非常低效,不能在实际中应用;Ateniese等[41]所提出的方案基于一个新的过强的安全假设;Boyen和Waters[42,44]基于标准模型下的Waters签名[74],提出了目前最为有效的常数长度的群签名方案,但是由于Waters签名基于树结构,从而其群签名方案公钥长度过长,运算量较大。2006年,Okamoto[28]提出了一个新的标准模型下可证明安全的签名方案,方案的安全性基于强Diflie-Hellman假设。本文中,基于Okamoto签名方案,我们提出了目前最为有效的不基于随机预言模型可证明安全的群签名方案。我们首先给出了Okamoto签名方案的一个改进方案,新方案隐藏了原方案的部分签名信息;然后利用Groth,Ostrovsky和Sahai[43]的非交互零知识证明的技巧来隐藏签名者的身份,以达到群签名匿名签名的目的。新方案基于强Diffie-Hellman假设和子群判断假设,与Boyen和Waters方案相比[44],所提方案所需公钥长度更短,而运算量也具有明显优势,具体比较如下:(1.)Boyen和Waters群签名方案的公钥大约需要m+4个群G1中的元素和1个群Gq中的元素,其中安全起见,m大约取值160;新方案需要4个G1中的元素,1个Gq的元素。(2.)新方案最终签名包括5个群G1中的元素和1个Zn中元素,Brent和Waters方案的签名包括6个G1中元素。(3.)就计算量而言,Brent和Waters方案平均需要m/2+10个群乘法运算(最坏情况需要m+10个),12个指数运算;新方案需要10个指数运算和9个乘法运算。2.基于身份的可链接和可转换环签名环签名[18]可以视为一种特殊的群签名,不同之处在于环签名没有可信中心,没有群的建立过程,从而也就不象群签名那样存在可以打开签名者身份的机构。签名者可以完全自主的构建一个环并匿名签名,验证者能够证明消息是由环中的某个成员签署的,但无法确认签名者的身份。环签名主要用于电子投票,电子现金,泄露隐私信息和认证通信等。为了适应应用的需要,标准环签名概念被添加了一些额外的附加性质。如可链接性[45]和可转换性[47]。在可链接环签名中,验证者虽不知道具体的签名者,但是可以确认两个签名是否是同一个签名者所签;而可转换环签名为签名者提供了将环签名转换成一般签名的机制。而由于基于身份密码系统密钥生成的特殊性,PKI系统下为环签名添加可链接性的方法不能直接适用于基于身份密码系统中,如何构造基于身份的可链接环签名是2005年欧洲PKI会议[52]所提出的公开问题之一。同时,环签名虽然具有简单的群构造过程,但是在通常的设计中,因为验证者需要知道整个环的描述,从而环签名的长度通常会随着环成员的增多而线性增长。从而需要大量空间存贮公钥信息,而验证也需要大量的运算,这大大限制了环签名的应用。为了设计有效的固定长度的环签名算法,研究者引入了许多新颖的设计思路。例如聚合器的引入为设计固定长度的环签名提供了不同以往的设计思想。本文中,我们研究了在基于身份密码系统下为环签名添加可链接性和可转换性的问题。我们将可链接性分为弱可链接性和强可链接性。在弱可链接环签名中,不要求同一签名者的所有签名全部链接,而由签名者决定其想链接的签名,而强可链接性则要求同一签名者所签消息必须链接。我们分两步来解决该问题:首先,对于基于身份的弱可链接环签名,我们可以利用PKI系统下可链接环签名的设计思想,由签名者自己生成链接标识,方案设计如下:如果一个身份为ID的签名者要链接两个消息的签名,其可随机选择r∈Zp*,并计算rP或者rH(ID)作为链接的标识,然后构建相应的知识证明系统设计环签名方案.我们以Zhang和Kim[49]的基于身份环签名为例,给出了一个具体的基于身份弱可链接环签名方案,然后提出了两个较为有效的方案,一个满足弱可链接性,一个同时满足弱可链接性和可转换性。所提方案满足完备匿名性和适应性选择消息攻击下的不可伪造性。然后,从签名长度和强链接性出发,我们对方案的结果进行了进一步的扩展。在满足弱可链接性的方案中,链接签名的标识由签名者产生,由于基于身份密码系统的特殊性,此设计思想并不适用于基于身份强可链接环签名的设计。我们利用基于双线性对聚合器和基于知识证明签名的设计思想,给出了常数长度满足强可链接性环签名的设计方法。方案中,链接标识是在密钥生成算法中,由PKG利用分发给用户的两个私钥生成而分发给用户,而不是由用户自己产生,从而方案具有可追踪环签名的某些性质,即签名者的身份PKG是可以打开的。不足之处是方案只满足计算匿名性而不满足完备匿名性。最后,我们给出了一个具体的交互式知识证明方案,并证明方案满足一致性,零知识性和鲁棒性。基于该方案,我们可以构造一个具体的基于身份强可链接环签名。3.基于身份的模糊签名目前主流的公钥系统包括PKI密码系统和基于身份密码系统[21]。基于身份密码系统不需要象PKI系统那样花费额外的开销存储和管理公钥证书,也不需要花费额外的时间来验证公钥证书的真伪,从而,基于身份密码系统在许多方面比传统的PKI系统更具优势。以往的基于身份密码系统都将身份看作是与用户信息紧密相关的字符串,如电子邮件地址、姓名等。这里,我们将身份看作是对用户某个描述性属性的集合,例如指纹和虹膜等生物特征。在实际应用中,通常利用生物特征提取用户的私钥。而采用生物特征作为公钥更加符合基于身份密码系统的构架,其比传统的身份特征具有如下的优势:(1.)生物特征是一个人固有的属性,并能被所有者随身携带;(2.)生物特征是唯一的,不存在两个个体具有相同的生物特征。但是由于生物特征的提取存在着一定的噪声,不同时刻提取的信息会存在差异,所以他们并不能被作为公钥而直接应用到目前的基于身份密码系统中。新设计的方案必须能够提供相应的抗公钥噪声差错的能力。Sahai和Waters[59]首先提出了基于身份的模糊加密概念,该方案中允许接收者用自身私钥解密用与生物特征有小出入的公钥加密的密文,也就是说一个密钥可以解密不同的公钥加密的密文,只要这两个公钥满足预先设定的假设条件。本文中,我们提出了基于身份的模糊签名的概念(Zhenfu Cao等[83]同时也提出了该概念,并基于Waters签名提出了标准模型下的方案设计),在该方案中,只要公钥信息ω和ω′满足某个预先设定的条件,则验证者可以利用公钥ω′去验证用ω对应的私钥所签署的签名。利用秘密共享的方法,我们提出了一个基于身份的模糊签名方案,其中公钥的距离定义为集合重合度(Set-overlap)。我们的方案满足随机预言模型下适应性选择消息攻击的弱不可伪造性。4.密钥托管问题密钥托管问题是基于身份密码系统所固有的,也是该系统的一个很大的不利之处。因为PKG知道所有用户的私钥信息,从而其可以解密所有的加密文件或仿造用户进行签名。Boneh和Franklin[22]利用门限技术通过引入多个PKG来解决这个问题,但这样不可避免的会增加通信负担。目前提出许多方案结合传统的PKI系统和基于身份系统的优势[63,64,26],其中,无证书密码系统[26]最受关注。从该概念提出伊始,涌现了大量针对其攻击模型和具体加密签名方案构造方法的研究文章。在一般的无证书的密码系统的密钥生成方案中,首先PKG利用用户身份信息为其生成一个私钥(sk),然后用户自身生成一个私钥/公钥对(sk1/pk1),PKG因不知道用户的私钥/公钥对而无法代替用户进行解密或签名操作。但这样的密钥生成方案造成用户自身生成的私钥/公钥对不唯一,当恶意PKG发布虚假的用户私钥/公钥对时,用户起诉PKG缺乏证据;而且,很多情况下,恶意PKG可以选择特殊的参数信息以获得用户自己选择的私钥。在2007年美密会上,Goyal[73]引入了基于身份的Accountable AuthorityEncryption的概念以削弱密钥托管问题。在该方案中,如果PKG曾经恶意的生成并且散布一个解密密钥的话,那他就将面临被发现并被处罚的危险,因为在其方案中,用户的私钥/公钥对是唯一的,其在和PKG的交互中对自己生成的公钥做了委托而不能更改。基于这样的思想,本文中,我们首先重新定义了无证书公钥系统的密钥生成算法,由用户首先生成私钥/公钥对(sk1/pk1),然后PKG利用用户的身份信息和公钥pk1为其生成另一个私钥(sk),这相当于PKG对用户身份和公钥信息做了一个签名,而用户成功伪造一个合法签名的概率是可忽略的。然后,我们提出了两种可行的密钥生成算法。并基于其中一个算法分别提出了无证书加密方案和无证书签名方案。所提方案分别满足随机预言模型下的可证明安全性,并可以抵抗恶意PKG选择参数攻击。并且,在无证书的签名方案中,如果我们把用户自己生成的部分公钥pk1也看作其签名的一部分,将其作为签名的一部分予以发布,则验证者在只需要用户ID信息的情况下便可以验证签名。通过这样的修改,无证书的签名方案可以转化成为一个完全的抗恶意PKG的基于身份签名方案。从而,基于身份的签名方案可以避免密钥托管问题。
【Abstract】 One of the most important developments from the work on public key cryptography is the digital signature,which has many applications in information security,including authentication,data integrity and non-repudiation. It is the crutial technique and theoretical guarantee to realize secure ecommerce and e-government.In this dissertation,we focus on our research in the following directions of digital signatures:1.Efficient Group Signature Scheme without Random OracleSecurity and efficiency are two crutial factors to evaluate a cryptographic schemes.Until 1999,all provably secure solutions for efficient digital signature schemes relied on the random oracle methodology[11].In the random oracle model(ROM),all parties(the legitimate ones as well as the adversaries) have black-box access to functions behaving like truly random functions, which are out of reach in the real world.The oracle is usually replaced by hash functions,so adversaries may exploit some weaknesses of the hash functions to attack the schemes.And even worse,many results[33]show separations between the random oracle scenario and standard model.As a consequence,a central line of research in modern cryptography is designing efficient schemes provably secure in the standard model.Group signature[15]is a method for allowing a member of a group to anonymously sign a message on behalf of the group,it has the following properties:(1)only members of the predefined group can sign message;(2) anyone can verify the validity of a signature but no one is able to identify which member of the group signed it;and(3)in case of the dispute,the signature can be opened to reveal the identity of the group member who signed it.There were a few group signature schemes provable secure in the standard model.Bellare,Micciancio and Warinschi[39]presented the first construction, but the scheme is too inefficient to be used in practice.Ateniese et.al.[41]proposed an efficient group signature scheme without random oracle under some new strong assumptions.Boyen and Waters[42,44]achieved a constant-size group signature scheme by combining a new NIZK proof techniques and the Waters signature in the standard model[74],but the public key length is too long to be utilized in practice.In 2006,Okamoto[28]proposed a new efficient signature scheme secure in the standard model,whose security depends on the Strong Diffie-Hellman assumptions.Based on this scheme,we firstly give a variant signature scheme of[28]to hide some information,then we present an efficient group signature scheme in the standard model,combining the variant signature scheme with the technique used by Groth,Ostrovsky and Sahai[43]to hide the identity. The security of the new scheme is based on Strong Diffie-Hellman assumptions and Subgroup Decision Assumption.Compared with the scheme presented by Boyen and Waters[44]:(1.)The public key PK in[44]contains about m+4 elements in group G1 where m at least takes 160,and one element in group Gq,while the public key in our scheme includes 4 elements in G1,1 element in Gq.(2.)The signature in our scheme contains 5 elements in G1 and one element in Zn,while the final signature in[44]has 6 elements in G1.(3.)As to the computation,there are about m/2+10 on average multiplicative computation(m+10 at worst case),12 exponentiation computation in[44],while our scheme contains 10 exponentiation computation and 9 multiplicative computation.2.Identity-based Linkable(Convertible)Ring SignatureRing signature[18],is similar to group signature,with the exception that no one else can reveal the identity of the signer.A user can sign anonymously on behalf of a group on his own choice,while group members can be totally unaware of being conscripted in the group.Considering the actual applications,the notion of the ring signature is extended,for example,linkable ring signature[45]and convertible ring signature[47].A linkable ring signature(LRS)additionally allows the signer to have the capacity to make anyone determine whether two ring signatures have been signed by the same group member while still remain the anonymity; and a convertible ring signature(CRS)allows the real signer to convert a ring signature into an ordinary one.In the PKI-based linkable ring signa- ture schemes,the signer can either link arbitrary messages he wants to link (we call it weakly linkable)or all the signatures signed by the same signer must be linked(we call it strongly linkable).Yet,how to construct linkable(convertible) ring signature schemes in the identity-based system is an open problem proposed in[52].In addition,although ring signature has simple group formation,but in most ring signature scheme,the signature size linearly depends on the group size,as the verifier needs to know at least the group descriptions.Thus,the schemes need too much computation which will restrict their application. To deal with designing less complicated schemes,some interesting primitives were used broadly,among which,accumulator scheme is a powerful primitive, and it provides a new method to construct constant size group signature or ring signature schemes.To construct identity-based ring signature with linkable and convertible requirements,we consider the problems in two steps:In the first step,we consider identity based ring signature with weak linkability,i.e.the signer has the right to determine which signatures to link. We can construct the scheme in this way:If the signer with the identity ID wants to link the signatures of two messages,he can choose r∈Zp randomly,and compute rP or rH(ID)as the identification,then construct the corresponding signature schemes based on proof of knowledge.We take Zhang and Kim’s identity-based ring signature scheme[49]as an example,and give a concrete scheme to show how to add linkability to some identity-based ring signatures.Then two efficient schemes are given, one satisfying weak linkability,and the other satisfying both linkability and convertibility.In the second step,considering efficiency and strongly linkable requirement, we extend the work to construct a short constant-size scheme satisfying strongly linkable requirement using accumulator scheme.In our scheme,it is the PKG but not the signer as in the traditional scheme produced the identification. So,the scheme is signer anonymous to all the verifier except for the PKG,and the PKG has the power to open the identity of the signer. In addition,we propose a concrete scheme of Interactive Zero-Knowledge proof system,based on which,we can construct a concrete scheme using the method of Signature Based on Proof of Knowledge. 3.Fuzzy Identity-based SignatureIdentity-based system can provide a more convenient way than the traditional PKI cryptosystem,for not maintaining a list of issued certificates. One common feature of all previous Identity-based systems is that they view identities as a string of characters,such as name or email address.Here,we view identity as a set of descriptive attributes,such as biometric identities, which fits the framework of identity-based system very well.Using the biometric identities,such as the fingerprint,as the identity has the following advantages:(1.)It is an inherent trait and will always be with a person;(2.)It is unique if the underlying biometric is of a good quality.Since biometric measurements are noisy,they can not be utilized in the existing identity-based system directly.The new construction must tolerant the error when extracting the identity each time.Sahai and Waters[59] presented the conception of Fuzzy Identity based Encryption to allow for a private key to decrypt a ciphertext encrypted with a slightly different measurement of the same biometric.In this dissertation,we bring forward of the conception of Fuzzy Identity-based Signature(At the same time,Zhenfu Cao et.al[83]also presented the same conception,and they presented a scheme in the standard model),which allows the verifier with the identity w’ to verify the signature signed with the secret key for the identity w if and only if w and w’ are within a certain distance of each other as judged by some metric.Using the method of secret sharing,we construct a fuzzy identity based signature scheme in the random oracle model using set-overlap as a similarity measure between identities,while in[83],they presented a scheme in the standard model using the structure of Waters signature.Unlike the encryption scheme whose public key size grows linearly with the number of potential attributes, the public key in the signature scheme is simple and constant.And we prove our construction is weakly unforgeable against adaptively chosen message attack.4.Key Escrow ProblemKey escrow problem has been rooted in the identity-based system since its introduction,and it is a significant disadvantage for PKG knows all the secret of the user.In[22],Boneh and Franklin solved this problem to a extent by the introduction of multiple PKGs using threshold techniques,but this inevitable involves extra communication.There are many schemes[63,64,26] to combine the best aspects of identity based cryptography and the public key infrastructure,among which the certificateless public key cryptography is the most noticeable.Since its introduction,a lot of work has been done to research on the attack model and construction methods.In the key generation algorithm defined in the original paper on certificateless public key cryptosystem and followings,first PKG generate one partial secret key(sk)for the user corresponding to user’s identity;then the user generate another partial secret/public key pair(sk1/pk1).This operation makes it impossible to sue the malicious PKG if it replaced the secret/public key pair of the user.In addition,the malicous PKG may choose some special parameters to deduce the secret key that the user set.In CRYPTO 2007,Goyal[73]introduces the concept of Accountable Authority Identity based Encryption(A-IBE)to mitigate the key escrow problem. In his system,if the PKG ever maliciously generates and distributes a decryption key for an identity,it runs the risk of being found and prosecuted, for the user only has one possible decryption key.We first introduced the idea of Goyal to certificateless public key cryptography, and change the operation position of the two secret keys generation, i.e.first the user generate the secret/public key pair(sk1/pk1),then PKG generate another secret key corresponding to pk1 and user’s identity.Thus, the user will only have one possible secret/public key pairs.In addition,we propose two concrete key generation algorithms.Using one of the key generation algorithms,we construct a certificateless encryption scheme and signature scheme respectively,which are secure under the adaptively chosen ciphertext(message)attack in the random oracle modle. In addition,in the certificateless signature scheme,if we regard the public key rP as one of the identity of the user,which will be released as part of the signature,i.e.the verifier can verify the signature only use the ID information, then the scheme is indeed an identity-based signature scheme secure against malicious PKG.