Similar articles

Abstract: Secret sharing and digital signature is an important research area in information security and has wide applications in such fields as safeguarding and legal use of confidential information, secure multiparty computation and electronic commerce. But up to now, study of signature based on general vector space secret sharing is very weak. Aiming at this drawback, the authors did some research on vector space secret sharing against cheaters, and proposed an efficient but secure vector space secret sharing based multi-signature scheme, which is implemented in two channels. In this scheme, the group signature can be easily produced if an authorized subset of participants pool their secret shadows and it is impossible for them to generate a group signature if an unauthorized subset of participants pool their secret shadows. The validity of the group signature can be verified by means of verification equations. A group signature of authorized subset of participants cannot be impersonated by any other set of participants. Moreover, the suspected forgery can be traced, and the malicious participants can be detected in the scheme. None of several possible attacks can successfully break this scheme.

.  INTRODUCTION

 Digital signatures play an important role in our modern electronic society because they have the properties of integrity and authentication. The integrity property ensures that the received message is not modified, and the authentication property ensures that the sender is not impersonated. In well-known conventional digital signatures, such as RSA and DSA, a single signer is sufficient to produce a valid signature, and anyone can verify the validity of any given signature. However, on many occasions, we need to share the responsibility of the signing message with a set of signers. Issuing checks for a company is an example for this. For the sake of security, it may be a policy of a company that checks must be signed by a group of individuals rather than one person. Secret sharing signature schemes (Gennaro et al., 1996; Safavi et al., 1999) and multi-signature schemes (Harn and Kiesler, 1989; Okamoto, 1988; Harn, 1994b) are designed to solve such problems. There are two major differences between secret sharing signature and multi-signature schemes. Firstly, it is not necessary to restrict the number of signers to generate a valid signature in a multi-signature scheme. In contrast to a multi-signature scheme, a so-called threshold value must be predetermined to guarantee the security of the system in a secret sharing signature scheme. Secondly, a secret sharing signature represents the signature signed by the group while a multi-signature is a signature that represents a set of individuals who sign the message. Consequently, a secret sharing signature is suitable for the case where the members of a group are allowed to sign on behalf of the group.

 But when cheaters appear in signatures, and if we want to detect and trace them, we may need to combine these two signatures to form a new one. We call it secret sharing based multi-signature scheme (Desmedt and Frankel, 1992b).

.  RELATED WORKS

 Since the secret sharing based multi-signature scheme can solve problems that cannot be solved by secret sharing signature and multi-signature scheme individually, much research had been focused on the topic. Desmedt and Frankel (1992b) applied a trusted key authentication center to determine the group’s secret key and the secret keys of all group members. However, Li et al.(1994) pointed out that Desmedt and Frankel’s scheme may suffer from conspiracy attacks and that the secret keys can be revealed if t or more participants act in collusion. To avoid conspiracy attacks, the new proposed schemes (Li et al., 1995) attach a random number to the secret key held by each member, so that the security of their schemes is guaranteed. Similarly, Harn (1994a) used the cryptographic technique of Shamir’s perfect secret sharing which is based on the Lagrange interpolating polynomial and digital signature algorithm to construct a (t, n) threshold signature scheme designed to partition the group’s secret key into n different shadows. By collecting any of the t shadows, the group signature can be easily generated. Michels and Horster (1996) showed that these solutions mentioned above are all vulnerable to forgery attack by an inside attacker and cannot withstand conspiracy attacks. Desmedt and Frankel (1992a) presented another threshold signature scheme based on RSA. But similar to their previous solution (Desmedt and Frankel, 1992b), the secret keys can still be revealed by conspiracy attacks.

 Most of the researches above consider only threshold structures: the system tolerates the presence of less than t corrupted players, and the subsets of players who can sign a message are those with k or more players. To thwart this weakness, Brickell (1989) introduced vector space construction that is more general than the threshold structure. In order to improve the security of vector space secret sharing, Padró and Sáez (1999) proposed a solution that can efficiently find out whether some cheaters exist. However, this solution cannot reveal the cheaters’ identities. Xu et al.(2002) improved Padró’s scheme and presented another secure vector space secret sharing scheme.

 Recently, in order to make the signature scheme more practical and general, Herranz et al.(2003) extended the vector space structure to a so-called general access structure and proposed a framework allowing a general access structure of players to sign and a general family of dishonest players that the scheme can tolerate. Using general access structure, Ventzislav et al.(2001) also built some unconditionally secure proactive secret sharing schemes. But up to now, study of signature based on vector space and general access structure is still very weak.

 Almost all of the signature schemes mentioned above are implemented in one channel. The main contribution of this paper is to design a two-channel secure vector space traceable multi-signature scheme. Security of the signature scheme in each channel is equal to that of an independent one. Malicious users can forge the signature only if the signatures in both channels can be forged. In our designed scheme, when a faulty signature is presented, cheaters can be detected and traced easily. In terms of performance, this scheme should not be less efficient than most of solutions available (e.g., Li et al., 1995; Harn, 1994a; Desmedt and Frankel, 1992a). We organize the rest of the paper as follows. First of all, secure vector space secret sharing scheme is reviewed and analyzed. Then we present our new proposed scheme and analyze its security and efficiency, respectively. At last, we draw our conclusions.

.  SECURE VECTOR SPACE SECRET SHARING

 This section contains some background and formal definitions of vector space secret sharing scheme (Brickell, 1989; Stinson, 1995), which will be referred in the rest of this paper.

 Let T be an access structure on a set of participants P={p₁, p₂, …, p_n} and D∉P a special participant called the dealer. T is said to be a vector space access structure if, for some vector space E=K^r over a finite field K, there exists a function (2)

 and sends to the participant p_i∈P his share (3)

 A scheme constructed in this way is called a vector space secret sharing scheme. Let A∈T be an authorized subset, then we have: for some λ_i∈K. In order to recover the secret, the players of A compute Unfortunately, such scheme is open to the Tompa-Woll attack (Tompa and Woll, 1988). To ensure the security of vector space secret sharing, Padró and Sáez (1999) proposed an improved scheme. The dealer D selects a vector pair (v₁, v₂), such that: , , D computes (1≤i≤n), and delivers to each p_i, i=1, 2, …, n. When is necessary to recover k, all the members in A show their shadows pair and compute k₁= If the equation holds, the recovered secret k₁ is valid. Otherwise, it denotes some participants in A may not be honest.

.  PROPOSED SCHEME

 We assume that there is an honest dealer D to determine the secret and to deliver the secret shadows to all the participants. The word “honest” implies that the dealer must ensure that the secret information is not disclosed or revealed to unauthorized people and prevent unauthorized modification or destruction of data. It is expected that if the dealer is compromised, the security of the whole system will be lost.

 Let us divide our scheme into three phases: the system initialization phase, the partial signature generation and verification phase, the group signature generation and verification phase.

.  System initialization phase

 The honest dealer D selects the following parameters: (1) A huge prime N, 2⁵¹¹<N<2⁵¹² and a generator with order N′ in GF(N), where N′=pq, N′|(N−1), p and q are two large primes, and 2¹⁶⁰<p,q<2¹⁶¹; (2) A one-way hash function h(); (3) Parameters σ_p, σ_q, where

 σ_p=1 mod p=0 mod q (4)

 Additionally, suppose A={p₁, p₂, …, p_l} is the subset authorized to sign a message. We can refer other parameters mentioned before, among which λ_i∈K can be computed by any participants. D computes the group public key delivers to each p_i, i=1, 2, …, n, and publishes N, N′, σ_p, σ_q, g, h, Y, ψ and keeps k₁, v₁, v₂ in secret.

.  Distribution of secret shadows and verification phase

 Each participant p_i in A has to generate a partial signature for message m as follows. p_i picks two random numbers b_ip∈[1, p−1], b_iq∈[1, q−1] and computes his public key pair (y_i1, y_i2) as b_i as (5)

 and r_i as (6)

 It is worth noting here that the public keys of each participant are also regarded as his identity information. Each p_i makes r_i publicly available through a broadcast channel. Once all r_i are available, each p_i can compute (7) (8)

 Then p_i uses his secret shadows and the random number b_i to compute (9)

 p_i sends the partial signature {m, r_i, s_i} to a designated clerk responsible for collecting the partial signatures and producing the group signature. Since no secret information is kept, the clerk can be anyone in the system. The clerk can check whether the equation (10)

 holds. If so, the partial signature from p_i is valid. The correctness of this equation can be easily seen as follows.

 Since we have To achieve traceability, our newly proposed signature scheme should not be forged, which was confirmed in our security analysis later in this paper. Furthermore, the incorrect partial signatures should be detected and identified if the signature is suspected forgery.

 Theorem 1 If the following congruence relation does not hold, then the false partial signature is detected: Proof This is due to the fact that y_i1, y_i2 is regarded as p_i’s public identity. If the participants do not preset bogus secret shadow or tampers with secret shadow, the equation must hold because forging s_i equals to solving the difficult discrete logarithm problem.

.  Group signature generation and verification phase

 When all partial signatures from participants in A={p₁, p₁, …, p_l} are valid, the clerk can compute the group signature: Thus, {m, A, R, S} is the group signature for the message m. Any verifiers can compute: (11)

 and then use the group public key to authenticate the validity of {m, A, R, S} by checking whether the following equation (12)

 holds. If so, the group signature {m, A, R, S} is valid. The correctness of this equation can be easily seen as follows:

 Since , then According to Eq.(11), we have With the help of σ_p, σ_q, we also have Obviously, The signers are anonymous to the verifier because it is not possible to find out the identities of the signers in from the group signature.

.  SECURITY ANALYSIS

 The security of the proposed scheme is based on well-known cryptographic assumptions: the intractability of reversing the one-way hash function (OWHF) and solving the discrete logarithm (DLP). Conspiracy and forgery attacks mentioned by Michels and Horster (1996) as scheme proposed by Desmedt and Frankel (1992b), Li et al.(1995), and Harn (1994a) cannot break our scheme.

 Theorem 2 The secret is secure, and this new scheme is invulnerable to conspiracy attacks.

 Proof Attackers who try to pirate the secret k₁ may include any outside adversaries and inside participants in A.

 Attack 1 Some participants in may cooperate to reveal k₁. Only when all the participants in the authorized subset cooperate with each other, can they recover k₁ through the equation Any other participants in subset who try to pirate k₁ must resolve k₁=v₁˙ψ(D) as follow: where ψ(D)∉<ψ(p₁), …, ψ(p_l′)>. Since v₁, v₂ is kept secret for them in our scheme, no member in A′={p₁, p₁, …, p_l′} will get any useful information about k₁. Similarly, when A′={p₁, p₁, …, p_l−1}⊂A is a set of cheaters who do not know k₁, each p_i in A′ may show his faulty shadow pair , (i=1, 2, …, l−1), where ε,δ∈K, ε≠0 if he wishes to resolve through the following equations Evidently, these cheaters cannot be detected only if , that is, . As a result, the probability that cheaters succeed with faulty (ε, δ) is only 1/q².

 Attack 2 An outside adversary tries to reveal k₁. He has to resolve k₁ through the public key Y= mod N. Obviously, that equals solving DLP.

 Theorem 3 Secret keys for each participant are secure.

 Proof As we know, in the distribution of secret shadows and verification phase, only each p_i’s public keys and are public. Attackers cannot pirate x_i1, x_i2 through other ways. It implies that revealation of x_i1, x_i2 by a cheater equals solving DLP.

 Theorem 4 Forgery attackers will not succeed.

 Proof Firstly, we implement two types of signature in two channels (one type in each channel). Malicious users can forge the signature only if the signatures in both p channel and q channel can be forged. Instead of attaching a random number to the secret key held by each member (Li et al., 1995), this new scheme can withstand conspiracy attacks. The attack described in (Michels and Horster, 1996) may succeed in forging the p channel signatures. However, the q channel signature can avoid this attack since we apply a hash function to the signed messages m and R. This countermeasure can avoid the attack mentioned by Michels and Horster (1996). In fact, we directly adopt the signature scheme proposed in Michels and Horster (1996)’s scheme (refer to its heuristic countermeasures) as our q channel signature; thus, our scheme can withstand the attack presented by Michels and Horster (1996).

 Furthermore, we can check the security of our scheme by resolving the questions given by Li et al.(1995). We omit detailed analysis here because it is very similar to the latter. The reader may refer to that solution for more detailed information.

 Let us consider the case where two members p_i and p_j conspire with each other to change the group signature {m, A, R, S} into {m, A′, R′, S′}, where R′=R, A′=A−p_i+p_j. In this case, the clerk will reject (A′)’s legality without verification of each participant’s partial signature. The reason is that HASH=h(m, R, A) includes the information about the authorized set A. For participants, the signed message is HASH=h(m, R, A). On the other hand, for the clerk, he will compute HASH′=h(m, R′, A′) first and then compute Z′R′^{HASH ′}, where Since HASH≠ HASH′, it is impossible that . Consequently, we can save the cost of partial signature verification.

 Table 1 shows comparison of signature scheme in terms of inherent properties. From this table, we know that our scheme does not need to determine signers and signing order in advance, although we should determine the authorized subset first.

.  EFFICIENCY ANALYSIS

 Data from Table 1 tell us our scheme is similar to that proposed by Li et al.(1995) in terms of properties. So in this Section, we will analyze the new proposed scheme’s efficiency, and compare it with that proposed by Li et al.(1995).

 Let T_e, T_m be the time complexity for computing 160 bits of exponentiation and multiplication, respectively. Because all the exponents except S in our scheme never exceed 160 bits and we assume that the prime factor q is also 160 bits in Li et al.(1995)’s scheme, we may further compare the performance between these two schemes. Considering the computational cost, we need only 2T_e+tT_m and 3T_e+T_m to compute the public verification value and to verify the signature, where computing g^S consumes 2T_e. Similarly, in Li et al.(1995)’s scheme, we need t(T_e+T_m) and 2(T_e+T_m) to compute T and to verify the signature. We optimize in advance the signature generation process (refer to Li et al.’s expression of T and Z in our scheme), and omit (t−3)T_e+T_m in terms of computational cost. Considering the storage cost, we need O(N+p+q) to store both public and secret keys. While in Li et al.(1995)’s scheme, O(2p+q) is needed. According to its assumption, we need 834 bits to store the keys while scheme in Li et al.’s scheme needs 1184 bits. Moreover, we can reduce the storage cost of each member’s public key pair (y_i1, y_i2) using the Chinese Remainder Theorem as follows:

 Let then we have: . Integrating two public keys y_i1 and y_i2 into a single public key Y_i reduces the storage cost by half. However, there is a potential drawback in increasing the computational cost. To derive (y_i1, y_i2) from Y_i, we need some extra computation.

 Considering the communication cost, in the group signature generation process, we need O(n) for participants to communicate with the clerk, which is the almost the same as that in scheme proposed by Okamoto (1988), Li et al.(1995), Desmedt and Frankel (1992a), while in scheme proposed by Harn and Kiesler (1989), Harn (1994b), we need O(n²).

 Table 2 compares signature scheme in terms of computational complexity.




 Obviously, our scheme is more efficient than other similar schemes in terms of verifying the group signature.

.  CONCLUSION

 By implementing the signatures in two channels and choosing the system parameters carefully, we built an efficient multi-signature scheme that extended the ordinary threshold signature scheme successfully. In the new scheme, conspiracy and forgery attackers cannot succeed. We also simplified the group signature verification process, but still ensured its anonymity and traceability.

 Furthermore, this new scheme achieves good extensibility. When applying vector space secret sharing scheme proposed by Xu et al.(2002) into our solution, we can easily construct a three-channel multi-signature, which will strengthen the security more but without loss of its property of anonymity and traceability. Because of space limitation, we will not describe such extended scheme here.

 Similarly, we can even extend our scheme into one that is implemented in n channels, if necessary. Analysis of its feasibility, security and efficiency still remains our future work.