Design And Analysis Of Threshold Signature Scheme

With rapid popularization and development of computer networks, normal personal signature schemes cannot satisfy the needs of many special application environments. In group-oriented cryptosystems, it is important and indispensable to execute the group's signing right by a qualified combination of members, e.g. a corporation's important contracts should be signed cooperatively by the president and other t directors. In order to meet the above-mentioned requirements, Desmedt and Frankel presented the concept and the first scheme of threshold signature in 1991. And since then, research on threshold signature schems has become a hotspot in cryptography. As the primary branch of group-oriented signatures, threshold signature is based on secret sharing technology and is provided with the fascinating properties of duty partaking, right distributing and trust sharing, so research on it has not only theoretical significance but also practical values.In this thesis, research on threshold signature schemes is focused on the following aspects: firstly, analyzes the security of some previously presented schemes in literatures and proposes new attacks; secondly, designs new threshold signature and signcryption schemes with stronger security properties and higher efficiency; thirdly, studies the applications of secret sharing and threshold signatures in virtual enterprises. The main contributions of this thesis are given as follows:In Chapter 3, a new secret sharing scheme based on operations in integer matrix is proposed. In this new scheme, the group's secret key is reconstructed through series of integral arithmetic operations in integer matrix, and no computation of any element's inverse in any algebraic structure is needed, which builds up the foundation of constructing efficient RSA-based threshold signature schemes.Based on the above new secret sharing scheme, an efficient and robust threshold RSA signature scheme is then constructed. Different from previously presented threshold RSA signature schemes, this new scheme can effectively avoid computation of any element's inverse in any algebraic structure (such as Z_φ(N) and Z_N), which makes the complicated algebraic extension, parameter constraint and inversion pre-computation all unnecessary. So this new scheme is not only more efficient than the previous ones, but also conduces to protect the large number N from factorizing. In addition, this new scheme has the property of robustness by employing verifiable secret sharing technology and Gennaro's non-interactive partial signature verification protocol.In Chapter 4, the security of an ElGamal type threshold signature scheme proposed by Wang and Li in 2003 (WL scheme for short) is first analyzed. It is found that WL scheme is not only vulnerable to conspiracy attacks, but also has another more serious weakness: sinceλ_i,j(ij=1,2,...,n; i≠j) are transmitted in broadcast fashion, any malicious attacker can easily acquire more than t values ofλ_i,j, with which he can further compute U_i's(t=1,...,n) secret key f_i(0) and the group's secret F(0). On this security flaw, two new forgery attacks and their corresponding conspiracy attacks are further given.Then, the security analysis is given on the improvement of WL scheme, which was presented by Xie and Yu in 2005 (XY scheme for short). It is pointed out that the signers' real identities cannot be tracked out by the tracing function of XY scheme, and this scheme's efficiency is very low due to the invalid redundancy information. Furthermore, both the distributed key generation protocols of WL scheme and XY scheme are insecure because the group's secret can be acquired by the t members in advance.In order to overcome the weaknesses of WL scheme and XY scheme, a new conspiracy attack immune (t,n) threshold signature scheme with traceability is proposed. Security analysis shows that this new scheme can not only resist the above-mentioned conspiracy attacks and forgery attacks essentially, but also provide anonymity and traceability simultaneously. Moreover, by constructing a secure distributed key generation protocol, the proposal realizes the unknowability of the group's secret. So, this new scheme is more secure than WL scheme and XY scheme. In addition, its efficiency is much higher than XY scheme and equivalent to WL scheme.In Chapter 5, a novel security enhanced generalized threshold signcryption scheme is presented, which can remedy all the security flaws existed in two previously proposed schemes (WCL scheme and TJC scheme). This new scheme can radically realize the characteristic of generalized threshold signcryption, i.e. (t,n) threshold signcryption and (k,l) threshold designcryption, and by means of Chaum-Pedersen discrete logarithm equation knowledge protocol, it can detect malicious members' deceitful behaviors. Further security analysis shows that this new scheme can resist all the attacks proposed in previous literatures, so its security is much higher than WCL scheme and TJC scheme.In Chapter 6, the theory and technology of secret sharing and threshold signature are used to construct a generalized variable privilege sets based trust-interaction scheme for Virtual Enterprise (VE for short), which can felicitously satisfy the special requirements of VE such as isomerism, provisionality, dynamic composition, automation and low-cost etc. In the proposed scheme, members' privilege sets are assigned flexibly according to the actual organization structures existed in different VEs, and they can also be dynamically adjusted when new members join in or old members drop out. The proposal is a generalized virtual CA resolution, and by constructing a series of changeable-number party protocols it can effectively solve the trust-interaction problem in VE with different organization structures. Relatively, the previously proposed LDZ scheme and LP scheme can just be regarded as two particular cases of this generalized scheme, because they are only applicable to two specific organization structures of VE.