# Cryptanalysis and Performance Evaluation of Enhanced Threshold Proxy Signature Scheme Based on RSA for Known Signers

Authors: Raman Kumar; Harsh Kumar Verma; Renu Dhir
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

In these days there are plenty of signature schemes such as the(t,n) threshold proxy signature scheme (Kumar and Verma 2010). The network is a shared medium so that the weakness security attacks such as eavesdropping, replay attack, and modification attack. Thus, we have to establish a common key for encrypting/decrypting our communications over an insecure network. In this scheme, a (t,n) threshold proxy signature scheme based on RSA, any t or more proxy signers can cooperatively generate a proxy signature while t-1 or fewer of them cannot do it. The threshold proxy signature scheme uses the RSA cryptosystem to generate the private and the public key of the signers (Rivest et al., 1978). Comparison is done on the basis of time complexity, space complexity, and communication overhead. We compare the performance of four schemes (Hwang et al. (2003), Kuo and Chen (2005), Yong-Jun et al. (2007), and Li et al. (2007), with the performance of a scheme that has been proposed earlier by the authors of this paper. In the proposed scheme, both the combiner and the secret share holder can verify the correctness of the information that they are receiving from each other. Therefore, the enhanced threshold proxy signature scheme is secure and efficient against notorious conspiracy attacks.


---

## Body

## 1. Introduction

Today Internet is an inseparable part of our life and millions of people will be using the Internet. Reading the news, chatting with friends, purchasing a new product, and researching for a paper, the number of uses of the Internet is endless. One of the attractions of the Internet is that one can do almost anything from the comfort of his/her own home and with a relative sense of anonymity.Unfortunately, the data going across the Internet may not be as secure as we would like to think. It is not especially difficult for a person with the right technical skills to intercept the data going from one computer to another. Usually this is not a problem; people do not really care if someone knows that they went tohttp://www.google.com/ and started researching Number Theory. However, if the intercepted data contains a credit card number, password, social security number, or some other private information, it becomes a whole different story.Online banking and a host of other services rely heavily upon the security of credit card numbers, PINs, and other private information as it goes across the network. But if it is easy to intercept these numbers, how do these services work? The answer is cryptography.In today’s commercial environment, establishing a framework for the authentication of computer-based information requires a familiarity with concepts and professional skills from both the legal and computer security fields. Combining these two disciplines is not an easy task because concepts from the information security field often correspond only loosely to concepts from the legal fields, even in situations where the terminology is similar. For example, from the information security point of view, “digital signature” means the result of applying to specific technical processes. The historical legal concept of “signature” is broader. It recognizes any mark made with the intention of authenticating the marked document [1].In this research paper, we discuss threshold proxy signature scheme. In a(t,n) threshold proxy signature schemes, an original signer delegates a group of n proxy signers to sign message on behalf of him or her. When the proxy signature is created, t or more proxy signers cooperate to generate valid proxy signatures and less than t proxy signers cannot cooperatively produce valid proxy signatures. In essence, we have tested our enhanced threshold proxy signature scheme by undergoing some fruitful attacks.


## 2. Review of Threshold Proxy Signature Schemes

### 2.1. History of Threshold Proxy Signature Schemes

In the history of proxy signature technological development, the(1,n) threshold proxy signature technique was the first to come. In (1,n) proxy signature schemes, a legal proxy signature can be generated by a designated proxy signer by using a proxy signing key. The proxy signing key is computed from the original signer’s private key, but the private key should not be computed from the proxy signing key in any way. In the eye of a modern user, such schemes are simple but not flexible. In order to extend proxy signature schemes to fit various practical situations, many (t,n) threshold proxy signature schemes have been proposed. For example, we have (t,n) threshold proxy signature schemes that allow any t or more proxy signers from a designated group of n members to cooperatively sign messages, while t-1 or fewer members cannot generate the legal proxy signature. In practice, the original signer can flexibly choose the threshold t. The approach agrees with (1,n), (t,n), and (n,n) threshold delegations.Rivest et al. [1] and Blakley firstly proposed the (t,n) threshold secret sharing scheme based upon Lagrange interpolating polynomial and linear projective geometry, respectively, in 1979. In a (t,n) threshold secret sharing scheme, secret holder delivers the distinct secret values (called shares or shadows) to n participants. At least t or more participants can combine their shares and reconstruct the secret, but only t-1 or fewer members cannot. Based on these properties, secret sharing is an important part of modern cryptography and has been used in many fields of modern cryptography. In 1996, Mambo et al. [12] proposed the concept of proxy signature. In their schemes, the original signer can delegate his/her right to the proxy signers who can sign the message instead of the original signer.Recently, many threshold proxy signature schemes were proposed. The history of threshold proxy signature schemes is made up in Table1.Table 1
History of threshold proxy signature schemes.
Serial  number
Scheme
Method
1
Rivest et al.  [1]
The Lagrange interpolating polynomial and linear projective geometry
2
ElGamal [2]
Discrete logarithms
3
Desmedt and Frankel [3]
RSA and Lagrange coefficient
4
Zhang [4]
Discrete logarithms
5
Kim et al. [5]
Discrete logarithms
6
Sun et al. [6]
Discrete logarithms
7
Lee(2001)
Discrete logarithms
8
Hwang et al. [7]
RSA and Lagrange coefficient
9
Wang et al. [8]
RSA and Lagrange coefficient
10
Kuo and Chen [9]
RSA and Lagrange coefficient
11
H. Jiang (2007)
RSA and Lagrange coefficient
12
Fanyu (2007)
RSA and Lagrange coefficient
13
Li et al. [10]
RSA and Lagrange coefficient
14
Yong-Jun et al. [11]
RSA and Lagrange coefficientThe concept of threshold cryptosystems was also brought up by Denmedt and Frankel in 1991. They adapted the ElGamal public key cryptosystem and used the Lagrange interpolation or geometry to produce shadows.To make proxy signature applicable to group-oriented situations, Sun [13] and Kim et al. [5] proposed a (t,n) threshold proxy signature in 1997, which is a variant of proxy signature by using the ideas of secret sharing and threshold cryptosystems. The basic strategy used in Kim et al.’s scheme is a random number generation.


### 2.2. Review of Kim et al.’s Scheme

#### 2.2.1. The Random Number Generation Phase

This scheme requires a protocol to generate a random number among the group without the dealer. LetP0 be the original signer, and let P1,P2,…,Pn be the n proxy signers of the proxy group.(1)
Each proxy signerPi selects  secret polynomial of degree t-1 such that
(1)fi(x)=ri+ai,1x+ai,2x2+⋯+ai,t-1xt-1modq,where ri, ai,1, ai,2, and ai,t-1 are random numbers.(2)
Then, eachPi computes fi(j) mod q and sends it to Pj for all 1≤j<n and j≠n. Furthermore, Pi computes
(2)gri,gai,1,gai,2,…,gai,t-1(modp)
and broadcasts them.(3)
After receivingfj(i) (for j=1,2,…,n and j≠i), Pi confirms that the validity of fj(i) by checking whether or not gfj(i) satisfies the following equation:
(3)gfj(i)=grj×((gaj,1)i)1×⋯×((gaj,t-1)i)t-1modp.(4)
If the verifications in Step 3 hold, eachPi computes the secret share
(4)Si=∑j=1j=nfj(i)
and computes public outputs
(5)r=∏j=1j=nrjmodp,ga1=∏j=1j=ngj,1modp,ga2=∏j=1j=ngj,2modp,⋮gat-1=∏j=1j=ngj,t-1modp.


#### 2.2.2. The Proxy Sharing Phase

(1)
Group Key Generation. First, the proxy group must execute the above protocol to obtain the share si and the public outputs yG=ga0 mod p, Aj=gaj mod p, where
(6)j=1,2,…,t-1.
(2)
Proxy Generation. The original signer computes K=gk mod p and e=h(mw,K), where k is a random number, mw is a warrant, and h() is one way hash function. After this, P0 computes
(7)σ=e×x0+kmodq,
where x0 is a private key of the original signer.
(3)
Proxy Sharing.
P
0 randomly chooses a polynomial such that
(8)f′(x)=σ+b1x+b2x2+⋯+bt-1xt-1,
where b1, b2, bt-1 are random numbers. Then, P0 computes f′(i) and sends it to each Pi in a secret manner; P0 also computes
(9)B1=gb1,B2=gb2,…,Bt-1=gt-1(modp)
and publishes mw,K,B1,B2,…,Bt-1(modp).
(4)
Proxy Share Generation. After receiving f′(i), each Pi has to validate f′(i) using
(10)gf′(i)=(y0)h(mw,K)K∏j=1t-1((Bj)i)jmodp,
where y0 is the original signer’s public key. If it holds, each proxy signer, Pi, computes the proxy sharing
(11)σi′=f′(i)+si×emodq.


#### 2.2.3. The Proxy Issuing and Verification Phase

(1)
Thet or more actual signers have to execute the random number generation phase to obtain the secret output si′ and public outputs
(12)y=gc0,C1=gc1,C2=gc2,…,Ct-1=gct-1(modp),
where
(13)si′=f′(i)=c0+c1i+c2i2+⋯+ct-1it-1.
(2)
Then each actual signer uses his proxy signature key to issue a partial proxy signature such thate′=h(y,m) and γi=si′+σi′×emodq, where m is message. Then, each actual signer reveals γi.
(3)
Everyone can verify the validity ofγi by the following equation:
(14)gγi=(y∏i=1t-1(Ci)j)i×(y0)h(mw,K)K∏i=1t-1((Bi)j)imodp×yG∏i=1t-1(((Ai)j)ih(mw,K))h(y,m)modp.
(4)
If the previous verification holds, the signature, onm is (m,T,e′,k,mw), where T=c0+σ×e′=f′(0)+f(0)×e′ can be computed by applying the Lagrange formula.
(5)
To verify the validity of the signature, anyone can examine the following equation:(15)y′=gT×((y0)h(mw,K)K)-eimodp,e′=h(y′,m).


### 2.3. Security Analysis of Kim et al. and Related Schemes

The Kim et al.’s [13] scheme has been shown insecure by Sun et al. [6] using the public key updating attack. Kim et al. proposed two types of threshold proxy signature schemes, which were the proxy-protected scheme and the proxy-unprotected scheme. In the proxy-protected scheme, the original cannot impersonate a proxy signer to issue a valid proxy signature. The proxy signing key combines the original signer’s secret sharing key and a secret value among the t proxy signers. Therefore, the original signer cannot obtain the proxy signing keys. This property is called proxy-protected. One major drawback in Kim et al.’s scheme is that the actual signers cannot be identified. This can be very inconvenient for internal auditing. Kim et al.’s scheme does not satisfy the known signer’s requirement, proxy protection requirement, and the time constrain requirement. It does not satisfy the known signer’s requirement as the actual signer cannot be identified. Also, it is necessary for a verifier to use the public information to check the validity of proxy signature. If the pubic information is not authenticated, the original signer is able to execute the (t,n) threshold proxy signature scheme to generate a valid proxy signature key by himself; that is, he plays the roles of the original signer and the proxy signers simultaneously. This is because a verifier is unable to distinguish whether the public information is created by the legal proxy group or by others (a dishonest original signer or unauthorized group). Hence, it does not satisfy the proxy protection requirement. This scheme does not have the ability to put time constraints on the threshold delegation.In order to remedy the problem of unknown signers, Sun et al. [6] revised Kim et al.’s [13] proxy-protected type threshold proxy signature scheme and made the actual signers able to be identified. Sun et al.’s scheme is also insecure since any n-1 proxy signers in the group can conspire to obtain secret key needed by the remainder of the group. Also, the computational as well as communicational overhead of Sun’s scheme is high. With t or more proxy signers, it issues a proxy signature which has to generate and share a random number among them. In essence, it requires several expansion modular exponential computations and communications.Unfortunately, Zhang’s scheme [13] has also shown to be insecure by Lee, Hwang, and Wang. They have shown a dishonest proxy signer can cheat to get a signature which is generated by the original signer on any message with the condition that a conventional digital signature scheme is a variation of ElGamal type signature.In 1991, Desmedt and Frankel proposed a threshold RSA signature scheme. This technique allowst out of n individuals to generate a signature for a message. The signature is on the behalf of group of n members; hence, we also call it group signature. Rivest et al. [1] extended the concepts and principles from Desmedt and Frankel’s threshold RSA signature to develop a threshold RSA proxy signature scheme.In 1999, Okamoto et al. [14] also suggested an enhanced proxy signature scheme based on both the Mambo-Usuda-Okamoto and Kim-Park-Won schemes. Later on, Sun, Lee, and Hwang examined the security of the Sun-Hsieh scheme based on the Kim-Park-Won scheme and proved that the scheme is not nonrepudiable. And also, a slightly modified version was suggested by them.Hwang et al. [7] have shown that Sun’s scheme has a security weakness. An adversary can impersonate a legal proxy signer to generate a proxy signature and the real proxy signer cannot deny having signed the proxy signature.Lee et al. [15] have proposed the generalization of the (t1/n1-t2/n2) proxy signature scheme based on factorization of the square root modulo of a composite number. They proposed three kinds of proxy signature schemes:  the (t/n-1), the (1-t/n), and the (1-1) proxy signature schemes. In this, the actual original signer cannot deny delegating the warrant or proxy signature either.Tzeng et al. [16] have proposed a batch verification scheme for multiple proxy signature to reduce proxy verification time. The proposed scheme is not efficient because it does not verify each proxy signature separately, but somehow it is secure because it can detect forged multiple proxy signatures without failure.Hwang et al. [17] have proposed a multiproxy multisignature scheme which allows any u or more proxy signers from a designated group of v proxy signers to sign messages on behalf of any t or more original signers from a group of n original signers in total. In this, they only make (u,v) proxy signers to sign on behalf of them.Lu et al. [18] have proposed a proxy signature scheme which allows the original signer to revoke delegations whenever necessary. In this, the authentication server will not issue the time-stamp unless the delegation has not been revoked or the delegation period specified in the warrant has not expired.Yang et al. [19] have proposed an improvement of Hsu et al.’s scheme that is somewhat efficient in terms of computational complexity and communication cost. Different from Hsu et al.’s, the original signer only computes a common proxy share and broadcasts it to the proxy group. As compared with Hsu et al.’s scheme, the secret shares calculations is not required.Tzeng et al. [20] have proposed a threshold multiproxy multisignature scheme with (t3,n3) shared verification. They have proposed the security on the basis of one-way hash function and discrete logarithm problem. They considered only a few attacks.Tzeng et al. [21] have presented security analysis of the Hwang-Lin-Lu scheme. The Hwang-Lin-Lu scheme is vulnerable to forge attack.Hwang et al. [22] have presented a generalized version of proxy signature scheme. A generalization version of the (t1/n1-t2/n2) proxy signature scheme is based on the elliptic curve discrete logarithm problem only. In this paper, the actual original signer cannot deny delegating the warrant or the proxy signature.In 2001, Hsu et al. proposed a nonrepudiable threshold proxy signature scheme. Tsai et al. [23] proposed a scheme to remedy the weakness of the Hsu-Wu-Wu scheme. In this, neither the original signer nor a malicious proxy signer can forge the legal proxy signature.Li et al. [24] have presented a generalized version of proxy signature scheme. A generalization version of the (t1/n1-t2/n2) is based on the discrete logarithm problem only. They discussed three kinds of proxy signature schemes:  the (t/n-1), the (1-t/n), and the (1-1) proxy signature schemes. The actual original signer cannot deny delegating the warrant or the proxy signature.Hwang et al. [25] have discussed Hwang and Shi’s scheme without using a one-way hash function. In their scheme, an original signer needs not send a proxy certificate to proxy signer through secure channels. This scheme is vulnerable to the public key substitution attacks.Hwang et al. [26] have presented a cryptanalysis of Sun’s threshold proxy signature scheme. They have shown only that the secret key can be compromised by collusion attack.Raman Kumar et al. [27] have presented a new scheme which includes the features and benefits of four schemes: Hwang et al., Wen et al., Geng et al. and Feng et al. They have compared these schemes and optimized their own proposed scheme on the basis of different parameters.


### 2.4. Review of Hwang et al.’s Scheme

In the HLL scheme, Hwang et al. [7] proposed a practical and efficient (t,n) threshold proxy signature scheme based on the RSA cryptosystem. This scheme uses only an RSA digital signature scheme and a simple Lagrange formula to share the proxy signature key.There are three types of participants in the scheme: the original signer, then proxy signer, and the combiner. The original signer allows a group of n proxy signers to sign a message. The combiner can be the secretary of the original signer. The proposed threshold proxy signature scheme can be divided into three phases:(1)
The proxy sharing phase;(2)
The proxy issuing phase;(3)
The verification phase.In the proxy generation phase, the original signer computes the partial proxy signing keys from his private key and sends them to each designated proxy signer. In the proxy signature issuing phase, the proxy signers cooperatively create a valid signature on a messageM. In the verification phase, the verifier can identify not only the original signer, but also the actual signers. P0 stands for the original signer and P1,P2,…,Pn stand for the n proxy signers. Ni is a public RSA modulus for Pi such that Ni is a public RSA modulus for Pi and Ni=pi×qi, where pi and qi are two secret large primes, while di is the private key for Pi and its corresponding public key is ei, such that di×ei=1 mod Φ(Ni), where Φ(Ni)=(pi-1)×(qi-1). The parameters ei and Ni can be published. The parameters di and Φ(Ni) are kept secret by the holder. [M]dimodNi represents M signed with Pi’s private key di, and [M]eimodNi represents M encrypted with Pi’s public key ei using the ordinary RSA cryptosystem. The message mw stands for a warrant that is minted by the original signer and it contains important information such as the validity period of the proxy key, the identities of the proxy signers, and the original signer. In the proposed scheme, let N0<Ni(i=1,2,…,n).


#### 2.4.1. The Proxy Sharing Phase

Assume that an original signerP0 delegates the power to sign messages to n members during s stipulated period. The steps to generate the proxy key are as follows.(
1
)
Proxy Generation.
P
0 produces the group proxy signing key D and proxy verification key E, where
(16)D=d0mwmodΦ(N0),E=e0mwmodΦ(N0),
where mw=(P+T+r) mod Φ(N0).P is the validity period of proxy signatures, T is the sum of identities of P0,P1,…,Pn, and r is a random number.ThenP0 publishes {mw,E,[mw,E]d0modN0}.(
2
)
Proxy Sharing.
P
0 selects a t-1 degree polynomial,
(17)f(x)=D+a1x+⋯+at-1xt-1modΦ(N0),
where a1, a2,…,at-1 are random numbers. Meanwhile, P0 calculates proxy signer Pi’s partial proxy signing key ki=f(i) and sends [[ki]d0modN0,ki]ei mod Ni to the proxy signer Pi.


#### 2.4.2. Proxy Share Generation

When proxy signerPi receives [[ki]d0modN0,ki]ei mod Ni, he or she can get {[ki]d0modN0,ki} by his or her secret key di. And then Pi confirms the validity of ki and keeps it secret.(
1
)
The Proxy Signature Issuing Phase. Let T denote the group members including any t or more proxy signers who want to generate a proxy signature on message M on behalf of P0 cooperatively. Each proxy signer Pi uses the partial proxy signing key ki to generate the partial signature
(18)si=MkimodN0.
Then Pi sends {[si,i]dimodNi,si} to the combiner.When the combiner receives all partial signaturesi from Pi, firstly, he or she verifies the validity of the partial proxy signature by checking if [si,i]di·eimodNi=(si,i) or not. If all partial signatures are valid, the combiner computes the value of
(19)v=∏IDa,IDb∈Ta>b(IDa-IDb),vLi=∏IDa,IDb∈Ta>b(IDa-IDb)∏j=1,j≠it(-IDj(IDi-IDj)).
Here,
(20)∏j=1,j≠i(IDi-IDj)isafactorof∏IDa,IDb∈Ta>bt(IDa-IDb).SovLi is an integer and the combiner need not compute the inverse of
(21)∏j=1,j≠it(IDi-IDj).Finally, the combiner generates the signatureS as follows:
(22)S=∏i∈TsivLimodN0.The result of proxy signature is{v,S}.


#### 2.4.3. The Proxy Signature Verification Phase

The verifier can verify the signature signed on behalf of the original signer by the following equation:(23)SE=MvmodN0.The original signer can differentiate the actual signer from the signaturesidieimodNi=si. Then the original signer can trace the actual signers by ei.


### 2.5. Conclusions from the Threshold Proxy Signature Schemes

All analyses indicated that the scheme fails to satisfy all the requirements except one or two. So, an enhanced threshold proxy signature scheme must satisfy all of the following basic requirements which can be called proxy requirements [7, 9–11].(
1
)
Secrecy. The original signer’s private key is very important. It must be kept secret. If it is discovered, the security of the system is ruined. Therefore, the system must ensure that the private key never gets derived from any information such as the sharing of the proxy signing key or the original signer’s public key. Furthermore, no proxy signers should be able to cooperatively derive the original signer’s private key.(
2
)
Proxy Protected. Only a delegated proxy signer can generate his partial proxy signature. Even the original signer cannot masquerade as a proxy signer to generate a partial proxy signature. This property protects the authority of the proxy signer.(
3
)
Unforgeability. A valid proxy signature can only be cooperatively generated by t or more proxy signers. Nondelegated signers have no capability to generate a valid proxy signature. Also, (t-1) or less proxy signers have no capability of forging a valid proxy signature.(
4
)
Nonrepudiation. Any valid proxy signature must be generated by t or more proxy signers. The verifier can make sure that the signed message is a correct one by using the proxy signing keys. The original signer cannot deny having delegated the power of signing messages to the proxy signers. Furthermore, the proxy signers cannot deny that they have signed the message.(
5
)
Time Constraint. The proxy signing keys can be used only during a stipulated period. Once expired, proxy signing keys become invalid; as a result, the signing capability of the proxy signers disappears. However, the original signer’s private key can be repeatedly used. This is more suitable for use in the real world.(
6
)
Known Signers. For internal auditing purposes, the system is able to identify the actual signers in the original signer’s private key. The proxy signer has the capability to sign on the behalf of the original signer, but from the proxy signing key, the proxy signer cannot recover the original signer’s private key.


## 2.1. History of Threshold Proxy Signature Schemes

In the history of proxy signature technological development, the(1,n) threshold proxy signature technique was the first to come. In (1,n) proxy signature schemes, a legal proxy signature can be generated by a designated proxy signer by using a proxy signing key. The proxy signing key is computed from the original signer’s private key, but the private key should not be computed from the proxy signing key in any way. In the eye of a modern user, such schemes are simple but not flexible. In order to extend proxy signature schemes to fit various practical situations, many (t,n) threshold proxy signature schemes have been proposed. For example, we have (t,n) threshold proxy signature schemes that allow any t or more proxy signers from a designated group of n members to cooperatively sign messages, while t-1 or fewer members cannot generate the legal proxy signature. In practice, the original signer can flexibly choose the threshold t. The approach agrees with (1,n), (t,n), and (n,n) threshold delegations.Rivest et al. [1] and Blakley firstly proposed the (t,n) threshold secret sharing scheme based upon Lagrange interpolating polynomial and linear projective geometry, respectively, in 1979. In a (t,n) threshold secret sharing scheme, secret holder delivers the distinct secret values (called shares or shadows) to n participants. At least t or more participants can combine their shares and reconstruct the secret, but only t-1 or fewer members cannot. Based on these properties, secret sharing is an important part of modern cryptography and has been used in many fields of modern cryptography. In 1996, Mambo et al. [12] proposed the concept of proxy signature. In their schemes, the original signer can delegate his/her right to the proxy signers who can sign the message instead of the original signer.Recently, many threshold proxy signature schemes were proposed. The history of threshold proxy signature schemes is made up in Table1.Table 1
History of threshold proxy signature schemes.
Serial  number
Scheme
Method
1
Rivest et al.  [1]
The Lagrange interpolating polynomial and linear projective geometry
2
ElGamal [2]
Discrete logarithms
3
Desmedt and Frankel [3]
RSA and Lagrange coefficient
4
Zhang [4]
Discrete logarithms
5
Kim et al. [5]
Discrete logarithms
6
Sun et al. [6]
Discrete logarithms
7
Lee(2001)
Discrete logarithms
8
Hwang et al. [7]
RSA and Lagrange coefficient
9
Wang et al. [8]
RSA and Lagrange coefficient
10
Kuo and Chen [9]
RSA and Lagrange coefficient
11
H. Jiang (2007)
RSA and Lagrange coefficient
12
Fanyu (2007)
RSA and Lagrange coefficient
13
Li et al. [10]
RSA and Lagrange coefficient
14
Yong-Jun et al. [11]
RSA and Lagrange coefficientThe concept of threshold cryptosystems was also brought up by Denmedt and Frankel in 1991. They adapted the ElGamal public key cryptosystem and used the Lagrange interpolation or geometry to produce shadows.To make proxy signature applicable to group-oriented situations, Sun [13] and Kim et al. [5] proposed a (t,n) threshold proxy signature in 1997, which is a variant of proxy signature by using the ideas of secret sharing and threshold cryptosystems. The basic strategy used in Kim et al.’s scheme is a random number generation.


## 2.2. Review of Kim et al.’s Scheme

### 2.2.1. The Random Number Generation Phase

This scheme requires a protocol to generate a random number among the group without the dealer. LetP0 be the original signer, and let P1,P2,…,Pn be the n proxy signers of the proxy group.(1)
Each proxy signerPi selects  secret polynomial of degree t-1 such that
(1)fi(x)=ri+ai,1x+ai,2x2+⋯+ai,t-1xt-1modq,where ri, ai,1, ai,2, and ai,t-1 are random numbers.(2)
Then, eachPi computes fi(j) mod q and sends it to Pj for all 1≤j<n and j≠n. Furthermore, Pi computes
(2)gri,gai,1,gai,2,…,gai,t-1(modp)
and broadcasts them.(3)
After receivingfj(i) (for j=1,2,…,n and j≠i), Pi confirms that the validity of fj(i) by checking whether or not gfj(i) satisfies the following equation:
(3)gfj(i)=grj×((gaj,1)i)1×⋯×((gaj,t-1)i)t-1modp.(4)
If the verifications in Step 3 hold, eachPi computes the secret share
(4)Si=∑j=1j=nfj(i)
and computes public outputs
(5)r=∏j=1j=nrjmodp,ga1=∏j=1j=ngj,1modp,ga2=∏j=1j=ngj,2modp,⋮gat-1=∏j=1j=ngj,t-1modp.


### 2.2.2. The Proxy Sharing Phase

(1)
Group Key Generation. First, the proxy group must execute the above protocol to obtain the share si and the public outputs yG=ga0 mod p, Aj=gaj mod p, where
(6)j=1,2,…,t-1.
(2)
Proxy Generation. The original signer computes K=gk mod p and e=h(mw,K), where k is a random number, mw is a warrant, and h() is one way hash function. After this, P0 computes
(7)σ=e×x0+kmodq,
where x0 is a private key of the original signer.
(3)
Proxy Sharing.
P
0 randomly chooses a polynomial such that
(8)f′(x)=σ+b1x+b2x2+⋯+bt-1xt-1,
where b1, b2, bt-1 are random numbers. Then, P0 computes f′(i) and sends it to each Pi in a secret manner; P0 also computes
(9)B1=gb1,B2=gb2,…,Bt-1=gt-1(modp)
and publishes mw,K,B1,B2,…,Bt-1(modp).
(4)
Proxy Share Generation. After receiving f′(i), each Pi has to validate f′(i) using
(10)gf′(i)=(y0)h(mw,K)K∏j=1t-1((Bj)i)jmodp,
where y0 is the original signer’s public key. If it holds, each proxy signer, Pi, computes the proxy sharing
(11)σi′=f′(i)+si×emodq.


### 2.2.3. The Proxy Issuing and Verification Phase

(1)
Thet or more actual signers have to execute the random number generation phase to obtain the secret output si′ and public outputs
(12)y=gc0,C1=gc1,C2=gc2,…,Ct-1=gct-1(modp),
where
(13)si′=f′(i)=c0+c1i+c2i2+⋯+ct-1it-1.
(2)
Then each actual signer uses his proxy signature key to issue a partial proxy signature such thate′=h(y,m) and γi=si′+σi′×emodq, where m is message. Then, each actual signer reveals γi.
(3)
Everyone can verify the validity ofγi by the following equation:
(14)gγi=(y∏i=1t-1(Ci)j)i×(y0)h(mw,K)K∏i=1t-1((Bi)j)imodp×yG∏i=1t-1(((Ai)j)ih(mw,K))h(y,m)modp.
(4)
If the previous verification holds, the signature, onm is (m,T,e′,k,mw), where T=c0+σ×e′=f′(0)+f(0)×e′ can be computed by applying the Lagrange formula.
(5)
To verify the validity of the signature, anyone can examine the following equation:(15)y′=gT×((y0)h(mw,K)K)-eimodp,e′=h(y′,m).


## 2.2.1. The Random Number Generation Phase

This scheme requires a protocol to generate a random number among the group without the dealer. LetP0 be the original signer, and let P1,P2,…,Pn be the n proxy signers of the proxy group.(1)
Each proxy signerPi selects  secret polynomial of degree t-1 such that
(1)fi(x)=ri+ai,1x+ai,2x2+⋯+ai,t-1xt-1modq,where ri, ai,1, ai,2, and ai,t-1 are random numbers.(2)
Then, eachPi computes fi(j) mod q and sends it to Pj for all 1≤j<n and j≠n. Furthermore, Pi computes
(2)gri,gai,1,gai,2,…,gai,t-1(modp)
and broadcasts them.(3)
After receivingfj(i) (for j=1,2,…,n and j≠i), Pi confirms that the validity of fj(i) by checking whether or not gfj(i) satisfies the following equation:
(3)gfj(i)=grj×((gaj,1)i)1×⋯×((gaj,t-1)i)t-1modp.(4)
If the verifications in Step 3 hold, eachPi computes the secret share
(4)Si=∑j=1j=nfj(i)
and computes public outputs
(5)r=∏j=1j=nrjmodp,ga1=∏j=1j=ngj,1modp,ga2=∏j=1j=ngj,2modp,⋮gat-1=∏j=1j=ngj,t-1modp.


## 2.2.2. The Proxy Sharing Phase

(1)
Group Key Generation. First, the proxy group must execute the above protocol to obtain the share si and the public outputs yG=ga0 mod p, Aj=gaj mod p, where
(6)j=1,2,…,t-1.
(2)
Proxy Generation. The original signer computes K=gk mod p and e=h(mw,K), where k is a random number, mw is a warrant, and h() is one way hash function. After this, P0 computes
(7)σ=e×x0+kmodq,
where x0 is a private key of the original signer.
(3)
Proxy Sharing.
P
0 randomly chooses a polynomial such that
(8)f′(x)=σ+b1x+b2x2+⋯+bt-1xt-1,
where b1, b2, bt-1 are random numbers. Then, P0 computes f′(i) and sends it to each Pi in a secret manner; P0 also computes
(9)B1=gb1,B2=gb2,…,Bt-1=gt-1(modp)
and publishes mw,K,B1,B2,…,Bt-1(modp).
(4)
Proxy Share Generation. After receiving f′(i), each Pi has to validate f′(i) using
(10)gf′(i)=(y0)h(mw,K)K∏j=1t-1((Bj)i)jmodp,
where y0 is the original signer’s public key. If it holds, each proxy signer, Pi, computes the proxy sharing
(11)σi′=f′(i)+si×emodq.


## 2.2.3. The Proxy Issuing and Verification Phase

(1)
Thet or more actual signers have to execute the random number generation phase to obtain the secret output si′ and public outputs
(12)y=gc0,C1=gc1,C2=gc2,…,Ct-1=gct-1(modp),
where
(13)si′=f′(i)=c0+c1i+c2i2+⋯+ct-1it-1.
(2)
Then each actual signer uses his proxy signature key to issue a partial proxy signature such thate′=h(y,m) and γi=si′+σi′×emodq, where m is message. Then, each actual signer reveals γi.
(3)
Everyone can verify the validity ofγi by the following equation:
(14)gγi=(y∏i=1t-1(Ci)j)i×(y0)h(mw,K)K∏i=1t-1((Bi)j)imodp×yG∏i=1t-1(((Ai)j)ih(mw,K))h(y,m)modp.
(4)
If the previous verification holds, the signature, onm is (m,T,e′,k,mw), where T=c0+σ×e′=f′(0)+f(0)×e′ can be computed by applying the Lagrange formula.
(5)
To verify the validity of the signature, anyone can examine the following equation:(15)y′=gT×((y0)h(mw,K)K)-eimodp,e′=h(y′,m).


## 2.3. Security Analysis of Kim et al. and Related Schemes

The Kim et al.’s [13] scheme has been shown insecure by Sun et al. [6] using the public key updating attack. Kim et al. proposed two types of threshold proxy signature schemes, which were the proxy-protected scheme and the proxy-unprotected scheme. In the proxy-protected scheme, the original cannot impersonate a proxy signer to issue a valid proxy signature. The proxy signing key combines the original signer’s secret sharing key and a secret value among the t proxy signers. Therefore, the original signer cannot obtain the proxy signing keys. This property is called proxy-protected. One major drawback in Kim et al.’s scheme is that the actual signers cannot be identified. This can be very inconvenient for internal auditing. Kim et al.’s scheme does not satisfy the known signer’s requirement, proxy protection requirement, and the time constrain requirement. It does not satisfy the known signer’s requirement as the actual signer cannot be identified. Also, it is necessary for a verifier to use the public information to check the validity of proxy signature. If the pubic information is not authenticated, the original signer is able to execute the (t,n) threshold proxy signature scheme to generate a valid proxy signature key by himself; that is, he plays the roles of the original signer and the proxy signers simultaneously. This is because a verifier is unable to distinguish whether the public information is created by the legal proxy group or by others (a dishonest original signer or unauthorized group). Hence, it does not satisfy the proxy protection requirement. This scheme does not have the ability to put time constraints on the threshold delegation.In order to remedy the problem of unknown signers, Sun et al. [6] revised Kim et al.’s [13] proxy-protected type threshold proxy signature scheme and made the actual signers able to be identified. Sun et al.’s scheme is also insecure since any n-1 proxy signers in the group can conspire to obtain secret key needed by the remainder of the group. Also, the computational as well as communicational overhead of Sun’s scheme is high. With t or more proxy signers, it issues a proxy signature which has to generate and share a random number among them. In essence, it requires several expansion modular exponential computations and communications.Unfortunately, Zhang’s scheme [13] has also shown to be insecure by Lee, Hwang, and Wang. They have shown a dishonest proxy signer can cheat to get a signature which is generated by the original signer on any message with the condition that a conventional digital signature scheme is a variation of ElGamal type signature.In 1991, Desmedt and Frankel proposed a threshold RSA signature scheme. This technique allowst out of n individuals to generate a signature for a message. The signature is on the behalf of group of n members; hence, we also call it group signature. Rivest et al. [1] extended the concepts and principles from Desmedt and Frankel’s threshold RSA signature to develop a threshold RSA proxy signature scheme.In 1999, Okamoto et al. [14] also suggested an enhanced proxy signature scheme based on both the Mambo-Usuda-Okamoto and Kim-Park-Won schemes. Later on, Sun, Lee, and Hwang examined the security of the Sun-Hsieh scheme based on the Kim-Park-Won scheme and proved that the scheme is not nonrepudiable. And also, a slightly modified version was suggested by them.Hwang et al. [7] have shown that Sun’s scheme has a security weakness. An adversary can impersonate a legal proxy signer to generate a proxy signature and the real proxy signer cannot deny having signed the proxy signature.Lee et al. [15] have proposed the generalization of the (t1/n1-t2/n2) proxy signature scheme based on factorization of the square root modulo of a composite number. They proposed three kinds of proxy signature schemes:  the (t/n-1), the (1-t/n), and the (1-1) proxy signature schemes. In this, the actual original signer cannot deny delegating the warrant or proxy signature either.Tzeng et al. [16] have proposed a batch verification scheme for multiple proxy signature to reduce proxy verification time. The proposed scheme is not efficient because it does not verify each proxy signature separately, but somehow it is secure because it can detect forged multiple proxy signatures without failure.Hwang et al. [17] have proposed a multiproxy multisignature scheme which allows any u or more proxy signers from a designated group of v proxy signers to sign messages on behalf of any t or more original signers from a group of n original signers in total. In this, they only make (u,v) proxy signers to sign on behalf of them.Lu et al. [18] have proposed a proxy signature scheme which allows the original signer to revoke delegations whenever necessary. In this, the authentication server will not issue the time-stamp unless the delegation has not been revoked or the delegation period specified in the warrant has not expired.Yang et al. [19] have proposed an improvement of Hsu et al.’s scheme that is somewhat efficient in terms of computational complexity and communication cost. Different from Hsu et al.’s, the original signer only computes a common proxy share and broadcasts it to the proxy group. As compared with Hsu et al.’s scheme, the secret shares calculations is not required.Tzeng et al. [20] have proposed a threshold multiproxy multisignature scheme with (t3,n3) shared verification. They have proposed the security on the basis of one-way hash function and discrete logarithm problem. They considered only a few attacks.Tzeng et al. [21] have presented security analysis of the Hwang-Lin-Lu scheme. The Hwang-Lin-Lu scheme is vulnerable to forge attack.Hwang et al. [22] have presented a generalized version of proxy signature scheme. A generalization version of the (t1/n1-t2/n2) proxy signature scheme is based on the elliptic curve discrete logarithm problem only. In this paper, the actual original signer cannot deny delegating the warrant or the proxy signature.In 2001, Hsu et al. proposed a nonrepudiable threshold proxy signature scheme. Tsai et al. [23] proposed a scheme to remedy the weakness of the Hsu-Wu-Wu scheme. In this, neither the original signer nor a malicious proxy signer can forge the legal proxy signature.Li et al. [24] have presented a generalized version of proxy signature scheme. A generalization version of the (t1/n1-t2/n2) is based on the discrete logarithm problem only. They discussed three kinds of proxy signature schemes:  the (t/n-1), the (1-t/n), and the (1-1) proxy signature schemes. The actual original signer cannot deny delegating the warrant or the proxy signature.Hwang et al. [25] have discussed Hwang and Shi’s scheme without using a one-way hash function. In their scheme, an original signer needs not send a proxy certificate to proxy signer through secure channels. This scheme is vulnerable to the public key substitution attacks.Hwang et al. [26] have presented a cryptanalysis of Sun’s threshold proxy signature scheme. They have shown only that the secret key can be compromised by collusion attack.Raman Kumar et al. [27] have presented a new scheme which includes the features and benefits of four schemes: Hwang et al., Wen et al., Geng et al. and Feng et al. They have compared these schemes and optimized their own proposed scheme on the basis of different parameters.


## 2.4. Review of Hwang et al.’s Scheme

In the HLL scheme, Hwang et al. [7] proposed a practical and efficient (t,n) threshold proxy signature scheme based on the RSA cryptosystem. This scheme uses only an RSA digital signature scheme and a simple Lagrange formula to share the proxy signature key.There are three types of participants in the scheme: the original signer, then proxy signer, and the combiner. The original signer allows a group of n proxy signers to sign a message. The combiner can be the secretary of the original signer. The proposed threshold proxy signature scheme can be divided into three phases:(1)
The proxy sharing phase;(2)
The proxy issuing phase;(3)
The verification phase.In the proxy generation phase, the original signer computes the partial proxy signing keys from his private key and sends them to each designated proxy signer. In the proxy signature issuing phase, the proxy signers cooperatively create a valid signature on a messageM. In the verification phase, the verifier can identify not only the original signer, but also the actual signers. P0 stands for the original signer and P1,P2,…,Pn stand for the n proxy signers. Ni is a public RSA modulus for Pi such that Ni is a public RSA modulus for Pi and Ni=pi×qi, where pi and qi are two secret large primes, while di is the private key for Pi and its corresponding public key is ei, such that di×ei=1 mod Φ(Ni), where Φ(Ni)=(pi-1)×(qi-1). The parameters ei and Ni can be published. The parameters di and Φ(Ni) are kept secret by the holder. [M]dimodNi represents M signed with Pi’s private key di, and [M]eimodNi represents M encrypted with Pi’s public key ei using the ordinary RSA cryptosystem. The message mw stands for a warrant that is minted by the original signer and it contains important information such as the validity period of the proxy key, the identities of the proxy signers, and the original signer. In the proposed scheme, let N0<Ni(i=1,2,…,n).


### 2.4.1. The Proxy Sharing Phase

Assume that an original signerP0 delegates the power to sign messages to n members during s stipulated period. The steps to generate the proxy key are as follows.(
1
)
Proxy Generation.
P
0 produces the group proxy signing key D and proxy verification key E, where
(16)D=d0mwmodΦ(N0),E=e0mwmodΦ(N0),
where mw=(P+T+r) mod Φ(N0).P is the validity period of proxy signatures, T is the sum of identities of P0,P1,…,Pn, and r is a random number.ThenP0 publishes {mw,E,[mw,E]d0modN0}.(
2
)
Proxy Sharing.
P
0 selects a t-1 degree polynomial,
(17)f(x)=D+a1x+⋯+at-1xt-1modΦ(N0),
where a1, a2,…,at-1 are random numbers. Meanwhile, P0 calculates proxy signer Pi’s partial proxy signing key ki=f(i) and sends [[ki]d0modN0,ki]ei mod Ni to the proxy signer Pi.


### 2.4.2. Proxy Share Generation

When proxy signerPi receives [[ki]d0modN0,ki]ei mod Ni, he or she can get {[ki]d0modN0,ki} by his or her secret key di. And then Pi confirms the validity of ki and keeps it secret.(
1
)
The Proxy Signature Issuing Phase. Let T denote the group members including any t or more proxy signers who want to generate a proxy signature on message M on behalf of P0 cooperatively. Each proxy signer Pi uses the partial proxy signing key ki to generate the partial signature
(18)si=MkimodN0.
Then Pi sends {[si,i]dimodNi,si} to the combiner.When the combiner receives all partial signaturesi from Pi, firstly, he or she verifies the validity of the partial proxy signature by checking if [si,i]di·eimodNi=(si,i) or not. If all partial signatures are valid, the combiner computes the value of
(19)v=∏IDa,IDb∈Ta>b(IDa-IDb),vLi=∏IDa,IDb∈Ta>b(IDa-IDb)∏j=1,j≠it(-IDj(IDi-IDj)).
Here,
(20)∏j=1,j≠i(IDi-IDj)isafactorof∏IDa,IDb∈Ta>bt(IDa-IDb).SovLi is an integer and the combiner need not compute the inverse of
(21)∏j=1,j≠it(IDi-IDj).Finally, the combiner generates the signatureS as follows:
(22)S=∏i∈TsivLimodN0.The result of proxy signature is{v,S}.


### 2.4.3. The Proxy Signature Verification Phase

The verifier can verify the signature signed on behalf of the original signer by the following equation:(23)SE=MvmodN0.The original signer can differentiate the actual signer from the signaturesidieimodNi=si. Then the original signer can trace the actual signers by ei.


## 2.4.1. The Proxy Sharing Phase

Assume that an original signerP0 delegates the power to sign messages to n members during s stipulated period. The steps to generate the proxy key are as follows.(
1
)
Proxy Generation.
P
0 produces the group proxy signing key D and proxy verification key E, where
(16)D=d0mwmodΦ(N0),E=e0mwmodΦ(N0),
where mw=(P+T+r) mod Φ(N0).P is the validity period of proxy signatures, T is the sum of identities of P0,P1,…,Pn, and r is a random number.ThenP0 publishes {mw,E,[mw,E]d0modN0}.(
2
)
Proxy Sharing.
P
0 selects a t-1 degree polynomial,
(17)f(x)=D+a1x+⋯+at-1xt-1modΦ(N0),
where a1, a2,…,at-1 are random numbers. Meanwhile, P0 calculates proxy signer Pi’s partial proxy signing key ki=f(i) and sends [[ki]d0modN0,ki]ei mod Ni to the proxy signer Pi.


## 2.4.2. Proxy Share Generation

When proxy signerPi receives [[ki]d0modN0,ki]ei mod Ni, he or she can get {[ki]d0modN0,ki} by his or her secret key di. And then Pi confirms the validity of ki and keeps it secret.(
1
)
The Proxy Signature Issuing Phase. Let T denote the group members including any t or more proxy signers who want to generate a proxy signature on message M on behalf of P0 cooperatively. Each proxy signer Pi uses the partial proxy signing key ki to generate the partial signature
(18)si=MkimodN0.
Then Pi sends {[si,i]dimodNi,si} to the combiner.When the combiner receives all partial signaturesi from Pi, firstly, he or she verifies the validity of the partial proxy signature by checking if [si,i]di·eimodNi=(si,i) or not. If all partial signatures are valid, the combiner computes the value of
(19)v=∏IDa,IDb∈Ta>b(IDa-IDb),vLi=∏IDa,IDb∈Ta>b(IDa-IDb)∏j=1,j≠it(-IDj(IDi-IDj)).
Here,
(20)∏j=1,j≠i(IDi-IDj)isafactorof∏IDa,IDb∈Ta>bt(IDa-IDb).SovLi is an integer and the combiner need not compute the inverse of
(21)∏j=1,j≠it(IDi-IDj).Finally, the combiner generates the signatureS as follows:
(22)S=∏i∈TsivLimodN0.The result of proxy signature is{v,S}.


## 2.4.3. The Proxy Signature Verification Phase

The verifier can verify the signature signed on behalf of the original signer by the following equation:(23)SE=MvmodN0.The original signer can differentiate the actual signer from the signaturesidieimodNi=si. Then the original signer can trace the actual signers by ei.


## 2.5. Conclusions from the Threshold Proxy Signature Schemes

All analyses indicated that the scheme fails to satisfy all the requirements except one or two. So, an enhanced threshold proxy signature scheme must satisfy all of the following basic requirements which can be called proxy requirements [7, 9–11].(
1
)
Secrecy. The original signer’s private key is very important. It must be kept secret. If it is discovered, the security of the system is ruined. Therefore, the system must ensure that the private key never gets derived from any information such as the sharing of the proxy signing key or the original signer’s public key. Furthermore, no proxy signers should be able to cooperatively derive the original signer’s private key.(
2
)
Proxy Protected. Only a delegated proxy signer can generate his partial proxy signature. Even the original signer cannot masquerade as a proxy signer to generate a partial proxy signature. This property protects the authority of the proxy signer.(
3
)
Unforgeability. A valid proxy signature can only be cooperatively generated by t or more proxy signers. Nondelegated signers have no capability to generate a valid proxy signature. Also, (t-1) or less proxy signers have no capability of forging a valid proxy signature.(
4
)
Nonrepudiation. Any valid proxy signature must be generated by t or more proxy signers. The verifier can make sure that the signed message is a correct one by using the proxy signing keys. The original signer cannot deny having delegated the power of signing messages to the proxy signers. Furthermore, the proxy signers cannot deny that they have signed the message.(
5
)
Time Constraint. The proxy signing keys can be used only during a stipulated period. Once expired, proxy signing keys become invalid; as a result, the signing capability of the proxy signers disappears. However, the original signer’s private key can be repeatedly used. This is more suitable for use in the real world.(
6
)
Known Signers. For internal auditing purposes, the system is able to identify the actual signers in the original signer’s private key. The proxy signer has the capability to sign on the behalf of the original signer, but from the proxy signing key, the proxy signer cannot recover the original signer’s private key.


## 3. Our Scheme

The concept of threshold cryptosystems was first proposed by Katzenbeisser [28]. They adapted the ElGamal [3] public key cryptosystem and used the Lagrange interpolation or geometry to produce the shadows. In the history of proxy signature technological development, the (1,n) threshold proxy signature technique was the first to come [7]. In (1,n) proxy signature schemes [12, 14, 29], a legal proxy signature can be generated by a designated proxy signer by using a proxy signing key. However, in a (t,n) threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of n members. Any t or more proxy signers of the group can cooperatively issue a proxy signature on the behalf of the original signer, but (t-1) or fewer proxy signers cannot. Previously, all of the proposed threshold proxy signature schemes, for instance, Lee et al. [30], ElGamal [2], Sun [13], and Mambo et al. [12], have been based on the discrete logarithm problem. However, the recently proposed threshold proxy signature schemes are based on the RSA cryptosystem [1] and the Lagrange coefficient. In 2003, Hwang et al. [7] proposed a practical and efficient (t,n) threshold proxy signature scheme based on the RSA cryptosystem. This scheme uses only an RSA digit signature scheme and a simple Lagrange formula to share the proxy signature key. In 2004, Wang et al. [8] pointed out a problem on the correctness of the HLL scheme. In 2005, Kuo and Chen [9] also indicated two security weaknesses in the HLL scheme and proposed a new scheme to overcome these weaknesses.We compare the performance of four schemes, Hwang et al. [7], Kuo and Chen [9], Yong-Jun et al. [11], and Li et al. [10], with the performance of a scheme that has been proposed by the authors of this paper earlier and proposed an enhanced secure threshold proxy signature scheme. In the proposed scheme, both the combiner and the secret share holder can verify the correctness of the information that they are receiving from each other. Therefore, the enhanced threshold proxy signature scheme is secure and efficient against notorious conspiracy attacks. Table 2 gives the comparison of threshold proxy signature schemes based on the proxy requirements of each scheme.Table 2
A comparison of threshold proxy signature schemes based on proxy requirements.
Serial number
Proxy signature scheme/requirements
Kim et al.
Sun et al.
HLL
Wen et al.
Enhanced scheme
1
Secrecy
Yes
Yes
No
No
Yes
2
Proxy protection
No
No
No
No
Yes
3
Unforgeability
Yes
No
No
No
Yes
4
Nonrepudiation
Yes
Yes
No
No
Yes
5
Time-constraint
No
No
Yes
Yes
Yes
6
Known signers
No
Yes
No
No
Yes


## 4. Security Analysis of the Proposed Scheme

### 4.1. Factorization of the RSA Module

Factoringn: the fastest known factoring algorithm developed by Pollard is the General Number Field Sieve [1], which has running time for factoring a large number of size n, of order
(24)O(exp((649logn)1/3(loglogn)2/3)).
The method relies upon the observation that if integers x and y are, such that x≠y (mod n) and x2=y2(modn), then gcd(x-y,n) and gcd(x+y,n) are nontrivial factors of n.Tables3(a) and 3(b) give the number of operations needed to factor n with the GNFS method and the time required if each operation uses one microsecond, for various lengths of the number n (in decimal digits).Table 3
(a) The number of operations needed to factorn  with GNFS method. (b) Computing  ϕ(n)  without Factoring “n.”
(a)
Digits
Number of operations
Time
100
9.6 × 108
16 minutes
200
3.3 × 1012
38 days
300
1.3 × 1015
41  years
400
1.7 × 1017
5313   years
500
1.1 × 1019
3.5 × 105 years
1024
1.3 × 1026
4.2 × 1012 years
2048
1.5 × 1035
4.9 × 1021 years
(b)
q
-
p
(
q
+
p
)
2
=
4
n
+
(
q
-
p
)
2
q
+
p
=
4
n
+
(
q
-
p
)
2
1
885
29.7489⋯
2
888
29.7993⋯
3
893
29.8831⋯
4
900
30Computingϕ(n) without factoring “n”:assume thatn=p×q,p<q,since(q+p)2-(q-p)2=4pq=4n,then(q+p)2=4n+(q-p)2 so q+p=4n+(q-p)2;guessq-p and then find q+p, so φ(n)=n-(p+q)+1.Example 1.
Supposen=221(4n=884).
So,q-p=4  and q+p=30; then φ(n)=221-30+1=192 and p=13, q=17, n=13×17.


### 4.2. Lattices and Lattice Reduction of RSA Module

#### 4.2.1. Lattice-Based Attacks on RSA

The following attacks have been tested for RSA modules:(i)
Hastad’s attack;(ii)
Franklin-Reiter attack;(iii)
extension to Wiener’s attack.


#### 4.2.2. Lattices and Lattice Reduction

Given a set ofm linearly independent vectors, {b1,…,bm} in Rn, the set of all real linear combinations of these vectors V={∑i=1maibi:ai∈R} is a vector subspace.Gram-Schmidt process [28] takes one basis {b1,…,bm} and produces a basis {b1*,…,bm*} which is pairwise orthogonal:
(25)b1*=b1,μi,j=〈bi,bj*〉〈bj*,bj*〉,for1≤j<i≤n,bi*=bi-∑j=1i-1μi,jbj*.Example 2.
Consider(26)b1=(20),b2=(11),b1*=b1=(20),μ2,1=〈b2,b1*〉〈b1*,b1*〉=12,b2*=b2-μ2,1=(01).
Given a set of basis vectors {b1,…,bm} in Rn and m≤n, a lattice L={∑i=1maibi:ai∈Z} is a set of all integer linear combinations of the bi.Definition 3.
A basis{b1,…,bm} is called LLL reduced if the associated Gram-Schmidt basis {b1*,…,bm*} satisfies
(27)|μi,j|≤12for1≤j<i≤m,∥b1*∥2≥(34-μi,i-12)∥bi-1*∥2for1<i≤m.
For all nonzero,∥b1∥≤2(m-1)/2∥x∥, we have
(28)∥b1∥≤2m/4Δ1/m,Δ=|det(BTB)|1/2.


#### 4.2.3. Security Levels of the RSA Module on Different Platforms

The following are the creation of key in seconds for different security levels which can be used for encryption and decryption.The fields in Tables4(a) and 4(b) have been generated by varying the values of security levels for both the Pentium and AlphaStation, respectively. It shows the various parameters generated for different security levels.Table 4
(a) Security levels of the RSA module on a 90 MHz Pentium platform. (b) Security levels of the RSA module on a 255 MHz digital AlphaStation.
(a)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
370
42
0.45
768 bit
189
15
1.5
1024 bit
116
7
3.8
(b)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
1020
125
0.26
768 bit
588
42
0.59
1024 bit
385
23
1.28


#### 4.2.4. A General Coalition Attack against Threshold Signature Schemes

Though our modification can withstand the forgery attack suffered by the said to be [7, 9–11] threshold group signature scheme, there is a general coalition attack against threshold signature schemes. In the ordinary threshold signature scheme, the group’s secret key is f(0), and each member Ui has the secret share f(xi). If t or more malicious members pool their secret shares together, they can recover f(0) by applying the Lagrange interpolating polynomial. Then each one of them can alone compute valid signatures for new messages on behalf of the group afterwards without the cooperation of other signers and without being detected by verifiers. Obviously, this violates the group’s signing policy. Otherwise, if such coalition is permissive, other signers would follow this kind of dishonesty. Thus, each user can also alone compute valid group signatures after one coalition. It is terrible for threshold signature schemes. This coalition attack is inherent in many threshold signature schemes using threshold secret share scheme, as long as the secret key can be recovered from secret shares.


#### 4.2.5. The Probability of Catching a User

The probability of catching a user in enhanced threshold proxy signature scheme depends on the number of identity pairs used in it. The more the pairs used, the greater the chance of catching the anonymous user. The probability of catching the anonymous user is(29)1-(12)n,
where n is the number of pairs used.For example, ifn=5, then the chance of catching a user is 0.97.


#### 4.2.6. An Algorithm to Check Primality of Any General Number Given

The algorithm is as follows.Input: integern>1.(1)
Ifn=ab for integers a>0 and b>1, output composite.(2)
Find the smallestr such that or(n)>log2(n).(3)
If1<gcd(a,n)<n for some a≤r, output composite.(4)
Ifn≤r, output prime.Fora=1 to ⌊φ(r)log(n)⌋ do if (X+a)n≠Xn+a(modXr-1,n), output composite.(6)
Outputprime.Hereor(n) is the multiplicative order of n modulo r, log is the binary logarithm, and φ(r) is Euler’s totient function of r.Ifn is a prime number, the algorithm will always return prime: since n is prime, Steps 1 and 3 will never return composite. Step 5 will also never return composite because Step 2 is true for all prime numbers n. Therefore, the algorithm will return prime either in Step 4 or in Step 6.Conversely, ifn is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either Step 4 or Step 6. In the first case, since n≤r, n has a factor a≤r such that 1<gcd(a,n)<n, which will return composite. The remaining possibility is that the algorithm returns prime in Step 6. The authors’ paper proves that this will not happen because the multiple equalities tested in Step 5 are sufficient to guarantee that the output is composite [31].


#### 4.2.7. An Algorithm to Determine If a Number Is a Probable Prime

The Fermat primality test is a probabilistic test to determine if a number is a probable prime. The algorithm is as follows.Inputs:n: a value to test for primality; k: a parameter that determines the number of times to test for primalityOutput:composite if n is composite, otherwise probably primerepeatk times:picka randomly in the range [1,n-1]ifan-1≢1 (mod n), then return compositeReturn Probably Prime. Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k×log2n×loglogn×logloglogn), where k is the number of times we test a random a and n is the value we want to test for primality [32].


#### 4.2.8. The Commonly Supported and Used Algorithms in Protocol

Here are some of the more commonly supported and used algorithms in protocol (see Table5).Table 5
The commonly supported and used algorithms used in protocol.
Diffie-Hellman key exchange algorithm
First published public key algorithm,can be used only for exchanging keys
Uses recipient’s public key to generate a secret key; public data is then sent to recipient who can now generate the secret key
DSA(digital signature algorithm)
Does not encrypt data, but produces a signature that can be verifiedA public key (of 3 parts) is calculated from a private key
Signing: input is data to be signed, private key, a random number; output is a signature, comprising 2 numbers calledr & s Verifying: input is data to be verified, public key & s; output is a number called v;ifv= rthen signature is verified
SHA(secure hash algorithm)
US government standard produced by NISTBased on MD4 algorithm.   Revised version of 1995 called SHA-1
Takes a message of less than 264 bits and produces a message digest/fingerprint of 160 bits
DSS(digital signature  standard)
US government standard method
Uses DSA to sign a message digest/fingerprint produced by SHA
ElGamal(T ElGamal’s algorithm)
Variant of Diffie-Hellman for encryption and decryption as well as key exchanges
Sometimes known as Diffie-Hellman in earlier versions of PGP
RSA(Rivest-Shamir-Adleman algorithm)
First main, and still, the most widely used general purpose public-key encryption algorithm
Encrypt message with public key to obtain confidentialityEncrypt message with private key to obtain authentication, integrity, and  nonrepudiation
3DEStriple DES (data enrcyption standard)
DES was the first widespread symmetric key encryption algorithm3DES applies the algorithm 3 times for additional security
DES is a 56-bit key, 64-bit block cypher using multiple rounds of permutations and substitutionsNow considered necessary to apply 3 times with 3 keys
CAST-128(developed by  Carlisle Adams and Stafford Tavares)
Modern symmetric key encryption algorithmCAST-128 is an implementation of the CAST design procedure
Uses key sizes of 40 to 128 bits (in 8-bit increments) with 16 rounds of 64-bit blocks of plaintextHas been extensively reviewed by cryptologists
IDEA(international data encryption algorithm)
Modern symmetric key encryption algorithm, designed as a replacement for DES
128-bit key block cypher encrypting 64-bit blocks of plaintext
AES/Rijndael(Daemen and  Rijmen’s algorithm)
Selected for the new “Advanced Encryption Standard” by NIST to replace DES
High performance and very secure algorithm, using key sizes of 128, 192, and 256 bits
RSA
Selected for the new “Advanced Encryption Standard” by NIST
High performance and very secure algorithm


## 4.1. Factorization of the RSA Module

Factoringn: the fastest known factoring algorithm developed by Pollard is the General Number Field Sieve [1], which has running time for factoring a large number of size n, of order
(24)O(exp((649logn)1/3(loglogn)2/3)).
The method relies upon the observation that if integers x and y are, such that x≠y (mod n) and x2=y2(modn), then gcd(x-y,n) and gcd(x+y,n) are nontrivial factors of n.Tables3(a) and 3(b) give the number of operations needed to factor n with the GNFS method and the time required if each operation uses one microsecond, for various lengths of the number n (in decimal digits).Table 3
(a) The number of operations needed to factorn  with GNFS method. (b) Computing  ϕ(n)  without Factoring “n.”
(a)
Digits
Number of operations
Time
100
9.6 × 108
16 minutes
200
3.3 × 1012
38 days
300
1.3 × 1015
41  years
400
1.7 × 1017
5313   years
500
1.1 × 1019
3.5 × 105 years
1024
1.3 × 1026
4.2 × 1012 years
2048
1.5 × 1035
4.9 × 1021 years
(b)
q
-
p
(
q
+
p
)
2
=
4
n
+
(
q
-
p
)
2
q
+
p
=
4
n
+
(
q
-
p
)
2
1
885
29.7489⋯
2
888
29.7993⋯
3
893
29.8831⋯
4
900
30Computingϕ(n) without factoring “n”:assume thatn=p×q,p<q,since(q+p)2-(q-p)2=4pq=4n,then(q+p)2=4n+(q-p)2 so q+p=4n+(q-p)2;guessq-p and then find q+p, so φ(n)=n-(p+q)+1.Example 1.
Supposen=221(4n=884).
So,q-p=4  and q+p=30; then φ(n)=221-30+1=192 and p=13, q=17, n=13×17.


## 4.2. Lattices and Lattice Reduction of RSA Module

### 4.2.1. Lattice-Based Attacks on RSA

The following attacks have been tested for RSA modules:(i)
Hastad’s attack;(ii)
Franklin-Reiter attack;(iii)
extension to Wiener’s attack.


### 4.2.2. Lattices and Lattice Reduction

Given a set ofm linearly independent vectors, {b1,…,bm} in Rn, the set of all real linear combinations of these vectors V={∑i=1maibi:ai∈R} is a vector subspace.Gram-Schmidt process [28] takes one basis {b1,…,bm} and produces a basis {b1*,…,bm*} which is pairwise orthogonal:
(25)b1*=b1,μi,j=〈bi,bj*〉〈bj*,bj*〉,for1≤j<i≤n,bi*=bi-∑j=1i-1μi,jbj*.Example 2.
Consider(26)b1=(20),b2=(11),b1*=b1=(20),μ2,1=〈b2,b1*〉〈b1*,b1*〉=12,b2*=b2-μ2,1=(01).
Given a set of basis vectors {b1,…,bm} in Rn and m≤n, a lattice L={∑i=1maibi:ai∈Z} is a set of all integer linear combinations of the bi.Definition 3.
A basis{b1,…,bm} is called LLL reduced if the associated Gram-Schmidt basis {b1*,…,bm*} satisfies
(27)|μi,j|≤12for1≤j<i≤m,∥b1*∥2≥(34-μi,i-12)∥bi-1*∥2for1<i≤m.
For all nonzero,∥b1∥≤2(m-1)/2∥x∥, we have
(28)∥b1∥≤2m/4Δ1/m,Δ=|det(BTB)|1/2.


### 4.2.3. Security Levels of the RSA Module on Different Platforms

The following are the creation of key in seconds for different security levels which can be used for encryption and decryption.The fields in Tables4(a) and 4(b) have been generated by varying the values of security levels for both the Pentium and AlphaStation, respectively. It shows the various parameters generated for different security levels.Table 4
(a) Security levels of the RSA module on a 90 MHz Pentium platform. (b) Security levels of the RSA module on a 255 MHz digital AlphaStation.
(a)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
370
42
0.45
768 bit
189
15
1.5
1024 bit
116
7
3.8
(b)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
1020
125
0.26
768 bit
588
42
0.59
1024 bit
385
23
1.28


### 4.2.4. A General Coalition Attack against Threshold Signature Schemes

Though our modification can withstand the forgery attack suffered by the said to be [7, 9–11] threshold group signature scheme, there is a general coalition attack against threshold signature schemes. In the ordinary threshold signature scheme, the group’s secret key is f(0), and each member Ui has the secret share f(xi). If t or more malicious members pool their secret shares together, they can recover f(0) by applying the Lagrange interpolating polynomial. Then each one of them can alone compute valid signatures for new messages on behalf of the group afterwards without the cooperation of other signers and without being detected by verifiers. Obviously, this violates the group’s signing policy. Otherwise, if such coalition is permissive, other signers would follow this kind of dishonesty. Thus, each user can also alone compute valid group signatures after one coalition. It is terrible for threshold signature schemes. This coalition attack is inherent in many threshold signature schemes using threshold secret share scheme, as long as the secret key can be recovered from secret shares.


### 4.2.5. The Probability of Catching a User

The probability of catching a user in enhanced threshold proxy signature scheme depends on the number of identity pairs used in it. The more the pairs used, the greater the chance of catching the anonymous user. The probability of catching the anonymous user is(29)1-(12)n,
where n is the number of pairs used.For example, ifn=5, then the chance of catching a user is 0.97.


### 4.2.6. An Algorithm to Check Primality of Any General Number Given

The algorithm is as follows.Input: integern>1.(1)
Ifn=ab for integers a>0 and b>1, output composite.(2)
Find the smallestr such that or(n)>log2(n).(3)
If1<gcd(a,n)<n for some a≤r, output composite.(4)
Ifn≤r, output prime.Fora=1 to ⌊φ(r)log(n)⌋ do if (X+a)n≠Xn+a(modXr-1,n), output composite.(6)
Outputprime.Hereor(n) is the multiplicative order of n modulo r, log is the binary logarithm, and φ(r) is Euler’s totient function of r.Ifn is a prime number, the algorithm will always return prime: since n is prime, Steps 1 and 3 will never return composite. Step 5 will also never return composite because Step 2 is true for all prime numbers n. Therefore, the algorithm will return prime either in Step 4 or in Step 6.Conversely, ifn is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either Step 4 or Step 6. In the first case, since n≤r, n has a factor a≤r such that 1<gcd(a,n)<n, which will return composite. The remaining possibility is that the algorithm returns prime in Step 6. The authors’ paper proves that this will not happen because the multiple equalities tested in Step 5 are sufficient to guarantee that the output is composite [31].


### 4.2.7. An Algorithm to Determine If a Number Is a Probable Prime

The Fermat primality test is a probabilistic test to determine if a number is a probable prime. The algorithm is as follows.Inputs:n: a value to test for primality; k: a parameter that determines the number of times to test for primalityOutput:composite if n is composite, otherwise probably primerepeatk times:picka randomly in the range [1,n-1]ifan-1≢1 (mod n), then return compositeReturn Probably Prime. Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k×log2n×loglogn×logloglogn), where k is the number of times we test a random a and n is the value we want to test for primality [32].


### 4.2.8. The Commonly Supported and Used Algorithms in Protocol

Here are some of the more commonly supported and used algorithms in protocol (see Table5).Table 5
The commonly supported and used algorithms used in protocol.
Diffie-Hellman key exchange algorithm
First published public key algorithm,can be used only for exchanging keys
Uses recipient’s public key to generate a secret key; public data is then sent to recipient who can now generate the secret key
DSA(digital signature algorithm)
Does not encrypt data, but produces a signature that can be verifiedA public key (of 3 parts) is calculated from a private key
Signing: input is data to be signed, private key, a random number; output is a signature, comprising 2 numbers calledr & s Verifying: input is data to be verified, public key & s; output is a number called v;ifv= rthen signature is verified
SHA(secure hash algorithm)
US government standard produced by NISTBased on MD4 algorithm.   Revised version of 1995 called SHA-1
Takes a message of less than 264 bits and produces a message digest/fingerprint of 160 bits
DSS(digital signature  standard)
US government standard method
Uses DSA to sign a message digest/fingerprint produced by SHA
ElGamal(T ElGamal’s algorithm)
Variant of Diffie-Hellman for encryption and decryption as well as key exchanges
Sometimes known as Diffie-Hellman in earlier versions of PGP
RSA(Rivest-Shamir-Adleman algorithm)
First main, and still, the most widely used general purpose public-key encryption algorithm
Encrypt message with public key to obtain confidentialityEncrypt message with private key to obtain authentication, integrity, and  nonrepudiation
3DEStriple DES (data enrcyption standard)
DES was the first widespread symmetric key encryption algorithm3DES applies the algorithm 3 times for additional security
DES is a 56-bit key, 64-bit block cypher using multiple rounds of permutations and substitutionsNow considered necessary to apply 3 times with 3 keys
CAST-128(developed by  Carlisle Adams and Stafford Tavares)
Modern symmetric key encryption algorithmCAST-128 is an implementation of the CAST design procedure
Uses key sizes of 40 to 128 bits (in 8-bit increments) with 16 rounds of 64-bit blocks of plaintextHas been extensively reviewed by cryptologists
IDEA(international data encryption algorithm)
Modern symmetric key encryption algorithm, designed as a replacement for DES
128-bit key block cypher encrypting 64-bit blocks of plaintext
AES/Rijndael(Daemen and  Rijmen’s algorithm)
Selected for the new “Advanced Encryption Standard” by NIST to replace DES
High performance and very secure algorithm, using key sizes of 128, 192, and 256 bits
RSA
Selected for the new “Advanced Encryption Standard” by NIST
High performance and very secure algorithm


## 4.2.1. Lattice-Based Attacks on RSA

The following attacks have been tested for RSA modules:(i)
Hastad’s attack;(ii)
Franklin-Reiter attack;(iii)
extension to Wiener’s attack.


## 4.2.2. Lattices and Lattice Reduction

Given a set ofm linearly independent vectors, {b1,…,bm} in Rn, the set of all real linear combinations of these vectors V={∑i=1maibi:ai∈R} is a vector subspace.Gram-Schmidt process [28] takes one basis {b1,…,bm} and produces a basis {b1*,…,bm*} which is pairwise orthogonal:
(25)b1*=b1,μi,j=〈bi,bj*〉〈bj*,bj*〉,for1≤j<i≤n,bi*=bi-∑j=1i-1μi,jbj*.Example 2.
Consider(26)b1=(20),b2=(11),b1*=b1=(20),μ2,1=〈b2,b1*〉〈b1*,b1*〉=12,b2*=b2-μ2,1=(01).
Given a set of basis vectors {b1,…,bm} in Rn and m≤n, a lattice L={∑i=1maibi:ai∈Z} is a set of all integer linear combinations of the bi.Definition 3.
A basis{b1,…,bm} is called LLL reduced if the associated Gram-Schmidt basis {b1*,…,bm*} satisfies
(27)|μi,j|≤12for1≤j<i≤m,∥b1*∥2≥(34-μi,i-12)∥bi-1*∥2for1<i≤m.
For all nonzero,∥b1∥≤2(m-1)/2∥x∥, we have
(28)∥b1∥≤2m/4Δ1/m,Δ=|det(BTB)|1/2.


## 4.2.3. Security Levels of the RSA Module on Different Platforms

The following are the creation of key in seconds for different security levels which can be used for encryption and decryption.The fields in Tables4(a) and 4(b) have been generated by varying the values of security levels for both the Pentium and AlphaStation, respectively. It shows the various parameters generated for different security levels.Table 4
(a) Security levels of the RSA module on a 90 MHz Pentium platform. (b) Security levels of the RSA module on a 255 MHz digital AlphaStation.
(a)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
370
42
0.45
768 bit
189
15
1.5
1024 bit
116
7
3.8
(b)
Securitylevel
Encrypt(blks/sec)
Decrypt(blks/sec)
CreateKey (sec)
512 bit
1020
125
0.26
768 bit
588
42
0.59
1024 bit
385
23
1.28


## 4.2.4. A General Coalition Attack against Threshold Signature Schemes

Though our modification can withstand the forgery attack suffered by the said to be [7, 9–11] threshold group signature scheme, there is a general coalition attack against threshold signature schemes. In the ordinary threshold signature scheme, the group’s secret key is f(0), and each member Ui has the secret share f(xi). If t or more malicious members pool their secret shares together, they can recover f(0) by applying the Lagrange interpolating polynomial. Then each one of them can alone compute valid signatures for new messages on behalf of the group afterwards without the cooperation of other signers and without being detected by verifiers. Obviously, this violates the group’s signing policy. Otherwise, if such coalition is permissive, other signers would follow this kind of dishonesty. Thus, each user can also alone compute valid group signatures after one coalition. It is terrible for threshold signature schemes. This coalition attack is inherent in many threshold signature schemes using threshold secret share scheme, as long as the secret key can be recovered from secret shares.


## 4.2.5. The Probability of Catching a User

The probability of catching a user in enhanced threshold proxy signature scheme depends on the number of identity pairs used in it. The more the pairs used, the greater the chance of catching the anonymous user. The probability of catching the anonymous user is(29)1-(12)n,
where n is the number of pairs used.For example, ifn=5, then the chance of catching a user is 0.97.


## 4.2.6. An Algorithm to Check Primality of Any General Number Given

The algorithm is as follows.Input: integern>1.(1)
Ifn=ab for integers a>0 and b>1, output composite.(2)
Find the smallestr such that or(n)>log2(n).(3)
If1<gcd(a,n)<n for some a≤r, output composite.(4)
Ifn≤r, output prime.Fora=1 to ⌊φ(r)log(n)⌋ do if (X+a)n≠Xn+a(modXr-1,n), output composite.(6)
Outputprime.Hereor(n) is the multiplicative order of n modulo r, log is the binary logarithm, and φ(r) is Euler’s totient function of r.Ifn is a prime number, the algorithm will always return prime: since n is prime, Steps 1 and 3 will never return composite. Step 5 will also never return composite because Step 2 is true for all prime numbers n. Therefore, the algorithm will return prime either in Step 4 or in Step 6.Conversely, ifn is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either Step 4 or Step 6. In the first case, since n≤r, n has a factor a≤r such that 1<gcd(a,n)<n, which will return composite. The remaining possibility is that the algorithm returns prime in Step 6. The authors’ paper proves that this will not happen because the multiple equalities tested in Step 5 are sufficient to guarantee that the output is composite [31].


## 4.2.7. An Algorithm to Determine If a Number Is a Probable Prime

The Fermat primality test is a probabilistic test to determine if a number is a probable prime. The algorithm is as follows.Inputs:n: a value to test for primality; k: a parameter that determines the number of times to test for primalityOutput:composite if n is composite, otherwise probably primerepeatk times:picka randomly in the range [1,n-1]ifan-1≢1 (mod n), then return compositeReturn Probably Prime. Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k×log2n×loglogn×logloglogn), where k is the number of times we test a random a and n is the value we want to test for primality [32].


## 4.2.8. The Commonly Supported and Used Algorithms in Protocol

Here are some of the more commonly supported and used algorithms in protocol (see Table5).Table 5
The commonly supported and used algorithms used in protocol.
Diffie-Hellman key exchange algorithm
First published public key algorithm,can be used only for exchanging keys
Uses recipient’s public key to generate a secret key; public data is then sent to recipient who can now generate the secret key
DSA(digital signature algorithm)
Does not encrypt data, but produces a signature that can be verifiedA public key (of 3 parts) is calculated from a private key
Signing: input is data to be signed, private key, a random number; output is a signature, comprising 2 numbers calledr & s Verifying: input is data to be verified, public key & s; output is a number called v;ifv= rthen signature is verified
SHA(secure hash algorithm)
US government standard produced by NISTBased on MD4 algorithm.   Revised version of 1995 called SHA-1
Takes a message of less than 264 bits and produces a message digest/fingerprint of 160 bits
DSS(digital signature  standard)
US government standard method
Uses DSA to sign a message digest/fingerprint produced by SHA
ElGamal(T ElGamal’s algorithm)
Variant of Diffie-Hellman for encryption and decryption as well as key exchanges
Sometimes known as Diffie-Hellman in earlier versions of PGP
RSA(Rivest-Shamir-Adleman algorithm)
First main, and still, the most widely used general purpose public-key encryption algorithm
Encrypt message with public key to obtain confidentialityEncrypt message with private key to obtain authentication, integrity, and  nonrepudiation
3DEStriple DES (data enrcyption standard)
DES was the first widespread symmetric key encryption algorithm3DES applies the algorithm 3 times for additional security
DES is a 56-bit key, 64-bit block cypher using multiple rounds of permutations and substitutionsNow considered necessary to apply 3 times with 3 keys
CAST-128(developed by  Carlisle Adams and Stafford Tavares)
Modern symmetric key encryption algorithmCAST-128 is an implementation of the CAST design procedure
Uses key sizes of 40 to 128 bits (in 8-bit increments) with 16 rounds of 64-bit blocks of plaintextHas been extensively reviewed by cryptologists
IDEA(international data encryption algorithm)
Modern symmetric key encryption algorithm, designed as a replacement for DES
128-bit key block cypher encrypting 64-bit blocks of plaintext
AES/Rijndael(Daemen and  Rijmen’s algorithm)
Selected for the new “Advanced Encryption Standard” by NIST to replace DES
High performance and very secure algorithm, using key sizes of 128, 192, and 256 bits
RSA
Selected for the new “Advanced Encryption Standard” by NIST
High performance and very secure algorithm


## 5. Performance Analysis of the Proposed Scheme

The analysis reports of the proposed hypothesis for enhanced threshold proxy signature scheme are given as the following.


### 5.1. Entropy

In this case, the value of entropy is the measure of the tendency of a process, to be entropicallyfavored or to proceed in a particular direction. Moreover, entropy provides an indication for a specific encryption method. We have analyzed our hypothesis on the basis of entropy generated.Figure1 shows that entropy for enhanced threshold proxy signature scheme. Figure 2 shows the compression ratio required in each scheme. Table 6 lists the name and compression ratio required in each scheme.Table 6
Compression ratio (in %) for threshold proxy signature schemes.
Threshold proxy signature scheme
Compressionratio (in %)
HLL
66
KUOCHEN
66
GENGVRF
66
FNGVERF
67
THRSPROX
72Figure 1
Entropy for the enhanced threshold proxy signature scheme.Figure 2
Radar chart showing compression ratio required in each scheme.


### 5.2. Floating Frequencies/Intuitive Synthesis

Floating frequencies/intuitive synthesis in its completed three parts entirety takes full advantage of the time complexity, space complexity, and communication overhead provided by the digital medium. We have calculated floating frequency of the threshold proxy signature scheme. Figure3 shows that floating frequencies/intuitive synthesis for the enhanced threshold proxy signature scheme.Figure 3
Floating frequencies/intuitive synthesis for the enhanced threshold proxy signature scheme.


### 5.3. ASCII Histogram

The ASCII histogram proved to be very useful since it helped enormously in debugging code involving probability calculations with simple print statements. Probabilistic simulations are extremely hard to test because the results of a given operation are never strictly the same. However, they should have the same probability distribution, so by looking at the rough shape of the histogram, it tells you if your calculations are going in the right direction. In this context, we have calculated ASCII histogram for our threshold proxy signature scheme. Figure4 shows that ASCII Histogram for enhanced threshold proxy signature.Figure 4
ASCII histogram for enhanced threshold proxy signature scheme.


### 5.4. Autocorrelation

This is mathematical representation of the degree of similarity between a given time series and a lagged version of itself over successive time intervals. It is the same a calculating the correlation between two different time series, except that the same time series is used twice—once in its original form and once lagged one or more time periods. The term can also be referred to as “lagged correlation” or “serial correlation”. In this, we have calculated autocorrelation for threshold proxy signature scheme. Figure5 shows the Autocorrelation for the enhanced threshold proxy signature scheme.Figure 5
Autocorrelation for enhanced threshold proxy signature scheme.


### 5.5. Histogram Analysis

A histogram is a graphical representation showing a visual impression of the distribution of data. We have analyzed histogram of for all threshold proxy signature schemes.Detailed View. The detailed view of the histogram analysis of all schemes can be represented as follows.Experiment 1.
Histogram analysis of〈1HLL〉. File size 12581 bytes. Descending sorted on frequency.Figure6 shows that radar chart showing histogram analysis for HLL threshold proxy signature scheme. Table 7 lists the histogram analysis for the HLL threshold proxy signature scheme.Table 7
Histogram analysis for the HLL threshold proxy signature scheme.
Number
Substring
Frequency (in %)
Frequency
1
N
11.0343
654
2
I
9.1277
541
3
T
8.824
523
4
E
8.6216
511
5
S
7.4405
441
6
R
7.1368
423
7
A
5.0785
301
8
O
4.6567
276
9
C
4.1842
248
10
D
3.6612
217
11
U
3.5937
213
12
F
3.2732
194
13
P
3.1213
185
14
G
3.0707
182
15
L
3.0201
179
16
H
2.8682
170
17
Y
2.6489
157
18
M
2.4296
144
19
X
1.4341
85
20
V
1.0798
64
21
W
0.9954
59
22
J
0.8267
49
23
B
0.7761
46
24
K
0.6917
41
25
Q
0.3374
20
26
Z
0.0675
4Figure 6
Radar chart showing histogram analysis for the HLL threshold proxy signature scheme.Experiment 2.
Histogram analysis of〈2KUOCHEN〉. File size 11733 bytes. Descending sorted on  frequency.Figure7 shows that radar chart showing histogram Analysis for KUOCHEN threshold proxy signature scheme. Table 8 lists the histogram analysis for the KUOCHEN threshold proxy signature scheme.Table 8
Histogram analysis for the KUOCHEN threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
11.3387
631
2
I
8.841
492
3
E
8.6253
480
4
T
8.4636
471
5
S
7.8886
439
6
R
7.044
392
7
O
4.8697
271
8
A
4.6361
258
9
C
4.4205
246
10
U
3.8455
214
11
G
3.2884
183
12
P
3.2165
179
13
L
3.1626
176
14
F
3.0189
168
15
H
2.9111
162
16
D
2.8392
158
17
M
2.6954
150
18
Y
1.8509
103
19
X
1.4196
79
20
W
1.2579
70
21
J
1.15
64
22
V
1.0422
58
23
B
0.9164
51
24
K
0.7907
44
25
Q
0.3953
22
26
Z
0.0719
4Figure 7
Radar chart showing histogram analysis for the KUOCHEN threshold proxy signature scheme.Experiment 3.
Histogram Analysis of〈3GENGVRF〉. File size 11259 bytes. Descending sorted on frequency.Figure8 shows that radar chart showing histogram analysis for the GENGVRF threshold proxy signature scheme. Table 9 lists the histogram analysis for the GENGVRF threshold proxy signature scheme.Table 9
Histogram analysis for the GENGVRF threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
10.9658
587
2
I
9.4153
504
3
T
9.079
486
4
S
8.3878
449
5
E
7.9208
424
6
R
7.1175
381
7
O
4.7076
252
8
A
4.5769
245
9
C
3.9978
214
10
U
3.6802
197
11
F
3.5681
191
12
P
3.5494
190
13
G
3.4747
186
14
L
2.989
160
15
D
2.8956
155
16
H
2.7835
149
17
M
2.3538
126
18
Y
1.8121
97
19
X
1.4945
80
20
V
1.3824
74
21
J
0.9714
52
22
B
0.8967
48
23
W
0.7659
41
24
K
0.7286
39
25
Q
0.411
22
26
Z
0.0747
4Figure 8
Radar chart showing histogram analysis for the GENGVRF threshold proxy signature scheme.Experiment 4.
Histogram ANALYSIS of〈4FNGVERF〉. File size 12067 bytes. Descending sorted on frequency.Figure9 shows that radar chart showing histogram analysis for the FNGVRF threshold proxy signature scheme. Table 10 lists the histogram analysis for the FNGVRF threshold proxy signature scheme.Table 10
Histogram analysis for the FNGVERF threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
10.947
630
2
I
9.1573
527
3
T
8.7576
504
4
S
8.3927
483
5
E
8.2711
476
6
R
6.9505
400
7
O
4.7089
271
8
A
4.6568
268
9
C
4.066
234
10
U
3.8401
221
11
F
3.5274
203
12
G
3.5274
203
13
P
3.4231
197
14
L
3.3189
191
15
D
2.7454
158
16
H
2.6933
155
17
M
2.6759
154
18
Y
1.7724
102
19
X
1.4248
82
20
V
1.1816
68
21
W
1.0252
59
22
B
0.8862
51
23
J
0.8688
50
24
K
0.7298
42
25
Q
0.3823
22
26
Z
0.0695
4Figure 9
Radar chart showing histogram analysis for the FNGVRF threshold proxy signature scheme.Experiment 5.
Histogram analysis of〈5THRSPROX〉. File size 16897 bytes. Descending sorted on frequency.
Figure10 shows that Radar Chart showing histogram analysis for the enhanced threshold proxy signature scheme. Table 11 lists the histogram analysis for enhanced threshold proxy signature scheme.
Figure11 shows that radar chart showing overall histogram analysis for all threshold proxy signature schemes. Table 17 lists the histogram analysis for the overall threshold proxy signature schemes.Table 11
Histogram analysis for the enhanced threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
11.5549
891
2
S
8.7278
673
3
E
8.5981
663
4
T
8.5722
661
5
I
8.3258
642
6
R
6.6399
512
7
O
5.4597
421
8
A
4.539
350
9
C
4.3963
339
10
U
3.696
285
11
F
3.4626
267
12
P
3.3329
257
13
G
3.307
255
14
L
3.1384
242
15
H
3.0865
238
16
D
2.5937
200
17
M
2.3603
182
18
Y
1.8934
146
19
X
1.634
126
20
V
1.2061
93
21
J
0.83
64
22
W
0.817
63
23
B
0.7522
58
24
K
0.7133
55
25
Q
0.3112
24
26
Z
0.0519
4Figure 10
Radar chart showing histogram analysis for the enhanced threshold proxy signature scheme.Figure 11
Radar chart showing overall analysis for all threshold proxy signature schemes.


### 5.6. Collusion Attack

The collusion attack is an action carried out by a given set of malicious users in possession of a copy of protected content that join together in order to obtain at the end of the attack procedure an unprotected asset. The attack is carried out by properly combining the protected copies of the multimedia documents collected by the colluders, according to the type of content and the kind of adopted protection system.When the protection is assured by a data hiding algorithm, the collusion usually can take place in one of two different application frameworks: multimedia fingerprinting and ownership verification. In multimedia fingerprinting, a content owner, to protect his/her copyright, embeds a different code into each copy of the content distributed to each customer in order to be able to trace possible illegal usage of data and discover the source of the leakage of information; in this case, then, each colluder possesses a slightly different copy of the same multimedia content, and the attack consists in averaging all documents they have, trying to produce a new document in which the watermark is no longer present. If the number of averaged documents is large enough, the attack is very effective even without the introduction of perceptually significant degradation between the averaged multimedia document and the original one. In ownership verification, a content owner, to demonstrate that he/she is the authorized holder of the distributed content, embeds always the same code, linked to his/her identity, into different watermarked documents before they are distributed to the customers in such a way that the hidden code can be used to prove ownership in court if someone will infringe on his/her copyrights; in this case, then, each colluder possesses different multimedia documents, with the same hidden code,  so that the attack is carried out by estimating the watermark by means of an average of all the different contents they have (this approach is suitable only for data-hiding systems in which the hidden watermark does not depend on the host data). Then the estimated watermark can be removed from all the documents hiding in it or even falsely inserted in other ones to generate fake watermarked documents [33].One advantage of enhanced threshold proxy signature schemes is that they can prevent a “collusion attack” in which two key generation servers communicate with each other to get useful information about the user’s private key. In essence, Figure19 shows the overall communication architecture for the secure threshold proxy signature scheme based on RSA cryptosystem for known signers.


### 5.7. Security of RSA Signature

Existential forgery using akey-only attack:
Choose a randomy
Computex=ek(y)
We havey=sigk(x), a valid signature of x.
Existential forgery using a known messageattack:
Supposey=sigk(x) and y′=sigk(x′)
Can checkek(yy′modn)=xx′modn
Soyy′modn=sigk(xx′modn).
Existential forgery using achosen message attack:
To get a signature forx, find x1x2=xmodn
Query for signatures ofx1 and x2.


### 5.8. Forgery Attack

RSA function is a multiplicative homomorphism; for allx, y,
(30)f(xymodn)=f(x)f(y)modn,f-1(xymodn)=f-1(x)f-1(y)modn.
More generally,
(31)f-1(∏ximodn)=∏(f-1(xi))modn.
The property not only is exploited in most forgery attacks on RSA signatures, but also enhances recent security proofs.


### 5.9. Friedman Test

The Friedman test is a nonparametric statistical test developed by the US economist Milton Friedman. Similar to the parametric repeated measures ANOVA, it is used to detect differences in treatments across multiple test attempts. The procedure involves ranking each row (or block) together, then considering the values of ranks by columns. Applicable to complete block designs, it is thus a special case of the Durbin test. The Friedman test is used for one-way repeated measures analysis of variance by ranks. In its use of ranks, it is similar to the Kruskal-Wallis one-way analysis of variance by ranks. We have tested our hypothesis against the Friedman test [31].Figure12 shows the chart showing Friedman test for all threshold proxy signature schemes.Figure 12
Chart showing Friedman test for all threshold proxy signature schemes.


## 5.1. Entropy

In this case, the value of entropy is the measure of the tendency of a process, to be entropicallyfavored or to proceed in a particular direction. Moreover, entropy provides an indication for a specific encryption method. We have analyzed our hypothesis on the basis of entropy generated.Figure1 shows that entropy for enhanced threshold proxy signature scheme. Figure 2 shows the compression ratio required in each scheme. Table 6 lists the name and compression ratio required in each scheme.Table 6
Compression ratio (in %) for threshold proxy signature schemes.
Threshold proxy signature scheme
Compressionratio (in %)
HLL
66
KUOCHEN
66
GENGVRF
66
FNGVERF
67
THRSPROX
72Figure 1
Entropy for the enhanced threshold proxy signature scheme.Figure 2
Radar chart showing compression ratio required in each scheme.


## 5.2. Floating Frequencies/Intuitive Synthesis

Floating frequencies/intuitive synthesis in its completed three parts entirety takes full advantage of the time complexity, space complexity, and communication overhead provided by the digital medium. We have calculated floating frequency of the threshold proxy signature scheme. Figure3 shows that floating frequencies/intuitive synthesis for the enhanced threshold proxy signature scheme.Figure 3
Floating frequencies/intuitive synthesis for the enhanced threshold proxy signature scheme.


## 5.3. ASCII Histogram

The ASCII histogram proved to be very useful since it helped enormously in debugging code involving probability calculations with simple print statements. Probabilistic simulations are extremely hard to test because the results of a given operation are never strictly the same. However, they should have the same probability distribution, so by looking at the rough shape of the histogram, it tells you if your calculations are going in the right direction. In this context, we have calculated ASCII histogram for our threshold proxy signature scheme. Figure4 shows that ASCII Histogram for enhanced threshold proxy signature.Figure 4
ASCII histogram for enhanced threshold proxy signature scheme.


## 5.4. Autocorrelation

This is mathematical representation of the degree of similarity between a given time series and a lagged version of itself over successive time intervals. It is the same a calculating the correlation between two different time series, except that the same time series is used twice—once in its original form and once lagged one or more time periods. The term can also be referred to as “lagged correlation” or “serial correlation”. In this, we have calculated autocorrelation for threshold proxy signature scheme. Figure5 shows the Autocorrelation for the enhanced threshold proxy signature scheme.Figure 5
Autocorrelation for enhanced threshold proxy signature scheme.


## 5.5. Histogram Analysis

A histogram is a graphical representation showing a visual impression of the distribution of data. We have analyzed histogram of for all threshold proxy signature schemes.Detailed View. The detailed view of the histogram analysis of all schemes can be represented as follows.Experiment 1.
Histogram analysis of〈1HLL〉. File size 12581 bytes. Descending sorted on frequency.Figure6 shows that radar chart showing histogram analysis for HLL threshold proxy signature scheme. Table 7 lists the histogram analysis for the HLL threshold proxy signature scheme.Table 7
Histogram analysis for the HLL threshold proxy signature scheme.
Number
Substring
Frequency (in %)
Frequency
1
N
11.0343
654
2
I
9.1277
541
3
T
8.824
523
4
E
8.6216
511
5
S
7.4405
441
6
R
7.1368
423
7
A
5.0785
301
8
O
4.6567
276
9
C
4.1842
248
10
D
3.6612
217
11
U
3.5937
213
12
F
3.2732
194
13
P
3.1213
185
14
G
3.0707
182
15
L
3.0201
179
16
H
2.8682
170
17
Y
2.6489
157
18
M
2.4296
144
19
X
1.4341
85
20
V
1.0798
64
21
W
0.9954
59
22
J
0.8267
49
23
B
0.7761
46
24
K
0.6917
41
25
Q
0.3374
20
26
Z
0.0675
4Figure 6
Radar chart showing histogram analysis for the HLL threshold proxy signature scheme.Experiment 2.
Histogram analysis of〈2KUOCHEN〉. File size 11733 bytes. Descending sorted on  frequency.Figure7 shows that radar chart showing histogram Analysis for KUOCHEN threshold proxy signature scheme. Table 8 lists the histogram analysis for the KUOCHEN threshold proxy signature scheme.Table 8
Histogram analysis for the KUOCHEN threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
11.3387
631
2
I
8.841
492
3
E
8.6253
480
4
T
8.4636
471
5
S
7.8886
439
6
R
7.044
392
7
O
4.8697
271
8
A
4.6361
258
9
C
4.4205
246
10
U
3.8455
214
11
G
3.2884
183
12
P
3.2165
179
13
L
3.1626
176
14
F
3.0189
168
15
H
2.9111
162
16
D
2.8392
158
17
M
2.6954
150
18
Y
1.8509
103
19
X
1.4196
79
20
W
1.2579
70
21
J
1.15
64
22
V
1.0422
58
23
B
0.9164
51
24
K
0.7907
44
25
Q
0.3953
22
26
Z
0.0719
4Figure 7
Radar chart showing histogram analysis for the KUOCHEN threshold proxy signature scheme.Experiment 3.
Histogram Analysis of〈3GENGVRF〉. File size 11259 bytes. Descending sorted on frequency.Figure8 shows that radar chart showing histogram analysis for the GENGVRF threshold proxy signature scheme. Table 9 lists the histogram analysis for the GENGVRF threshold proxy signature scheme.Table 9
Histogram analysis for the GENGVRF threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
10.9658
587
2
I
9.4153
504
3
T
9.079
486
4
S
8.3878
449
5
E
7.9208
424
6
R
7.1175
381
7
O
4.7076
252
8
A
4.5769
245
9
C
3.9978
214
10
U
3.6802
197
11
F
3.5681
191
12
P
3.5494
190
13
G
3.4747
186
14
L
2.989
160
15
D
2.8956
155
16
H
2.7835
149
17
M
2.3538
126
18
Y
1.8121
97
19
X
1.4945
80
20
V
1.3824
74
21
J
0.9714
52
22
B
0.8967
48
23
W
0.7659
41
24
K
0.7286
39
25
Q
0.411
22
26
Z
0.0747
4Figure 8
Radar chart showing histogram analysis for the GENGVRF threshold proxy signature scheme.Experiment 4.
Histogram ANALYSIS of〈4FNGVERF〉. File size 12067 bytes. Descending sorted on frequency.Figure9 shows that radar chart showing histogram analysis for the FNGVRF threshold proxy signature scheme. Table 10 lists the histogram analysis for the FNGVRF threshold proxy signature scheme.Table 10
Histogram analysis for the FNGVERF threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
10.947
630
2
I
9.1573
527
3
T
8.7576
504
4
S
8.3927
483
5
E
8.2711
476
6
R
6.9505
400
7
O
4.7089
271
8
A
4.6568
268
9
C
4.066
234
10
U
3.8401
221
11
F
3.5274
203
12
G
3.5274
203
13
P
3.4231
197
14
L
3.3189
191
15
D
2.7454
158
16
H
2.6933
155
17
M
2.6759
154
18
Y
1.7724
102
19
X
1.4248
82
20
V
1.1816
68
21
W
1.0252
59
22
B
0.8862
51
23
J
0.8688
50
24
K
0.7298
42
25
Q
0.3823
22
26
Z
0.0695
4Figure 9
Radar chart showing histogram analysis for the FNGVRF threshold proxy signature scheme.Experiment 5.
Histogram analysis of〈5THRSPROX〉. File size 16897 bytes. Descending sorted on frequency.
Figure10 shows that Radar Chart showing histogram analysis for the enhanced threshold proxy signature scheme. Table 11 lists the histogram analysis for enhanced threshold proxy signature scheme.
Figure11 shows that radar chart showing overall histogram analysis for all threshold proxy signature schemes. Table 17 lists the histogram analysis for the overall threshold proxy signature schemes.Table 11
Histogram analysis for the enhanced threshold proxy signature schemes.
Number
Substring
Frequency (in %)
Frequency
1
N
11.5549
891
2
S
8.7278
673
3
E
8.5981
663
4
T
8.5722
661
5
I
8.3258
642
6
R
6.6399
512
7
O
5.4597
421
8
A
4.539
350
9
C
4.3963
339
10
U
3.696
285
11
F
3.4626
267
12
P
3.3329
257
13
G
3.307
255
14
L
3.1384
242
15
H
3.0865
238
16
D
2.5937
200
17
M
2.3603
182
18
Y
1.8934
146
19
X
1.634
126
20
V
1.2061
93
21
J
0.83
64
22
W
0.817
63
23
B
0.7522
58
24
K
0.7133
55
25
Q
0.3112
24
26
Z
0.0519
4Figure 10
Radar chart showing histogram analysis for the enhanced threshold proxy signature scheme.Figure 11
Radar chart showing overall analysis for all threshold proxy signature schemes.


## 5.6. Collusion Attack

The collusion attack is an action carried out by a given set of malicious users in possession of a copy of protected content that join together in order to obtain at the end of the attack procedure an unprotected asset. The attack is carried out by properly combining the protected copies of the multimedia documents collected by the colluders, according to the type of content and the kind of adopted protection system.When the protection is assured by a data hiding algorithm, the collusion usually can take place in one of two different application frameworks: multimedia fingerprinting and ownership verification. In multimedia fingerprinting, a content owner, to protect his/her copyright, embeds a different code into each copy of the content distributed to each customer in order to be able to trace possible illegal usage of data and discover the source of the leakage of information; in this case, then, each colluder possesses a slightly different copy of the same multimedia content, and the attack consists in averaging all documents they have, trying to produce a new document in which the watermark is no longer present. If the number of averaged documents is large enough, the attack is very effective even without the introduction of perceptually significant degradation between the averaged multimedia document and the original one. In ownership verification, a content owner, to demonstrate that he/she is the authorized holder of the distributed content, embeds always the same code, linked to his/her identity, into different watermarked documents before they are distributed to the customers in such a way that the hidden code can be used to prove ownership in court if someone will infringe on his/her copyrights; in this case, then, each colluder possesses different multimedia documents, with the same hidden code,  so that the attack is carried out by estimating the watermark by means of an average of all the different contents they have (this approach is suitable only for data-hiding systems in which the hidden watermark does not depend on the host data). Then the estimated watermark can be removed from all the documents hiding in it or even falsely inserted in other ones to generate fake watermarked documents [33].One advantage of enhanced threshold proxy signature schemes is that they can prevent a “collusion attack” in which two key generation servers communicate with each other to get useful information about the user’s private key. In essence, Figure19 shows the overall communication architecture for the secure threshold proxy signature scheme based on RSA cryptosystem for known signers.


## 5.7. Security of RSA Signature

Existential forgery using akey-only attack:
Choose a randomy
Computex=ek(y)
We havey=sigk(x), a valid signature of x.
Existential forgery using a known messageattack:
Supposey=sigk(x) and y′=sigk(x′)
Can checkek(yy′modn)=xx′modn
Soyy′modn=sigk(xx′modn).
Existential forgery using achosen message attack:
To get a signature forx, find x1x2=xmodn
Query for signatures ofx1 and x2.


## 5.8. Forgery Attack

RSA function is a multiplicative homomorphism; for allx, y,
(30)f(xymodn)=f(x)f(y)modn,f-1(xymodn)=f-1(x)f-1(y)modn.
More generally,
(31)f-1(∏ximodn)=∏(f-1(xi))modn.
The property not only is exploited in most forgery attacks on RSA signatures, but also enhances recent security proofs.


## 5.9. Friedman Test

The Friedman test is a nonparametric statistical test developed by the US economist Milton Friedman. Similar to the parametric repeated measures ANOVA, it is used to detect differences in treatments across multiple test attempts. The procedure involves ranking each row (or block) together, then considering the values of ranks by columns. Applicable to complete block designs, it is thus a special case of the Durbin test. The Friedman test is used for one-way repeated measures analysis of variance by ranks. In its use of ranks, it is similar to the Kruskal-Wallis one-way analysis of variance by ranks. We have tested our hypothesis against the Friedman test [31].Figure12 shows the chart showing Friedman test for all threshold proxy signature schemes.Figure 12
Chart showing Friedman test for all threshold proxy signature schemes.


## 6. Implementation and Comparison of the Proposed Scheme

The implementation of the schemes has been done.


### 6.1. Time Complexity

When determining the time complexity of an algorithm, we measure how fast the computing requirements grow as the size of the input grows.


#### 6.1.1. Readings

Readings are taken for two scenarios described below. Each reading shown in Table11 is the average of 30 readings.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Table12 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 11 and Table 13 shows the readings of execution time (in microseconds) and when the number of threshold signers is equal to number of proxy signers.Table 12
Variation of time with number of signers for scenario 1 (t=1).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
135.92
135.7567
135.46
107.42
103.9967
3
145.9433
142.23
146.5733
110.98
112.6033
4
163.4033
152.1533
168.17
115.01
116.68
5
164.8167
157.0067
172.7933
128.6167
122.1067
6
167.7767
175.15
194.65
130.22
132.5533
7
176.0667
178.7533
196.7933
135.69
135.77
8
205.11
188.2633
213.01
138.0067
137.9133
9
207.7133
189.5567
224.61
155.59
146.92
10
214.1167
191.36
226.2533
159.64
158.2633Table 13
Variation of time with number of signers for scenario 2 (t=n).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
138.9933
147.0233
152.16
115.6033
117.08
3
163.9733
175.71
191.2133
138.89
139.5033
4
177.2367
206.82
225.47
166.2267
165.08
5
196.0533
216.4767
254.1533
190.6533
179.8767
6
217.9833
257.7233
276.2533
214.4267
209.7767
7
252.38
282.3267
305.4967
249.96
233.82
8
261.4233
313.67
337.4967
283.1467
256.4967
9
304.9767
346.7833
375.7
315.74
270.6067
10
324.8367
387.2833
415.05
350.9433
303.99


#### 6.1.2. Graphs

We plot the graphs with the following:(1)
execution time (in microseconds) onY-axis,(2)
number of proxy signers (N) on X-axis.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.


#### 6.1.3. Results

Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, Geng et al. scheme has the maximum time complexity and the proposed scheme has the minimum time complexity; also Fengying et al.’s time complexity falls very near the proposed scheme. We find that the proposed and Fengying et al.’s schemes have minimum time complexities. The time complexity of HLL scheme is more in case of scenario 1 (for t=1) but less in case of scenario (t=n). This is because it has an extra constant overhead to verify the validity of the stipulated period. As this overhead is constant, hence, for scenario 1, HLL scheme has more time complexity as compared to other schemes. The proposed scheme has less time complexity as compared to other schemes because it need not compute the inverse when we compute the value of Lagrange coefficient (Figure 15), which makes the scheme more efficient [11]. Also, we do not verify message warrant, which saves the extra overhead, that was incurred in case of KC scheme.(a) Comparison of schemes based on time complexity whent=1. (b) Three-dimensional view for comparison of schemes based on time complexity when t=1.
(a)
(b)(a) comparison of schemes based on time complexity whent=n. (b) Three-dimensional view for comparison of schemes based on time complexity when t=n.
(a)
(b)Figure 15
Comparison of schemes based on time complexity whent=1 and n.Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, the execution time increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of computations also increases, due to, which the execution time increases. The number of computations increases because for each proxy signers, following parameters have to be computed.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the computations. The graphs generated also confirm this point. Also, we observe that in the graphs in Figures14(a) and 14(b) the execution time is more in case of t=n than in case of t=1. It is because the number of computations increases with the number of threshold signers as well. For each threshold signer, the following computations have to done.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the computations as confirmed by the graphs generated.Scenario 3: when number of threshold signers,t=1 and n.Table14 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 1 and is equal to number of proxy signers, where number of Signers N=15, days = 80, and threshold number of Signers N=15.Table 14
Variation of time with number of signers for scenario 3.
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
103.296
106.593
107.142
99.45
100.549
2
124.175
118.132
119.230
121.978
118.132
3
127.473
137.362
146.450
134.066
128.571
4
154.945
156.044
154.395
172.527
173.076
5
179.670
173.626
185.165
181.268
172.428
6
195.054
203.846
209.890
203.846
196.703
7
216.043
235.714
231.868
235.164
222.527
8
256.593
268.329
259.340
249.400
243.956
9
265.187
278.219
272.967
278.571
276.923
10
286.264
313.626
311.538
304.285
305.274
11
347.472
369.010
326.923
318.241
330.769
12
364.325
371.428
345.114
350
351.648
13
357.143
356.593
368.021
386.153
353.846
14
373.143
364.286
367.142
386.505
370.879
15
378.021
388.461
403.890
384.835
371.538Scenario 3:  when number of threshold signers,t=1 and n.


### 6.2. Space Complexity

The space complexity of a program is the number of elementary objects that this program needs to store during its execution. We generate graphs to analyze the space complexity of the schemes.


#### 6.2.1. Estimation Based on Number of Variables

Table14 lists the name and number of variables required in each scheme. Beside the variables shown in Table 14, a character string is required to store the message M which has to be signed.


#### 6.2.2. Graphs

We plot the graphs with the following:(1)
memory overhead (in terms of number of variables) ony-axis,(2)
Number of proxy signers (N) on x-axis.The graphs have been shown in Figures16 and 17.Figure 16
Comparison of schemes based on space complexity whent=1.Figure 17
Comparison of schemes based on space complexity whent=n.


#### 6.2.3. Results

Figures16 and 17 have been generated by varying the values of n for both scenarios in Table 15, which shows the memory overhead in terms of memory variables required for each scheme. In Figures 16 and 17, we see that for both scenarios, the proposed scheme has the maximum space complexity and the HLL scheme has the minimum space complexity. The complexity of KC, Geng et al., and Fengying et al. scheme falls between the two schemes’ space complexity with KC and Fengying et al. schemes having the same space complexity. We note that in Table 4, the proposed scheme requires only (n+3) more variables than the HLL scheme, which has the minimum space complexity. For example, the proposed scheme requires only 4 extra variables than the HLL scheme for N=1, which has the minimum space complexity, and for N=n, the proposed scheme requires only 13 more variables than the HLL scheme. Also, this difference can be easily accommodated with the development of very large storage devices. Hence, we can see that the space complexities of the schemes are almost equal and the performance of the schemes in the case of the space complexity is almost the same.Table 15
Space Requirements of the Schemes.
Serial no.
Scheme
HLL
KC
Geng
Fengying
Proposed
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
1.
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
2.
K
i
,
i
2
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
3.
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
4.
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
5.
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
6
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
,
T
,
r
8
×
1
Total
8
n
+
3
t
+
12
9
n
+
3
t
+
12
9
n
+
3
t
+
13
9
n
+
3
t
+
12
9
n
+
3
t
+
15Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Figures16 and 17 also show that for both the scenarios, the space complexity increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of variables also increases due to which the memory requirements increase. Memory overhead increases because for each proxy signers, the following parameters are required.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the memory requirements. The figures generated also confirm this point.Also, we observe in the graphs that memory overhead is more in the case oft=n than in the case of t=1. It is because the number of variables increases with the number of threshold signers as well. For each threshold signer, the following variables have to be declared.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the memory requirements as confirmed by the graphs generated.


### 6.3. Communication Overhead

The communication overhead includes two types of communication in the schemes:(1)
number of transmissions;(2)
number of broadcasts.


#### 6.3.1. Comparison of the Schemes

Table6 shows the communication overhead for each scheme for various phases. In Figure 6, we find that the communication overhead of all the schemes is the same.


#### 6.3.2. Results

Figure18 has been generated from Table 15, which can be referred to to find the number of transmissions and broadcasts to compute the communication overhead for all the schemes. Table 16 can be referred to to find the comparison between threshold proxy signature schemes based upon proxy requirements. As evident from Figure 18, the communication overhead of all the schemes is the same.Table 16
Comparison of communication overheads of the threshold proxy signature schemes.
Schemes
HLL
KC
Geng
Fengying
Proposed
Number  of Communications
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
Number of transmissions
n
t
n
t
n
t
n
t
n
t
Number of broadcasts
3
0
3
0
3
0
3
0
3
0
Total
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
PS: proxy sharing phase.
PSIV: proxy signature issuing and verification phase.Table 17
*
Schemes
HLL
Frequency 1
KUOCHEN
Frequency 2
GENGVRF
Frequency 3
FNGVERF
Frequency 4
THRSPROX
Frequency 5
No.
Substring
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
1
N
11.0343
654
11.3387
631
10.9658
587
10.947
630
11.5549
891
2
I
9.1277
541
8.841
492
9.4153
504
9.1573
527
8.7278
673
3
T
8.824
523
8.6253
480
9.079
486
8.7576
504
8.5981
663
4
E
8.6216
511
8.4636
471
8.3878
449
8.3927
483
8.5722
661
5
S
7.4405
441
7.8886
439
7.9208
424
8.2711
476
8.3258
642
6
R
7.1368
423
7.044
392
7.1175
381
6.9505
400
6.6399
512
7
A
5.0785
301
4.8697
271
4.7076
252
4.7089
271
5.4597
421
8
O
4.6567
276
4.6361
258
4.5769
245
4.6568
268
4.539
350
9
C
4.1842
248
4.4205
246
3.9978
214
4.066
234
4.3963
339
10
D
3.6612
217
3.8455
214
3.6802
197
3.8401
221
3.696
285
11
U
3.5937
213
3.2884
183
3.5681
191
3.5274
203
3.4626
267
12
F
3.2732
194
3.2165
179
3.5494
190
3.5274
203
3.3329
257
13
P
3.1213
185
3.1626
176
3.4747
186
3.4231
197
3.307
255
14
G
3.0707
182
3.0189
168
2.989
160
3.3189
191
3.1384
242
15
L
3.0201
179
2.9111
162
2.8956
155
2.7454
158
3.0865
238
16
H
2.8682
170
2.8392
158
2.7835
149
2.6933
155
2.5937
200
17
Y
2.6489
157
2.6954
150
2.3538
126
2.6759
154
2.3603
182
18
M
2.4296
144
1.8509
103
1.8121
97
1.7724
102
1.8934
146
19
X
1.4341
85
1.4196
79
1.4945
80
1.4248
82
1.634
126
20
V
1.0798
64
1.2579
70
1.3824
74
1.1816
68
1.2061
93
21
W
0.9954
59
1.15
64
0.9714
52
1.0252
59
0.83
64
22
J
0.8267
49
1.0422
58
0.8967
48
0.8862
51
0.817
63
23
B
0.7761
46
0.9164
51
0.7659
41
0.8688
50
0.7522
58
24
K
0.6917
41
0.7907
44
0.7286
39
0.7298
42
0.7133
55
25
Q
0.3374
20
0.3953
22
0.411
22
0.3823
22
0.3112
24
26
Z
0.0675
4
0.0719
4
0.0747
4
0.0695
4
0.0519
4Figure 18
Comparison of schemes based on communication overhead.Figure 19
Overall communication architecture for secure threshold proxy signature scheme based on RSA cryptosystem.Figure19 shows the overall communication architecture for the secure threshold proxy signature scheme based on RSA cryptosystem for known signers. It sends a message after logging in to the system. It also sends a message to the other client using the secure threshold proxy signature scheme based on the RSA cryptosystem for known signers. In this, the delegates can send the message to the n proxy signers with security. After sending the message, it logs out from the system. We have improved the results after improving the performance of four schemes: Hwang et al. [7], Kuo and Chen [9], Yong-Jun et al. [11], and Li et al. [10], with the performance of a scheme that has been proposed by the authors of this paper earlier. In this paper, we compared the various threshold proxy signature schemes based on how they violate proxy signature requirements. Table 16 summarizes the comparison of four threshold proxy signature schemes: Kim et al.’s scheme, Sun’s scheme, HLL scheme, and Wen et al.’s scheme. We also propose a new scheme which includes the features and benefits of the two schemes: Fengying et al. and Geng et al. The main advantages of our proposed scheme are as follows.(i)
It achieved the property of nonrepudiation.(ii)
Anyone cannot forge the legal proxy signature.(iii)
The verifier can identify the actual proxy signer of its group.(iv)
It also provides more refined result against its time complexity, space complexity, and communication overhead.(v)
The proposed scheme is secure and efficient against notorious conspiracy attacks.


## 6.1. Time Complexity

When determining the time complexity of an algorithm, we measure how fast the computing requirements grow as the size of the input grows.


### 6.1.1. Readings

Readings are taken for two scenarios described below. Each reading shown in Table11 is the average of 30 readings.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Table12 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 11 and Table 13 shows the readings of execution time (in microseconds) and when the number of threshold signers is equal to number of proxy signers.Table 12
Variation of time with number of signers for scenario 1 (t=1).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
135.92
135.7567
135.46
107.42
103.9967
3
145.9433
142.23
146.5733
110.98
112.6033
4
163.4033
152.1533
168.17
115.01
116.68
5
164.8167
157.0067
172.7933
128.6167
122.1067
6
167.7767
175.15
194.65
130.22
132.5533
7
176.0667
178.7533
196.7933
135.69
135.77
8
205.11
188.2633
213.01
138.0067
137.9133
9
207.7133
189.5567
224.61
155.59
146.92
10
214.1167
191.36
226.2533
159.64
158.2633Table 13
Variation of time with number of signers for scenario 2 (t=n).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
138.9933
147.0233
152.16
115.6033
117.08
3
163.9733
175.71
191.2133
138.89
139.5033
4
177.2367
206.82
225.47
166.2267
165.08
5
196.0533
216.4767
254.1533
190.6533
179.8767
6
217.9833
257.7233
276.2533
214.4267
209.7767
7
252.38
282.3267
305.4967
249.96
233.82
8
261.4233
313.67
337.4967
283.1467
256.4967
9
304.9767
346.7833
375.7
315.74
270.6067
10
324.8367
387.2833
415.05
350.9433
303.99


### 6.1.2. Graphs

We plot the graphs with the following:(1)
execution time (in microseconds) onY-axis,(2)
number of proxy signers (N) on X-axis.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.


### 6.1.3. Results

Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, Geng et al. scheme has the maximum time complexity and the proposed scheme has the minimum time complexity; also Fengying et al.’s time complexity falls very near the proposed scheme. We find that the proposed and Fengying et al.’s schemes have minimum time complexities. The time complexity of HLL scheme is more in case of scenario 1 (for t=1) but less in case of scenario (t=n). This is because it has an extra constant overhead to verify the validity of the stipulated period. As this overhead is constant, hence, for scenario 1, HLL scheme has more time complexity as compared to other schemes. The proposed scheme has less time complexity as compared to other schemes because it need not compute the inverse when we compute the value of Lagrange coefficient (Figure 15), which makes the scheme more efficient [11]. Also, we do not verify message warrant, which saves the extra overhead, that was incurred in case of KC scheme.(a) Comparison of schemes based on time complexity whent=1. (b) Three-dimensional view for comparison of schemes based on time complexity when t=1.
(a)
(b)(a) comparison of schemes based on time complexity whent=n. (b) Three-dimensional view for comparison of schemes based on time complexity when t=n.
(a)
(b)Figure 15
Comparison of schemes based on time complexity whent=1 and n.Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, the execution time increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of computations also increases, due to, which the execution time increases. The number of computations increases because for each proxy signers, following parameters have to be computed.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the computations. The graphs generated also confirm this point. Also, we observe that in the graphs in Figures14(a) and 14(b) the execution time is more in case of t=n than in case of t=1. It is because the number of computations increases with the number of threshold signers as well. For each threshold signer, the following computations have to done.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the computations as confirmed by the graphs generated.Scenario 3: when number of threshold signers,t=1 and n.Table14 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 1 and is equal to number of proxy signers, where number of Signers N=15, days = 80, and threshold number of Signers N=15.Table 14
Variation of time with number of signers for scenario 3.
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
103.296
106.593
107.142
99.45
100.549
2
124.175
118.132
119.230
121.978
118.132
3
127.473
137.362
146.450
134.066
128.571
4
154.945
156.044
154.395
172.527
173.076
5
179.670
173.626
185.165
181.268
172.428
6
195.054
203.846
209.890
203.846
196.703
7
216.043
235.714
231.868
235.164
222.527
8
256.593
268.329
259.340
249.400
243.956
9
265.187
278.219
272.967
278.571
276.923
10
286.264
313.626
311.538
304.285
305.274
11
347.472
369.010
326.923
318.241
330.769
12
364.325
371.428
345.114
350
351.648
13
357.143
356.593
368.021
386.153
353.846
14
373.143
364.286
367.142
386.505
370.879
15
378.021
388.461
403.890
384.835
371.538Scenario 3:  when number of threshold signers,t=1 and n.


## 6.1.1. Readings

Readings are taken for two scenarios described below. Each reading shown in Table11 is the average of 30 readings.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Table12 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 11 and Table 13 shows the readings of execution time (in microseconds) and when the number of threshold signers is equal to number of proxy signers.Table 12
Variation of time with number of signers for scenario 1 (t=1).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
135.92
135.7567
135.46
107.42
103.9967
3
145.9433
142.23
146.5733
110.98
112.6033
4
163.4033
152.1533
168.17
115.01
116.68
5
164.8167
157.0067
172.7933
128.6167
122.1067
6
167.7767
175.15
194.65
130.22
132.5533
7
176.0667
178.7533
196.7933
135.69
135.77
8
205.11
188.2633
213.01
138.0067
137.9133
9
207.7133
189.5567
224.61
155.59
146.92
10
214.1167
191.36
226.2533
159.64
158.2633Table 13
Variation of time with number of signers for scenario 2 (t=n).
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
128.0267
118.5867
123.6233
100.5567
98.52333
2
138.9933
147.0233
152.16
115.6033
117.08
3
163.9733
175.71
191.2133
138.89
139.5033
4
177.2367
206.82
225.47
166.2267
165.08
5
196.0533
216.4767
254.1533
190.6533
179.8767
6
217.9833
257.7233
276.2533
214.4267
209.7767
7
252.38
282.3267
305.4967
249.96
233.82
8
261.4233
313.67
337.4967
283.1467
256.4967
9
304.9767
346.7833
375.7
315.74
270.6067
10
324.8367
387.2833
415.05
350.9433
303.99


## 6.1.2. Graphs

We plot the graphs with the following:(1)
execution time (in microseconds) onY-axis,(2)
number of proxy signers (N) on X-axis.Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.


## 6.1.3. Results

Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, Geng et al. scheme has the maximum time complexity and the proposed scheme has the minimum time complexity; also Fengying et al.’s time complexity falls very near the proposed scheme. We find that the proposed and Fengying et al.’s schemes have minimum time complexities. The time complexity of HLL scheme is more in case of scenario 1 (for t=1) but less in case of scenario (t=n). This is because it has an extra constant overhead to verify the validity of the stipulated period. As this overhead is constant, hence, for scenario 1, HLL scheme has more time complexity as compared to other schemes. The proposed scheme has less time complexity as compared to other schemes because it need not compute the inverse when we compute the value of Lagrange coefficient (Figure 15), which makes the scheme more efficient [11]. Also, we do not verify message warrant, which saves the extra overhead, that was incurred in case of KC scheme.(a) Comparison of schemes based on time complexity whent=1. (b) Three-dimensional view for comparison of schemes based on time complexity when t=1.
(a)
(b)(a) comparison of schemes based on time complexity whent=n. (b) Three-dimensional view for comparison of schemes based on time complexity when t=n.
(a)
(b)Figure 15
Comparison of schemes based on time complexity whent=1 and n.Figures13(a), 13(b), 14(a), and 14(b) show that for both scenarios, the execution time increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of computations also increases, due to, which the execution time increases. The number of computations increases because for each proxy signers, following parameters have to be computed.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the computations. The graphs generated also confirm this point. Also, we observe that in the graphs in Figures14(a) and 14(b) the execution time is more in case of t=n than in case of t=1. It is because the number of computations increases with the number of threshold signers as well. For each threshold signer, the following computations have to done.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the computations as confirmed by the graphs generated.Scenario 3: when number of threshold signers,t=1 and n.Table14 shows the readings of execution time (in microseconds) when the number of threshold signers is equal to 1 and is equal to number of proxy signers, where number of Signers N=15, days = 80, and threshold number of Signers N=15.Table 14
Variation of time with number of signers for scenario 3.
Number of signersN
Time (in microseconds)
HLL
KC
Geng
Fengying
Proposed
1
103.296
106.593
107.142
99.45
100.549
2
124.175
118.132
119.230
121.978
118.132
3
127.473
137.362
146.450
134.066
128.571
4
154.945
156.044
154.395
172.527
173.076
5
179.670
173.626
185.165
181.268
172.428
6
195.054
203.846
209.890
203.846
196.703
7
216.043
235.714
231.868
235.164
222.527
8
256.593
268.329
259.340
249.400
243.956
9
265.187
278.219
272.967
278.571
276.923
10
286.264
313.626
311.538
304.285
305.274
11
347.472
369.010
326.923
318.241
330.769
12
364.325
371.428
345.114
350
351.648
13
357.143
356.593
368.021
386.153
353.846
14
373.143
364.286
367.142
386.505
370.879
15
378.021
388.461
403.890
384.835
371.538Scenario 3:  when number of threshold signers,t=1 and n.


## 6.2. Space Complexity

The space complexity of a program is the number of elementary objects that this program needs to store during its execution. We generate graphs to analyze the space complexity of the schemes.


### 6.2.1. Estimation Based on Number of Variables

Table14 lists the name and number of variables required in each scheme. Beside the variables shown in Table 14, a character string is required to store the message M which has to be signed.


### 6.2.2. Graphs

We plot the graphs with the following:(1)
memory overhead (in terms of number of variables) ony-axis,(2)
Number of proxy signers (N) on x-axis.The graphs have been shown in Figures16 and 17.Figure 16
Comparison of schemes based on space complexity whent=1.Figure 17
Comparison of schemes based on space complexity whent=n.


### 6.2.3. Results

Figures16 and 17 have been generated by varying the values of n for both scenarios in Table 15, which shows the memory overhead in terms of memory variables required for each scheme. In Figures 16 and 17, we see that for both scenarios, the proposed scheme has the maximum space complexity and the HLL scheme has the minimum space complexity. The complexity of KC, Geng et al., and Fengying et al. scheme falls between the two schemes’ space complexity with KC and Fengying et al. schemes having the same space complexity. We note that in Table 4, the proposed scheme requires only (n+3) more variables than the HLL scheme, which has the minimum space complexity. For example, the proposed scheme requires only 4 extra variables than the HLL scheme for N=1, which has the minimum space complexity, and for N=n, the proposed scheme requires only 13 more variables than the HLL scheme. Also, this difference can be easily accommodated with the development of very large storage devices. Hence, we can see that the space complexities of the schemes are almost equal and the performance of the schemes in the case of the space complexity is almost the same.Table 15
Space Requirements of the Schemes.
Serial no.
Scheme
HLL
KC
Geng
Fengying
Proposed
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
1.
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
2.
K
i
,
i
2
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
3.
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
4.
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
5.
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
6
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
,
T
,
r
8
×
1
Total
8
n
+
3
t
+
12
9
n
+
3
t
+
12
9
n
+
3
t
+
13
9
n
+
3
t
+
12
9
n
+
3
t
+
15Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Figures16 and 17 also show that for both the scenarios, the space complexity increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of variables also increases due to which the memory requirements increase. Memory overhead increases because for each proxy signers, the following parameters are required.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the memory requirements. The figures generated also confirm this point.Also, we observe in the graphs that memory overhead is more in the case oft=n than in the case of t=1. It is because the number of variables increases with the number of threshold signers as well. For each threshold signer, the following variables have to be declared.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the memory requirements as confirmed by the graphs generated.


## 6.2.1. Estimation Based on Number of Variables

Table14 lists the name and number of variables required in each scheme. Beside the variables shown in Table 14, a character string is required to store the message M which has to be signed.


## 6.2.2. Graphs

We plot the graphs with the following:(1)
memory overhead (in terms of number of variables) ony-axis,(2)
Number of proxy signers (N) on x-axis.The graphs have been shown in Figures16 and 17.Figure 16
Comparison of schemes based on space complexity whent=1.Figure 17
Comparison of schemes based on space complexity whent=n.


## 6.2.3. Results

Figures16 and 17 have been generated by varying the values of n for both scenarios in Table 15, which shows the memory overhead in terms of memory variables required for each scheme. In Figures 16 and 17, we see that for both scenarios, the proposed scheme has the maximum space complexity and the HLL scheme has the minimum space complexity. The complexity of KC, Geng et al., and Fengying et al. scheme falls between the two schemes’ space complexity with KC and Fengying et al. schemes having the same space complexity. We note that in Table 4, the proposed scheme requires only (n+3) more variables than the HLL scheme, which has the minimum space complexity. For example, the proposed scheme requires only 4 extra variables than the HLL scheme for N=1, which has the minimum space complexity, and for N=n, the proposed scheme requires only 13 more variables than the HLL scheme. Also, this difference can be easily accommodated with the development of very large storage devices. Hence, we can see that the space complexities of the schemes are almost equal and the performance of the schemes in the case of the space complexity is almost the same.Table 15
Space Requirements of the Schemes.
Serial no.
Scheme
HLL
KC
Geng
Fengying
Proposed
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
Variables
Quantity
1.
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
N
i
,
d
i
,
e
i
,
ϕ
(
N
i
)
,
p
i
,
q
i
6
×
(
n
+
1
)
2.
K
i
,
i
2
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
K
i
,
i
,
I
D
i
3
×
n
3.
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
s
i
,
L
i
2
×
t
4.
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
a
i
t
-
1
5.
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
6
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
5
×
1
D
,
E
,
S
,
P
,
m
w
,
t
,
n
,
v
,
T
,
r
8
×
1
Total
8
n
+
3
t
+
12
9
n
+
3
t
+
12
9
n
+
3
t
+
13
9
n
+
3
t
+
12
9
n
+
3
t
+
15Scenario 1: when number of threshold signers,t=1.Scenario 2: when number of threshold signers,t=n.Figures16 and 17 also show that for both the scenarios, the space complexity increases with the increase in the number of proxy signers. This is because as the number of proxy signers increases, the number of variables also increases due to which the memory requirements increase. Memory overhead increases because for each proxy signers, the following parameters are required.(1)
RSA modulus,Ni.(2)
Private key,di.(3)
Public key,ei.(4)
pi and qi.(5)
Φ(Ni).(6)
Ki.The more the number of proxy signers, the more the memory requirements. The figures generated also confirm this point.Also, we observe in the graphs that memory overhead is more in the case oft=n than in the case of t=1. It is because the number of variables increases with the number of threshold signers as well. For each threshold signer, the following variables have to be declared.(1)
Partial proxy signatures,si.(2)
The Lagrange coefficient,Li.The more the number of threshold proxy signers, the more the memory requirements as confirmed by the graphs generated.


## 6.3. Communication Overhead

The communication overhead includes two types of communication in the schemes:(1)
number of transmissions;(2)
number of broadcasts.


### 6.3.1. Comparison of the Schemes

Table6 shows the communication overhead for each scheme for various phases. In Figure 6, we find that the communication overhead of all the schemes is the same.


### 6.3.2. Results

Figure18 has been generated from Table 15, which can be referred to to find the number of transmissions and broadcasts to compute the communication overhead for all the schemes. Table 16 can be referred to to find the comparison between threshold proxy signature schemes based upon proxy requirements. As evident from Figure 18, the communication overhead of all the schemes is the same.Table 16
Comparison of communication overheads of the threshold proxy signature schemes.
Schemes
HLL
KC
Geng
Fengying
Proposed
Number  of Communications
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
Number of transmissions
n
t
n
t
n
t
n
t
n
t
Number of broadcasts
3
0
3
0
3
0
3
0
3
0
Total
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
PS: proxy sharing phase.
PSIV: proxy signature issuing and verification phase.Table 17
*
Schemes
HLL
Frequency 1
KUOCHEN
Frequency 2
GENGVRF
Frequency 3
FNGVERF
Frequency 4
THRSPROX
Frequency 5
No.
Substring
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
1
N
11.0343
654
11.3387
631
10.9658
587
10.947
630
11.5549
891
2
I
9.1277
541
8.841
492
9.4153
504
9.1573
527
8.7278
673
3
T
8.824
523
8.6253
480
9.079
486
8.7576
504
8.5981
663
4
E
8.6216
511
8.4636
471
8.3878
449
8.3927
483
8.5722
661
5
S
7.4405
441
7.8886
439
7.9208
424
8.2711
476
8.3258
642
6
R
7.1368
423
7.044
392
7.1175
381
6.9505
400
6.6399
512
7
A
5.0785
301
4.8697
271
4.7076
252
4.7089
271
5.4597
421
8
O
4.6567
276
4.6361
258
4.5769
245
4.6568
268
4.539
350
9
C
4.1842
248
4.4205
246
3.9978
214
4.066
234
4.3963
339
10
D
3.6612
217
3.8455
214
3.6802
197
3.8401
221
3.696
285
11
U
3.5937
213
3.2884
183
3.5681
191
3.5274
203
3.4626
267
12
F
3.2732
194
3.2165
179
3.5494
190
3.5274
203
3.3329
257
13
P
3.1213
185
3.1626
176
3.4747
186
3.4231
197
3.307
255
14
G
3.0707
182
3.0189
168
2.989
160
3.3189
191
3.1384
242
15
L
3.0201
179
2.9111
162
2.8956
155
2.7454
158
3.0865
238
16
H
2.8682
170
2.8392
158
2.7835
149
2.6933
155
2.5937
200
17
Y
2.6489
157
2.6954
150
2.3538
126
2.6759
154
2.3603
182
18
M
2.4296
144
1.8509
103
1.8121
97
1.7724
102
1.8934
146
19
X
1.4341
85
1.4196
79
1.4945
80
1.4248
82
1.634
126
20
V
1.0798
64
1.2579
70
1.3824
74
1.1816
68
1.2061
93
21
W
0.9954
59
1.15
64
0.9714
52
1.0252
59
0.83
64
22
J
0.8267
49
1.0422
58
0.8967
48
0.8862
51
0.817
63
23
B
0.7761
46
0.9164
51
0.7659
41
0.8688
50
0.7522
58
24
K
0.6917
41
0.7907
44
0.7286
39
0.7298
42
0.7133
55
25
Q
0.3374
20
0.3953
22
0.411
22
0.3823
22
0.3112
24
26
Z
0.0675
4
0.0719
4
0.0747
4
0.0695
4
0.0519
4Figure 18
Comparison of schemes based on communication overhead.Figure 19
Overall communication architecture for secure threshold proxy signature scheme based on RSA cryptosystem.Figure19 shows the overall communication architecture for the secure threshold proxy signature scheme based on RSA cryptosystem for known signers. It sends a message after logging in to the system. It also sends a message to the other client using the secure threshold proxy signature scheme based on the RSA cryptosystem for known signers. In this, the delegates can send the message to the n proxy signers with security. After sending the message, it logs out from the system. We have improved the results after improving the performance of four schemes: Hwang et al. [7], Kuo and Chen [9], Yong-Jun et al. [11], and Li et al. [10], with the performance of a scheme that has been proposed by the authors of this paper earlier. In this paper, we compared the various threshold proxy signature schemes based on how they violate proxy signature requirements. Table 16 summarizes the comparison of four threshold proxy signature schemes: Kim et al.’s scheme, Sun’s scheme, HLL scheme, and Wen et al.’s scheme. We also propose a new scheme which includes the features and benefits of the two schemes: Fengying et al. and Geng et al. The main advantages of our proposed scheme are as follows.(i)
It achieved the property of nonrepudiation.(ii)
Anyone cannot forge the legal proxy signature.(iii)
The verifier can identify the actual proxy signer of its group.(iv)
It also provides more refined result against its time complexity, space complexity, and communication overhead.(v)
The proposed scheme is secure and efficient against notorious conspiracy attacks.


## 6.3.1. Comparison of the Schemes

Table6 shows the communication overhead for each scheme for various phases. In Figure 6, we find that the communication overhead of all the schemes is the same.


## 6.3.2. Results

Figure18 has been generated from Table 15, which can be referred to to find the number of transmissions and broadcasts to compute the communication overhead for all the schemes. Table 16 can be referred to to find the comparison between threshold proxy signature schemes based upon proxy requirements. As evident from Figure 18, the communication overhead of all the schemes is the same.Table 16
Comparison of communication overheads of the threshold proxy signature schemes.
Schemes
HLL
KC
Geng
Fengying
Proposed
Number  of Communications
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
PS
PSIV
Number of transmissions
n
t
n
t
n
t
n
t
n
t
Number of broadcasts
3
0
3
0
3
0
3
0
3
0
Total
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
n
+
t
+
3
PS: proxy sharing phase.
PSIV: proxy signature issuing and verification phase.Table 17
*
Schemes
HLL
Frequency 1
KUOCHEN
Frequency 2
GENGVRF
Frequency 3
FNGVERF
Frequency 4
THRSPROX
Frequency 5
No.
Substring
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
Frequency(in %)
Frequency
1
N
11.0343
654
11.3387
631
10.9658
587
10.947
630
11.5549
891
2
I
9.1277
541
8.841
492
9.4153
504
9.1573
527
8.7278
673
3
T
8.824
523
8.6253
480
9.079
486
8.7576
504
8.5981
663
4
E
8.6216
511
8.4636
471
8.3878
449
8.3927
483
8.5722
661
5
S
7.4405
441
7.8886
439
7.9208
424
8.2711
476
8.3258
642
6
R
7.1368
423
7.044
392
7.1175
381
6.9505
400
6.6399
512
7
A
5.0785
301
4.8697
271
4.7076
252
4.7089
271
5.4597
421
8
O
4.6567
276
4.6361
258
4.5769
245
4.6568
268
4.539
350
9
C
4.1842
248
4.4205
246
3.9978
214
4.066
234
4.3963
339
10
D
3.6612
217
3.8455
214
3.6802
197
3.8401
221
3.696
285
11
U
3.5937
213
3.2884
183
3.5681
191
3.5274
203
3.4626
267
12
F
3.2732
194
3.2165
179
3.5494
190
3.5274
203
3.3329
257
13
P
3.1213
185
3.1626
176
3.4747
186
3.4231
197
3.307
255
14
G
3.0707
182
3.0189
168
2.989
160
3.3189
191
3.1384
242
15
L
3.0201
179
2.9111
162
2.8956
155
2.7454
158
3.0865
238
16
H
2.8682
170
2.8392
158
2.7835
149
2.6933
155
2.5937
200
17
Y
2.6489
157
2.6954
150
2.3538
126
2.6759
154
2.3603
182
18
M
2.4296
144
1.8509
103
1.8121
97
1.7724
102
1.8934
146
19
X
1.4341
85
1.4196
79
1.4945
80
1.4248
82
1.634
126
20
V
1.0798
64
1.2579
70
1.3824
74
1.1816
68
1.2061
93
21
W
0.9954
59
1.15
64
0.9714
52
1.0252
59
0.83
64
22
J
0.8267
49
1.0422
58
0.8967
48
0.8862
51
0.817
63
23
B
0.7761
46
0.9164
51
0.7659
41
0.8688
50
0.7522
58
24
K
0.6917
41
0.7907
44
0.7286
39
0.7298
42
0.7133
55
25
Q
0.3374
20
0.3953
22
0.411
22
0.3823
22
0.3112
24
26
Z
0.0675
4
0.0719
4
0.0747
4
0.0695
4
0.0519
4Figure 18
Comparison of schemes based on communication overhead.Figure 19
Overall communication architecture for secure threshold proxy signature scheme based on RSA cryptosystem.Figure19 shows the overall communication architecture for the secure threshold proxy signature scheme based on RSA cryptosystem for known signers. It sends a message after logging in to the system. It also sends a message to the other client using the secure threshold proxy signature scheme based on the RSA cryptosystem for known signers. In this, the delegates can send the message to the n proxy signers with security. After sending the message, it logs out from the system. We have improved the results after improving the performance of four schemes: Hwang et al. [7], Kuo and Chen [9], Yong-Jun et al. [11], and Li et al. [10], with the performance of a scheme that has been proposed by the authors of this paper earlier. In this paper, we compared the various threshold proxy signature schemes based on how they violate proxy signature requirements. Table 16 summarizes the comparison of four threshold proxy signature schemes: Kim et al.’s scheme, Sun’s scheme, HLL scheme, and Wen et al.’s scheme. We also propose a new scheme which includes the features and benefits of the two schemes: Fengying et al. and Geng et al. The main advantages of our proposed scheme are as follows.(i)
It achieved the property of nonrepudiation.(ii)
Anyone cannot forge the legal proxy signature.(iii)
The verifier can identify the actual proxy signer of its group.(iv)
It also provides more refined result against its time complexity, space complexity, and communication overhead.(v)
The proposed scheme is secure and efficient against notorious conspiracy attacks.


## 7. Conclusion

As the proxy signature is the solution to the delegation of signing capabilities in any electronic environment, in this paper, various threshold proxy signature schemes have been compared based on whether they fulfill the proxy signature requirements or not and proposed an enhanced secure threshold proxy signature scheme. Some of these schemes are based on an RSA cryptosystem for known signers, as the RSA cryptosystem is a popular security technique. In this, we also propose a new scheme which includes the features and benefits of the two schemes: Fengying et al. and Geng et al. The implementation of the encryption and decryption functions justifies the real-life applicability of the proposed scheme. In this, we have analyzed our enhanced threshold proxy signature scheme for various parameters.In essence, the results show that the enhanced threshold proxy signature scheme is an efficient one and it can provide great capabilities for various applications.



---

*Source: 790257-2013-03-28.xml*