# An ECC-Based Digital Signature Scheme for Privacy Protection in Wireless Communication Network

Authors: Ping Zhang; Yamin Li; Muhua Liu; Youlin Shang; Zhumu Fu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Aiming at the security problems of wireless communication network and the shortcomings of Elliptic Curve Digital Signature Algorithm (ECDSA), this paper designed a forward secure digital signature scheme and proved that the scheme has forward security and unforgeability in the random oracle model. Experimental simulations are done in this paper, and the results show that the proposed scheme has the highest efficiency compared with the ECDSA scheme and the three existing forward secure schemes. This scheme not only meets the forward security and protects the users’ privacies but also reduces the requirement of computing power of the user in the wireless communication network.


---

## Body

## 1. Introduction

In recent years, with the popularization of mobile devices in daily life, wireless network communication has developed rapidly. Now, for most mobile terminals, the wireless network is even the only means to access the network. The most prominent feature of the wireless network is that it breaks through the limitations of the wired network, saves a lot of line maintenance costs, and spreads more widely and flexibly. As an extension of the wired network, the application of the wireless network has greatly improved the efficiency of users’ work and life [1–3]. However, with the deepening of wireless network applications, the security problems of wireless networks are becoming more and more obvious. The potential security risks of wireless networks pose a serious threat to users’ information security. The security requirements of wireless network communication include the following three aspects. (1) Confidentiality: the wireless network communication should ensure the information security of both sides of the communication and prevent others from illegally using the information. (2) Integrity: the wireless network communication should ensure the integrity of data information to prevent illegal users from modifying, inserting and deleting information unintentionally or maliciously. (3) Nonrepudiation: the wireless network communication needs to realize the nonrepudiation of the information between the two communicating parties, so as to prevent the sender from denying that it has sent the information after sending the information, and also prevent the receiver from denying that it has received the information after receiving the information. In the above security requirements, the confidentiality is guaranteed by encryption technology, while the integrity and nonrepudiation need to use digital signature technology. Digital signature is the key technology in privacy protection scheme.The digital signature plays an important role in many occasions, such as identity authentication, data integrity protection, and anonymity. It can solve many problems, such as signature forgery, repudiation, impersonation, and tampering [4]. The wireless communication network is a restricted environment, i.e., time (key generation, signature and verification, etc.) and space (data memory, program memory, bandwidth, code and data length, etc.) limit the achievement of security goals. In addition, wireless devices have relatively low computing power and relatively small storage space. This limits the application of cryptography technology, which requires a large number of complex operations, in wireless communication network. Therefore, how to design an efficient and secure digital signature scheme for wireless communication networks has become an urgent problem.The common digital signature includes RSA digital signature, ElGamal digital signature, and elliptic curve (ECC-based) digital signature. When the key lengths of the three digital signatures are equal, the ECC-based digital signature [5] has the highest security. In 1985, Neal Koblitz [6] and V.S. Miller [7] proposed this algorithm, respectively. In the ECC-based digital signature, it is the elliptic curve finite group [8], instead of the finite cyclic group. Compared with the former two digital signatures, the ECC-based digital signature has the following advantages. Firstly, there are many different elliptic curves in the same finite field, which additionally ensures security. Secondly, the ECC-based digital signature is based on ECDLP, which is more difficult to solve than the discrete logarithm problem on the multiplication group of the prime field [9]. Finally, the key length of the ECC-based digital signature is shorter when the same level of security is required. In 1992, Scott Vanstone firstly proposed ECDSA, which was defined as a standard digital signature algorithm by the International Standards Organization [10]. However, in the elliptic curve digital signature, the leakage of the key will bring great loss to the users.Anderson firstly proposed forward security to prevent key leakage in CCCS’97. However, he only put forward a brief description and did not give a specific scheme. Two years later, Bellare and Miner [11] not only proposed a detailed concept of forward security in Crypto’99 but also designed a forward secure digital signature scheme firstly. Forward security of the digital signature means that an attacker cannot know the key of previous time and forge the signature of previous time even if he acquires the key of a certain time [12]. The main idea of this technology is easy. That is, the system time is divided into many periods so that the key is different at any period [13]. Therefore, in a forward secure digital signature scheme, even if the private key of a certain period is leaked, the security of the message will not be affected in the previous period. This paper designs a forward secure ECC-based digital signature scheme for privacy protection in wireless communication network and proves that the scheme has forward security and unforgeability in the random oracle model. Compared with the ECDSA scheme and three existing forward secure schemes, the improved scheme not only meets the forward security and protects the users’ privacies but also reduces the requirement of computing power of the user in the wireless network.


### 1.1. Related Works

In 2000, based on any regular scheme (such as RSA and DSA), Krawczyk [14] proposed a more efficient and simple digital signature scheme with forward security. In the same year, Abdalla and Reyzin [15] improved Bellare’s scheme [11] in the ROM. They have improved the scheme with the shorter keys, which increased the practicability of this scheme. Bellare introduced some methods to construct digital signature schemes with forward security. Abdalla and Reyzin summarized and supplemented Bellare’s methods. In 2001, Malkin et al. [16] combined the existing schemes into a new forward secure digital signature scheme without knowing the total number of periods. This scheme not only can take any digital signature scheme as the underlying module but also does not depend on any specific assumptions. They also constructed the first efficient digital signature scheme with forward security, which does not need to determine the total period in advance. In the same year, Itkis and Reyzin [17] designed a digital signature scheme with forward security, which requires only four modular exponential with short exponents in signature and verification. They proved this scheme is secure in the ROM. In 2002, Kozlov and Reyzin [18] designed a digital signature scheme that only needs a simple modular square in the KeyUpdate. They proved this scheme is secure based on the Fiat-Shamir transformation and the strong RSA assumption. In 2003, Fei et al. [19] designed a new digital signature scheme based on bilinear mapping, which has strong robustness. They proved this scheme is secure based on the computational Diffie-Hellman assumption. In 2004, McCullagh and Barreto [20] proposed a new efficient digital signature scheme with forward security. In the same year, Kang et al. [21] designed two digital signature schemes using the same KeyUpdate algorithm. In 2006, Boyen et al. [22] firstly proposed the forward security digital signature with un-trusted updates.In 2011, Buchmann et al. [23] designed a hash-based digital signature scheme with a smaller signature size. In 2011, Liu et al. [24] proposed a ring signature scheme with forward security. This scheme ensures that all previous signatures containing this member are valid even if the key of some ring member is disclosed. In 2012, Yao-Chang et al. [25] analyzed the shortcomings of the digital signature in Electronic Medical Record (EMR) and proposed a forward secure digital signature scheme for EMR. In 2013, based on the Guillou-Quisquater signature scheme and Rabin cryptosystem, Guang-bao et al. [26] proposed a strong forward secure digital signature scheme. In 2014, based on Schnorr’s digital signature scheme and Shamir’s t,n threshold scheme, Yao-Chang et al. [27] proposed an efficient group signature scheme with forward security. This scheme has integrity and improves the efficiency of authentication of EMR in the KeyUpdate. In 2015, Zhenping et al. [28] proposed an ID-based forward secure digital signature algorithm using the Chebyshev public-key algorithm. The public key of this algorithm is the identity information of the signer. In addition, this algorithm has higher security, which based on large integer factorization and Cheyshev discrete logarithm problem. In 2016, based on the elliptic curve, Keyuan [29] proposed a digital signature scheme with message recovery, which not only resists forgery signature attack but also is forward secure. In the same year, Yarong et al. [30] proposed a forward secure proxy signature scheme, which is secure for all requirements of forward secure proxy signature. Based on ElGamal system, Shun-bo et al. [31] designed a digital signature scheme by using one-way hash chain technology. In 2017, based on the elliptic curve, Jinyuan and Xianghua [32] designed a forgery signature method to solve the security problem of the digital signature scheme with forward security. In 2017, for embedded real-time systems, considering the limited sensor resources and time constraints, Kim et al. [33] designed a forward secure digital signature scheme. In the ROM, they proved the proposed scheme is secure and gave the concrete implementation of the scheme. In the same year, aiming at the shortcomings of the certificateless signature scheme, Xu et al. [34] firstly designed a forward secure certificateless digital signature scheme based on random lattice in the standard model. They proved the strong unforgeability of the scheme based on small integer solution problem. In 2019, Xiaoping [35] combined certificateless public-key system with forward security and proposed a proxy blind signature scheme. This scheme solved the problem of key escrow and certificate management. Based on the above works, we propose a forward secure elliptic curve digital signature scheme to enhance the security of information systems.


### 1.2. Contribution

Aiming at the security problems of wireless communication network and the shortcomings of ECDSA scheme, this paper constructed an improved digital signature scheme and proved the security of the scheme. Compared with the ECDSA scheme, the improved scheme added key update algorithm to achieve the forward security and avoided the modular inversion by adjusting the signature formula. Compared with the ECDSA scheme and three existing forward secure schemes, the improved scheme reduces the requirement of computing power of the user in the wireless network. So, it is more suitable for wireless communication network.


### 1.3. Organization

We organized our paper as follows. The first section is the introduction of this paper. The second section introduces the knowledge of quadratic congruence equation, elliptic curve cryptography, and ROM. In the third section, we introduce the formal definition of Forward secure digital signature scheme (FSDSS), including adversary model and security definition. In the fourth section, we design an ECC-based digital signature scheme (the improved scheme). In the fifth section, we prove the improved scheme is secure. In the sixth section, we compare the efficiency of the improved scheme with the other four schemes. Finally, in the seventh section, we summarize the full text.


## 1.1. Related Works

In 2000, based on any regular scheme (such as RSA and DSA), Krawczyk [14] proposed a more efficient and simple digital signature scheme with forward security. In the same year, Abdalla and Reyzin [15] improved Bellare’s scheme [11] in the ROM. They have improved the scheme with the shorter keys, which increased the practicability of this scheme. Bellare introduced some methods to construct digital signature schemes with forward security. Abdalla and Reyzin summarized and supplemented Bellare’s methods. In 2001, Malkin et al. [16] combined the existing schemes into a new forward secure digital signature scheme without knowing the total number of periods. This scheme not only can take any digital signature scheme as the underlying module but also does not depend on any specific assumptions. They also constructed the first efficient digital signature scheme with forward security, which does not need to determine the total period in advance. In the same year, Itkis and Reyzin [17] designed a digital signature scheme with forward security, which requires only four modular exponential with short exponents in signature and verification. They proved this scheme is secure in the ROM. In 2002, Kozlov and Reyzin [18] designed a digital signature scheme that only needs a simple modular square in the KeyUpdate. They proved this scheme is secure based on the Fiat-Shamir transformation and the strong RSA assumption. In 2003, Fei et al. [19] designed a new digital signature scheme based on bilinear mapping, which has strong robustness. They proved this scheme is secure based on the computational Diffie-Hellman assumption. In 2004, McCullagh and Barreto [20] proposed a new efficient digital signature scheme with forward security. In the same year, Kang et al. [21] designed two digital signature schemes using the same KeyUpdate algorithm. In 2006, Boyen et al. [22] firstly proposed the forward security digital signature with un-trusted updates.In 2011, Buchmann et al. [23] designed a hash-based digital signature scheme with a smaller signature size. In 2011, Liu et al. [24] proposed a ring signature scheme with forward security. This scheme ensures that all previous signatures containing this member are valid even if the key of some ring member is disclosed. In 2012, Yao-Chang et al. [25] analyzed the shortcomings of the digital signature in Electronic Medical Record (EMR) and proposed a forward secure digital signature scheme for EMR. In 2013, based on the Guillou-Quisquater signature scheme and Rabin cryptosystem, Guang-bao et al. [26] proposed a strong forward secure digital signature scheme. In 2014, based on Schnorr’s digital signature scheme and Shamir’s t,n threshold scheme, Yao-Chang et al. [27] proposed an efficient group signature scheme with forward security. This scheme has integrity and improves the efficiency of authentication of EMR in the KeyUpdate. In 2015, Zhenping et al. [28] proposed an ID-based forward secure digital signature algorithm using the Chebyshev public-key algorithm. The public key of this algorithm is the identity information of the signer. In addition, this algorithm has higher security, which based on large integer factorization and Cheyshev discrete logarithm problem. In 2016, based on the elliptic curve, Keyuan [29] proposed a digital signature scheme with message recovery, which not only resists forgery signature attack but also is forward secure. In the same year, Yarong et al. [30] proposed a forward secure proxy signature scheme, which is secure for all requirements of forward secure proxy signature. Based on ElGamal system, Shun-bo et al. [31] designed a digital signature scheme by using one-way hash chain technology. In 2017, based on the elliptic curve, Jinyuan and Xianghua [32] designed a forgery signature method to solve the security problem of the digital signature scheme with forward security. In 2017, for embedded real-time systems, considering the limited sensor resources and time constraints, Kim et al. [33] designed a forward secure digital signature scheme. In the ROM, they proved the proposed scheme is secure and gave the concrete implementation of the scheme. In the same year, aiming at the shortcomings of the certificateless signature scheme, Xu et al. [34] firstly designed a forward secure certificateless digital signature scheme based on random lattice in the standard model. They proved the strong unforgeability of the scheme based on small integer solution problem. In 2019, Xiaoping [35] combined certificateless public-key system with forward security and proposed a proxy blind signature scheme. This scheme solved the problem of key escrow and certificate management. Based on the above works, we propose a forward secure elliptic curve digital signature scheme to enhance the security of information systems.


## 1.2. Contribution

Aiming at the security problems of wireless communication network and the shortcomings of ECDSA scheme, this paper constructed an improved digital signature scheme and proved the security of the scheme. Compared with the ECDSA scheme, the improved scheme added key update algorithm to achieve the forward security and avoided the modular inversion by adjusting the signature formula. Compared with the ECDSA scheme and three existing forward secure schemes, the improved scheme reduces the requirement of computing power of the user in the wireless network. So, it is more suitable for wireless communication network.


## 1.3. Organization

We organized our paper as follows. The first section is the introduction of this paper. The second section introduces the knowledge of quadratic congruence equation, elliptic curve cryptography, and ROM. In the third section, we introduce the formal definition of Forward secure digital signature scheme (FSDSS), including adversary model and security definition. In the fourth section, we design an ECC-based digital signature scheme (the improved scheme). In the fifth section, we prove the improved scheme is secure. In the sixth section, we compare the efficiency of the improved scheme with the other four schemes. Finally, in the seventh section, we summarize the full text.


## 2. Preliminaries

### 2.1. Quadratic Congruence Equation

The general form of the quadratic congruence equation is(1)ax2+bx+c≡0modN,a≡0modN,which can be transformed to another equation:
(2)x2≡a′modN,a′,N=1.This form is the standard form of the quadratic congruence equation.When the decomposition ofN is known, it is simple to calculate x. However, when the decomposition of N is unknown, it is difficult to calculate x. Therefore, the quadratic congruence equation has the same difficulty as the factorization problem [36]. The theory of quadratic congruence equation will be used in the KeyUpdate of the improved scheme.


### 2.2. Elliptic Curve Cryptography

The elliptic curve (cubic smooth algebraic curve) can be expressed as Weierstrass equation(3)y2+axy+by=x3+cx2+dx+e.In this equation,a,b,c,d,e are constants defined in the field. If the characteristic of the field is not 2, equation (3) can be transformed into
(4)y+ax2+b22=x3+c+a24x2+d+ab2x+e+b24,which can be written as
(5)y12=x3+a1x2+a2x+a3,withy1=y+ax/2+b/2 and some constants a1,a2,a3. If the characteristic of the field is also not 3, we can let x1=x+a1/3 and obtain
(6)y12=x13+Ax1+B,for constantsA,BΔ=4A3+27B2≠0.In the real field, in addition to all points on the elliptic curve, the Abel addition group also includes the infinity pointO (zero point).Definition 1. (Abel addition group of elliptic curve).
The points of the elliptic curveE can generate an Abel addition group, if the addition of points on E satisfies the following five properties.
(i)
(Closure): onE, for any points P1 and P2, there is a point P3 with P1+P2=P3(ii)
(Associativity): for any pointsP1, P2, and P3 on E, there is P1+P2+P3=P1+P2+P3(iii)
(Existence of identity): for any pointP on E, there is P+O=P(iv)
(Existence of inverses): onE, for any point P, there is a point P′ with P+P′=O. This point P′ is often denoted as −P(v)
(Commutativity): for all pointsP1 and P2 on E, there is P1+P2=P2+P1Definition 2. (Elliptic curve addition rule).
The elliptic curve addition rule is defined as follows.(i)
(Add to zero point): letO be the unit element of the addition. For any point R on E, there is R+O=R(ii)
(Add to the inverse element): for any pointR=x,y on E, its additive inverse is −R=x,−y). There is −R+R=R+−R=R−R=O(iii)
(Add two points): for any pointsP=x1,y1 and Q=x2,y2 on E, there is P+Q=x3,y3=λ2−x1−x2,λx1−x3−y1, where(7)λ=y2−y1x2−x1P≠Q3x12+a2y1P=Q.Definition 3. (Elliptic curve discrete logarithm problem).
For an elliptic curveE, G is a point on E, and its order n is a prime number. For any random number k, it is easy to calculate Q=kG. However, if G and Q are known, it is very difficult to find k.


### 2.3. Random Oracle Model

In ROM, the random oracle is a deterministic, accessible publicly, random uniform distribution function. It uniformly selects a value with deterministic length from the output field and makes the value as the answer (output) for the query (input) of the message with any length.In the scheme, the hash function is idealized as a random oracle. The adversary can only obtain the required hash value by asking the random oracle. Between random oracle and adversary, there is also a simulator in the model. The simulator transforms the ability of the adversary into an advantage of breaking a known difficult problem.In the ROM, the provable security is regarded as a simulation game. It is called training that the simulator answers all of the queries defined by the adversary. At the end of the simulation game, if the adversary can complete the pre-determined challenge from the simulator, the simulation game succeeds. This predetermined challenge contains some knowledge. The simulator can use this knowledge to solve the difficult problem in the scheme. Therefore, if the success probability of the simulation game is a nonnegligible value, this difficult problem is no longer difficult in the environment with the given adversary. This contradicts the computational difficulty of the known difficult problem in the real world.


## 2.1. Quadratic Congruence Equation

The general form of the quadratic congruence equation is(1)ax2+bx+c≡0modN,a≡0modN,which can be transformed to another equation:
(2)x2≡a′modN,a′,N=1.This form is the standard form of the quadratic congruence equation.When the decomposition ofN is known, it is simple to calculate x. However, when the decomposition of N is unknown, it is difficult to calculate x. Therefore, the quadratic congruence equation has the same difficulty as the factorization problem [36]. The theory of quadratic congruence equation will be used in the KeyUpdate of the improved scheme.


## 2.2. Elliptic Curve Cryptography

The elliptic curve (cubic smooth algebraic curve) can be expressed as Weierstrass equation(3)y2+axy+by=x3+cx2+dx+e.In this equation,a,b,c,d,e are constants defined in the field. If the characteristic of the field is not 2, equation (3) can be transformed into
(4)y+ax2+b22=x3+c+a24x2+d+ab2x+e+b24,which can be written as
(5)y12=x3+a1x2+a2x+a3,withy1=y+ax/2+b/2 and some constants a1,a2,a3. If the characteristic of the field is also not 3, we can let x1=x+a1/3 and obtain
(6)y12=x13+Ax1+B,for constantsA,BΔ=4A3+27B2≠0.In the real field, in addition to all points on the elliptic curve, the Abel addition group also includes the infinity pointO (zero point).Definition 1. (Abel addition group of elliptic curve).
The points of the elliptic curveE can generate an Abel addition group, if the addition of points on E satisfies the following five properties.
(i)
(Closure): onE, for any points P1 and P2, there is a point P3 with P1+P2=P3(ii)
(Associativity): for any pointsP1, P2, and P3 on E, there is P1+P2+P3=P1+P2+P3(iii)
(Existence of identity): for any pointP on E, there is P+O=P(iv)
(Existence of inverses): onE, for any point P, there is a point P′ with P+P′=O. This point P′ is often denoted as −P(v)
(Commutativity): for all pointsP1 and P2 on E, there is P1+P2=P2+P1Definition 2. (Elliptic curve addition rule).
The elliptic curve addition rule is defined as follows.(i)
(Add to zero point): letO be the unit element of the addition. For any point R on E, there is R+O=R(ii)
(Add to the inverse element): for any pointR=x,y on E, its additive inverse is −R=x,−y). There is −R+R=R+−R=R−R=O(iii)
(Add two points): for any pointsP=x1,y1 and Q=x2,y2 on E, there is P+Q=x3,y3=λ2−x1−x2,λx1−x3−y1, where(7)λ=y2−y1x2−x1P≠Q3x12+a2y1P=Q.Definition 3. (Elliptic curve discrete logarithm problem).
For an elliptic curveE, G is a point on E, and its order n is a prime number. For any random number k, it is easy to calculate Q=kG. However, if G and Q are known, it is very difficult to find k.


## 2.3. Random Oracle Model

In ROM, the random oracle is a deterministic, accessible publicly, random uniform distribution function. It uniformly selects a value with deterministic length from the output field and makes the value as the answer (output) for the query (input) of the message with any length.In the scheme, the hash function is idealized as a random oracle. The adversary can only obtain the required hash value by asking the random oracle. Between random oracle and adversary, there is also a simulator in the model. The simulator transforms the ability of the adversary into an advantage of breaking a known difficult problem.In the ROM, the provable security is regarded as a simulation game. It is called training that the simulator answers all of the queries defined by the adversary. At the end of the simulation game, if the adversary can complete the pre-determined challenge from the simulator, the simulation game succeeds. This predetermined challenge contains some knowledge. The simulator can use this knowledge to solve the difficult problem in the scheme. Therefore, if the success probability of the simulation game is a nonnegligible value, this difficult problem is no longer difficult in the environment with the given adversary. This contradicts the computational difficulty of the known difficult problem in the real world.


## 3. Forward Secure Digital Signature Scheme

In the FSDSS, we assume that the system time is divided intoT periods, and the key is different in every period. In the KeyUpdate, the private key SKj of the j-th period can be calculated by the private key SKj−1 of the j−1-th period. However, it is difficult to calculate SKj−1 from SKj. During a certain period, since the signer uses only the private key SKj of this period, the key leakage of this period does not endanger the security of the system in the previous period.Definition 4. (Forward secure digital signature). The FSDSS generally consists of the following four algorithms [37].
Gen1λ,⋯⟶PK,SK0: this is a random algorithm. This algorithm takes a security parameter λ and other system parameters as input and outputs the public key PK, the initial private key SK0Updatej,SKj−1⟶SKj: this algorithm takes the private key SKj−1 of the previous period as input and outputs the private key SKj of this periodSignj,SKj,m⟶Sj: this algorithm takes the private key SKj of the j-th period and the message m as input and outputs the signature Sj of the j-th periodVrfyPK,m,Sj⟶0,1: this algorithm takes the public key PK, the message m, and the signature Sj of the j-th period as input. If the verification is valid, this algorithm outputs 1, otherwise 0. When VrfyPK,m,Sj=1, the signature Sj is the valid signature of message m at the j-th period


### 3.1. Adversary Model

We assume that the adversary is a third party; that is, we only consider external attacks. The adversary’s goal is to forge the signature information of the unsigned message. We assume that an adversary can submit the query of any message to the random oracle. After the adversary knows the result from the random oracle, he can still query the message.


### 3.2. Security Definition

Assuming that FSDSS is a four tupleFSDSS=Gen,Update,Sign,Vrfy, and A is an adversary. Next, let us consider the following game as Algorithm 1.Algorithm 1
gameλ,A,FSDSSPK,SK0⟵Gen1λbreakinj+1≤j+<T:SKj+⟵Update⋯UpdateSK0Signj,m1≤j<j+:Sj⟵SignSKj,mj∗,m∗,Sj∗⟵Aλ,PKbreakinj+,Signj,mIfPK is invalid then return 0.If0≤j∗<j+, m∗∉M and 1⟵VrfyPK,m∗,Sj∗.then return 1, else return0}(Assuming thatM is the set of messages m submitted by A to the signature oracle.)Definition 5. (Existential unforgeability).
If noPPT adversary can win this game with a nonnegligible advantage, the signature scheme FSDSS=Gen,Update,Sign,Vrfy is existentially unforgeable under an adaptive chosen-message attack. Let SuccA=Prgameλ,A,FSDSS=1. In this paper, “PPT” represents probabilistic polynomial time.


## 3.1. Adversary Model

We assume that the adversary is a third party; that is, we only consider external attacks. The adversary’s goal is to forge the signature information of the unsigned message. We assume that an adversary can submit the query of any message to the random oracle. After the adversary knows the result from the random oracle, he can still query the message.


## 3.2. Security Definition

Assuming that FSDSS is a four tupleFSDSS=Gen,Update,Sign,Vrfy, and A is an adversary. Next, let us consider the following game as Algorithm 1.Algorithm 1
gameλ,A,FSDSSPK,SK0⟵Gen1λbreakinj+1≤j+<T:SKj+⟵Update⋯UpdateSK0Signj,m1≤j<j+:Sj⟵SignSKj,mj∗,m∗,Sj∗⟵Aλ,PKbreakinj+,Signj,mIfPK is invalid then return 0.If0≤j∗<j+, m∗∉M and 1⟵VrfyPK,m∗,Sj∗.then return 1, else return0}(Assuming thatM is the set of messages m submitted by A to the signature oracle.)Definition 5. (Existential unforgeability).
If noPPT adversary can win this game with a nonnegligible advantage, the signature scheme FSDSS=Gen,Update,Sign,Vrfy is existentially unforgeable under an adaptive chosen-message attack. Let SuccA=Prgameλ,A,FSDSS=1. In this paper, “PPT” represents probabilistic polynomial time.


## 4. Construction

In 1999, ECDSA became an ANSI standard. In 2000, ECDSA became an IEEE and NIST standard. However, there are three double-point arithmetic, four modular multiplications, and two modular inverses in the ECDSA scheme. Therefore, the operation of ECDSA is complicated, and the ECDSA scheme does not have the forward security. Once the attacker gets the private key, he can forge the signatures of all messages of the previous periods. The purpose of this paper is to design an improved ECC-based digital signature scheme with forward security. In the improved scheme, we add the key update algorithm to ensure the forward security of the scheme. In the signature generation algorithm and signature verification algorithm, we simplify the calculation to improve signature efficiency. The improved scheme is as follows.


### 4.1. Parameter Selection

Assuming that the system’s time is divided intoT periods, GFq is a finite field with order q. E:y2=x3+ax+bmodq (a,b∈GFq,4a3+27b2≠0) is an elliptic curve over finite field GFq. G is the base point of the elliptic curve E with order n. That is, ordG=n, where n is a large prime number. N is a composite number (N>n), h=#EGFq/n, and (h≪n) is the cofactor. #EGFq represents the number of points on the elliptic curve E, which is defined on the finite field GFq. H:0,1∗⟶0,1160 is a secure hash algorithm. 0,1∗ represents a string with any length. SK0=a0 (a0∈1,n−1) is the initial private key, and PK=a0−1G is the public key. Then, we keep parameter SK0 secret, expose elliptic curve parameters D=q,a,b,G,n,h, the public key PK, and hash function H·.


### 4.2. Key Update

In thej-th period (1≤j≤T), the signer uses the key SKj−1 of the j−1-th period to calculate the key SKj=SKj−12modN of the j-th period. Therefore, in the j-th period (1≤j≤T), the private key is SKj=a02jmodN, where a02j is precalculated in each period. The key SKj−1 is deleted, and the key SKj is saved in the secret key list.


### 4.3. Signature Generation

The signer calculates the signature of messagem in the j-th (1≤j≤T) period [(1)].
(1)
At first, select a random numberk∈1,n−1(2)
Computek2−jG=x1,y1, r=x1modN. If r=0, return to step (1)(3)
Compute the hash valueej=Hj,m,r(4)
Computesj=SKjk−ejmodN. If sj=0, return to step (1)(5)
Get the signatureSj=r,sj


### 4.4. Signature Verification

The verifier checks whetherr,sj is the signature of message m in the j-th period (1≤j≤T) after receiving the signature r,sj and message m [(1)].
(1)
At first, verifyr,sj∈1,n−1. If not, return directly and reject the signature(2)
Compute the hash valuee′j=Hj,m,r(3)
Computewj=e′j+sjmodN(4)
ComputeX=wj2−jPK=x2,y2. If X=0, reject the signature(5)
Computev=x2modN. If v=r, the verifier accepts the signature. Otherwise, the signature Sj=r,sj will be rejected


### 4.5. Correctness Analysis

IfSj=r,sj is a valid signature for the message m in the j-th period (1≤j≤T), then the hash value is e′j=Hj,m,r=ej. Thus, wj=e′j+sjmodN=ej+sjmodN, it results in the second equal sign in equation. Since the signature component sj=SKjk−ejmodN, it results in the third equal sign in equation. And because of the private key SKj=a02jmodN and public key PK=a0−1G, they result in the fifth and seventh equal signs in equation, respectively. In addition, we recall that the initial private key is SK0=a0 (a0∈1,n−1), where n<N, and we can get a0<N. It results in the sixth equal sign in equation.
(8)X=wj2−jPK=ej+sjmodN2−jPK=SKjkmodN2−jPK=SKjmodN2−jkmodN2−jPK=a02jmodN2−jk2−jPK=a0k2−jPK=a0k2−ja0−1G=k2−jG.Thus, we havex2,y2=X=k2−jG=x1,y1. Since r=x1modN and v=x2modN, we can get v=r. This means the verifier could believe and accept the signature Sj=r,sj of message m. Therefore, the construction of the signature is correct.


## 4.1. Parameter Selection

Assuming that the system’s time is divided intoT periods, GFq is a finite field with order q. E:y2=x3+ax+bmodq (a,b∈GFq,4a3+27b2≠0) is an elliptic curve over finite field GFq. G is the base point of the elliptic curve E with order n. That is, ordG=n, where n is a large prime number. N is a composite number (N>n), h=#EGFq/n, and (h≪n) is the cofactor. #EGFq represents the number of points on the elliptic curve E, which is defined on the finite field GFq. H:0,1∗⟶0,1160 is a secure hash algorithm. 0,1∗ represents a string with any length. SK0=a0 (a0∈1,n−1) is the initial private key, and PK=a0−1G is the public key. Then, we keep parameter SK0 secret, expose elliptic curve parameters D=q,a,b,G,n,h, the public key PK, and hash function H·.


## 4.2. Key Update

In thej-th period (1≤j≤T), the signer uses the key SKj−1 of the j−1-th period to calculate the key SKj=SKj−12modN of the j-th period. Therefore, in the j-th period (1≤j≤T), the private key is SKj=a02jmodN, where a02j is precalculated in each period. The key SKj−1 is deleted, and the key SKj is saved in the secret key list.


## 4.3. Signature Generation

The signer calculates the signature of messagem in the j-th (1≤j≤T) period [(1)].
(1)
At first, select a random numberk∈1,n−1(2)
Computek2−jG=x1,y1, r=x1modN. If r=0, return to step (1)(3)
Compute the hash valueej=Hj,m,r(4)
Computesj=SKjk−ejmodN. If sj=0, return to step (1)(5)
Get the signatureSj=r,sj


## 4.4. Signature Verification

The verifier checks whetherr,sj is the signature of message m in the j-th period (1≤j≤T) after receiving the signature r,sj and message m [(1)].
(1)
At first, verifyr,sj∈1,n−1. If not, return directly and reject the signature(2)
Compute the hash valuee′j=Hj,m,r(3)
Computewj=e′j+sjmodN(4)
ComputeX=wj2−jPK=x2,y2. If X=0, reject the signature(5)
Computev=x2modN. If v=r, the verifier accepts the signature. Otherwise, the signature Sj=r,sj will be rejected


## 4.5. Correctness Analysis

IfSj=r,sj is a valid signature for the message m in the j-th period (1≤j≤T), then the hash value is e′j=Hj,m,r=ej. Thus, wj=e′j+sjmodN=ej+sjmodN, it results in the second equal sign in equation. Since the signature component sj=SKjk−ejmodN, it results in the third equal sign in equation. And because of the private key SKj=a02jmodN and public key PK=a0−1G, they result in the fifth and seventh equal signs in equation, respectively. In addition, we recall that the initial private key is SK0=a0 (a0∈1,n−1), where n<N, and we can get a0<N. It results in the sixth equal sign in equation.
(8)X=wj2−jPK=ej+sjmodN2−jPK=SKjkmodN2−jPK=SKjmodN2−jkmodN2−jPK=a02jmodN2−jk2−jPK=a0k2−jPK=a0k2−ja0−1G=k2−jG.Thus, we havex2,y2=X=k2−jG=x1,y1. Since r=x1modN and v=x2modN, we can get v=r. This means the verifier could believe and accept the signature Sj=r,sj of message m. Therefore, the construction of the signature is correct.


## 5. Proof of Security

### 5.1. Unforgeability

Theorem 1.
If the ECDLP problem is difficult, the improved scheme is existentially unforgeable under adaptive chosen-message attack in the ROM.Proof.
Assume that adversaryA breaks the improved scheme with advantage ε, the algorithm B simulates the challenger of A to perform the following operations:
(i)
Setup phase:B sets the number of periods to be T and guesses the signature of the J-th (0≤J≤T) period forged by A. B selects an elliptic curve E over the finite field GFq and selects the base point G (ordG=n) on the elliptic curve E. B selects the hash function H·, and the initial private key a0 calculates a0−1G. B sends the public key a0−1G to A(ii)
Query phase(1)
(Hash query): the hash query is firstly simulated, andB has a hash query list LH, which is initially empty. In the j-th period, m,ej is stored in the list LH. When A performs a hash query of message m, the algorithm B firstly inspects whether m has appeared in the list LH. If so, it returns ej to A directly. Otherwise, B selects ej⟵ℤn∗=1,2,⋯,n−1 at random, stores m,ej in the list LH, and returns ej to A(2)
(Key leakage query):A submits breakinj+ (1≤j+≤T). If j+≤J, B reports failure and aborts. If j+>J, B calculates the key SKJ+1. If j+≠J+1, B performs the KeyUpdate algorithm to generate SKj+, i.e., SKj+⟵Update⋯UpdateSKJ+1. B returns SKj+ to A(3)
(Signature query):A submits j,m (0≤j≤j+). B arbitrarily selects k∈1,n−1 and calculates k2−jG=x1,y1, r=x1modN, ej=Hj,m,r, sj=SKjk−ejmodN. Then, B returns the signature r,sj to A(iii)
Forge phase: if the algorithmB does not abort in the query phase, the adversary A will output a period index j∗(0≤j∗<j+), message m∗, and valid forgery r∗,sj∗ with an advantage of at least ε. If j∗≠J, B reports failure and aborts; otherwise, k=ej+sja0−2jmodN. So, ECDLP problem can be solvedIn the above simulation, ifB guesses the period that A forge the signature, there is j+>J in the key leaks query. That is, B can generate the private key SKj+ without stopping and exiting. B has 1/T probability to guess correctly the period that A forge the signature. Therefore, ε′=ε/T−negln is the minimum probability that the algorithm B successfully solves the ECDLP.


### 5.2. Forward Security

Theorem 2.
Because the quadratic congruence equation of moduloN is difficult, the improved scheme has forward security.Proof.
If the adversary obtains the private key of thej-th period, he cannot use this private key to forge the signature of the j−1-th period. The reasons are as follows.Firstly, if the adversary wants to calculate the keySKj−1 of the j−1-th period by SKj=SKj−12modN, he must solve the quadratic congruence equation of modulo N. The difficulty of this problem is equivalent to the factorization problem.Secondly, if the adversary wants to forge the signaturer,sj−1 of the j−1-th period from sj−1=SKj−1k−ej−1modN, he must know SKj−1. According to the above, the adversary cannot find the private key SKj−1 of the j−1-th period by the private key SKj of the j-th period.We will prove this theorem as follows.Assume that the adversaryO attacks the forward security of the improved scheme, an algorithm D is constructed to solve the quadratic congruence equation by using O as a subroutine. D runs in two phases: the chosen-message-attack (CMA) and the forge. The algorithm has access to the signature oracle and the hash oracle. We make the public key PK=v−2−a+1G be the input of the algorithm D in the CMA phase. Then, we begin running O in the CMA phase and return PK.We choose a numberw∈ZN∗ randomly and let v=w2modN. Then, we choose a value SKj at random. We begin running O for the first time in the CMA phase and return PK. In the CMA phase, O can submit queries to the hash oracle and the signature oracle. Consequently, at the beginning of every period, O stays in the CMA phase, and the algorithm D is running. We randomly pick a value SKj∈ZN. Here, we assume that the key will be revealed in both the previous and current periods if it is revealed at the beginning of the KeyUpdate.
(i)
Query phase is as follows:(1)
(Signature query): we can simulate the signature oracle ofO using our signature oracle easily and also simulate O’s view of the signature algorithm. Assume that message m is queried to the signature oracle from O, we query our signature oracle for the signature r,sj of m and return the signature r,sj to O as the answer of O’s signature queryThen, we simulateO’s view of the signature algorithm. At first, we simulate the generation of k and compute k2−jG=x1,y1 to get r.
(2)
(Hash query): we can simulate the hash oracle ofO using our hash oracle. Suppose j,m,r is queried to the hash oracle from O, we query our hash oracle for the same input and return O the answer(ii)
Forge phase is as follows: suppose in thet-th period, we get into the breakin phase to know the current secret SKt and return SKt to O. Suppose O outputs the forgery m,r,st, we simply return m,r,st and take it as the output of DThe success probability of algorithmD is almost the same as that of adversary O. The only difference is as follows. In the simulation for the signature oracle above, all the values we used come from ZN∗. However, in the real signature oracle, it is possible that some of the values it outputs come from ZN not ZN∗. Because the value k is randomly picked from ZN in the signature phase, the probability that the value does not come from ZN∗ is negligible. If N=pq, the probability is at most p+q/pq=1/q+1/p. Therefore, if qs is the total number of queries that submitted to the signature oracle, qs1/q+1/p is the success probability of the algorithm D exactly.In summary, the improved scheme has forward security.


## 5.1. Unforgeability

Theorem 1.
If the ECDLP problem is difficult, the improved scheme is existentially unforgeable under adaptive chosen-message attack in the ROM.Proof.
Assume that adversaryA breaks the improved scheme with advantage ε, the algorithm B simulates the challenger of A to perform the following operations:
(i)
Setup phase:B sets the number of periods to be T and guesses the signature of the J-th (0≤J≤T) period forged by A. B selects an elliptic curve E over the finite field GFq and selects the base point G (ordG=n) on the elliptic curve E. B selects the hash function H·, and the initial private key a0 calculates a0−1G. B sends the public key a0−1G to A(ii)
Query phase(1)
(Hash query): the hash query is firstly simulated, andB has a hash query list LH, which is initially empty. In the j-th period, m,ej is stored in the list LH. When A performs a hash query of message m, the algorithm B firstly inspects whether m has appeared in the list LH. If so, it returns ej to A directly. Otherwise, B selects ej⟵ℤn∗=1,2,⋯,n−1 at random, stores m,ej in the list LH, and returns ej to A(2)
(Key leakage query):A submits breakinj+ (1≤j+≤T). If j+≤J, B reports failure and aborts. If j+>J, B calculates the key SKJ+1. If j+≠J+1, B performs the KeyUpdate algorithm to generate SKj+, i.e., SKj+⟵Update⋯UpdateSKJ+1. B returns SKj+ to A(3)
(Signature query):A submits j,m (0≤j≤j+). B arbitrarily selects k∈1,n−1 and calculates k2−jG=x1,y1, r=x1modN, ej=Hj,m,r, sj=SKjk−ejmodN. Then, B returns the signature r,sj to A(iii)
Forge phase: if the algorithmB does not abort in the query phase, the adversary A will output a period index j∗(0≤j∗<j+), message m∗, and valid forgery r∗,sj∗ with an advantage of at least ε. If j∗≠J, B reports failure and aborts; otherwise, k=ej+sja0−2jmodN. So, ECDLP problem can be solvedIn the above simulation, ifB guesses the period that A forge the signature, there is j+>J in the key leaks query. That is, B can generate the private key SKj+ without stopping and exiting. B has 1/T probability to guess correctly the period that A forge the signature. Therefore, ε′=ε/T−negln is the minimum probability that the algorithm B successfully solves the ECDLP.


## 5.2. Forward Security

Theorem 2.
Because the quadratic congruence equation of moduloN is difficult, the improved scheme has forward security.Proof.
If the adversary obtains the private key of thej-th period, he cannot use this private key to forge the signature of the j−1-th period. The reasons are as follows.Firstly, if the adversary wants to calculate the keySKj−1 of the j−1-th period by SKj=SKj−12modN, he must solve the quadratic congruence equation of modulo N. The difficulty of this problem is equivalent to the factorization problem.Secondly, if the adversary wants to forge the signaturer,sj−1 of the j−1-th period from sj−1=SKj−1k−ej−1modN, he must know SKj−1. According to the above, the adversary cannot find the private key SKj−1 of the j−1-th period by the private key SKj of the j-th period.We will prove this theorem as follows.Assume that the adversaryO attacks the forward security of the improved scheme, an algorithm D is constructed to solve the quadratic congruence equation by using O as a subroutine. D runs in two phases: the chosen-message-attack (CMA) and the forge. The algorithm has access to the signature oracle and the hash oracle. We make the public key PK=v−2−a+1G be the input of the algorithm D in the CMA phase. Then, we begin running O in the CMA phase and return PK.We choose a numberw∈ZN∗ randomly and let v=w2modN. Then, we choose a value SKj at random. We begin running O for the first time in the CMA phase and return PK. In the CMA phase, O can submit queries to the hash oracle and the signature oracle. Consequently, at the beginning of every period, O stays in the CMA phase, and the algorithm D is running. We randomly pick a value SKj∈ZN. Here, we assume that the key will be revealed in both the previous and current periods if it is revealed at the beginning of the KeyUpdate.
(i)
Query phase is as follows:(1)
(Signature query): we can simulate the signature oracle ofO using our signature oracle easily and also simulate O’s view of the signature algorithm. Assume that message m is queried to the signature oracle from O, we query our signature oracle for the signature r,sj of m and return the signature r,sj to O as the answer of O’s signature queryThen, we simulateO’s view of the signature algorithm. At first, we simulate the generation of k and compute k2−jG=x1,y1 to get r.
(2)
(Hash query): we can simulate the hash oracle ofO using our hash oracle. Suppose j,m,r is queried to the hash oracle from O, we query our hash oracle for the same input and return O the answer(ii)
Forge phase is as follows: suppose in thet-th period, we get into the breakin phase to know the current secret SKt and return SKt to O. Suppose O outputs the forgery m,r,st, we simply return m,r,st and take it as the output of DThe success probability of algorithmD is almost the same as that of adversary O. The only difference is as follows. In the simulation for the signature oracle above, all the values we used come from ZN∗. However, in the real signature oracle, it is possible that some of the values it outputs come from ZN not ZN∗. Because the value k is randomly picked from ZN in the signature phase, the probability that the value does not come from ZN∗ is negligible. If N=pq, the probability is at most p+q/pq=1/q+1/p. Therefore, if qs is the total number of queries that submitted to the signature oracle, qs1/q+1/p is the success probability of the algorithm D exactly.In summary, the improved scheme has forward security.


## 6. Efficiency Analysis

The wireless communication network is a restricted environment, i.e., time (key generation, signature and verification, etc.) and space (data memory, program memory, bandwidth, code and data length, etc.) limit the achievement of security goals. In addition, wireless devices have relatively low computing power and relatively small storage space. This requires that the digital signature scheme used in wireless communication network should be as efficient as possible while ensuring security. In this section, we analyze the efficiency of signature generation algorithm and signature verification algorithm.We compare the calculation amount of the improved scheme with the ECDSA scheme, the Huiyan scheme [38], the Keyuan scheme [29], and the Jinyuan scheme [32]. The latter three also have forward security. The comparison results are shown in Table 1. In this table, “DP” represents the double-point arithmetic, “MM” represents the modular multiplication, and “MI” represents the modular inversion.Table 1
Comparison of the computational complexity of the five schemes.
Signature generationSignature verificationDPMMMIDPMMMIImproved scheme110100ECDSA scheme121221Huiyan scheme120111Keyuan scheme431030Jinyuan scheme230211Assuming that the data scale of one modular multiplication ist, the complexity of one double-point arithmetic is Ot2, the complexity of one modular inversion is O9t2, and the complexity of one modular multiplication is Ot2log2t[39]. According to Table 1, the total computational complexity of the improved scheme is N1=Olog2n+2n2, the total computational complexity of the ECDSA scheme is N2=O4log2n+21n2, the total computational complexity of the Huiyan scheme is N3=O3log2n+11n2, the total computational complexity of the Keyuan scheme is N4=O6log2n+13n2, and the total computational complexity of the Jinyuan scheme is N5=O4log2n+13n2. The total computational complexity of the five schemes is shown in Figure 1.Figure 1
The total computational complexity of the five schemes.Modular multiplication and modular inversion are the main arithmetic that affects the total computational complexity. In the signature generation algorithm and signature verification algorithm, the improved scheme has one double-point arithmetic, three modular multiplications, and two modular inversions less than the ECDSA scheme. Besides, according to Figure1, compared with the ECDSA scheme and other three schemes, the total computational complexity of the improved scheme is much smaller.


## 7. Conclusion

The potential security risks of wireless networks pose a serious threat to users’ information security. Digital signature is the key technology for privacy protection in wireless communication network. However, the existing ECDSA scheme is computationally complex and does not have forward security. Aiming at the security problems of wireless communication network and the shortcomings of ECDSA scheme, we constructed an improved scheme and proved the security of the scheme. Compared with the ECDSA scheme and three existing forward secure schemes, our scheme not only meets the forward security but also reduces the requirement of computing power of the user in the wireless network. Therefore, our improved scheme is more suitable for wireless communication network. With its high security and high efficiency, our improved scheme can be widely applied to the scenarios involving privacy protection in wireless communication network. However, how to deploy our improved scheme to the application scenarios of wireless communication network will be our future work.



---

*Source: 1977798-2022-04-13.xml*