英文论文模板.doc

A new signature scheme with shared verificationJia Xiaoyun1，3 Luo Shoushan2，3 Liu Zhiqing21.School of Continuing Education, Beijing University of Posts and Telecommunications, Beijing 100876, China;2. School of Software Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China;3. National Key Lab. of Integrated Service Networks, Xidian University, Xian 710071,ChinaAbstract: With the differences of users demands, digital signature techniques are being expanded greatly, from the single signature, single verification mode to the multi-users one. This paper presents a new signature scheme with shared verification based on Fiat-Shamir signatures scheme, which is not only suitable for one public key for signature, but can be applied to many public keys situation. In addition, the scheme could resist all kinds of collusion which make it more practicable and safer, and it is more efficient than other scheme.Key word: digital signature; shared verification; verifiable secret sharing1 IntroductionWith the development of computer and network communication technology, and with the difference of users demands, digital signature techniques are being expanded greatly, from the single signature, single verification mode to the multi-users one. For example, a document synchronously needs multiple signatures in some cases, thus it is called multiple digital signatures, existing some schemes have 1,2,3. Sometimes a digital signature needs multiple verifier to verify its correctness, such as 4. In single verifiable signature scheme, the verifier is apt to cause the security performance bottleneck of the whole system. Once he isnt reliable, this will jeopardize the use of the whole secure system. So we can adopt multi-verifiable signature service which have many witnesses, thus it can disperse responsibility and strengthen the system security.Thus we propose the definition of digital signature with shared verification. A digital signature with shared verification only can verify the validity of the signature when all verifiers are honest and cooperative in an access structure. A digital signature with (t, n) shared verification is a special digital signature with shared verification, which enabled any t of the n verifiers to verify the validity of the signature. A digital signature with (t, n) shared verification 4,5 has the following properties:(1) any t of the n verifiers can verify the validity of the signature(2) any t-1 or fewer verifiers cannot verify the validity of the signatureThe first digital signature with (t, n) shared verification was proposed by Soete al. 4 in 1989. In the paper, the construction of the digital signature with (t, n) shared verification was based on a special class of geometric incidence structures, so called generalized quadrangles. The author applies special generalized quadrangles, and its ovoid and special point and liner to structure a digital signature with (t, n) shared verification. The disadvantage of the scheme is inefficient and only can apply the case of one public key for signature.Harn L. proposes a digital signature with (t, n) shared verification 6 based on discrete logarithms. In the scheme, the secret-key of signer is fixed, but the public-key of verification signature is changed with the message. The signer gives a secret share to every verifier respective through a (t, n) threshold secret sharing scheme. Any t of the n verifiers can recover the secret-key of verification signature when they Foundation Item:The National Natural Science Foundation of China(60772110)receive the signature of a message, so they can verify the validity of the signature. Afterwards, 7,8,9 have revised in security question of 6 , thus make it become more and more perfect gradually. 10 proposes a new digital signature with shared verification based on a verifiable secret sharing scheme, but the scheme only applies in one public-key situation for signature, it is nothing in many public-keys situation. There is a proposed digital signature with shared verification in this paper which can solve this question.In the paper, a new digital signature with shared verification is proposed, which was not only suitable for one public key for signature, but can be applied to many public keys situation. In addition, its security and efficiency are not lower than other signature schemes. In the paper, first, we propose a new digital signature with shared verification based on a publicly verification secret sharing scheme and analyze its security, then we analyze the efficiency of the scheme, finally, we generalize its advantage and disadvantage.2 a new digital signature with shared verification2.1 preliminaries (systematic parameter)Suppose p and q are two large primes, N=pq, where for the security of the RSA system it is assumed that p and q are sufficiently large (e.g., 512 digit numbers) 11. and . The secret key of signer A is , public key is , where i=1,2,k. The verifiers is a set of persons who participate in verification. The singer A can choose random a integers from n+2-t,N for verifierthat only can be identity and is a public-known message, where l=1,2,n.The signature scheme 12: (Fiat-Shamir Signatures) In Fiat-Shamir signature scheme, there are two security parameters k and m, and a hash function H that outputs a m*k bit-matrix . The signer A selects at random, and computes , where ,. The public key consists of N and , and the secret key consists of . To sign a message M, for , the signer A chooses at random and computes , and then computes . Finally, for , the signer A computes . The signature is . To verify a signature, one checks that, where .2.2 The sharing scheme of the signers public key among the verifiers We can share the public keys that we need as following, we share here, where i=1,2,k. If the following is no special explanation we can always have i=1,2,k，j=1,2,m, l=1,2,n.(1) A chooses and random for every secret , where and is relatively prime to p-1 and q-1, then computes .(2) Find out that make , where is Euler function.(3) Publish the public-known andfor secret . Every verifier chooses a integer from 2, N at random, and computes . Then the verifier keeps the secret and sends to the signer A.(4) Use n+1 points and Lagrange polynomial interpolation method 13 to construct n degree polynomial :We can see easily there are k polynomials.(5) Compute and publish . The above method can regard as a publicly verifiable secret sharing scheme, it can efficiently prevent that the dealer sends a wrong share to the participant and identify the participant who offer wrong share when resume secrets.2.3 Signature generationWhen the signer A signs for message M, A firstly chooses the generator g in which satisfy , then chooses at random and computes and . Finally, A computes .So the signature is, verifiable formula is, where .2.4 Signature verificationTheory: When receive the signature of the signer A and shares from A, any t of the n verifiers can verify that the signature is validity or not. We can assume that is the t verifiers here. The detailed process is as following: We assume all i=1,2,k, v=1,2,t if there is no special explanation. Every verifier can use his secret to compute his share, any entity can verify that the verifier offer real share or not. If is true, honestly offer share, in other words is right. When all are verified, we can use k*(n+1) points and Lagrange polynomial interpolation method to resume n degree polynomials. For simpleness, we use to denote the k*(n+1) points, where u=1,2,n,n+1, i=1,2,k. Then we can resume n degree Lagrange polynomial :So we can resume the shared verifiable public keys , then we can verify the validity of the signature through verifying , where .Proof: The security of the proposed scheme bases on the security of Fiat-Shamir signature scheme and the verifiable secret sharing scheme. The security of Fiat-Shamir signature scheme can be seen from 12, and the security of verifiable secret sharing scheme bases on the difficulty of computing discrete logarithm and factoring large numbers. Now we analyze the security of the proposed scheme in detail.As to a digital signature with (t, n) shared verification, it is a basic request that any t-1 or fewer verifiers cant verify the validity of the signature. In the proposed scheme, we only need to explain that any t-1 or fewer verifiers cant resume the verifiable public keys. Because we want to recover the n degree polynomial, we need to know k pairs n+1 points , where , u=1,2,t. But any t-1 or fewer verifiers cant find such n+1 points, so they cant verify the validity of the signature.In the proposed scheme, every participant offers a share for the signer which he computes through his secret, he neednt offer his secret, we can know it is impossible that compute the secret from his share because of the difficulty of computing discrete logarithm. Thus the secret can repeatedly apply. On the other hand, the attacker can try to attack from the public message of participant. The public message is computed by, so we can consider that execute decryption algorithm of RSA algorithm: N is the modulus, is the secret key, g is the cipher-text, is the plain-text. It is impossible that the attacker wants to computer the secret key of participant because of the same reason. Whats more, because the secret of every participant is only computed by himself, other participant even knows the share about the others secret message, he still cant compute the share of about the message. So it is assured that only t or more verifiers should verify the validity of the signature. Further, the proposed scheme neednt special verifiable algorithm, it can verify that every participant is honest or not when recover secret key. In other words, we can decide that the participant honestly offer the share or not through. Now, we can explain the reasonableness of the verifiable algorithm. We can know from Euler theory 11, but , so we can obtain.So if is honest, we can obtain, where l1，2n.Now we explain the logicality of the signature verification algorithm. We can easily see we only need to prove, where, in other word we need to prove , but where we apply to, so we can see the logicality of the signature verification algorithm in proposed scheme.We can see that the proposed scheme is a secure signature scheme with shared verification from above proof.3 efficiency analysis We can easily find that the proposed scheme take most time in polynomial interpolation arithmetic and modular exponential arithmetic. So the improvement of efficiency in the proposed scheme mostly depends on how to effectively calculate polynomial interpolation arithmetic and modular exponential arithmetic. Many papers have already researched the two question and gain many successes. For example 13 proposed an effective method of polynomial interpolation arithmetic which the calculated complication is; 14, 15 advanced some effective methods of modular exponential arithmetic. We can enhance efficiency of the proposed scheme through those methods. Suppose TD denotes calculated complication of modular exponential arithmetic, we can gain that the calculated complication of the proposed scheme is . We can see that the proposed scheme is very effective from above analysis.4 Conclusion In the paper, we propose a new digital signature with shared verification which has some special properties: (1) The length of participants share is equal to the length of the shared secret. (2) The secret of participant is totally chosen by the participant himself, the signer dont know the participants share. (3) The signer has fixed secret key and perennial public key, and the share of every verifier can be publicly verifiable, so we can prevent failing verification because of the wrong share of a verifier. (4) The proposed scheme is not only suitable for one public key for signature, but can be applied to many public keys situation. The proposed scheme can efficiently get over the secure limitation of other digital signature with shared verification 10, and can be applied to many public keys situation. It can offer security for the signer and the verifiers and is a practice scheme. But the scheme has some limitations, such as the scheme need to construct k polynomials, this make higher calculated complication.Reference1 J Subhlok, B Yang. A New Model for Integrated Nested Task and Parallel ProgrammingJ. ACM SIGPLAN NOTICES, 1997, 32(7):1-12.2 Harn L. Group-oriented (t,n) Threshold Digital Signature Scheme and Digital MultisignatureJ. IEE Computers and Digital Techniques, 1994, 141(5):307-313.3 Li Weike, Li Fangwei. Digital Multi-signature Scheme Based on Schonorr SignatureJ. Jouranl of Chongqing University of Posts and Telecommunications, 2005, 17(3):336-338.4 De S M, Quisquater J J, Vedder K. A Signature with Shared Verification SchemeA. Advances in Cryptology 2CRYPTOp89C. Berlin Soringer2Verlag, 1989. 253-262.5 Simmons GJ. Anatural Taxonomy for Digital Information Authentication SchemeA. Advance in CryptologyCRYPTO87 C. Berlin SpringerVerlag, 1987. 269-288.6 Harn L. Digital Signatuer with (t,n) Shared Verification Based on Discrete LogarithmsJ. Electron Lett, 1993, 29(24):2094-2095.7 Lee WB,Chang C C. Comment: Digital Signature with (t,n) Shared Verification Based on Discret LogarithmsJ. Electron Lett, 1995, 31(3):176-177.8 Harn L. Comment on “Digital Signature with (t,n) Shared Verification Based on Discrete Logarithms” and replyJ. Electron Lett,