The Research On Digital Signature Schemes

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 G₁ where m at least takes 160,and one element in group G_q,while the public key in our scheme includes 4 elements in G₁,1 element in G_q.(2.)The signature in our scheme contains 5 elements in G₁ and one element in Z_n,while the final signature in[44]has 6 elements in G₁.(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∈Z_p 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(sk₁/pk₁).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(sk₁/pk₁),then PKG generate another secret key corresponding to pk₁ 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.