Full Text:   <1241>

CLC number: TP309

On-line Access: 

Received: 2004-01-20

Revision Accepted: 2004-10-29

Crosschecked: 0000-00-00

Cited: 0

Clicked: 3385

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
8. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.1 P.56~62


Applying two channels to vector space secret sharing based multi-signature scheme

Author(s):  Qing-hua Xiao, Ling-di Ping, Xiao-ping Chen, Xue-zeng Pan

Affiliation(s):  . School of Computer Science, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   foxqinghua@etang.com

Key Words:  Vector space secret sharing, Multi-signature, Discrete logarithm, Chinese remainder theorem

XIAO Qing-hua, PING Ling-di, CHEN Xiao-ping, PAN Xue-zeng. Applying two channels to vector space secret sharing based multi-signature scheme[J]. Journal of Zhejiang University Science A, 2005, 6(1): 56~62.

@article{title="Applying two channels to vector space secret sharing based multi-signature scheme",
author="XIAO Qing-hua, PING Ling-di, CHEN Xiao-ping, PAN Xue-zeng",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Applying two channels to vector space secret sharing based multi-signature scheme
%A XIAO Qing-hua
%A PING Ling-di
%A CHEN Xiao-ping
%A PAN Xue-zeng
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 1
%P 56~62
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A0056

T1 - Applying two channels to vector space secret sharing based multi-signature scheme
A1 - XIAO Qing-hua
A1 - PING Ling-di
A1 - CHEN Xiao-ping
A1 - PAN Xue-zeng
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 1
SP - 56
EP - 62
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A0056

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Article Content


 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).


 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.


 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={p1, p2, …, pn} and DP a special participant called the dealer. T is said to be a vector space access structure if, for some vector space E=Kr over a finite field K, there exists a function

 and sends to the participant piP his share

 A scheme constructed in this way is called a vector space secret sharing scheme. Let AT be an authorized subset, then we have: for some λiK. 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 (v1, v2), such that: , , D computes (1≤in), and delivers to each pi, i=1, 2, …, n. When is necessary to recover k, all the members in A show their shadows pair and compute k1= If the equation holds, the recovered secret k1 is valid. Otherwise, it denotes some participants in A may not be honest.


 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, 2511<N<2512 and a generator with order N′ in GF(N), where N′=pq, N′|(N−1), p and q are two large primes, and 2160<p,q<2161; (2) A one-way hash function h(); (3) Parameters σp, σq, where

 σp=1 mod p=0 mod q

 Additionally, suppose A={p1, p2, …, pl} is the subset authorized to sign a message. We can refer other parameters mentioned before, among which λiK can be computed by any participants. D computes the group public key delivers to each pi, i=1, 2, …, n, and publishes N, N′, σp, σq, g, h, Y, ψ and keeps k1, v1, v2 in secret.

.  Distribution of secret shadows and verification phase

 Each participant pi in A has to generate a partial signature for message m as follows. pi picks two random numbers bip∈[1, p−1], biq∈[1, q−1] and computes his public key pair (yi1, yi2) as bi as

 and ri as

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

 Then pi uses his secret shadows and the random number bi to compute

 pi sends the partial signature {m, ri, si} 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

 holds. If so, the partial signature from pi 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 yi1, yi2 is regarded as pi’s public identity. If the participants do not preset bogus secret shadow or tampers with secret shadow, the equation must hold because forging si equals to solving the difficult discrete logarithm problem.

.  Group signature generation and verification phase

 When all partial signatures from participants in A={p1, p1, …, pl} 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:

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

 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.


 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 k1 may include any outside adversaries and inside participants in A.

 Attack 1 Some participants in may cooperate to reveal k1. Only when all the participants in the authorized subset cooperate with each other, can they recover k1 through the equation Any other participants in subset who try to pirate k1 must resolve k1=v1˙ψ(D) as follow: where ψ(D)∉<ψ(p1), …, ψ(pl)>. Since v1, v2 is kept secret for them in our scheme, no member in A′={p1, p1, …, pl} will get any useful information about k1. Similarly, when A′={p1, p1, …, pl−1}⊂A is a set of cheaters who do not know k1, each pi 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/q2.

 Attack 2 An outside adversary tries to reveal k1. He has to resolve k1 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 pi’s public keys and are public. Attackers cannot pirate xi1, xi2 through other ways. It implies that revealation of xi1, xi2 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 pi and pj conspire with each other to change the group signature {m, A, R, S} into {m, A′, R′, S′}, where R′=R, A′=Api+pj. 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 ZRHASH, where Since HASHHASH′, 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.

Table 1

Properties comparison
Scheme Type Signing order predetermined Signers determined in advance Traceability property
Multi-signature Harn and Kiesler (1989) S Yes Yes No
Okamoto (1988) S No No No
Harn (1994b) P No Yes Yes
Threshold multi-signature Li et al.(1995) P No No Yes
Desmedt and Frankel (1992a) P No No No
Vector space secret sharing based multi-signature Proposed P No No Yes
Distributed RSA signature for general access structure Herranz et al.(2003) P No No No

  • S(Serial digital multi-signature scheme; P(Parallel digital multi-signature scheme


     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 Te, Tm 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 2Te+tTm and 3Te+Tm to compute the public verification value and to verify the signature, where computing gS consumes 2Te. Similarly, in Li et al.(1995)’s scheme, we need t(Te+Tm) and 2(Te+Tm) 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)Te+Tm 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 (yi1, yi2) using the Chinese Remainder Theorem as follows:

     Let then we have: . Integrating two public keys yi1 and yi2 into a single public key Yi reduces the storage cost by half. However, there is a potential drawback in increasing the computational cost. To derive (yi1, yi2) from Yi, 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(n2).

     Table 2 compares signature scheme in terms of computational complexity.

    Table 2

    Computational complexity comparison
    Scheme Modulo multiplication Modulo exponentiation Inverse computation
    Li et al.(1995) t+2 t+2 0
    Harn (1994a) op 2t+3 t(1
    Desmedt and Frankel (1992a) t+1 0 0
    Herranz et al.(2003) t t+3 0
    Proposed t+1 5 0

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


     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.


    [1] Brickell, E.F., 1989. Some ideal secret sharing schemes. Journal of Combin Math and Combin Comput, 9:105-113. 

    [2] Desmedt, Y., Frankel, Y., 1992. Parallel Reliable Threshold Multi-signature. Technical Report TR-92-04-02. , (Available from: )http://citeseer.nj.nec.com/frankel92parallel.html,:

    [3] Desmedt, Y., Frankel, Y., 1992. Shared Generation of AuThenticators and Signatures, Advances in Cryptology-Crypto91. Springer, Berlin,:457-469. 

    [4] Gennaro, R., Jarecki, S., Krawczyk, H., 1996. Robust Threshold DSS Signature. , Advances in Cryptology-Eurocrypto96. Springer, Berlin, p.354-371. Harn, L., 1994a. Group-oriented (t,n) threshold digital signature scheme and multisignature. IEEE Proc Computers and Digital Tech, 307-313. (5):307-313. 

    [5] Harn, L., 1994. , :

    [6] Harn, L., Kiesler, T., 1989. New scheme for digital multisignature. Electron Lett, 25(15):1002-1003. 

    [7] Herranz, C., Padr, C., Sez, G., 2003. Distributed RSA Signature Schemes for General Access Structures. , Information Security Conference (ISC03). LNCS.2851, Bristol, United Kingdom, 123-137. :123-137. 

    [8] Li, C., Hwang, T., Lee, N., 1994. Remark on the Threshold RSA Signature Scheme. , Advances in Cryptology-Crypto93, Lecture Notes in Computer Science, 773:773

    [9] Li, C., Hwang, T., Lee, N., 1995. Threshold-multisignature Schemes Where Suspected Forgery Implies Traceability of Adversarial Shareholders, Advances in Cryptology-Eurocrypt94. Springer, Berlin,:194-204. 

    [10] Michels, M., Horster, P., 1996. On the risk of disruption in several multiparty signature schemes. , Proc of the International Conference on the Theory and Applications of Cryptology and Information Security, 334-345. (7):334-345. 

    [11] Okamoto, T., 1988. A digital multisignature scheme using bijective public key cryptosystems. ACM Trans Comput Syst, 6(8):432-441. 

    [12] Padr, C., Sez, G., 1999. Detection of cheaters in vector space secret sharing schemes. Designs, Codes and Cryptoraphy, 16(1):75-85. 

    [13] Safavi, N.R., Wang, H., Lam, K.Y., 1999. A New Approach to Bobust Threshold RSA Signature Schemes, Information Security and Cryptology-ICISC99. Springer, Korea,:184-196. 

    [14] Stinson, D.R., 1995. Cryptography: Theory and Practice, CRC Press, Florida,:343-350. 

    [15] Tompa, M., Woll, H., 1988. How to share a secret with cheaters. Journal of Cryptology, 1(2):133-138. 

    [16] Ventzislav, N., Svetla, N., Bart, P., 2001. Applying General Access Structure to Proactive Secret Sharing schemes. , (Available from: )http://www.esat.kuleuven.ac.be/~snikova/svbj_benelux02.pdf,:

    [17] Xu, C.X., Chen, K., Xiao, G.Z., 2002. A secure vector space secret sharing scheme. ACTA ELECTRONICA SINICA, 30(5):715-718. 

    Open peer comments: Debate/Discuss/Question/Opinion


    Please provide your name, email address and a comment

    Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
    Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
    Copyright © 2000 - Journal of Zhejiang University-SCIENCE