# Cryptanalytic Performance Appraisal of Improved CCH2 Proxy Multisignature Scheme

Authors: Raman Kumar; Nonika Singla
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Many of the signature schemes are proposed in which thet out of n threshold schemes are deployed, but they still lack the property of security. In this paper, we have discussed implementation of improved CCH1 and improved CCH2 proxy multisignature scheme based on elliptic curve cryptosystem. We have represented time complexity, space complexity, and computational overhead of improved CCH1 and CCH2 proxy multisignature schemes. We have presented cryptanalysis of improved CCH2 proxy multisignature scheme and showed that improved CCH2 scheme suffered from various attacks, that is, forgery attack and framing attack.


---

## Body

## 1. Introduction

During the last decade there has been an exponential growth in the number of handheld devices being used all over the world. Devices with limited processing capability such as PDA and smart cards also exchange information over the networks. To provide the confidentiality and authenticity of information is a challenging task in a network environment which consists of constrained devices. The security of public key systems is based on the relative complexity of the underlying mathematical problem. For example, the security of RSA depends on integer factorizing systems and that of DSA depends on discrete logarithm systems [1]. Proxy signatures are very useful tools when one needs to delegate his/her signing capability to another party. Relatively longer key lengths are required to maintain the security of a cryptosystem, because the computational power for cryptanalysis increases. This increases the need for higher computational power in devices to achieve reasonable security. But handheld devices like PDAs, smart cards, and so forth have limited processing capability and therefore the overheads associated with communication must be minimal.


### 1.1. Various Terms

(i)
Proxy signature: proxy signature, as a variant of ordinary digital signature, allows one party (original signer) to delegate his/her signing capability to another party (proxy signer) such that the proxy signer can sign messages on behalf of the original signer [2].
(ii)
Proxy multisignature: in proxy multisignature, one proxy signer can create signature on behalf of group of original signers.
(iii)
Multiproxy signature: in multiproxy signature, multiple proxy signers can create signature on behalf of one original signer.
(iv)
Multiproxy multisignature: in multiproxy multisignature, multiple proxy signers can create signature on behalf of multiple original signers.
(v)
Proxy unprotected proxy signature: in proxy unprotected, the proxy signer generates proxy signatures only with the proxy signing key given by the original signer. So the original signer can also generate the same proxy signatures.
(vi)
Proxy protected proxy signature: in proxy protected, the proxy signer generates proxy signature not only with the proxy signing key given by the original signer but also with his own private key. Therefore, anyone else, including the original signer, cannot generate the same proxy signatures.According to authenticated degree, Mambo et al. [4] give a classification, that is, full delegation, partial delegation, and delegation by warrant.In full delegation, the original signer gives the same secret key(s) to proxy signer that he has, so that proxy signer can create the same signature as original signer creates. In partial delegation, a proxy signer has proxy private key, which is different from original signer’s private key. Proxy signer can sign range of messages. In delegation by warrant, warrant is added that specifies what kinds of messages are delegated, the delegation period, IDs of original signers and proxy signer, and so forth.


### 1.2. Elliptic Curve over Finite Field GF (p)

In 1985, elliptic curve cryptography was introduced by Miller [5] and Koblitz [6]. ECC is an attractive public key cryptosystem due to small key size and low computational overhead.Equation of the elliptic curve on a prime field GF (p) is
(1)
y
2
(
mod
⁡
p
)
=
x
3
+
a
x
+
b
(
mod
⁡
p
)
,
where 4
a
3
+
27
b
2 mod p
≠
0. Here the elements of the finite field are integers between 0 and p
-
1, where p is a large prime number and greater than 3. The operations are performed using modular arithmetic. Modular arithmetic works like ordinary arithmetic except that the answers of the calculation are reduced to its remainder on division by p. The variables and coefficients all take values in set of integers from 0 through p
-
1. The prime number p is chosen such that there is finitely large number of points on the elliptic curve to make the cryptosystem secure. Point multiplication is calculated by two elliptic curve operations, that is, point addition and point doubling (Figure 2). The rules for point addition and point doubling over GF (p) are explained below and see Figure 1.Point addition [3].
(a)
(b)Point doubling [3].
(a)
(b)


### 1.3. Point Addition

The elliptic curve addition is different from simple addition.J and K are two distinct points on the elliptic curve; that is, J
=
(
x
1
,
y
1
) and K
=
(
x
2
,
y
2
) [3].LetL
=
J
+
K
=
(
x
3
,
y
3
) be obtained through the following rules:
(2)
x
3
=
λ
2
-
x
1
-
x
2
(
mod
⁡
p
)
,
y
3
=
λ
(
x
1
-
x
3
)
-
y
1
(
mod
⁡
p
)
,
where λ
=
(
y
2
-
y
1
)
/
(
x
2
-
x
1
) mod p is the slope of the line through J and K. (i)
IfK
=
-
J, that is, K
=
(
x
1
,
-
y
1
mod
⁡
p
), then J
+
K
=
O, where O is the point at infinity.
(ii)
IfK
=
J, then J
+
K
=
2
J; then point doubling equations are used.


### 1.4. Point Doubling

Consider a pointJ such that J
=
(
x
1
,
y
1
), where y
1
≠
0 [3]. Let L
=
2
J where L
=
(
x
2
,
y
2
). Then
(3)
x
2
=
λ
2
-
2
x
1
(
mod
⁡
p
)
,
y
2
=
λ
(
x
1
-
x
2
)
-
y
1
(
mod
⁡
p
)
,
where λ
=
(
(
3
×
12
+
a
)
/
(
2
y
1
)
) mod p is the tangent at point J and a is one of the parameters chosen with the elliptic curve.(i)
Ify
1
=
0, then 2
J
=
O, where O is the point at infinity.


### 1.5. Domain Parameters for Elliptic Curve over GF (p) Are (p, a, b, B, t)

p is the prime number defined for finite field GF (p). a, b
∈
GF
(
p
) are the two coefficients defining the curve y
2
mod
⁡
p
=
(
x
3
+
a
x
+
b
)
mod
⁡
p. B is the generator point (
X
B
,
Y
B
) and t is the order of B.


### 1.6. Various Security Parameters

A proxy signature should have security properties [4] and they are as follows.(1)
Strong unforgeability: proxy signatures can be created only by designated proxy signer. Original signer or any other party cannot generate proxy signatures.
(2)
Verifiability: a verifier can be convinced of the original signer’s agreement on the signed message from the proxy signature.
(3)
Strong identifiability: from the proxy signature, anyone can determine the identity of corresponding proxy signer.
(4)
Strong undeniability: once valid proxy signature is created by proxy signer, he/she cannot repudiate signature creation.
(5)
Distinguishability: proxy signatures are distinguishable from ordinary signature created by original signer.


### 1.7. Various Attacks

(i)
Public key substitution attack: in this attack, original signer can generate proxy multisignature by updating his own public key [7].
(ii)
Original signer’s forgery attack: in this attack, original signers can generate valid proxy multisignature without agreement of proxy signer and verifier will be convinced that any proxy multisignature generated by using forged signing key is generated by agreement of all, original signer and proxy signer [8]. Under the name of proxy signer, original signer can forge valid proxy multisignature.
(iii)
Framing attack: in this attack, any userP is framed by malicious users A
1
,
A
2
,
…
,
A
n. User P does not receive any delegation from the users A
1
,
A
2
,
…
,
A
n, but the malicious users A
1
,
A
2
,
…
,
A
n can forge a proxy multisignature for message m by user P on behalf of users A
1
,
A
2
,
…
,
A
n [9].


## 1.1. Various Terms

(i)
Proxy signature: proxy signature, as a variant of ordinary digital signature, allows one party (original signer) to delegate his/her signing capability to another party (proxy signer) such that the proxy signer can sign messages on behalf of the original signer [2].
(ii)
Proxy multisignature: in proxy multisignature, one proxy signer can create signature on behalf of group of original signers.
(iii)
Multiproxy signature: in multiproxy signature, multiple proxy signers can create signature on behalf of one original signer.
(iv)
Multiproxy multisignature: in multiproxy multisignature, multiple proxy signers can create signature on behalf of multiple original signers.
(v)
Proxy unprotected proxy signature: in proxy unprotected, the proxy signer generates proxy signatures only with the proxy signing key given by the original signer. So the original signer can also generate the same proxy signatures.
(vi)
Proxy protected proxy signature: in proxy protected, the proxy signer generates proxy signature not only with the proxy signing key given by the original signer but also with his own private key. Therefore, anyone else, including the original signer, cannot generate the same proxy signatures.According to authenticated degree, Mambo et al. [4] give a classification, that is, full delegation, partial delegation, and delegation by warrant.In full delegation, the original signer gives the same secret key(s) to proxy signer that he has, so that proxy signer can create the same signature as original signer creates. In partial delegation, a proxy signer has proxy private key, which is different from original signer’s private key. Proxy signer can sign range of messages. In delegation by warrant, warrant is added that specifies what kinds of messages are delegated, the delegation period, IDs of original signers and proxy signer, and so forth.


## 1.2. Elliptic Curve over Finite Field GF (p)

In 1985, elliptic curve cryptography was introduced by Miller [5] and Koblitz [6]. ECC is an attractive public key cryptosystem due to small key size and low computational overhead.Equation of the elliptic curve on a prime field GF (p) is
(1)
y
2
(
mod
⁡
p
)
=
x
3
+
a
x
+
b
(
mod
⁡
p
)
,
where 4
a
3
+
27
b
2 mod p
≠
0. Here the elements of the finite field are integers between 0 and p
-
1, where p is a large prime number and greater than 3. The operations are performed using modular arithmetic. Modular arithmetic works like ordinary arithmetic except that the answers of the calculation are reduced to its remainder on division by p. The variables and coefficients all take values in set of integers from 0 through p
-
1. The prime number p is chosen such that there is finitely large number of points on the elliptic curve to make the cryptosystem secure. Point multiplication is calculated by two elliptic curve operations, that is, point addition and point doubling (Figure 2). The rules for point addition and point doubling over GF (p) are explained below and see Figure 1.Point addition [3].
(a)
(b)Point doubling [3].
(a)
(b)


## 1.3. Point Addition

The elliptic curve addition is different from simple addition.J and K are two distinct points on the elliptic curve; that is, J
=
(
x
1
,
y
1
) and K
=
(
x
2
,
y
2
) [3].LetL
=
J
+
K
=
(
x
3
,
y
3
) be obtained through the following rules:
(2)
x
3
=
λ
2
-
x
1
-
x
2
(
mod
⁡
p
)
,
y
3
=
λ
(
x
1
-
x
3
)
-
y
1
(
mod
⁡
p
)
,
where λ
=
(
y
2
-
y
1
)
/
(
x
2
-
x
1
) mod p is the slope of the line through J and K. (i)
IfK
=
-
J, that is, K
=
(
x
1
,
-
y
1
mod
⁡
p
), then J
+
K
=
O, where O is the point at infinity.
(ii)
IfK
=
J, then J
+
K
=
2
J; then point doubling equations are used.


## 1.4. Point Doubling

Consider a pointJ such that J
=
(
x
1
,
y
1
), where y
1
≠
0 [3]. Let L
=
2
J where L
=
(
x
2
,
y
2
). Then
(3)
x
2
=
λ
2
-
2
x
1
(
mod
⁡
p
)
,
y
2
=
λ
(
x
1
-
x
2
)
-
y
1
(
mod
⁡
p
)
,
where λ
=
(
(
3
×
12
+
a
)
/
(
2
y
1
)
) mod p is the tangent at point J and a is one of the parameters chosen with the elliptic curve.(i)
Ify
1
=
0, then 2
J
=
O, where O is the point at infinity.


## 1.5. Domain Parameters for Elliptic Curve over GF (p) Are (p, a, b, B, t)

p is the prime number defined for finite field GF (p). a, b
∈
GF
(
p
) are the two coefficients defining the curve y
2
mod
⁡
p
=
(
x
3
+
a
x
+
b
)
mod
⁡
p. B is the generator point (
X
B
,
Y
B
) and t is the order of B.


## 1.6. Various Security Parameters

A proxy signature should have security properties [4] and they are as follows.(1)
Strong unforgeability: proxy signatures can be created only by designated proxy signer. Original signer or any other party cannot generate proxy signatures.
(2)
Verifiability: a verifier can be convinced of the original signer’s agreement on the signed message from the proxy signature.
(3)
Strong identifiability: from the proxy signature, anyone can determine the identity of corresponding proxy signer.
(4)
Strong undeniability: once valid proxy signature is created by proxy signer, he/she cannot repudiate signature creation.
(5)
Distinguishability: proxy signatures are distinguishable from ordinary signature created by original signer.


## 1.7. Various Attacks

(i)
Public key substitution attack: in this attack, original signer can generate proxy multisignature by updating his own public key [7].
(ii)
Original signer’s forgery attack: in this attack, original signers can generate valid proxy multisignature without agreement of proxy signer and verifier will be convinced that any proxy multisignature generated by using forged signing key is generated by agreement of all, original signer and proxy signer [8]. Under the name of proxy signer, original signer can forge valid proxy multisignature.
(iii)
Framing attack: in this attack, any userP is framed by malicious users A
1
,
A
2
,
…
,
A
n. User P does not receive any delegation from the users A
1
,
A
2
,
…
,
A
n, but the malicious users A
1
,
A
2
,
…
,
A
n can forge a proxy multisignature for message m by user P on behalf of users A
1
,
A
2
,
…
,
A
n [9].


## 2. Review of Existing Schemes

Mambo et al. [4] define the different types of delegations like full delegation, partial delegation, and delegation by warrant. They have proposed a proxy signature scheme that is based on discrete logarithm problem. They have compared different proxy signature schemes like Schnorr scheme, Elgamal scheme, and Okamoto scheme on the basis of message length and amount of computational work. In all the above schemes, the amount of computational work in partial delegation is smaller than that with delegation by warrant. In partial delegation, a proxy signer can create proxy signature forever because valid period is not specified. In this case the original signer can revoke the signing capability of the proxy signer by two ways, that is, (1) to make revocation list publicly seen and (2) to change the public key of original signer and all proxies of honest proxy signers are updated accordingly.Mambo et al. [10] proposed a new type of proxy signature scheme based on discrete logarithm problem. Scheme that is proposed by Mambo et al.’s [4] holds sufficient properties if original signer is trustworthy and never cheats. If the original signer is not trustworthy then proxy protected proxy signature scheme is important and they have introduced proxy protected proxy signature scheme based on discrete logarithm problem.Kim et al. [11] have introduced two new types of proxy signature schemes based on discrete logarithm problem, that is, partial delegation with warrant and threshold delegation. Partial delegation with warrant combines the benefits of partial delegation and delegation with warrant. Valid period can be specified in proxy signature for partial delegation with warrant, so their new scheme does not require an additional proxy revocation protocol. In threshold delegation, the original signer delegates the power to sign message in such a way that from the designated group of n proxy signers, t or more proxy signers can create signature and t
-
1 or less proxy signers cannot create signature on behalf of original signer.Yi et al. [12] proposed a new type of proxy signature scheme, that is, proxy multisignature scheme in which a proxy signer can create signature on behalf of two or more original signers. They give the overview of proxy monosignature schemes, that is, Mambo et al.’s [4] and Kim et al.’s [11]. They have introduced Mambo-like proxy multisignature scheme and Kim-like proxy multisignature scheme. Their schemes are proxy unprotected schemes; that is, original signer can also create proxy signature.Sun [7] analyzes the proxy signature and proxy multisignature schemes and their analysis indicates that these schemes suffer from the public key substitution attack and direct forgery attack. They analyzes Yi et al.’s [12] proxy multisignature schemes and shows that these schemes suffer from public key substitution attack (an original signer can forge proxy multisignature by updating his own public key) and direct forgery attack (one original signer can generate forged proxy multisignature on arbitrary message for multiple original signers). They proposed a new proxy protected and proxy unprotected proxy multisignature schemes which do not suffer from these attacks.Lee et al. [13] provide new classifications of proxy signature scheme, that is, strong and weak proxy signature, designated and nondesignated proxy signature, and self-proxy signature. They proposed a strong nondesignated proxy signature scheme. The proposed scheme does not specify proxy signer so it can be applied to multiproxy signature in which multiple original signers can delegate their signing capabilities to proxy signers.Chen et al. [14] proposed a new proxy protected proxy signature scheme which is based on elliptic curve discrete logarithm problem. They analyze the performance of Sun [7] and the proposed scheme on the basis of time complexity.Chen et al. [1] proposed an improved scheme in which the exponential operations are changed into elliptic curve multiplicative ones. Sun [7] improvement increases security but requires complex operations to derive the proxy public key that is required to verify the proxy multisignature. ECC has lower computational overhead and a smaller key size than that of RSA or DSA and ECC can achieve a level of security equal to that of the RSA or DSA. This proposed scheme is called CCH1 scheme. They compared the Sun [7] and proposed proxy multisignature schemes. The time complexity of proposed scheme is reduced and performance is enhanced without loss of security.Chen et al. [15] introduced a traceable proxy multisignature scheme. This scheme makes size of proxy signature independent of number of original signers, so computation overhead means none of operations required for verification is greatly reduced. This proposed scheme is called CCH2 scheme. They compare the Sun [7] and proposed proxy multisignature schemes on the basis of time complexity.Hwang et al. [16] proposed a generalized version of the (
t
1
/
n
1
-
t
2
/
n
2
) proxy signature scheme based on elliptic curve discrete logarithm problem. In a generalized proxy signature scheme with known signers, any t
1 or more original signers out of n
1 original signers (
1
≤
t
1
≤
n
1
) can represent the original group to delegate the signing capability, and t
2 or more proxy signers out of n
2 proxy signers (
1
≤
t
2
≤
n
2
) can represent the proxy group to sign message on behalf of the group of original signers. They have discussed special cases, namely, the (
t
1
/
n
1
-
1
) proxy signature (proxy multisignature) scheme, (
1
-
t
2
/
n
2
) proxy signature scheme (multiproxy signature), and (
1
-
1
) proxy signature scheme.Wang et al. [17] present security analysis of some proxy signature schemes, that is, Mambo et al.’s [10] and Lee et al.’s [13]. By identifying several attacks, they show that all these schemes are insecure.Wang et al. [2] review Chen et al.’s [14] proxy protected proxy signature scheme based on elliptic curve cryptosystem and they show that it is vulnerable to an original signer forgery attack. They present an improved scheme which is secure against the proposed attack.Park et al. [8] show that proxy multisignature schemes proposed by Chen et al. [1, 15] are insecure against the malicious original signer(s). They review the CCH1 and CCH2 schemes and analyze their security. These schemes are vulnerable to proxy signing forgery attack by one or all original signers.Chang et al. [18] proposed a proxy protected signature scheme based on ECDSA which satisfies security properties. They show that the time complexity of proxy signature is similar in both proxy signature based on ECDSA and ECDSA.Li and Xue [19] have reviewed CCH1 and CCH2 proxy multisignature schemes based on elliptic curve cryptography. Park et al. [8] show that these schemes suffer from forgery attack by one or all original signers. They have proposed improved CCH1 and improved CCH2 schemes that do not suffer from forgery attack.Tutanescu et al. [3] examine that ECC is more attractive cryptosystem than conventional cryptosystem (RSA/DSA) for mobile devices, which are limited in terms of their CPU, power, and network connectivity. ECC is fast and can be implemented with less hardware, because of shorter key length. They have presented the application of ECC, that is, internet, smart cards, PDAs, and PCs. Their opinion is that ECC could become the next generation of PKC.Wang and Yu [20] have discussed two fatal flaws of the cryptosystem which are based on the logistic map and proposed by Wang and Xiang are pointed out. According to this, cryptanalysts could recover the plaintext by the chosen plaintext attacked in a short time. Authors proposed a remedial improvement which can avoid the flaws and enhance the security of the cryptosystem.In this paper [21], have analyzed the security of a parallel keyed hash function based on chaotic neural network proposed by Wang and Zhao recently. Weak keys and forgery attacks against Wang and Zhao’s scheme are demonstrated. Both theoretical analysis and experimental results show that the parallel keyed hash function is not security. Besides, some improvement measures are presented to enhance the security of the parallel keyed hash function.Wang and He [22] have introduced a novel image encryption method based on a skew tent map that is proposed recently. In this paper, some flaws of this algorithm are pointed out and then a chosen plaintext attack against it is presented. Both theoretical analysis and experimental simulation indicate that the plain image can be recovered exactly from the cipher image without the secret key. So it can be seen that this algorithm is not secure enough to be applied in network communication.Wang and Liu [23] have cryptanalysis of a parallel subimage encryption method with high-dimensional chaos.


## 3. Estimation of Time, Space, and Computational Overhead of Improved CCH1 and CCH2 Schemes

### 3.1. Implementation of Improved CCH1 Proxy Multisignature Scheme

There are four phases—the system initialization phase, the key generation phase, the proxy multisignature generation phase, and the proxy multisignature verification phase [19].Phase 1. System initialization phase: before the whole scheme can be initialized, the following parameters over the elliptic curve domain must be known:(i)
a field sizep, which is odd prime;
(ii)
two parametersa, b
∈
F
p to define the equation of elliptic curve E over F
p (i.e., y
2
=
x
3
+
a
x
+
b (mod
⁡
p)), where 4
a
3
+
27
b
2
≠
0 (mod
⁡
p);
(iii)
a finite pointB
=
(
x
B
,
y
B
) whose order is a large prime number in E
(
F
p
), where B is a point in E
(
F
p
), where B
≠
O, because O denotes an infinity point;
(iv)
the order ofB
=
t.Phase 2. Key generation phase: this phase can be further divided into two parts.Part 1. Personal public key generation phase: all original signers and the designated proxy signer are authorized to select their own individual secret keys.(i)
For each1
≤
i
≤
n, the original signer A
i secretly selects a random number 1
≤
d
i
≤
t
-
1 as his private key and computes the corresponding public key Q
i
=
d
i
×
B
=
(
x
Q
i
,
y
Q
i
), where “×” indicates the multiplication of a number by an elliptic curve point.
(ii)
The proxy signer is provided with a private key1
≤
d
p
≤
t
-
1 and a corresponding public key Q
p
=
d
p
×
B
=
(
x
Q
p
,
y
Q
p
). All public keys Q
i and Q
p must be certified by the CA.Part 2. Proxy-signature secret key generation phase.Step  1 (secret key generation). For each 1
≤
i
≤
n, the original signer A
i selects a random number k
i
∈
{
1
,
2
⋯
t
-
1
}
/
d
i as secret key.Step  2 (group commitment value generation). They then computes
(4)
R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
)
.
If x
R
i
=
0, then return to step 1; otherwise A
i broadcasts R
i to other original signers.Step  3 (subdelegation parameter generation). For each 1
≤
i
≤
n, the original signer A
i uses his own secret keys d
i, k
i and the group commitment value x
R to compute the following:
(5)
s
i
=
d
i
*
x
Q
i
*
h
(
M
w
,
R
i
)
-
k
i
*
x
R
i
(
mod
⁡
t
)
,
where h
(
) is a hash function and the warrant M
w contains information such as the IDs of all original signers and proxy signer. Then, the subdelegation parameter for A
i is (
M
w
,
R
i
,
s
i
).Step  4 (subdelegation parameter verification). After the proxy signer has received the subdelegation parameters, then the proxy signer P computes
(6)
S
i
×
B
=
(
x
Q
i
*
h
(
M
w
,
R
i
)
)
*
Q
i
-
x
R
i
R
i
and checks whether it holds. If it holds then the proxy signer accepts (
M
w
,
R
i
,
s
i
) as a valid subdelegation parameter; otherwise, he can reject it and requests a valid one A
i or terminate this protocol.Step  5 (proxy multisignature secret key generation). He then computes the proxy multisignature secret key as follows:
(7)
d
=
d
p
*
x
Q
P
+
∑
i
=
1
n
s
i

(
mod
⁡
t
)
.
Phase 3. Proxy multisignature generation phase: the proxy multisignature affixed to the m is in the form of (
m
,
m
w
,
R
,
Sig
d
(
m
)
), where Sig
d
(
m
) is the signature generated by a designated signature scheme (EC-Schnorr signature scheme) using the proxy signing key d and m is message.Step  1. Proxy signer P chooses random number j where 1
≤
j
≤
t
-
1 and calculates J
=
j
×
B
=
(
J
x
,
J
y
).Step  2. Compute e
=
h
(
m
,
J
x
) where h
(
J
x
,
m
) is hash function. If e
=
0, then go to step 1.Step  3. Compute
(8)
y
=
j
-
d
*
e
(
mod
⁡
t
)
,
and the output sign
⁡
d
(
m
)
=
(
e
,
y
).Phase 4. Proxy multisignature verification phase: when the verifier verifies the signature, he or she calculates the proxy public value Q corresponding to the proxy signature key d as
(9)
Q
=
Q
P
*
x
Q
p
+
∑
i
=
1
n
(
h
(
M
w
,
R
i
)
*
Q
i
-
x
R
i
×
R
i
)
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


### 3.2. Implementation of Improved CCH2 Proxy Multisignature Scheme

There are four phases—the system initialization phase, the key generation phase, the proxy multisignature generation phase, and the proxy multisignature verification phase [19].Phase 1. System initialization phase: before the whole scheme can be initialized, the following parameters over the elliptic curve domain must be known:(i)
a field sizep, which is an odd prime;
(ii)
two parametersa, b
∈
F
p to define the equation of elliptic curve E over F
p (i.e., y
2
=
x
3
+
a
x
+
b
(
mod
⁡
p
)
), where 4
a
3
+
27
b
2
≠
0
(
mod
⁡
p
);
(iii)
a finite pointB
=
(
x
B
,
y
B
) whose order is a large prime number in (
F
p
), where B is a point in E
(
F
p
), where B
≠
O, because O denotes an infinity point;
(iv)
the order ofB
=
t.Phase 2. Key generation phase: this phase can be further divided into two parts.Part 1. Personal public key generation phase: all original signers and the designated proxy signer are authorized to select their own individual secret keys.(i)
For each1
≤
i
≤
n, the original signer A
i secretly selects a random number 1
≤
d
i
≤
t
-
1 as his private key and computes the corresponding public key Q
i
=
d
i
×
B
=
(
x
Q
i
,
y
Q
i
), where “×” indicates the multiplication of a number by an elliptic curve point.
(ii)
The proxy signer is provided with a private key1
≤
d
p
≤
t
-
1 and a corresponding public key Q
p
=
d
p
×
B
=
(
x
Q
p
,
y
Q
p
). All public keys Q
i and Q
p must be certified by the CA.Part 2. Proxy-signature secret key generation phase.Step  1 (secret key generation). For each 1
≤
i
≤
n, the original signer A
i selects a random number k
i
∈
{
1
,
2
,
…
,
t
-
1
}
/
d
i as secret key.Step  2 (group commitment value generation). Then computes R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
). If x
R
i
=
0, then return to step 1; otherwise A
i broadcasts R
i to other original signers. On receiving R
j
(
1
≤
j
≤
n,  j
≠
i
), A
i calculates
(10)
i
=
(
x
R
,
y
R
)
.Step  3 (subdelegation parameter generation). For each 1
≤
i
≤
n, the original signer A
i uses his own secret keys d
i, k
i and the group commitment value x
R to compute the following:
(11)
s
i
=
d
i
*
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
-
k
i
*
x
R
(
mod
⁡
t
)
,
where h
(
) is a hash function and the warrant M
w contains information such as the IDs of all original signers and proxy signer. Then, the subdelegation parameter for A
i is (
M
w
,
s
i
).Step  4 (subdelegation parameter verification). After the proxy signer has received the subdelegation parameters then the proxy signer P computes
(12)
s
i
*
B
=
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
*
Q
i
-
x
R
×
R
i
and checks whether it holds. If it holds then the proxy signer accepts (
M
w
,
s
i
) as a valid subdelegation parameter; otherwise, he can reject it and requests a valid one A
i or terminate this protocol.Step  5 (proxy multisignature secret key generation). They then computes the proxy multisignature secret key as follows:
(13)
d
=
d
p
+
∑
i
=
1
n
s
i
(
mod
⁡
t
)
.Phase 3. Proxy multisignature generation phase: the proxy multisignature affixed to the m is in the form of (
m
,
m
w
,
R
,
Sig
d
(
m
)
), where Sig
d
(
m
) is the signature generated by a designated signature scheme (EC-Schnorr signature scheme) using the proxy signing key d and m is message.Step  1. Proxy signer P chooses random number j where 1
≤
j
≤
t
-
1 and calculates J
=
j
×
B
=
(
J
x
,
J
y
).Step  2. Compute e
=
h
(
m
,
J
x
) where h
(
J
x
,
m
) is hash function. If e
=
0, then go to step 1.Step  3. Compute
(14)
y
=
j
-
d
×
e
(
mod
⁡
t
)
,
and the output sign
⁡
d
(
m
)
=
(
e
,
y
).Phase 4. Proxy multisignature verification phase. When the verifier verifies the signature, he or she calculates the proxy public value Q corresponding to the proxy signature key d as
(15)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 3.1. Implementation of Improved CCH1 Proxy Multisignature Scheme

There are four phases—the system initialization phase, the key generation phase, the proxy multisignature generation phase, and the proxy multisignature verification phase [19].Phase 1. System initialization phase: before the whole scheme can be initialized, the following parameters over the elliptic curve domain must be known:(i)
a field sizep, which is odd prime;
(ii)
two parametersa, b
∈
F
p to define the equation of elliptic curve E over F
p (i.e., y
2
=
x
3
+
a
x
+
b (mod
⁡
p)), where 4
a
3
+
27
b
2
≠
0 (mod
⁡
p);
(iii)
a finite pointB
=
(
x
B
,
y
B
) whose order is a large prime number in E
(
F
p
), where B is a point in E
(
F
p
), where B
≠
O, because O denotes an infinity point;
(iv)
the order ofB
=
t.Phase 2. Key generation phase: this phase can be further divided into two parts.Part 1. Personal public key generation phase: all original signers and the designated proxy signer are authorized to select their own individual secret keys.(i)
For each1
≤
i
≤
n, the original signer A
i secretly selects a random number 1
≤
d
i
≤
t
-
1 as his private key and computes the corresponding public key Q
i
=
d
i
×
B
=
(
x
Q
i
,
y
Q
i
), where “×” indicates the multiplication of a number by an elliptic curve point.
(ii)
The proxy signer is provided with a private key1
≤
d
p
≤
t
-
1 and a corresponding public key Q
p
=
d
p
×
B
=
(
x
Q
p
,
y
Q
p
). All public keys Q
i and Q
p must be certified by the CA.Part 2. Proxy-signature secret key generation phase.Step  1 (secret key generation). For each 1
≤
i
≤
n, the original signer A
i selects a random number k
i
∈
{
1
,
2
⋯
t
-
1
}
/
d
i as secret key.Step  2 (group commitment value generation). They then computes
(4)
R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
)
.
If x
R
i
=
0, then return to step 1; otherwise A
i broadcasts R
i to other original signers.Step  3 (subdelegation parameter generation). For each 1
≤
i
≤
n, the original signer A
i uses his own secret keys d
i, k
i and the group commitment value x
R to compute the following:
(5)
s
i
=
d
i
*
x
Q
i
*
h
(
M
w
,
R
i
)
-
k
i
*
x
R
i
(
mod
⁡
t
)
,
where h
(
) is a hash function and the warrant M
w contains information such as the IDs of all original signers and proxy signer. Then, the subdelegation parameter for A
i is (
M
w
,
R
i
,
s
i
).Step  4 (subdelegation parameter verification). After the proxy signer has received the subdelegation parameters, then the proxy signer P computes
(6)
S
i
×
B
=
(
x
Q
i
*
h
(
M
w
,
R
i
)
)
*
Q
i
-
x
R
i
R
i
and checks whether it holds. If it holds then the proxy signer accepts (
M
w
,
R
i
,
s
i
) as a valid subdelegation parameter; otherwise, he can reject it and requests a valid one A
i or terminate this protocol.Step  5 (proxy multisignature secret key generation). He then computes the proxy multisignature secret key as follows:
(7)
d
=
d
p
*
x
Q
P
+
∑
i
=
1
n
s
i

(
mod
⁡
t
)
.
Phase 3. Proxy multisignature generation phase: the proxy multisignature affixed to the m is in the form of (
m
,
m
w
,
R
,
Sig
d
(
m
)
), where Sig
d
(
m
) is the signature generated by a designated signature scheme (EC-Schnorr signature scheme) using the proxy signing key d and m is message.Step  1. Proxy signer P chooses random number j where 1
≤
j
≤
t
-
1 and calculates J
=
j
×
B
=
(
J
x
,
J
y
).Step  2. Compute e
=
h
(
m
,
J
x
) where h
(
J
x
,
m
) is hash function. If e
=
0, then go to step 1.Step  3. Compute
(8)
y
=
j
-
d
*
e
(
mod
⁡
t
)
,
and the output sign
⁡
d
(
m
)
=
(
e
,
y
).Phase 4. Proxy multisignature verification phase: when the verifier verifies the signature, he or she calculates the proxy public value Q corresponding to the proxy signature key d as
(9)
Q
=
Q
P
*
x
Q
p
+
∑
i
=
1
n
(
h
(
M
w
,
R
i
)
*
Q
i
-
x
R
i
×
R
i
)
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 3.2. Implementation of Improved CCH2 Proxy Multisignature Scheme

There are four phases—the system initialization phase, the key generation phase, the proxy multisignature generation phase, and the proxy multisignature verification phase [19].Phase 1. System initialization phase: before the whole scheme can be initialized, the following parameters over the elliptic curve domain must be known:(i)
a field sizep, which is an odd prime;
(ii)
two parametersa, b
∈
F
p to define the equation of elliptic curve E over F
p (i.e., y
2
=
x
3
+
a
x
+
b
(
mod
⁡
p
)
), where 4
a
3
+
27
b
2
≠
0
(
mod
⁡
p
);
(iii)
a finite pointB
=
(
x
B
,
y
B
) whose order is a large prime number in (
F
p
), where B is a point in E
(
F
p
), where B
≠
O, because O denotes an infinity point;
(iv)
the order ofB
=
t.Phase 2. Key generation phase: this phase can be further divided into two parts.Part 1. Personal public key generation phase: all original signers and the designated proxy signer are authorized to select their own individual secret keys.(i)
For each1
≤
i
≤
n, the original signer A
i secretly selects a random number 1
≤
d
i
≤
t
-
1 as his private key and computes the corresponding public key Q
i
=
d
i
×
B
=
(
x
Q
i
,
y
Q
i
), where “×” indicates the multiplication of a number by an elliptic curve point.
(ii)
The proxy signer is provided with a private key1
≤
d
p
≤
t
-
1 and a corresponding public key Q
p
=
d
p
×
B
=
(
x
Q
p
,
y
Q
p
). All public keys Q
i and Q
p must be certified by the CA.Part 2. Proxy-signature secret key generation phase.Step  1 (secret key generation). For each 1
≤
i
≤
n, the original signer A
i selects a random number k
i
∈
{
1
,
2
,
…
,
t
-
1
}
/
d
i as secret key.Step  2 (group commitment value generation). Then computes R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
). If x
R
i
=
0, then return to step 1; otherwise A
i broadcasts R
i to other original signers. On receiving R
j
(
1
≤
j
≤
n,  j
≠
i
), A
i calculates
(10)
i
=
(
x
R
,
y
R
)
.Step  3 (subdelegation parameter generation). For each 1
≤
i
≤
n, the original signer A
i uses his own secret keys d
i, k
i and the group commitment value x
R to compute the following:
(11)
s
i
=
d
i
*
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
-
k
i
*
x
R
(
mod
⁡
t
)
,
where h
(
) is a hash function and the warrant M
w contains information such as the IDs of all original signers and proxy signer. Then, the subdelegation parameter for A
i is (
M
w
,
s
i
).Step  4 (subdelegation parameter verification). After the proxy signer has received the subdelegation parameters then the proxy signer P computes
(12)
s
i
*
B
=
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
*
Q
i
-
x
R
×
R
i
and checks whether it holds. If it holds then the proxy signer accepts (
M
w
,
s
i
) as a valid subdelegation parameter; otherwise, he can reject it and requests a valid one A
i or terminate this protocol.Step  5 (proxy multisignature secret key generation). They then computes the proxy multisignature secret key as follows:
(13)
d
=
d
p
+
∑
i
=
1
n
s
i
(
mod
⁡
t
)
.Phase 3. Proxy multisignature generation phase: the proxy multisignature affixed to the m is in the form of (
m
,
m
w
,
R
,
Sig
d
(
m
)
), where Sig
d
(
m
) is the signature generated by a designated signature scheme (EC-Schnorr signature scheme) using the proxy signing key d and m is message.Step  1. Proxy signer P chooses random number j where 1
≤
j
≤
t
-
1 and calculates J
=
j
×
B
=
(
J
x
,
J
y
).Step  2. Compute e
=
h
(
m
,
J
x
) where h
(
J
x
,
m
) is hash function. If e
=
0, then go to step 1.Step  3. Compute
(14)
y
=
j
-
d
×
e
(
mod
⁡
t
)
,
and the output sign
⁡
d
(
m
)
=
(
e
,
y
).Phase 4. Proxy multisignature verification phase. When the verifier verifies the signature, he or she calculates the proxy public value Q corresponding to the proxy signature key d as
(15)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 4. Performance Analysis of the Proposed Scheme

The analysis reports of the proposed scheme are given below.


### 4.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 [24].Figure3 shows the entropy for the proposed scheme. The Figure 4 shows that compression ratio required in each scheme. Table 1 lists the name and compression ratio required in each scheme.Table 1
Compression ratio (in %) in each scheme.
Schemes
Compression ratio (in %)
CCH1
75
CCH2
89
The proposed scheme
75Figure 3
Entropy for the proposed scheme.Figure 4
Radar chart showing compression ratio required in each scheme.


### 4.2. Floating Frequencies/Intuitive Synthesis

Floating frequencies/intuitive synthesis in its completed three part entirety which takes full advantage of the time complexity, space complexity, and communication overhead provided by the digital medium. We have calculated floating frequency of threshold proxy signature scheme [24]. Figure 5 shows floating frequencies/intuitive synthesis for the proposed scheme.Figure 5
Floating frequencies/intuitive synthesis for the proposed scheme.


### 4.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, you tell if your calculations are going in the right direction. In this context, we have calculated ASCII histogram for our threshold proxy signature scheme [24]. Figure 6 shows ASCII histogram for the proposed scheme.Figure 6
ASCII histogram for the proposed scheme.


### 4.4. Autocorrelation

A 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 as 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 [24]. Figure 7 shows autocorrelation for the proposed scheme.Figure 7
Autocorrelation for the proposed scheme.


### 4.5. Histogram Analysis

A histogram is a graphical representation showing a visual impression of the distribution of data. We have analyzed histogram for all schemes. Table2 lists the histogram analysis for overall threshold proxy signature schemes [24]. Figure 8 shows radar chart showing overall analysis for all schemes.Table 2
Number
Substring
CCH1
Frequency1
CCH2
Frequency2
Proposed technology
Frequency3
Frequency (in %)
Frequency
Frequency (in %)
Frequency
Frequency (in %)
Frequency
1
N
10.9477
201
10.9477
201
10.9477
201
2
I
10.512
193
10.512
193
10.512
193
3
T
9.3137
171
9.3137
171
9.3137
171
4
E
8.5512
157
8.5512
157
8.5512
157
5
S
6.9172
127
6.9172
127
6.9172
127
6
R
5.3377
98
5.3377
98
5.3377
98
7
A
4.3028
79
4.3028
79
4.3028
79
8
O
4.085
75
4.085
75
4.085
75
9
C
3.8126
70
3.8126
70
3.8126
70
10
D
3.8126
70
3.8126
70
3.8126
70
11
U
3.5403
65
3.5403
65
3.5403
65
12
F
3.268
60
3.268
60
3.268
60
13
P
3.268
60
3.268
60
3.268
60
14
G
3.2135
59
3.2135
59
3.2135
59
15
L
3.2135
59
3.2135
59
3.2135
59
16
H
3.159
58
3.159
58
3.159
58
17
Y
2.9412
54
2.9412
54
2.9412
54
18
M
2.0697
38
2.0697
38
2.0697
38
19
X
1.9063
35
1.9063
35
1.9063
35
20
V
1.6885
31
1.6885
31
1.6885
31
21
W
1.3617
25
1.3617
25
1.3617
25
22
J
0.817
15
0.817
15
0.817
15
23
B
0.817
15
0.817
15
0.817
15
24
K
0.5447
10
0.5447
10
0.5447
10
25
Q
0.4902
9
0.4902
9
0.4902
9
26
Z
0.1089
2
0.1089
2
0.1089
2Figure 8
Radar chart showing overall analysis for all schemes.


## 4.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 [24].Figure3 shows the entropy for the proposed scheme. The Figure 4 shows that compression ratio required in each scheme. Table 1 lists the name and compression ratio required in each scheme.Table 1
Compression ratio (in %) in each scheme.
Schemes
Compression ratio (in %)
CCH1
75
CCH2
89
The proposed scheme
75Figure 3
Entropy for the proposed scheme.Figure 4
Radar chart showing compression ratio required in each scheme.


## 4.2. Floating Frequencies/Intuitive Synthesis

Floating frequencies/intuitive synthesis in its completed three part entirety which takes full advantage of the time complexity, space complexity, and communication overhead provided by the digital medium. We have calculated floating frequency of threshold proxy signature scheme [24]. Figure 5 shows floating frequencies/intuitive synthesis for the proposed scheme.Figure 5
Floating frequencies/intuitive synthesis for the proposed scheme.


## 4.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, you tell if your calculations are going in the right direction. In this context, we have calculated ASCII histogram for our threshold proxy signature scheme [24]. Figure 6 shows ASCII histogram for the proposed scheme.Figure 6
ASCII histogram for the proposed scheme.


## 4.4. Autocorrelation

A 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 as 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 [24]. Figure 7 shows autocorrelation for the proposed scheme.Figure 7
Autocorrelation for the proposed scheme.


## 4.5. Histogram Analysis

A histogram is a graphical representation showing a visual impression of the distribution of data. We have analyzed histogram for all schemes. Table2 lists the histogram analysis for overall threshold proxy signature schemes [24]. Figure 8 shows radar chart showing overall analysis for all schemes.Table 2
Number
Substring
CCH1
Frequency1
CCH2
Frequency2
Proposed technology
Frequency3
Frequency (in %)
Frequency
Frequency (in %)
Frequency
Frequency (in %)
Frequency
1
N
10.9477
201
10.9477
201
10.9477
201
2
I
10.512
193
10.512
193
10.512
193
3
T
9.3137
171
9.3137
171
9.3137
171
4
E
8.5512
157
8.5512
157
8.5512
157
5
S
6.9172
127
6.9172
127
6.9172
127
6
R
5.3377
98
5.3377
98
5.3377
98
7
A
4.3028
79
4.3028
79
4.3028
79
8
O
4.085
75
4.085
75
4.085
75
9
C
3.8126
70
3.8126
70
3.8126
70
10
D
3.8126
70
3.8126
70
3.8126
70
11
U
3.5403
65
3.5403
65
3.5403
65
12
F
3.268
60
3.268
60
3.268
60
13
P
3.268
60
3.268
60
3.268
60
14
G
3.2135
59
3.2135
59
3.2135
59
15
L
3.2135
59
3.2135
59
3.2135
59
16
H
3.159
58
3.159
58
3.159
58
17
Y
2.9412
54
2.9412
54
2.9412
54
18
M
2.0697
38
2.0697
38
2.0697
38
19
X
1.9063
35
1.9063
35
1.9063
35
20
V
1.6885
31
1.6885
31
1.6885
31
21
W
1.3617
25
1.3617
25
1.3617
25
22
J
0.817
15
0.817
15
0.817
15
23
B
0.817
15
0.817
15
0.817
15
24
K
0.5447
10
0.5447
10
0.5447
10
25
Q
0.4902
9
0.4902
9
0.4902
9
26
Z
0.1089
2
0.1089
2
0.1089
2Figure 8
Radar chart showing overall analysis for all schemes.


## 5. Graphical Representation of Time, Space, and Computational Overhead of Improved CCH1 Scheme

### 5.1. Time Complexity, Space Complexity, and Computational Overhead

When determining the time complexity of an algorithm, we measure how fast the computing requirements grow as the size of the input grows. We generate graphs to analyze the time complexity of the schemes. 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. The computational overhead includes two types of communication in the schemes: number of transmissions and number of broadcasts. We generate graphs to analyze the computational overhead of the schemes [24]. Figures 9, 10, 11, 12, 13, 14, 15 and 16 show time complexity, space complexity, and computational overhead for the CCH1 and CCH2 schemes.Figure 9
Time complexity of improved CCH1 scheme with varying value of field size (p).Figure 10
Time complexity of improved CCH2 scheme with varying value of field size (p).Figure 11
Space complexity of improved CCH1 scheme with varying value of field size (p).Figure 12
Space complexity of improved CCH2 scheme with varying value of field size (p).Figure 13
Computational overhead of improved CCH1 scheme with varying value of field size (p).Figure 14
Computational overhead of improved CCH2 scheme with varying value of field size (p).Figure 15
Time complexity of improved CCH1 scheme with varying value of field size (p).Figure 16
Time complexity of improved CCH2 scheme with varying value of field size (p).


## 5.1. Time Complexity, Space Complexity, and Computational Overhead

When determining the time complexity of an algorithm, we measure how fast the computing requirements grow as the size of the input grows. We generate graphs to analyze the time complexity of the schemes. 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. The computational overhead includes two types of communication in the schemes: number of transmissions and number of broadcasts. We generate graphs to analyze the computational overhead of the schemes [24]. Figures 9, 10, 11, 12, 13, 14, 15 and 16 show time complexity, space complexity, and computational overhead for the CCH1 and CCH2 schemes.Figure 9
Time complexity of improved CCH1 scheme with varying value of field size (p).Figure 10
Time complexity of improved CCH2 scheme with varying value of field size (p).Figure 11
Space complexity of improved CCH1 scheme with varying value of field size (p).Figure 12
Space complexity of improved CCH2 scheme with varying value of field size (p).Figure 13
Computational overhead of improved CCH1 scheme with varying value of field size (p).Figure 14
Computational overhead of improved CCH2 scheme with varying value of field size (p).Figure 15
Time complexity of improved CCH1 scheme with varying value of field size (p).Figure 16
Time complexity of improved CCH2 scheme with varying value of field size (p).


## 6. Cryptanalysis of Improved CCH2 Proxy Multisignature Scheme

See Figures15, 16, 17, 18, 19, 20, 21, 22, and 23.Figure 17
Time complexity of enhanced scheme with varying value of field size (p).Figure 18
Space complexity of improved CCH1 scheme with varying value of field size (p).Figure 19
Space complexity of improved CCH2 scheme with varying value of field size (p).Figure 20
Space complexity of enhanced scheme with varying value of field size (p).Figure 21
Computational overhead of improved CCH1 scheme with varying value of field size (p).Figure 22
Computational overhead of improved CCH2 scheme with varying value of field size (p).Figure 23
Computational overhead of enhanced scheme with varying value of field size (p).In improved CCH2 proxy multisignature scheme, elliptic curve based Schnorr signature scheme is used to generate and verify the signature.


### 6.1. Forge a Proxy Multisignature

Suppose proxy signerP signed a message with his private key d
p; the signature is (
m
,
m
w
,
R
,
e
,
y
′
′
) where e
=
h
(
m
,
j
x
) and y
′
′
=
j
-
d
p
*
e
(
mod
⁡
t
). Upon receiving the signature (
m
,
m
w
,
R
,
e
,
y
′
′
) the malicious original signers A
1
,
…
,
A
n can forge a valid proxy signature as follows.(i)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
).
(ii)
Computey
=
y
′′
-
y
′.Finally, the malicious original signersA
1
,
…
,
A
n can forge a valid proxy signature (
m
,
m
w
,
R
,
e
,
y
). The following shows why the proxy signature (
m
,
m
w
,
R
,
e
,
y
) is valid.Proof.
Consider the following:(16)
y
=
y
′′
-
y
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
-
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
(
mod
⁡
t
)
,
y
=
j
-
d
*
e
(
mod
⁡
t
)
.
Proxy multisignature verification: when the verifier verifies the signature, he or she calculates the proxy public valueQ corresponding to the proxy signature key d as
(17)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


### 6.2. Forge the Proxy Signer’s Signature

After getting signature(
m
,
m
w
,
R
,
e
,
y
) where e
=
h
(
m
,
j
x
) and y
=
j
-
d
*
e (mod
⁡
t), the original signer A
1
,
…
,
A
n can forge proxy signer P’s signature on message m as follows.(i)
EachA
i computes s
i
*
e where i
=
1,2
,
…
n.
(ii)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
).
(iii)
Computey
′
′
=
y
+
y
′.
(iv)
(
m
,
m
w
,
R
,
e
,
y
′
′
) is valid signature on message m.The malicious original signers can forge a valid signature(
m
,
m
w
,
R
,
e
,
y
′
′
) on message m with respect to proxy signer P’s private key d
p.The following shows why the signature(
m
,
m
w
,
R
,
e
,
y
′
′
) is valid.Proof.
Consider the following:(18)
y
′
′
=
y
+
y
′
=
j
-
d
*
e
+
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
+
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
,
y
′
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
.
Proxy multisignature verification: when the verifier verifies the signature, he or she uses proxy public valueQ
p corresponding to the proxy signature key d
p. With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
P
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


### 6.3. Framing Attack

In this attack, malicious usersA
1
,
A
2
,
…
,
A
n also can forge a proxy multisignature for message m by some user P on behalf of users A
1
,
A
2
,
…
,
A
n, such that user P was never designated by users A
1
,
A
2
,
…
,
A
n. Suppose proxy signer P signed a message with his private key d
p; the signature is (
m
,
m
w
,
R
,
e
,
y
′
′
) where e
=
h
(
m
,
j
x
) and y
′
′
=
j
-
d
p
*
e (mod
⁡
t).Upon receiving the signature(
m
,
m
w
,
R
,
e
,
y
′
′
), then the malicious original signers A
1
,
…
,
A
n can forge a valid proxy signature as follows.(i)
The malicious usersA
1
,
A
2
,
…
,
A
n pretend to produce a forged warrant m
w, which records the delegation information such as identities of the malicious users A
1
,
A
2
,
…
,
A
n and user P.
(ii)
For each1
≤
i
≤
n, the malicious user A
i selects a random number 1
≤
k
i
≤
t
-
1 and then computes R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
) and broadcasts R
i to other users.
(iii)
On receivingR
j
(
1
≤
j
≤
n
,
j
≠
i
), A
i calculates
(19)
R
=
∑
i
=
1
n
R
i
=
(
x
R
,
y
R
)
,
s
i
=
d
i
*
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
-
k
i
*
x
R
-
(
mod
⁡
t
)
.Note that userP does not receive any information from the malicious users A
1
,
A
2
,
…
,
A
n.(i)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
);
(ii)
Computey
=
y
′′
-
y
′.Finally the malicious users can forge a valid signature(
m
,
m
w
,
R
,
e
,
y
) on message m by some user P on behalf of users A
1
,
…
,
A
n, such that user P was never designated by users A
1
,
…
,
A
n. The following shows why the signature (
m
,
m
w
,
R
,
e
,
y
) is valid.Proof.
Consider the following:(20)
y
=
y
′
′
-
y
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
-
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
(
mod
⁡
t
)
,
y
=
j
-
d
*
e
(
mod
⁡
t
)
.
From above we can see that an innocent userP is framed by the malicious users A
1
,
…
,
A
n.
Proxy multisignature verification phase: when the verifier verifies the signature, he or she calculates the proxy public valueQ corresponding to the proxy signature key d as
(21)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of  Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 6.1. Forge a Proxy Multisignature

Suppose proxy signerP signed a message with his private key d
p; the signature is (
m
,
m
w
,
R
,
e
,
y
′
′
) where e
=
h
(
m
,
j
x
) and y
′
′
=
j
-
d
p
*
e
(
mod
⁡
t
). Upon receiving the signature (
m
,
m
w
,
R
,
e
,
y
′
′
) the malicious original signers A
1
,
…
,
A
n can forge a valid proxy signature as follows.(i)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
).
(ii)
Computey
=
y
′′
-
y
′.Finally, the malicious original signersA
1
,
…
,
A
n can forge a valid proxy signature (
m
,
m
w
,
R
,
e
,
y
). The following shows why the proxy signature (
m
,
m
w
,
R
,
e
,
y
) is valid.Proof.
Consider the following:(16)
y
=
y
′′
-
y
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
-
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
(
mod
⁡
t
)
,
y
=
j
-
d
*
e
(
mod
⁡
t
)
.
Proxy multisignature verification: when the verifier verifies the signature, he or she calculates the proxy public valueQ corresponding to the proxy signature key d as
(17)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 6.2. Forge the Proxy Signer’s Signature

After getting signature(
m
,
m
w
,
R
,
e
,
y
) where e
=
h
(
m
,
j
x
) and y
=
j
-
d
*
e (mod
⁡
t), the original signer A
1
,
…
,
A
n can forge proxy signer P’s signature on message m as follows.(i)
EachA
i computes s
i
*
e where i
=
1,2
,
…
n.
(ii)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
).
(iii)
Computey
′
′
=
y
+
y
′.
(iv)
(
m
,
m
w
,
R
,
e
,
y
′
′
) is valid signature on message m.The malicious original signers can forge a valid signature(
m
,
m
w
,
R
,
e
,
y
′
′
) on message m with respect to proxy signer P’s private key d
p.The following shows why the signature(
m
,
m
w
,
R
,
e
,
y
′
′
) is valid.Proof.
Consider the following:(18)
y
′
′
=
y
+
y
′
=
j
-
d
*
e
+
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
+
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
,
y
′
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
.
Proxy multisignature verification: when the verifier verifies the signature, he or she uses proxy public valueQ
p corresponding to the proxy signature key d
p. With the value, the verifier can confirm the validity of Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
P
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 6.3. Framing Attack

In this attack, malicious usersA
1
,
A
2
,
…
,
A
n also can forge a proxy multisignature for message m by some user P on behalf of users A
1
,
A
2
,
…
,
A
n, such that user P was never designated by users A
1
,
A
2
,
…
,
A
n. Suppose proxy signer P signed a message with his private key d
p; the signature is (
m
,
m
w
,
R
,
e
,
y
′
′
) where e
=
h
(
m
,
j
x
) and y
′
′
=
j
-
d
p
*
e (mod
⁡
t).Upon receiving the signature(
m
,
m
w
,
R
,
e
,
y
′
′
), then the malicious original signers A
1
,
…
,
A
n can forge a valid proxy signature as follows.(i)
The malicious usersA
1
,
A
2
,
…
,
A
n pretend to produce a forged warrant m
w, which records the delegation information such as identities of the malicious users A
1
,
A
2
,
…
,
A
n and user P.
(ii)
For each1
≤
i
≤
n, the malicious user A
i selects a random number 1
≤
k
i
≤
t
-
1 and then computes R
i
=
k
i
×
B
=
(
x
R
i
,
y
R
i
) and broadcasts R
i to other users.
(iii)
On receivingR
j
(
1
≤
j
≤
n
,
j
≠
i
), A
i calculates
(19)
R
=
∑
i
=
1
n
R
i
=
(
x
R
,
y
R
)
,
s
i
=
d
i
*
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
-
k
i
*
x
R
-
(
mod
⁡
t
)
.Note that userP does not receive any information from the malicious users A
1
,
A
2
,
…
,
A
n.(i)
Computey
′
=
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
);
(ii)
Computey
=
y
′′
-
y
′.Finally the malicious users can forge a valid signature(
m
,
m
w
,
R
,
e
,
y
) on message m by some user P on behalf of users A
1
,
…
,
A
n, such that user P was never designated by users A
1
,
…
,
A
n. The following shows why the signature (
m
,
m
w
,
R
,
e
,
y
) is valid.Proof.
Consider the following:(20)
y
=
y
′
′
-
y
′
=
j
-
d
p
*
e
(
mod
⁡
t
)
-
∑
i
=
1
n
s
i
*
e
(
mod
⁡
t
)
=
j
-
(
d
p
+
∑
i
=
1
n
s
i
)
e
(
mod
⁡
t
)
,
y
=
j
-
d
*
e
(
mod
⁡
t
)
.
From above we can see that an innocent userP is framed by the malicious users A
1
,
…
,
A
n.
Proxy multisignature verification phase: when the verifier verifies the signature, he or she calculates the proxy public valueQ corresponding to the proxy signature key d as
(21)
Q
=
Q
P
+
∑
i
=
1
n
h
(
M
w
,
x
Q
p
,
x
Q
i
,
x
R
)
×
Q
i
-
R
×
x
R
.
With the value, the verifier can confirm the validity of  Sig
d
(
m
) by validating the verification equality of the designated signature scheme.
Step  1. Compute J
-
=
y
×
B
+
e
×
Q
=
(
J
-
x
,
J
-
y
).
Step  2. And compute e
′
=
h
(
J
-
x
,
m
). Then check that e
′
=
e and if this equation satisfies then valid signature generated otherwise not.


## 7. Conclusion

In this paper, we have discussed implementation of improved CCH1 and improved CCH2 proxy multisignature scheme based on elliptic curve cryptosystem. We have represented time complexity, space complexity, and computational overhead of improved CCH1 and CCH2 proxy multisignature schemes. We have presented cryptanalysis of improved CCH2 proxy multisignature scheme and showed that improved CCH2 scheme suffers from various attacks, that is, forgery attack and framing attack.



---

*Source: 429271-2014-04-27.xml*