A novel multisignature scheme based on chaotic maps

Abstract

In this paper, a novel multisignature scheme based on chaotic maps is proposed. The purpose of multisignatures is to manage the complexities of a document signed by numerous signatories. The chaotic system is an encryption method proposed in recent years that has received widespread attention in the field of cryptography. This paper first examines the methods of multisignatures and chaotic maps, and then proposes a multisignature scheme that was designed using chaotic maps. During the processing of a multisignature scheme, to authenticate the precision of the received document, the signatory must first obtain the signed document, and then utilize the characteristics of chaotic maps to recover the original document. If the recovered document is meaningful, this indicates that no errors exist in the signature, thus the signatures are valid and the document can be signed. If the recovered document is not sufficiently clear, signing is denied. At present, because no relevant literature exists that has proposed utilizing chaotic maps to establish a multisignature system; this paper aims to develop a novel research method.

Keywords

Cryptography multisignature digital signature chaotic maps

1 Introduction

Digital signatures were first proposed by Diffie-Hellman [39] in 1976, and the procedure can be explained as follows:

Signatory A uses a secret key to sign document M (i.e. plaintext), producing the signature S.

Signatory A uses the Internet to publicly transfer the document and signature (M, S) to receiver B.

Next, receiver B uses a public key to restore the received signature S to document M. If the public key verifies the signature, the signature is effective; otherwise, it is regarded as an ineffective signature.

After 1978, several schemes on the technology of digital signatures were proposed in succession; most schemes were based on the RSA or ElGamal algorithms [1 , 35]. By 1993, David [15] conducted a comprehensive review of the state of the art of digital signatures, and recommended that research efforts in digital signatures should be directed toward smart card applications. Digital signatures have been able to replace traditional signatures precisely because they possess two primary functions:

Validation and integrity: a valid signature ensures that the message content has not been tampered with.

Authenticity: similar to traditional handwritten signatures, a digital signature confirms the identity of the originator of the digital document.

Thus, digital signatures are equivalent to handwritten “signatures” in everyday life; when documents with official effect are digitally signed, the signer need not fear forgery or document tampering. In reality, a digital signature is a text string composed of a combination of 0 and 1 character. Digital signatures are currently used in areas such as e-mail, office automation (OA), electronic data interchange (EDI), and electronic fund transfers [12 , 43].

The definition of multisignature [9] is: “Many signatories (signers) sign a document together.” Just as a single digital signature can be used for the processing and presenting for review of general official documents, a multisignature extends digital signature technology for the implementation of official electronic documents. Conventional multisignature methods are mostly based on the ElGamal or RSA methods. The concept of a multisignature method was first proposed jointly by Itakura and Nakamura [18] in 1983; its purpose was to develop OA. The practice was to establish the hierarchical relationship between users in advance and to build on the extended RSA method. The disadvantage was that the signing order was fixed according to the hierarchical relationship; during the signing process, this resulted in message expansion. Subsequently, in 1988, Okamoto [37] incorporated one-way functions and overcame some of the weaknesses of the Itakura-Nakamura scheme to propose a multisignature. However, the signature and verification processes of Okamoto’s scheme were overly complex, and the scheme was thus impractical. Therefore, in 1989 Harn and Kiesler [21] proposed a multisignature scheme based on the RSA system. Their procedures during the signature and authentication phases were simpler and more practical, and were an improvement on Okamoto’s scheme; they considered the obstacle of message expansion and solved the weaknesses of the Itakura-Nakamura scheme. The Harn-Kiesler digital multisignature scheme employed the RSA cryptosystem because RSA is a widely known, one-to-one bijective public key cryptosystem. Thus, it was a “good candidate” well suited for the development of digital signatures, and was able to circumvent the obstacles that had hampered past methods; notably, it allowed numerous signatories to sign without causing message expansion. Harn continued to successively develop other multisignature frameworks [22, 23]. The digital multisignature scheme proposed by Ohta and Okamoto [19] in 1991 required two phases of loops and possessed the complication that signatories could not confirm whether those who should have signed before had already signed. Subsequently, in 2000, Mitomi and Miyaji proposed two schemes based on the discrete logarithm problem and integer factorization, respectively [33]. In 2010, Harn also proposed an identity-based RSA digital multisignature scheme [24]. Because multisignatures are better suited for modern electronic operations than conventional signature schemes, several different multisignature schemes have been proposed [14 , 40].

Since the 1990 s, chaotic systems [7 , 25] have been used in secure communication protocol designs. In recent years, chaotic-map-based cryptosystems have been proven to be superior to conventional cryptosystems that utilize the point multiplication computations of modular exponentiation and elliptic curves. These cryptosystems also possess several similar mathematical characteristics, such as semi group and commutative properties. Chaotic maps employ the designs of symmetric encryption protocol [8 , 42] and hash functions [5, 30]. Recently, chaotic systems have also been used for digital signatures [16] and key management [17, 44].

From the perspective of the current processing of official documents, this paper assumes the signing process of a request for approval to be: “those in lower positions sign first and those in higher positions sign later.” The assumption of signing according to a fixed sequence, level by level, is in line with the process of handling official documents. Therefore, in the proposed multisignature scheme, this paper combines the advantages of several multisignature schemes for the signature processing of official electronic documents.

This scheme utilizes the characteristics of multisignatures and chaotic maps. Therefore, some relevant characteristics of multisignatures and chaotic maps are introduced in Section 2. In Section 3, the proposed multisignature scheme is described. The security of this scheme is analyzed in Section 4, and comparisons are made with other schemes in Section 5. The final section presents the conclusion.

2 Preliminaries

In this section, the fundamental concept of multisignatures and a few characteristics of chaotic maps are briefly introduced.

2.1 ElGamal multisignature scheme

Notations

First, we list some notations in Table 1.

Table 1
Notations description

Notations Descriptions

n Assume a set of n signatories exists.

p A large prime number.

e Primitive element (mod p).

x _i A secret key.

y _i A public key.

M The same document.

Notations	Descriptions
n	Assume a set of n signatories exists.
p	A large prime number.
e	Primitive element (mod p).
x _i	A secret key.
y _i	A public key.
M	The same document.

Parameter settings

In a network system, assume a set of n signatories exists, {U_i, 1 ≤ i ≤ n}.

Let p be a large prime number and let e be a primitive element (mod p).

Each signatory U_i selects a secret key x_i, and a public key y_i. By using x_i and e, the value of y_i can be obtained. The formula for deriving y_i is y_i = e^{x
_i}p

The system publishes the values of (p, e, y_i), but retains all x_i as secret keys that are not to be published.

Secondly, assume each user in a set of t users {U_i1, U_i2, …, U_it} must sign the same document M (0≤M≤p–1). This scheme requires an issuer to be responsible for document preparation and to determine the signing order of each signatory.

Signature phase

Firstly, the issuer uses a public key encryption procedure to encrypt document M as a ciphertext pair $[C_{1}^{(i_{1})}, C_{2}^{(i_{2})}]$ . The procedure is as follows:

Randomly select a number g, with g satisfying 0 ≤ g ≤ p - 1. Let $k = y_{(i_{1})}^{g} mod p$ , such that gcd (k, p - 1) =1.

Find ciphertext pair $[C_{1}^{(i_{1})}, C_{2}^{(i_{2})}]$ ; the calculation formulas for $C_{1}^{(i_{1})}$ and $C_{1}^{(i_{2})}$ are respectively:

Ciphertext C_{1}^{(i_{1})} = (e)^{g} mod p

(1)

Ciphertext C_{1}^{(i_{2})} = (M)^{k} mod p

(2)

After the ciphertext pair $[C_{1}^{(i_{1})}, C_{2}^{(i_{2})}]$ is obtained, the issuer selects a random number r such that 0 < r < p - 1 and gcd (r, p - 1) =1. Next, (e, r) and other known parameter values are used to find value V. The solution formula for value V is: $V = (e)^{r} mod p$ (3)

Subsequently, the issuer combines the signing order list, ciphertext, and the random numbers ${(U_{i 1}, U_{i 2}, \dots, U_{it}), [C_{1}^{(i_{1})}, C_{2}^{(i_{2})}], (r, v)}$ and sends them to signatory U_i1. To prevent a replay attack in which multiple instances of the same r value are used for signing a single document, time stamp technology is used for document M.

The first signatory U_i1 receives the information sent by the issuer, immediately decrypts the ciphertext pair $[C_{1}^{(i_{1})}, C_{2}^{(i_{2})}]$ , and restores it to the original meaningful document M. This signing protocol is: if the signatory agrees to sign the document, a valid signature is produced according to the signing order list. Otherwise, the delivery is terminated.

Signing order list (taking the jth signatory as an example):

$Step 1 : Calculate S_{i_{j}} = M^{(x_{i_{j}})} mod p$ (4)

$Step 2 : Find q_{i_{j}} = e^{(x_{i_{j}})} mod p$ (5)

Step 3: Using equation $x_{i_{j}} + q_{i_{j}} = (S_{i_{j}} \times v) + (r \times w_{i_{j}}) mod (p - 1)$ (6)

Derive w_{i
_j}.

$Step 4 : Using Q_{1} = \sum_{k = 1}^{j} q_{i_{k}} mod (p - 1)$ (7)

$Q_{2} = \sum_{k = 1}^{j} q_{i_{k}} mod p$ (8) $W = \sum_{k = 1}^{j} w_{i_{k}} mod (p - 1)$ (9)

From the aforementioned three formulas, find the value of (Q₁, Q₂, W).

Similarly, the jth signatory U_{i
_j} encrypts document M into the ciphertext pair $[C_{1}^{(i_{j + 1})}, C_{2}^{(i_{j + 1})}]$ ; the signatory U_{i
_j} combines and sends the signing order list, ciphertext pair, and a partial multisignature: ${((U_{i_{1}}, U_{i_{2}}, \dots, U_{i_{t}}), [C_{1}^{(i_{j + 1})}, C_{2}^{(i_{j + 1})}], [(Q_{1}, Q_{2}, W),$ (r, v)])} to the j + 1th signatory U_{i
_(j+1)}, 1 ≤ j ≤ t - 2. When the j + 1th signatory receives the message, the signatory decrypts the ciphertext pair $[C_{1}^{(i_{j + 1})}, C_{2}^{(i_{j + 1})}]$ and derives the original document M.

Authentication phase

After the j + 1th signatory receives the message of the jth signatory, the signatory authenticates the partial multisignature [(Q₁, Q₂, W) , (r, v)] according to the authentication procedure.

Authentication procedure (with the jth signatory as an example):

Step 1. The public key Y of the signatory before calculation is: $Y = \prod_{k = 1}^{j} (y_{i_{k}}) mod p$ (10) $\begin{matrix} ∴ Y = (y_{i_{1}} \times y_{i_{2}} \times \dots \times y_{i_{j}}) mod p \\ = (e^{x_{i_{1}}} \times \dots \times e^{x_{i_{j}}}) mod p = [(e)^{\sum_{k = 1}^{j} x_{i_{k}}}] mod p \end{matrix}$

Step 2. Examine whether the left and right sides of the following discriminant are equal to authenticate the precision of the multisignature. The discriminant is: $Y \times (e)^{Q_{1}} \overset{?}{\equiv} \begin{matrix} \end{matrix} (Q_{2})^{v} \times (v)^{W} mod p$ (11)

If the aforementioned authentication is established and U_{i
_(j+1)} also agrees to sign this document, then he can generate the following in accordance with the signing order list: {(U_{i
₁}, U_{i
₂}, …, U_{i
_t}), [ $C_{1}^{(i_{j + 2})}, C_{2}^{(i_{j + 2})}$ ], and [(Q₁, Q₂, W), (r, v)]}. Otherwise, U_{i
_(j+1)} terminates the delivery and ends the signing operation. Therefore, the method to include t users who wish to sign a document M is:

Signatory U_{i
_t} sends the multisignature to receiver R.

Receiver R decrypts the ciphertext, and authenticates whether document M is precise and effective.

2.2 RSA-based multisignature scheme

To enable secure conversations between two different users, Professors Harn and Kiesler [21] of the University of Missouri proposed a multisignature scheme based on a modified RSA public key cryptosystem (i.e. an extended RSA scheme).

The Harn-Kiesler scheme is characterized by the use of the well-known RSA public key cryptosystem; in this highly efficient scheme, every user participating in the signing is provided with secure data and digital signatures. Any number of signatories is permitted to sign the same document, and the signature is secretly delivered to the receiver. Regardless of how large the number of signatories is, the length of the ciphertext generated by the signatories remains constant. However, the limiting condition of this scheme is that the signing order list must be predetermined by the issuer; this practice prevents the complication of message expansion.

From the perspective of the current processing of official documents, the signing process of a request for approval should be that those in lower positions sign first and those in higher positions sign later; this is in line with the process of handling official documents. Therefore, the assumption of presenting a document for signing in a certain fixed sequence, level by level, is in line with the process of handling official documents.

RSA is a widely known, one-to-one public key cryptosystem. Therefore, it is a good candidate for generating digital signatures, and has also solved the past deficiency of message expansion due to an increase in the number of signatories. This paper thus referenced the concept of Harn et al. [21 –24] in the generation of the signing procedure, and proposed a digital multisignature scheme suitable for the processing of official electronic documents according to this concept.

2.3 Characteristics of chaotic maps

In this section, the definition and relevant characteristics of chaotic maps are introduced.

Definition 1. The Chebyshev polynomial T_n (x) is a polynomial where the frequency of x is n. Assume that n is an integer and x is a variable value with an interval of [–1, 1]. The Chebyshev polynomial is given by the following relation: $T_{n} (x) = cos (n arcos (x)) (- 1 \leq x \leq 1)$ (12)

Following Definition 1, the relation of T_n (x) is defined as: $T_{n} (x) = 2 {xT}_{n - 1} (x) - T_{n - 2} (x) (n \geq 1)$ (13) where T₀(x)=1 and T₁(x)=x.

Here, the formula can be used to obtain the characteristic equation, as follows: $f (x) = t^{2} - 2 xt + 1$ (14)

Then, (14) can be used to obtain two different solvable equations: $α = \frac{x + \sqrt{x^{2} - 1}}{2} and β = \frac{x - \sqrt{x^{2} - 1}}{2} .$ (15)

Therefore, $T_{n} (x) = \frac{(x + \sqrt{x^{2} - 1})^{n} + (x - \sqrt{x^{2} - 1})^{n}}{2} mod p .$ (16)

The Chebyshev polynomial possesses the two following key properties:

The semigroup property:

\begin{matrix} T_{r} (T_{s} (x)) = cos (r {cos}^{- 1} (cos (s {cos}^{- 1} (x)))) \\ = cos (rs {cos}^{- 1} (x)) \\ = T_{sr} (x) \\ = T_{s} (T_{r} (x)) \end{matrix}

(17) where r and s are positive integers and x ∈ [-1, 1].

The chaotic property:

Where the frequency n > 1, the Chebyshev polynomial map is: T_n (x): [–1, 1] ⟶ [–1, 1]; the frequency n is a chaotic map’s constant density $f * (x) = \frac{1}{π \sqrt{1 - x^{2}}}$ from the Lyapunov exponent λ = ln n > 0.

To enhance the property, Zhang [13] proved that the semigroup property was preserved as the time interval defined by the Chebyshev polynomial (-∞ , + ∞), as follows: $T_{n} (x) \equiv (2 {xT}_{n - 1} (x) - T_{n - 2} (x)) mod P$ (18) where n ≥ 2, x ∈ (- ∞ , + ∞), and P is a large prime number. Evidently, $T_{rs} (x) \equiv T_{r} (T_{s} (x)) \equiv T_{s} (T_{r} (x)) mod P$ (19)

Definition 2. If given the two elements x and y, the task of the discrete logarithm problem is to find the integer s such that T_s (x) = y.

Definition 3. Given the three elements x, T_r (x), and T_s (x), the task of the Diffie–Hellman problem is to calculate T_rs (x).

3 The proposed multisignature scheme

This paper uses chaotic maps to design a novel digital multisignature scheme.

3.1 Notations

This multisignature method enables every signatory to review and sign a document, and further uses a ring network to deliver the document to the next signatory. Each signatory performs verification before performing the action of signing. The notation assumptions of this protocol are shown in Table 2.

Table 2
Notations description

Notations Descriptions

U _i Indicates the ith signatory.

p_i, q_i A large prime number, the secret key of a signatory, not public.

n _i n_i = p_i × q_i, a signatory can make n_i public, is a public key.

M Message, a document that requires the joint signatures of all signatories.

e _i Public key of a signatory.

d _i Decryption key of a signatory.

U _R The receiver of the entire multisignature document; this receiver can be determined according to the process flow.

Notations	Descriptions
U _i	Indicates the ith signatory.
p_i, q_i	A large prime number, the secret key of a signatory, not public.
n _i	n_i = p_i × q_i, a signatory can make n_i public, is a public key.
M	Message, a document that requires the joint signatures of all signatories.
e _i	Public key of a signatory.
d _i	Decryption key of a signatory.
U _R	The receiver of the entire multisignature document; this receiver can be determined according to the process flow.

All the cryptosystems whose security is based on factorization need strong primes. As defined by Gordon [11], Ogiwara [27] and Laih et al. [2], a prime p is called a strong prime if p satisfies the following conditions:

There exist two large primes p₁ and p₂ such that p₁ | p - 1 and p₂ | p + 1.

There exit two large primes r₁ and s₁ such that r₁ | p₁ - 1 and s₁ | p₁ + 1.

There exit two large primes r₂ and s₂ such that r₂ | p₂ - 1 and s₂ | p₂ + 1.

The prime that meets the above conditions is called a strong prime.

3.2 Multisignature scheme

The multisignature scheme proposed in this paper, based on chaotic maps, can be subdivided into the phase descriptions of the initialization phase and signature and authentication phase.

Initialization phase

Firstly, the system delivers the document intended for signature through the ring network to individuals who must sign the document, according to the position of each signatory in the signing order list. The first signatory is designated as the issuer of the document. The document is first signed by the issuer, and the multisignature is progressively performed according to the sequence of the network. Here, each signatory U_i is required to first complete the preprocessing of the signature. The performed steps can be summarized as follows:

Step 1. The system makes the p_i and q_i of every signatory U_i into n_i = p_i × q_i. According to the actual signing order list, the system requires the public key n_i of each signatory to satisfy the inequality n₁< n₂ < n₃ …; all public keys must be delivered to the ring network for implementation.

Step 2. For the document intended for signature M, the system will make M < n_i and gcd(M, n_i) =1.

Step 3. The system is used to calculate the discriminant D = M² - 4 and obtain the value of D. The following is found for each signatory: Lehmer totient function S (n_i): S (n_i) = lcm [p_i - (D/p_i) , q_i - (D/q_i)], where (D/p_i) and (D/q_i) are Legendre symbols, and (D/p_i) and (D/q_i) are defined as: $\begin{matrix} (D / p_{i}) = {(0, if p_{i} divides D); \\ (1, \exists X, \exists D = X^{2} mod p_{i}); (- 1, otherwise)}, \end{matrix}$ $\begin{matrix} (D / q_{i}) = {(0, if q_{i} divides D); (1, \exists X, \exists D = X^{2} \\ mod q_{I}); (- 1, otherwise)} . \end{matrix}$

Step 4. Each signatory U_i selects any pair of keys (e_i, d_i), selects a public key e_i, and satisfies gcd [e_i, (p_i - 1) (q_i - 1) (p_i + 1) (q_i + 1)] =1. There exists an integer d_i such that e_i × d_i ≡ 1 mod S (n_i). Additionally, d_i is the inverse of e_i and can be obtained using the extended Euclidean algorithm [19].

Step 5. For any given document M, the signatory establishes the corresponding series:

if T₀ (M) =1, T₁ (M) = M, then $T_{i} (M) = 2 {MT}_{i - 1} (M) - T_{i - 2} (M) mod n_{i}$ (20) where i≥1

Step 6. Finally, each signatory makes (n_i, e_i) public, and regards (p_i, q_i, d_i) as the signatory’s own secret key.

Signature and authentication phase

Assume that a document M is to be signed by t individuals {U_i, 1 ≤ i ≤ t}, where U₁ is specified as the issuer of the document and U₁ signs the document first. Each signatory first performs authentication of the signature, according to the signing order list specified by official documents, to determine whether the previous signature is valid. Then, signatories use their own secret keys to perform the task of signing the document and deliver the document to the next signatory through the ring network to complete the entire multisignature. The authentication and signature phase can be divided into five steps:

Step 1. First, the first signatory U₁ (i.e. the issuer of the document) signs document M; the calculations of the signature are of the form: $S_{1} = T_{d_{1}} (M) mod n_{1} .$ (21)

Step 2. The digital signature S₁ of the first signatory is delivered to the second signatory U₂.

Step 3. The second signatory U₂ must use the public key e₁ of signatory U₁ to obtain document M (i.e. to restore M), $M = T_{e_{1}} (S_{1}) mod n_{1} .$ (22)

If M is meaningful, this indicates no errors exist in the authentication of U₁, and the second signatory U₂ accepts this signature; otherwise, it is rejected. If the second signatory agrees to sign, the signature S₁ of the first signatory is used to sign. The formula for signature calculation is: $S_{2} = T_{d_{2}} (S_{1}) mod n_{2},$ (23) and signature S₂ is delivered to U₃ using the network.

Step 4. When i is between 3 and t - 1 (i.e. 3 ≤ i ≤ t - 1), and this step is repeatedly performed: U_i uses the public keys (e₁, e₂, …, e_i-1) of (U₁, U₂, …, U_i-1) to decrypt S_i-1 and recover document M, M = (T_{e
₁} (T_{e
₂} … (T_{e
_i-1} (S_i-1)) …)). Because the relation n₁ < n₂ < … < n_i-1 exists in the ring network, document M can be recovered by U_i. If M is meaningful, this indicates no errors exist in the authentication of the signatures of U₁, U₂, …, U_i-1. If signatory U_i agrees to sign, and signs the signature S_i-1 of the i - 1th signatory, the signature is then changed to: $S_{i} = T_{d_{i}} (S_{i - 1}) mod n_{i} .$ (24)

Signatory U_i then delivers signature S_i to U_i+1.

Step 5. The final signatory U_t decrypts the received signature S_t-1 to recover document M, M = (T_{e
₁} (T_{e
₂} … (T_{e
_t-1} (S_t-1)) …)). If M is meaningful, this indicates no errors exist in the authentication of the signatures of U₁, U₂, …, U_t-1. If signatory U_t agrees to sign, and signs S_t-1 as S_t, $S_{t} = T_{d_{t}} (S_{t - 1}) mod n_{t} .$ (25)

Finally, the signatory delivers signature S_t to the receiver U_R. If the system has the issuer as the receiver, the issuer may, according to the aforementioned authentication steps, recognize that signing of the official document has been completed. The issuer can then grant approval to issue and implement the document according to the specifications of official document processing, followed by archiving of the document according to procedure.

The multisignature scheme based on chaotic maps proposed in this paper is not limited regarding the number of signatories. Specifically, for each signed official document, the t + 1th signatory can be determined by the tth signatory according to the procedure of official document signing and personal authority. This multisignature scheme is also a true signature; that is, the receiver can also perform confirmation independently, upon receiving the signature, and does not require an intermediate moderator. Thus, communication on both sides can utilize the proposed multisignature scheme to establish a secure multisignature operating system.

4 Security analysis

A multisignature is secure when, in the event that deceit or fraud occurs during the process of handling multiple signatures, the cheater can be identified, and various types of attacks can be prevented to ensure the security of the scheme. This section analyzes the security of the multisignature scheme proposed in this paper, and performs a step-by-step, in-depth explanation from the perspectives of theory, the security of multisignature schemes, and its ability to prevent multiplicative attacks.

4.1 This framework is established on the basis of computational security

This framework proposes a new multisignature scheme that was designed using chaotic maps. In the theory of cryptography, the difficulty of solving chaotic maps is equivalent to the difficulty of the generalized discrete logarithm problem and is a computationally secure problem. Because the secret key d_i of each signatory is only under the possession of the producer himself, and it would be highly difficult to be obtain d_i using the public key e_i, no one is able to forge the signature. Similarly, a signatory cannot repudiate a signature; the existence of the signature effectively proves that the signatory’s secret key made the signature.

Additionally, in the initialization phase of this framework, each signatory must select two strong prime numbers p and q and keep them confidential. The product of the two large prime numbers p × q can be made public, which is similar to the traditional RSA scheme and possesses a similar level of security. Thus, the security of this framework is established on the difficulty of the factorization problem, and is classified as computationally secure.

4.2 This framework possesses recoverability

The authentication of the multisignature scheme proposed in this paper was intended to restore the obtained signature S to the original document M. In the following, it is proved that because this scheme possesses the characteristic of the composition rule, it enables the authentication of signatures to have recoverability.

Lemma 1. The given d and e are the signature and authentication keys, respectively, and the characteristic of chaotic maps can be used to restore signature S to the original document M, i.e. $T_{e} (T_{d} (M)) = T_{e} (S) = T_{ed} (M) = M$

Proof 1. The characteristic polynomial of the chaotic map established by document M is f (x) = x² - 2Mx + 1 =0, and there exist two roots, α and β, where α × β = 1 . ∴ β = α^-1, therefore the roots of the polynomial are defined here as α, α^-1. According to the definition of chaotic maps [11], the relation T_x (M) = α^x + α^-x exists. Therefore, using the signature key d on the signature of document M can be expressed as T_d (M) = α^d + α^-d.

2. Assuming that in the chaotic map established by document T_d (M), the roots of the characteristic polynomial f (x) = x² - T_d (M) x + 1 =0 are β and β^-1, whereas β + β^-1 = T_d (M) = α^d + α^-d.

3. Because the relation β + β^-1 = α^d + α^-d exists, the two solutions β = α^d and β = α^-d can be obtained [42]. Therefore, the recoverability of the document can be divided into two solutions for further analysis:

Case 1: When β = α^d, $\begin{matrix} T_{e} (T_{d} (M)) = T_{e} (α^{d} + α^{- d}) = T_{e} (β + β^{- 1}) \\ = β^{e} + β^{- e} = α^{ed} + α^{- ed} = T_{ed} (M) . \end{matrix}$ (26)

Case 2: When β = α^-d, $\begin{matrix} T_{e} (T_{d} (M)) = T_{e} (α^{d} + α^{- d}) = β^{e} + β^{- e} \\ = α^{- ed} + α^{ed} = T_{ed} (M) . \end{matrix}$ (27)

4. Furthermore, because the two keys d and e are mutually inverse, $T_{e} (T_{d} (M)) = T_{ed} (M) = T_{1} (M) = M .$ (28)

This proves that this multisignature scheme possesses recoverability.

4.3 This framework can prevent multiplicative attacks

Because the familiar RSA cryptosystem is characterized by the multiplicative property, as shown in Fig. 1, it is vulnerable to multiplicative attacks during the generation of digital signatures.

Fig.1

Characteristics of the multiplicative property.

Lemma 2. Multiplicative attacks are defined as follows: If an intruder into any system knows the two signatures and the corresponding plaintext pair {(S₁, M₁) , (S₂, M₂)}, without knowing the secret key d of the signatory, the intruder is nevertheless able to forge a valid plaintext and signature pair {(M₁ × M₂) , (S₁ × S₂)}. This type of attack can be expressed as:

$\begin{matrix} If [S_{1} \equiv M_{1}^{d} (mod n)] and [S_{2} \equiv M_{2}^{d} (mod n)] \\ then (S_{1} \times S_{2}) = (M_{1} \times M_{2})^{d} . \end{matrix}$ (29)

5 Functionality comparison

The proposed digital multisignature scheme is established using chaotic maps. Because the chaotic cryptosystem itself is nonmultiplicative, this scheme can avoid multiplicative attacks. This can be expanded to avoid modular inverse attacks and chosen-plaintext attacks. Therefore, this scheme is more secure than multisignature schemes established using the RSA system.

Overall, according to the aforementioned security analysis, it can be found that a multisignature scheme based on chaotic maps can defend against attacks by individuals with harmful intentions and achieve a favorable effect of confidentiality.

Existing multisignature schemes are mostly designed using public key cryptosystems. However, public key cryptosystems at the present stage require time-consuming factorization computation, modular exponentiation, or elliptic curve point multiplication. Several expert scholars have attempted to develop more efficient cryptographic techniques and schemes, and chaotic maps are a new type of technique proposed in recent years for the development of public key cryptosystems. The computation of chaotic maps has been proven to possess mathematical characteristics similar to those of modular inverse and elliptic curve point multiplication computations; chaotic map schemes are clearly more efficient than other schemes.

Items of functionality are expressed here, and Table 3 is used to show the functionality between related plans, described as follows:

Can avoid multiplicative attacks

Can avoid modular inverse attacks

Can avoid chosen-plaintext attacks

Can avoid replay attacks

Computation and communication costs are low

Possesses recoverability

Table 3
Comparison with other relevant mechanisms

RSA [18 , 24] ElGamal [22, 23] Our scheme

C1 NO YES YES

C2 NO NO YES

C3 NO NO YES

C4 YES YES YES

C5 NO NO YES

C6 YES YES YES

	RSA [18 , 24]	ElGamal [22, 23]	Our scheme
C1	NO	YES	YES
C2	NO	NO	YES
C3	NO	NO	YES
C4	YES	YES	YES
C5	NO	NO	YES
C6	YES	YES	YES

6 Conclusion

In the past, research on public key cryptosystems has only discussed schemes based on RSA or ElGamal. Cryptosystems based on chaos theory are gradually gaining attention, which proves that they possess crucial value.

This paper proposed a multisignature scheme based on chaotic maps; at present, no relevant studies have proposed such a scheme, and this paper thus provides a new research direction. The security and effectiveness of this scheme are superior to those of conventional public key cryptosystems; the proposed scheme can avoid the vulnerabilities and shortcomings of other schemes, including multiplicative attacks, modular inverse attacks, and chosen-plaintext attacks. Therefore, the security of the scheme proposed in this framework can be affirmed.

Footnotes

Acknowledgments

The authors would like to thank the Ministry of Science and Technology of the Republic of China, for financially supporting this research under Contract No. MOST 106-2221-E-145-002-.

References

C.M.

, Hwang

and Lee

N.Y.

, Remark on the threshold RSA signature scheme, Advances in Cryptology-CRYPTO’93, Santa Barbara, California (1994), 413–419.

Laih

C.S.

, Yang

W.C.

and Chen

C.H.

, Efficient method for generating strong primes with constraint of bit length, Electronics Letters 27(20) (1991), 1807–1808.

Denning

D.E.

, Digital signatures with RSA and other public-key cryptosystem, Communications of the ACM 27(4) (1984), 388–392.

Davies

D.W.

, Applying the RSA digital signature to electronic mail, IEEE Computer Magazine 16(2) (1983), 55–62.

Xiao

, Shih

and Liao

, A chaos-based hash function with both modification detection and localization capabilities, Commun Nonlinear Sci Numer Simul 15(9) (2010), 2254–2261.

Brickell

E.F.

and McCurley

K.S.

, An interactive identification scheme based on discrete logarithms and factoring,: pp, Advances in Cryptology-EUROCRYPT’90 Proceeding, Berlin: Springer-Verlag, (1990), 63–71.

Dachselt

and Schwarz

, Chaos and cryptography, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 48(12) (2001), 1498–1509.

Chen

, Mao

and Chui

, A symmetric image encryption scheme based on 3D chaotic cat maps, Chaos Solitons Fractals 21(3) (2004), 749–761.

Simmons

G.J.

Contemporary Cryptology: The Science of Information Integrity, Piscatoway, New York, IEEE Press, 1992.

10.

Fridrich

, Symmetric ciphers based on two-dimensional chaotic maps, International Journal of Bifurcation and Chaos 8(6) (1998), 1259–1284.

11.

Gordon

, Strong RSA keys, Electron Letters 20 (1984), 514–516.

12.

Liu

J.K.

, Au

M.H.

and Susilo

, Self-Generated-Certificate Public Key Cryptography and Certificateless Signature/Encryption Scheme in the Standard Model, In: 2007 ACM Symposium on InformAtion, Computer and Communications Security - ASIACCS’07.

13.

Zhang

, Chen

, Wang

On the Security of a Digital Signature with Message Recovery Using Self-certified Public Key, Proceedings of the International Conference on Applied Mathematics and Computer Science (AMCOS’05) (2005), 343–346.

14.

Shim

K.A.

, Forgery attacks on the ID-based multisignature scheme without reblocking and predetermined signing order, Computer Standards & Interfaces 30 (2008), 121–123.

15.

David

K.B.

, The digital signature standard: Overview and current status, Computer & Security 12 (1993), 437–446.

16.

Chain

and Kuo

W.C.

, A new digital signature scheme based on chaotic maps, Nonlinear Dynamics 74(4) (2013), 1003–1012.

17.

Chain

, Kuo

W.C.

and Chang

K.H.

, Enhancement key agreement scheme based on chaotic maps, International Journal of Computers and Applications 37(2) (2015), 67–72.

18.

Itakura

and Nakamura

, A public-key cryptosystem suitable for digital multisignatures, NEC Research and Development 71 (1983), 1–8.

19.

Ohta

and Okamoto

, A digital multisignature scheme based on the Fiat-Shamir scheme, pp, Advances in Cryptology-ASIACRYPT’91, International Conference on the Theory and Application of Cryptology Proceedings Fujiyoshida, Japan, Springer-Verlag 1991, pp. 139–148.

20.

Wong

K.W.

, A fast chaotic cryptographic scheme with dynamic look up table, Physics Letters A 298(4) (2002), 238–242.

21.

Harn

and Kiesler

, New scheme for digital multisignatures, Electronics Letters 25(15) (1989), 1002–1003.

22.

Harn

, New digital signature scheme based on discrete logarithms, Electronic Letts 30(5) (1994), 396–398.

23.

Harn

, Digital multi-signature with distinguished signing authorities, Electronics Letters 35 (1999), 294–295.

24.

Harn

and Ren

, Efficient identity-based RSA multisignatures, Computers and Security 27 (2010), 12–15.

25.

Kocarev

, Chaos-based cryptography: A brief overview, IEEE Circuits and Systems Magazine 1(3) (2001), 6–21.

26.

Bellare

and Neven

, Identity-based multi-signatures from RSA, Proceedings of the Topics in cryptology CTRSA, LNCS 2007 (4377), 145–162.

27.

Ogiwara

, A method for generating cryptographically strong primes, Transactions IEICE E73 (1990), 985–994.

28.

Rivest

R.L.

, Shamir

and Adelman

L.M.

, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21(2) (1978), 120–126.

29.

Al-Riyami

and Paterson

, Certificateless public key cryptography, In: Proceedings of the Asiacrypt’03, LNCS 2894, Springer Verlag, 2003, pp. 452–473.

30.

Deng

, Li

and Xiao

, Analysis and improvement of a chaos-based Hash function construction, Commun Nonlinear Sci Numer Simul 15(5) (2010), 1338–1347.

31.

Islam

S.H.

and Biswas

G.P.

, Certificateless short sequential and broadcast multisignature schemes using elliptic curve bilinear pairings, Journal of King Saud University - Computer and Information Sciences 26 (2014), 89–97.

32.

Jye

, A speech encryption using fractional chaotic systems, Nonlinear Dynamics 65 (2011), 103–108.

33.

Mitomi

and Miyaji

, A Multisignature Scheme with Message Flexibility, Order Flexibility and Order Verifiability, Proceedings of the 5th Australasian Conference on Information Security and Privacy (ACISP 2000), Spring-Verlag, 2000, pp. 98–312.

34.

Micali

, Ohta

and Reyzin

, Accountable-subgroup multisignatures: Extended abstract, Proceedings of the ACM Conference on Computer and Communications Security 2001 (CCS2001), ACM press, 2001, pp. 245–254.

35.

ElGamal

, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transaction on Information Theory IT-31(4) (1985), 469–472.

36.

Okamoto

, Fujika

, Fujisaki

An efficient digital signature scheme based on an Elliptic curve over the ring Zn Crypto’92, Santa Barbara, California, 1992, pp. 54–65.

37.

Okamoto

, A digital multisignature scheme using bijective public-key cryptosystems, ACM Transactions on Computer Systems 6(4) (1988), 432–441.

38.

Biao

, Xiaodong

and Guang

, An Identity Based Multisignature Scheme from the Weil Pairing, Proceedings of the International Conference on Computer Design and Applications 5 (2010), 585–587.

39.

Diffie

and Hellman

M.E.

, New directions in cryptography, IEEE Transactions on Information Theory IT-22(6) (1976), 644–654.

40.

Gui

W.X.

and Zhang

X.P.

, ID-based designed-verifier multisignature without trusted PKG, Proceedings of the Third International Conference on Information and Computing, 2010, pp. 213–215.

41.

Wang

, Yang

and Liu

, A chaotic image encryption algorithm based on perceptron model, Nonlinear Dynamics 62 (2010), 615–621.

42.

Wang

, Wang

and Zhao

, Chaotic encryption algorithm based on alternant of stream cipher and block cipher, Nonlinear Dynamics 63 (2011), 587–597.

43.

Chung

Y.F.

, Huang

K.H.

, Lai

and Chen

T.S.

, ID-based digital signature scheme on the elliptic curve cryptosystem, Computer Standards and Interfaces 29 (2000), 601–604.

44.

Tan

, A chaotic maps-based authenticated key agreement protocol with strong anonymity, Nonlinear Dynamics 72(1-2) (2013), 311–320.

A novel multisignature scheme based on chaotic maps

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 ElGamal multisignature scheme

Table 1 Notations description Notations Descriptions n Assume a set of n signatories exists. p A large prime number. e Primitive element (mod p). x i A secret key. y i A public key. M The same document.

2.3 Characteristics of chaotic maps

3.1 Notations

4.1 This framework is established on the basis of computational security

4.2 This framework possesses recoverability

Table 3 Comparison with other relevant mechanisms RSA [18, 24] ElGamal [22, 23] Our scheme C1 NO YES YES C2 NO NO YES C3 NO NO YES C4 YES YES YES C5 NO NO YES C6 YES YES YES

Footnotes

Acknowledgments

References

Table 1
Notations description

Notations Descriptions

n Assume a set of n signatories exists.

p A large prime number.

e Primitive element (mod p).

x _i A secret key.

y _i A public key.

M The same document.

Table 3
Comparison with other relevant mechanisms

RSA [18 , 24] ElGamal [22, 23] Our scheme

C1 NO YES YES

C2 NO NO YES

C3 NO NO YES

C4 YES YES YES

C5 NO NO YES

C6 YES YES YES