# Practical SM2-Based Multisignature Scheme with Applications to Vehicular Networks

Authors: Lin Hou; Wei Liu; Lisha Yao; Xiaojian Liang; Guo-Qiang Zeng
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In vehicular networks, the increasing value of transportation data and scale of connectivity also brings many security and privacy concerns. Peer authentication and message integrity are two vital security requirements to ensure safe transportation system. Because of the constrained resources of the units performing the cryptographic components, the proposed security-enhancing schemes should be lightweight and scalable. In this paper, we present a multisignature scheme derived from the SM2 signature which enables a group of parties to collaboratively sign a message and generate a compact joint signature at the end. Our scheme requires no preprocessing or interactions among the parties before signing, and its performance matches or surpasses known ones in terms of signing time, verification time, and signature size. Therefore, our scheme is also suitable for vehicular networks, with the goal to enhance security with small computation and storage cost.


---

## Body

## 1. Introduction

With the development of advanced information and communication-based technologies, intelligent transportation system (ITS) can provide a seamless transportation infrastructure and more functionalities for vehicles than a decade ago. Specifically, the Vehicle-to-Everything (V2X) communication technology in vehicular networks nowadays is able to support information sharing between vehicles and any other element involved in ITS [1, 2], including nearby vehicles (V2V), the infrastructure (V2I), mobile devices carried by pedestrians (V2P), and remote application servers or cloud platforms (V2N). The increasing scale of ITS ecosystem and the growing trend to integrate vehicular network deployment with other networks also bring concerns about cybersecurity for ITS since any message interception or modification by malicious units could result in fatal consequences [3, 4].Digital signature is commonly used in vehicular networks to ensure integrity of messages exchanged among devices. However, the effectiveness of information propagation and routing, which are associated to delays and hence also have impacts on road safety, naturally depends on the computational overhead imposed by the applied security mechanisms [5]. Beyond traditional signature schemes, multisignature (MS) and aggregate signature (AS) are extended primitives considering multiuser setting to support cosigning and to reduce verification cost. The two primitives in common allow a group of signers to combine their individual signatures into a single short one. Specifically, an MS scheme [6, 7] enables a group of signers, each having a public key and a corresponding private key, to collaboratively produce a joint signature on a common message which can be publicly verified given the set of public keys of all signers. As a more general primitive, an AS scheme [8, 9] allows each of the signers to sign a different message, and all these individual signatures can still be aggregated into a single short one. As in the traditional signature scheme, the short combined signature should convince the verifier that all signers signed their designated messages.Both MS and AS schemes have many potential uses in vehicular networks, such as in the distributed certificate authority (CA) or in V2I/V2V communications. Unfortunately, the commonly used technologies including dedicated short-range communications (DSRC) and cellular-V2X (C-V2X) mainly exploit elliptic curve-based signature schemes, e.g., ECDSA and SM2, which to the best of our knowledge has very few MS or AS extensions due to their nonlinear construction.In this paper, we propose a candidate multisignature schemeMS−SM2 based on the SM2 signature algorithm and specify the applications of MS−SM2 for vehicular networks. SM2 is a signature algorithm standard based on the elliptic curve published by the Chinese government and has been extensively used in cryptographic devices in finance and industry. Our proposed MS−SM2 scheme allows dynamic joining of signers (with certified public keys) and has no burdensome assumptions on the public-key infrastructure (PKI), which makes it plausible in vehicular networks.


### 1.1. Our Contributions

The original contribution of this work is mainly twofold:(i)
We first present a multisignature schemeMS−SM2 based on the SM2 signature by designing a cosigning protocol and prove its security in plain public-key and semihonest model. No preprocessing or any proof-of-knowledge step on the signer side is required in our scheme. The experimental results also show that our protocol is relatively practical for many applications.(ii)
We then illustrate some possible applications ofMS−SM2 in vehicular networks, especially the usage in the multiple CAs architecture to reduce the certification storage for vehicles and RSUs and in V2I communication to reduce the computational overhead for RSUs.


### 1.2. Related Work

A trivial way to build a multisignature from standard signatures is to concatenate all stand-alone signatures signed individually. However, the resulted multisignature is of large size and particularly of size proportional to the number of signers, which does not scale well in practice [6, 7, 10]. Therefore, a multisignature should be short, meaning its length should be (ideally) independent from the number of signers and about the same as that of an ordinary stand-alone signature. Informally, the possibility of extending standard signature schemes to multisignatures comes from the homomorphism of the involved arithmetic operations of the underlying assumptions. However, the homomorphism also brings a serious vulnerability and allows adversaries to mount rogue key attacks, in which the attackers without valid key pairs can set its public key as a function of those from other honest signers and finally forge multisignatures. Micali et al. [6] described the formal model for the attack and showed a way to prevent such attacks known as knowledge of secret key (KOSK) assumption, in which users are required to prove knowledge of their secret keys during public key registration. Bellare and Neven [7] proposed a new practical multisignature scheme based on the Schnorr signature without KOSK assumption and proved that it can avoid rogue attack in the so-called plain public key model. There are several following-up work on constructing 2-round Schnorr-based multisignatures, i.e., all singers only need 2 rounds of communications to produce a multisignature [11–15]. Recently, public key aggregation is introduced to a multisignature scheme by which the verifier can check the validity of a multisignature only using a short aggregate key rather than a public key list [16, 17].


## 1.1. Our Contributions

The original contribution of this work is mainly twofold:(i)
We first present a multisignature schemeMS−SM2 based on the SM2 signature by designing a cosigning protocol and prove its security in plain public-key and semihonest model. No preprocessing or any proof-of-knowledge step on the signer side is required in our scheme. The experimental results also show that our protocol is relatively practical for many applications.(ii)
We then illustrate some possible applications ofMS−SM2 in vehicular networks, especially the usage in the multiple CAs architecture to reduce the certification storage for vehicles and RSUs and in V2I communication to reduce the computational overhead for RSUs.


## 1.2. Related Work

A trivial way to build a multisignature from standard signatures is to concatenate all stand-alone signatures signed individually. However, the resulted multisignature is of large size and particularly of size proportional to the number of signers, which does not scale well in practice [6, 7, 10]. Therefore, a multisignature should be short, meaning its length should be (ideally) independent from the number of signers and about the same as that of an ordinary stand-alone signature. Informally, the possibility of extending standard signature schemes to multisignatures comes from the homomorphism of the involved arithmetic operations of the underlying assumptions. However, the homomorphism also brings a serious vulnerability and allows adversaries to mount rogue key attacks, in which the attackers without valid key pairs can set its public key as a function of those from other honest signers and finally forge multisignatures. Micali et al. [6] described the formal model for the attack and showed a way to prevent such attacks known as knowledge of secret key (KOSK) assumption, in which users are required to prove knowledge of their secret keys during public key registration. Bellare and Neven [7] proposed a new practical multisignature scheme based on the Schnorr signature without KOSK assumption and proved that it can avoid rogue attack in the so-called plain public key model. There are several following-up work on constructing 2-round Schnorr-based multisignatures, i.e., all singers only need 2 rounds of communications to produce a multisignature [11–15]. Recently, public key aggregation is introduced to a multisignature scheme by which the verifier can check the validity of a multisignature only using a short aggregate key rather than a public key list [16, 17].


## 2. Preliminaries

For prime numberp, ℤp denotes the additive group of integer modulo p. We consider elliptic curve E:y2=x3+ax+bmodp in ℤp, where a,b∈ℤp and 4a3+27b2≠0modp. The set of points on E along with the infinity point O constitutes an additive elliptic-curve group Eℤp under points addition, denoted by ⊕, with O being the identity. Let GxG,yG∈EℤpG≠O be the base point in Eℤp with order n. For k∈ℤ, QxQ,yQ=kG denotes the scalar multiplication in Eℤp.Rangex,y denotes the set of integers i, x≤i≤y. Given a nonempty set S, s⟵$S denotes the operation of sampling an element of S uniformly at random and assigning it to s. For a randomized algorithm A, y⟵Ax1,…,xn;ρ denotes the operation of running A on inputs x1,…,xn and random coins ρ then assigning its output to y.


### 2.1. Multisignature Scheme

#### 2.1.1. Syntax

We follow the description of Bellare and Neven [7] and define a multisignature scheme as a tuple MS=Setup,KeyGen,MSign,Vrfy. Note that the scheme is defined in the plain public key model, where the key generation is as same as that in any public-key cryptography and no more preprocessing protocol or key verification is required.Setup1κ⟶pp: the setup algorithm takes as input the security parameter κ and generates system parameters pp.KeyGenpp⟶sk,pk: the key generation algorithm is a randomized algorithm executed by every signer on input pp to generate a key pair sk,pk.MSignpp,L,ski,m⟶σ: the MSign algorithm represents the signing protocol run by a group of signers who intend to collaboratively sign the same message m. Each signer i executes the protocol on input pp, a set of public keys of signers L=pk1,…,pkN, private key ski and message m. The protocol outputs a multisignature σ.Vrfypp,L,m,σ⟶0/1: the verification algorithm checks the validity of a multisignature σ on message m on behalf of the group of signers whose public keys are in set L and output 1 or 0 indicating the multisignature is valid or not.


#### 2.1.2. Completeness

A multisignature scheme should satisfy the followingcompleteness property, meaning that for any number n and message m, if pki,ski←Key Genpp for i∈1,…,N and all signers run MSignpp,L,m,ski, then every signer will output the same signature σ such that Vrfypp,L,m,σ=1.


#### 2.1.3. Security

The security of multisignature requires that it is infeasible to forge a signature involving at least one honest signer. We assume an adversary (forger)ℱ that corrupts all other signers except the honest one and can choose their public keys in arbitrary ways as it likes, e.g., the rogue key attack. The unforgeability of multisignature in plain public key model is defined by the following three-phase game ExpMSUF−CMAℱ between the forger ℱ and a challenger.Setup. The challenger generates system parameter pp←Setup1κ and a challenge key pair pk∗,sk∗←KeyGenpp for the target honest signer. It returns pp,pk∗ to ℱ.Query. The forger ℱ is allowed to make signature queries on any message m for any set L of signers with pk∗∈L. This signing oracle Opp,⋅,sk∗,⋅ simulates the honest signer with key sk∗ interacting in a signing protocol with other signers in list L. ℱ can make any number of such queries concurrently.Forge. ℱ outputs a set L∗ of public keys, a message m∗, and a multisignature σ∗. The forger is said to win the game if Vrfypp,L∗,m∗,σ∗=1 with pk∗∈L∗ and the message m∗ never appeared in Query phase.The advantage of forgerℱ in breaking the multisignature scheme is defined as the probability that ℱ wins the above game (over the random coins of the challenger), denoted as AdvMSUF−CMAℱ.Definition 1.
(UF-CMA security). A multisignature scheme ist,qs,N,ε-unforgeable if it holds that AdvMSUF−CMAℱ≤ε for every forger ℱ that runs in time at most t, makes at most qs signing queries, produces forgeries on behalf of N parties, and wins the ExpMSUF−CMAℱ game with negligible probability ε. In random oracle model, we define it as t,qs,qh,N,ε-unforgeable where qh denotes the maximum number of hash queries.


### 2.2. SM2 Signature Algorithm

The SM2 signature algorithm is initialized by taking as input a security parameterκ and outputs ppEℤp,O,G,n,H⋅ as public parameters, in which H:0,1∗⟶ℤn is a cryptography hash function. The SM2 signature scheme is briefly reviewed in Table 1.Table 1
SM2 signature algorithm.
Key GenerationSigningVerificationFor userj, it generatesTo sign messageM, j computesTo verifyM′,σ′ with Pj,sk: dj←$1,n−21.e=HZjM1. Ifr′,s′∉1,n−1,pk: Pj=djG2.k←$1,n−1Return REJECTZj: public hash bits of user3.x1,y1=kG2.e′=HZjM′j’s information including pk4.r=e+x1modn;3.t=r′+s′modnIfr=0 or r+k=n, go to Step 2Ift=0, return REJECT5.s=1+dj−1k−r⋅djmodn;4.x1′,y1′=s1′G+tPjIfs=0, go to Step 25. Ifr1′=e1′+x1′modn,6. Return signatureσ=r,sReturn REJECTElseReturn ACCEPT


### 2.3. General Forking Lemma

We will use the general forking lemma [7] to prove the security of our scheme, which is a useful tool by extending the forking lemma of Pointcheval and Stern [18] without mentioning concrete signatures or random oracles.Lemma 1 (general forking lemma).
LetH be a set of size h≥2, and h1,…,hq←$H. Let A be a randomized algorithm that on input x,h1,…,hq returns a pair i,σ, where i∈0,…,q and σ is a side output. For some randomized input generator IG, the accepting probability of algorithm A, denoted by acc, is defined as Pri≥1||x←$IG;h1,…,hq←$H;i,σ←$Ax,h1,…,hq. Consider randomized algorithm ForkA associated with A, taking as input x, proceeds as described in Algorithm 1. Let frk be the probability that Prb=1|x←$IG;b,σ,σ′←$ForkAx. Then,(1)frk≥accaccq−1h.Algorithm 1: The forking algorithm ForkA.
(1)
Select random coinsρ for A(2)
h1,…,hq←$0,1ℓ;(3)
i,σ←Ax,h1,…,hq;ρ;(4)
ifi=0 then(5)
return0,ε,ε;(6)
end(7)
hi′,…,hq′←$0,1ℓ;(8)
i′,σ′←Ax,h1,…,hi−1,hi′,…,hq′;ρ;(9)
if (i=i′ and hi≠hi′) then(10)
return1,σ,σ′(11)
else(12)
return0,ε,ε′(13)
end


### 2.4. Secure Multiparty Computation

Secure multiparty computation (MPC) enables a group to jointly perform a computation without disclosing any participant’s private inputs. The participants agree on a function to compute and then can use an MPC protocol to jointly compute the output of that function on their secret inputs without revealing them [19]. There are several well-studied MPC protocols such as the GMW protocol [20] and the BGW protocol [21]. Both of the two schemes are based on the secret-sharing technique and can support both Boolean circuit and arithmetic circuit.Here, we only present the general idea of a simple addition function to show how the protocols work. The basic idea is to allow each party holding the secret shares of the inputs; therefore, each party can locally sum up their shares and get a valid sharing of the final result. We describe it in a bit more detail in Figure1.Figure 1
The MPC protocol for additionℱadd.


## 2.1. Multisignature Scheme

### 2.1.1. Syntax

We follow the description of Bellare and Neven [7] and define a multisignature scheme as a tuple MS=Setup,KeyGen,MSign,Vrfy. Note that the scheme is defined in the plain public key model, where the key generation is as same as that in any public-key cryptography and no more preprocessing protocol or key verification is required.Setup1κ⟶pp: the setup algorithm takes as input the security parameter κ and generates system parameters pp.KeyGenpp⟶sk,pk: the key generation algorithm is a randomized algorithm executed by every signer on input pp to generate a key pair sk,pk.MSignpp,L,ski,m⟶σ: the MSign algorithm represents the signing protocol run by a group of signers who intend to collaboratively sign the same message m. Each signer i executes the protocol on input pp, a set of public keys of signers L=pk1,…,pkN, private key ski and message m. The protocol outputs a multisignature σ.Vrfypp,L,m,σ⟶0/1: the verification algorithm checks the validity of a multisignature σ on message m on behalf of the group of signers whose public keys are in set L and output 1 or 0 indicating the multisignature is valid or not.


### 2.1.2. Completeness

A multisignature scheme should satisfy the followingcompleteness property, meaning that for any number n and message m, if pki,ski←Key Genpp for i∈1,…,N and all signers run MSignpp,L,m,ski, then every signer will output the same signature σ such that Vrfypp,L,m,σ=1.


### 2.1.3. Security

The security of multisignature requires that it is infeasible to forge a signature involving at least one honest signer. We assume an adversary (forger)ℱ that corrupts all other signers except the honest one and can choose their public keys in arbitrary ways as it likes, e.g., the rogue key attack. The unforgeability of multisignature in plain public key model is defined by the following three-phase game ExpMSUF−CMAℱ between the forger ℱ and a challenger.Setup. The challenger generates system parameter pp←Setup1κ and a challenge key pair pk∗,sk∗←KeyGenpp for the target honest signer. It returns pp,pk∗ to ℱ.Query. The forger ℱ is allowed to make signature queries on any message m for any set L of signers with pk∗∈L. This signing oracle Opp,⋅,sk∗,⋅ simulates the honest signer with key sk∗ interacting in a signing protocol with other signers in list L. ℱ can make any number of such queries concurrently.Forge. ℱ outputs a set L∗ of public keys, a message m∗, and a multisignature σ∗. The forger is said to win the game if Vrfypp,L∗,m∗,σ∗=1 with pk∗∈L∗ and the message m∗ never appeared in Query phase.The advantage of forgerℱ in breaking the multisignature scheme is defined as the probability that ℱ wins the above game (over the random coins of the challenger), denoted as AdvMSUF−CMAℱ.Definition 1.
(UF-CMA security). A multisignature scheme ist,qs,N,ε-unforgeable if it holds that AdvMSUF−CMAℱ≤ε for every forger ℱ that runs in time at most t, makes at most qs signing queries, produces forgeries on behalf of N parties, and wins the ExpMSUF−CMAℱ game with negligible probability ε. In random oracle model, we define it as t,qs,qh,N,ε-unforgeable where qh denotes the maximum number of hash queries.


## 2.1.1. Syntax

We follow the description of Bellare and Neven [7] and define a multisignature scheme as a tuple MS=Setup,KeyGen,MSign,Vrfy. Note that the scheme is defined in the plain public key model, where the key generation is as same as that in any public-key cryptography and no more preprocessing protocol or key verification is required.Setup1κ⟶pp: the setup algorithm takes as input the security parameter κ and generates system parameters pp.KeyGenpp⟶sk,pk: the key generation algorithm is a randomized algorithm executed by every signer on input pp to generate a key pair sk,pk.MSignpp,L,ski,m⟶σ: the MSign algorithm represents the signing protocol run by a group of signers who intend to collaboratively sign the same message m. Each signer i executes the protocol on input pp, a set of public keys of signers L=pk1,…,pkN, private key ski and message m. The protocol outputs a multisignature σ.Vrfypp,L,m,σ⟶0/1: the verification algorithm checks the validity of a multisignature σ on message m on behalf of the group of signers whose public keys are in set L and output 1 or 0 indicating the multisignature is valid or not.


## 2.1.2. Completeness

A multisignature scheme should satisfy the followingcompleteness property, meaning that for any number n and message m, if pki,ski←Key Genpp for i∈1,…,N and all signers run MSignpp,L,m,ski, then every signer will output the same signature σ such that Vrfypp,L,m,σ=1.


## 2.1.3. Security

The security of multisignature requires that it is infeasible to forge a signature involving at least one honest signer. We assume an adversary (forger)ℱ that corrupts all other signers except the honest one and can choose their public keys in arbitrary ways as it likes, e.g., the rogue key attack. The unforgeability of multisignature in plain public key model is defined by the following three-phase game ExpMSUF−CMAℱ between the forger ℱ and a challenger.Setup. The challenger generates system parameter pp←Setup1κ and a challenge key pair pk∗,sk∗←KeyGenpp for the target honest signer. It returns pp,pk∗ to ℱ.Query. The forger ℱ is allowed to make signature queries on any message m for any set L of signers with pk∗∈L. This signing oracle Opp,⋅,sk∗,⋅ simulates the honest signer with key sk∗ interacting in a signing protocol with other signers in list L. ℱ can make any number of such queries concurrently.Forge. ℱ outputs a set L∗ of public keys, a message m∗, and a multisignature σ∗. The forger is said to win the game if Vrfypp,L∗,m∗,σ∗=1 with pk∗∈L∗ and the message m∗ never appeared in Query phase.The advantage of forgerℱ in breaking the multisignature scheme is defined as the probability that ℱ wins the above game (over the random coins of the challenger), denoted as AdvMSUF−CMAℱ.Definition 1.
(UF-CMA security). A multisignature scheme ist,qs,N,ε-unforgeable if it holds that AdvMSUF−CMAℱ≤ε for every forger ℱ that runs in time at most t, makes at most qs signing queries, produces forgeries on behalf of N parties, and wins the ExpMSUF−CMAℱ game with negligible probability ε. In random oracle model, we define it as t,qs,qh,N,ε-unforgeable where qh denotes the maximum number of hash queries.


## 2.2. SM2 Signature Algorithm

The SM2 signature algorithm is initialized by taking as input a security parameterκ and outputs ppEℤp,O,G,n,H⋅ as public parameters, in which H:0,1∗⟶ℤn is a cryptography hash function. The SM2 signature scheme is briefly reviewed in Table 1.Table 1
SM2 signature algorithm.
Key GenerationSigningVerificationFor userj, it generatesTo sign messageM, j computesTo verifyM′,σ′ with Pj,sk: dj←$1,n−21.e=HZjM1. Ifr′,s′∉1,n−1,pk: Pj=djG2.k←$1,n−1Return REJECTZj: public hash bits of user3.x1,y1=kG2.e′=HZjM′j’s information including pk4.r=e+x1modn;3.t=r′+s′modnIfr=0 or r+k=n, go to Step 2Ift=0, return REJECT5.s=1+dj−1k−r⋅djmodn;4.x1′,y1′=s1′G+tPjIfs=0, go to Step 25. Ifr1′=e1′+x1′modn,6. Return signatureσ=r,sReturn REJECTElseReturn ACCEPT


## 2.3. General Forking Lemma

We will use the general forking lemma [7] to prove the security of our scheme, which is a useful tool by extending the forking lemma of Pointcheval and Stern [18] without mentioning concrete signatures or random oracles.Lemma 1 (general forking lemma).
LetH be a set of size h≥2, and h1,…,hq←$H. Let A be a randomized algorithm that on input x,h1,…,hq returns a pair i,σ, where i∈0,…,q and σ is a side output. For some randomized input generator IG, the accepting probability of algorithm A, denoted by acc, is defined as Pri≥1||x←$IG;h1,…,hq←$H;i,σ←$Ax,h1,…,hq. Consider randomized algorithm ForkA associated with A, taking as input x, proceeds as described in Algorithm 1. Let frk be the probability that Prb=1|x←$IG;b,σ,σ′←$ForkAx. Then,(1)frk≥accaccq−1h.Algorithm 1: The forking algorithm ForkA.
(1)
Select random coinsρ for A(2)
h1,…,hq←$0,1ℓ;(3)
i,σ←Ax,h1,…,hq;ρ;(4)
ifi=0 then(5)
return0,ε,ε;(6)
end(7)
hi′,…,hq′←$0,1ℓ;(8)
i′,σ′←Ax,h1,…,hi−1,hi′,…,hq′;ρ;(9)
if (i=i′ and hi≠hi′) then(10)
return1,σ,σ′(11)
else(12)
return0,ε,ε′(13)
end


## 2.4. Secure Multiparty Computation

Secure multiparty computation (MPC) enables a group to jointly perform a computation without disclosing any participant’s private inputs. The participants agree on a function to compute and then can use an MPC protocol to jointly compute the output of that function on their secret inputs without revealing them [19]. There are several well-studied MPC protocols such as the GMW protocol [20] and the BGW protocol [21]. Both of the two schemes are based on the secret-sharing technique and can support both Boolean circuit and arithmetic circuit.Here, we only present the general idea of a simple addition function to show how the protocols work. The basic idea is to allow each party holding the secret shares of the inputs; therefore, each party can locally sum up their shares and get a valid sharing of the final result. We describe it in a bit more detail in Figure1.Figure 1
The MPC protocol for additionℱadd.


## 3. SM2-Based Multisignature Scheme:MS−SM2

In this section, we present a multisignature scheme based on the SM2 signature in the plain public key model. Intuitively, the original signing algorithm of SM2 involves a nonlinear combination of secret key and randomness; therefore, it is nontrivial to extend it directly to a multisignature. To cope with the problem, in the protocol, we first exploit the linear part in SM2 to produce a semiaggregated signature and then employ a simple MPC protocol for addition to finally achieve the goal. Note that we slightly modify the output of original SM2 signing algorithm in protocol where we take the inverse ofs instead to be the part of signature by each party. Therefore, the multisignature in our scheme is almost of the same structure as the original SM2 signature and remains practical. The unforgeability of the multisignature under chosen message attack can be proved in the random oracle model using general forking lemma [7, 16].


### 3.1. Construction

The initializationSetup algorithm and KeyGen algorithm of the multisignature are almost the same as that in the SM2 scheme, except that there are two hash functions used in multisignature scheme, denoted as H0:Eℤp⟶ℤn,H1:0,1∗⟶ℤn. We now proceed to describe the signing protocol and verification algorithm of the MS−SM2 scheme. Note that we take L to be size of N for simplicity, where N is the maximum number of cosigners and N≪n.MSignpp,L,m,ski: each signer i with secret key ski=di and public key pki=Pi in set L runs an interactive protocol to collaboratively sign a message m. The communication proceeds in a number of rounds, where in each round, every signer sends and receives messages to and from other signers and also performs some local computation.(1)
Chooseki←$1,n−1, compute Kixi,1,yi,1=kiG and ti=H0xi,1,yi,1, and broadcast ti.(2)
Upon receivingtj from all other signers, broadcast Kixi,1,yi,1.(3)
Upon receivingxj,1,yj,1 from all other signers, check the hash values and abort the protocol if for any j that tj≠H0xj,1,yj,1. Otherwise, set ei=H1Zi‖L‖ii=1NKi‖m, ri=ei+xi,1modn, and si˜=ki−ri⋅dimodn. Then, broadcast si˜.(4)
Upon receivingsj˜ from all other signers, compute s˜=∑i=1Ns˜modn and run the protocol for ℱadd with input si=1+di⋅s˜−1modn to get the addition s=∑i=1Nsimodn.At the end the interactive protocol, the algorithm outputs a multisignatureσ=K,s, where K is the set of all points Kixi,1,yi,1.Vrfypp,L,m,σ: given a multiset of public keys L, message m, and multisignature σ, the verifier computes ei=H1Zi‖L‖ii=1NKi‖m and ri=ei+xi,1modn, accepts the signature if s⊕i=1NKi−s⊕i=1NriPi=NG+⊕i=1NPi, and outputs 1. Otherwise, it outputs 0.Correctness: ifσ=K,s is a valid output of protocol, Vrfy algorithm always accepts and outputs 1. The equation only holds when all signers follow the protocol and use valid key pairs. Note that the integer computations are all modulo n, and we omit the notation for simplicity.(2)s⊕i=1NKi−s⊕i=1NriPi=s∑i=1NkiG−s∑i=1Nri⋅diG=s⋅∑i=1Nki−∑i=1Nri⋅diG=∑i=1Nsi⋅∑i=1Nsi˜G=∑i=1N1+di⋅s˜−1⋅s˜G=∑i=1N1+diG=NG+⊕i=1NPi.


### 3.2. Security Proof

In general, we can treat the multisignature scheme as a multiparty computation protocol and prove its security in simulation-based framework for a clearer security guarantee. Unfortunately, the security of multisignature is traditionally defined in game-based framework, and on the other hand, simulation-based proof is complex in the random oracle model. Here, we follow the game-based definition of Bellare and Neven [7] and only show a proof sketch for the scheme.The basic idea of game-based proof is to obtain fromℱ two different forgeries σ and σ′ with the same randomness by employing the general forking lemma. As a result, we can extract the secret key from the target public key pk∗, which is usually a solution of the discrete-logarithm problem in the elliptic-curve group Eℤp. For simplification, we take an equivalent verification equation into consideration, and if σ=K,s and σ′=K,s′ satisfy (3)⊕i=1NKi−⊕i=1NriPi=s−1NG+s−1⊕i=1NPi,⊕i=1NKi−⊕i=1NriPi=s−1NG+s−1⊕i=1NPi,then the secret key d∗ corresponding to pk∗ can be computed from the equation(4)∑i=1Nri′−ridi=s−1−s′−1N−∑i=1Ndi.However, in the process ofMSign, each signer can check the value s˜ before continuing to execute the protocol, which allows signers to quit cosigning immediately if there is any rogue key attack. Specifically, they can compute x1′,y1′=s˜G+∑i=1NriPi and check if x1′ is equal to the corresponding part in the result.(5)s˜G+∑i=1NriPi=∑i=1Nsi˜G+∑i=1Nri⋅diG=∑i=1Nki−ri⋅diG+∑i=1Nri⋅diG=∑i=1NkiG=⊕i=1Nxi,1,yi,1.Therefore, we can let the simulator halt if the forger successfully forgeds˜.Lemma 2.
If there exists at,qs,qh,N,ε-forger ℱ′ that can output a forgery s˜, then there exists a PPT algorithm A which t′,ε′-solves the DL problem in Eℤp.Proof.
Note thats˜=∑i=1Nsi˜modn and each si˜ has similar structure with Schnorr signature. Therefore, the proof of Lemma 2 is similar to that of the MS−BN scheme. Generally, given a t,qs,qh,N,ε-forger ℱ′, we first wrap it into an algorithm ℬ that can be used in the general forking lemma. We then describe an algorithm A that on input pk∗=P∗ and runs Forkℬpk∗ to output the corresponding discrete logarithm.Letq=qh+qs, T0⋅,T1⋅ be the programmed hash tables for oracles H0andH1, respectively, and h1h1,1,…,h1,q be the answers of queries to H1. Two counters ctr1 and ctr2 are initialized to zero. An additional array T2⋅ records a unique index 1≤i≤qh+Nqs to each public key Pi occurring either as a cosigner’s public key in signature queries or H1 queries, where T2P∗=0. On input pp,h1,P∗∈Eℤp, ℬ plays the ExpMSUF−CMAℱ game with ℱ′ with the target public key pk∗=P∗. ℬ answers queries from ℱ′ by programming the oracles as follows:(i)
H0Ki: if H0Ki is undefined, then ℬ randomly assigns T0Ki←$ℤn and then returns ti=T0Ki.(ii)
H1Zi‖L‖ii=1NKi‖m: if T2Pi is undefined, then ℬ increments ctr2 and sets T2Pi=ctr2. Let k=T2Pi; if T1k,L‖ii=1NKi‖m has not yet been defined, then ℬ assigns random values to all T1j,L‖ii=1NKi‖m for 1≤j≤qh+Nqs, increases ctr1, and assigns T10,L‖⊕i=1NKi‖m=h1,ctr1.(iii)
OsignL,m: if P∗∉L, then ℬ returns ⊥ to the forger. Otherwise, it parses L as P∗,P2,…,PN. ℬ first checks whether T2Pi2≤i≤N has already been defined, if not it increases ctr2 and sets T2Pi=ctr2. Then, it increases counter ctr1 and sets e1=h1,ctr1. It chooses s1˜←$ℤn and computes a elliptic curve point K1 such that K1x1,1,y1,1=s1˜G+r1P∗, where r1=h1,ctr1+x1,1. It finally sends t1=H0K1 to all cosigners. After receiving all tj from ℱ′ (all other cosigners), ℬ looks up the corresponding Kj in table T0 such that tj=T0Kj. If not all such values can be found, ℬ randomly chooses K1′←$Eℤp and broadcasts K1′. If there exists Kj′≠Kj such that T0Kj′=T0Kj, then ℬ sets bad1=true and aborts the execution of ℱ′ by outputting 0,⊥. Otherwise, ℬ computes K∗=ii=1NKi and checks whether T10,L‖K∗‖m has already been defined. If the entry was taken, ℬ sets bad2=true and aborts the execution by outputting 0,⊥. If not, ℬ sets T10,L‖K∗‖m=e1 and broadcasts K1. Upon receiving all Kj, ℬ stops the process if for any 2≤j≤N such that H0Kj≠tj. ℬ then broadcasts s1˜.Finally, ifℱ′ outputs a valid forgery K,s˜ on message m under the signer list L, then ℬ checks T10,Lii=1NKim. Let J be the index that h1,J=T10,Lii=1NKim. ℬ returns J,K,h1,J,s˜,L. The accepting probability of ℬ is as follows:(6)accℬ=Prℱ′succeeds∧bad1¯∧bad2¯≥Prℱ′succeeds−Prbad1¯−Prbad2¯≥ε−qh+Nqs+122n−2qsqh+Nqsn.We then construct the algorithmA that on input pk∗=P∗ and runs Forkℬpk∗. According to the general forking lemma, it returns 1,K,h1,J,s˜,L,K,h1,J′,s′˜,L with probability frkA. Note that the discrete logarithm with regard to P∗ can be computed through K,h1,J,s˜,L,K,h1,J′,s′˜,L. Therefore, the probability ε′ is as follows:(7)ε′≥frkA≥accℬaccℬqh+qs−1n≥ε2qh+qs−4qsqh+Nqs+12nqh+qs.


### 3.3. Experimental Results

We now present the concrete experimental results based on our implementation. We implemented theMS−SM2 scheme in Java and ran it on an EC2 instance of type CPU 2.50 GHz with 1 GB RAM. We use the standard SM2 curve and the SM3 hash algorithm. We ran experiments from 2 to 20 parties and compare our results in two-party setting with a related protocol from Zhang et al. [22] in Table 2. Note that [22] is an SM2-based two-party distributed signing protocol, which is slightly different from multisignature in the way that parties should also cooperate in key generation. Moreover, they omit the zero-knowledge proof component in their implementation, and our demo (https://github.com/lhoou/ms-sm2) as a simulation only includes local computation and omits the communication cost in real world. As for multiuser setting, the performances of our scheme are presented in Table 3.Table 2
Comparison of performances (in milliseconds) between [22] and our scheme in two-party setting.
SchemeKey GenerationSigningVerificationRef. [22]123.44 ms152.34 ms4.17 msOurs51.16 ms18.04 ms10.20 msTable 3
The performances of our protocol in multiparty setting.
Number ofpartiesSignature Length (compressed)Signing (local computation)VerificationN = 5192 B13.648 ms20.916 msN = 10352 B10.021 ms44.191 msN = 20674 B9.646 ms49.399 ms


## 3.1. Construction

The initializationSetup algorithm and KeyGen algorithm of the multisignature are almost the same as that in the SM2 scheme, except that there are two hash functions used in multisignature scheme, denoted as H0:Eℤp⟶ℤn,H1:0,1∗⟶ℤn. We now proceed to describe the signing protocol and verification algorithm of the MS−SM2 scheme. Note that we take L to be size of N for simplicity, where N is the maximum number of cosigners and N≪n.MSignpp,L,m,ski: each signer i with secret key ski=di and public key pki=Pi in set L runs an interactive protocol to collaboratively sign a message m. The communication proceeds in a number of rounds, where in each round, every signer sends and receives messages to and from other signers and also performs some local computation.(1)
Chooseki←$1,n−1, compute Kixi,1,yi,1=kiG and ti=H0xi,1,yi,1, and broadcast ti.(2)
Upon receivingtj from all other signers, broadcast Kixi,1,yi,1.(3)
Upon receivingxj,1,yj,1 from all other signers, check the hash values and abort the protocol if for any j that tj≠H0xj,1,yj,1. Otherwise, set ei=H1Zi‖L‖ii=1NKi‖m, ri=ei+xi,1modn, and si˜=ki−ri⋅dimodn. Then, broadcast si˜.(4)
Upon receivingsj˜ from all other signers, compute s˜=∑i=1Ns˜modn and run the protocol for ℱadd with input si=1+di⋅s˜−1modn to get the addition s=∑i=1Nsimodn.At the end the interactive protocol, the algorithm outputs a multisignatureσ=K,s, where K is the set of all points Kixi,1,yi,1.Vrfypp,L,m,σ: given a multiset of public keys L, message m, and multisignature σ, the verifier computes ei=H1Zi‖L‖ii=1NKi‖m and ri=ei+xi,1modn, accepts the signature if s⊕i=1NKi−s⊕i=1NriPi=NG+⊕i=1NPi, and outputs 1. Otherwise, it outputs 0.Correctness: ifσ=K,s is a valid output of protocol, Vrfy algorithm always accepts and outputs 1. The equation only holds when all signers follow the protocol and use valid key pairs. Note that the integer computations are all modulo n, and we omit the notation for simplicity.(2)s⊕i=1NKi−s⊕i=1NriPi=s∑i=1NkiG−s∑i=1Nri⋅diG=s⋅∑i=1Nki−∑i=1Nri⋅diG=∑i=1Nsi⋅∑i=1Nsi˜G=∑i=1N1+di⋅s˜−1⋅s˜G=∑i=1N1+diG=NG+⊕i=1NPi.


## 3.2. Security Proof

In general, we can treat the multisignature scheme as a multiparty computation protocol and prove its security in simulation-based framework for a clearer security guarantee. Unfortunately, the security of multisignature is traditionally defined in game-based framework, and on the other hand, simulation-based proof is complex in the random oracle model. Here, we follow the game-based definition of Bellare and Neven [7] and only show a proof sketch for the scheme.The basic idea of game-based proof is to obtain fromℱ two different forgeries σ and σ′ with the same randomness by employing the general forking lemma. As a result, we can extract the secret key from the target public key pk∗, which is usually a solution of the discrete-logarithm problem in the elliptic-curve group Eℤp. For simplification, we take an equivalent verification equation into consideration, and if σ=K,s and σ′=K,s′ satisfy (3)⊕i=1NKi−⊕i=1NriPi=s−1NG+s−1⊕i=1NPi,⊕i=1NKi−⊕i=1NriPi=s−1NG+s−1⊕i=1NPi,then the secret key d∗ corresponding to pk∗ can be computed from the equation(4)∑i=1Nri′−ridi=s−1−s′−1N−∑i=1Ndi.However, in the process ofMSign, each signer can check the value s˜ before continuing to execute the protocol, which allows signers to quit cosigning immediately if there is any rogue key attack. Specifically, they can compute x1′,y1′=s˜G+∑i=1NriPi and check if x1′ is equal to the corresponding part in the result.(5)s˜G+∑i=1NriPi=∑i=1Nsi˜G+∑i=1Nri⋅diG=∑i=1Nki−ri⋅diG+∑i=1Nri⋅diG=∑i=1NkiG=⊕i=1Nxi,1,yi,1.Therefore, we can let the simulator halt if the forger successfully forgeds˜.Lemma 2.
If there exists at,qs,qh,N,ε-forger ℱ′ that can output a forgery s˜, then there exists a PPT algorithm A which t′,ε′-solves the DL problem in Eℤp.Proof.
Note thats˜=∑i=1Nsi˜modn and each si˜ has similar structure with Schnorr signature. Therefore, the proof of Lemma 2 is similar to that of the MS−BN scheme. Generally, given a t,qs,qh,N,ε-forger ℱ′, we first wrap it into an algorithm ℬ that can be used in the general forking lemma. We then describe an algorithm A that on input pk∗=P∗ and runs Forkℬpk∗ to output the corresponding discrete logarithm.Letq=qh+qs, T0⋅,T1⋅ be the programmed hash tables for oracles H0andH1, respectively, and h1h1,1,…,h1,q be the answers of queries to H1. Two counters ctr1 and ctr2 are initialized to zero. An additional array T2⋅ records a unique index 1≤i≤qh+Nqs to each public key Pi occurring either as a cosigner’s public key in signature queries or H1 queries, where T2P∗=0. On input pp,h1,P∗∈Eℤp, ℬ plays the ExpMSUF−CMAℱ game with ℱ′ with the target public key pk∗=P∗. ℬ answers queries from ℱ′ by programming the oracles as follows:(i)
H0Ki: if H0Ki is undefined, then ℬ randomly assigns T0Ki←$ℤn and then returns ti=T0Ki.(ii)
H1Zi‖L‖ii=1NKi‖m: if T2Pi is undefined, then ℬ increments ctr2 and sets T2Pi=ctr2. Let k=T2Pi; if T1k,L‖ii=1NKi‖m has not yet been defined, then ℬ assigns random values to all T1j,L‖ii=1NKi‖m for 1≤j≤qh+Nqs, increases ctr1, and assigns T10,L‖⊕i=1NKi‖m=h1,ctr1.(iii)
OsignL,m: if P∗∉L, then ℬ returns ⊥ to the forger. Otherwise, it parses L as P∗,P2,…,PN. ℬ first checks whether T2Pi2≤i≤N has already been defined, if not it increases ctr2 and sets T2Pi=ctr2. Then, it increases counter ctr1 and sets e1=h1,ctr1. It chooses s1˜←$ℤn and computes a elliptic curve point K1 such that K1x1,1,y1,1=s1˜G+r1P∗, where r1=h1,ctr1+x1,1. It finally sends t1=H0K1 to all cosigners. After receiving all tj from ℱ′ (all other cosigners), ℬ looks up the corresponding Kj in table T0 such that tj=T0Kj. If not all such values can be found, ℬ randomly chooses K1′←$Eℤp and broadcasts K1′. If there exists Kj′≠Kj such that T0Kj′=T0Kj, then ℬ sets bad1=true and aborts the execution of ℱ′ by outputting 0,⊥. Otherwise, ℬ computes K∗=ii=1NKi and checks whether T10,L‖K∗‖m has already been defined. If the entry was taken, ℬ sets bad2=true and aborts the execution by outputting 0,⊥. If not, ℬ sets T10,L‖K∗‖m=e1 and broadcasts K1. Upon receiving all Kj, ℬ stops the process if for any 2≤j≤N such that H0Kj≠tj. ℬ then broadcasts s1˜.Finally, ifℱ′ outputs a valid forgery K,s˜ on message m under the signer list L, then ℬ checks T10,Lii=1NKim. Let J be the index that h1,J=T10,Lii=1NKim. ℬ returns J,K,h1,J,s˜,L. The accepting probability of ℬ is as follows:(6)accℬ=Prℱ′succeeds∧bad1¯∧bad2¯≥Prℱ′succeeds−Prbad1¯−Prbad2¯≥ε−qh+Nqs+122n−2qsqh+Nqsn.We then construct the algorithmA that on input pk∗=P∗ and runs Forkℬpk∗. According to the general forking lemma, it returns 1,K,h1,J,s˜,L,K,h1,J′,s′˜,L with probability frkA. Note that the discrete logarithm with regard to P∗ can be computed through K,h1,J,s˜,L,K,h1,J′,s′˜,L. Therefore, the probability ε′ is as follows:(7)ε′≥frkA≥accℬaccℬqh+qs−1n≥ε2qh+qs−4qsqh+Nqs+12nqh+qs.


## 3.3. Experimental Results

We now present the concrete experimental results based on our implementation. We implemented theMS−SM2 scheme in Java and ran it on an EC2 instance of type CPU 2.50 GHz with 1 GB RAM. We use the standard SM2 curve and the SM3 hash algorithm. We ran experiments from 2 to 20 parties and compare our results in two-party setting with a related protocol from Zhang et al. [22] in Table 2. Note that [22] is an SM2-based two-party distributed signing protocol, which is slightly different from multisignature in the way that parties should also cooperate in key generation. Moreover, they omit the zero-knowledge proof component in their implementation, and our demo (https://github.com/lhoou/ms-sm2) as a simulation only includes local computation and omits the communication cost in real world. As for multiuser setting, the performances of our scheme are presented in Table 3.Table 2
Comparison of performances (in milliseconds) between [22] and our scheme in two-party setting.
SchemeKey GenerationSigningVerificationRef. [22]123.44 ms152.34 ms4.17 msOurs51.16 ms18.04 ms10.20 msTable 3
The performances of our protocol in multiparty setting.
Number ofpartiesSignature Length (compressed)Signing (local computation)VerificationN = 5192 B13.648 ms20.916 msN = 10352 B10.021 ms44.191 msN = 20674 B9.646 ms49.399 ms


## 4. Applications to Vehicular Networks

In this section, we describe two potential applications ofMS−SM2 to vehicular networks. We first show that it can be employed in the architecture of multiple certificate authorities to reduce the number of certificates that are required for devices in the system including on-board units (OBU) and road-side units (RSU). In addition, we also specify its possible usage in the process of V2I communications. The goal is to reduce computation and storage overhead for the units while maintaining security properties.


### 4.1. Multi-CA Architecture

In vehicular networks, taking C-V2X, for example, certificate authorities usually include organizations for registration, communication authorization, and pseudonym authorization. Specifically, any device that is involved in the network should first require for registration certificate from registration CA and then require for other certificates from different CAs that are needed to send and receive messages in the network.For instance, a vehicle is required to get a certificate from the registration CA using its unique identity before joining the network. It can then require a pseudonym certificate for the anonymous V2V communication and a secure V2I communication certificate from secure communication CA using its registration certificate. The vehicle can also apply multiple registration certificates from different registration CAs. To simplify the authentication process, the distributed CAs can employMS−SM2 in order to jointly generate only one certificate or one registration certificate for the vehicle at the same time, instead of generating certificates one by one.


### 4.2. Cooperative V2I Communication

Cooperative communication in vehicular networks has been leveraged to offer various improvements on spectral efficiency, transmission reliability, and reduced transmission delay. Vehicles can cooperate with each other either directly or through an RSU, and the vehicular node which helps the source node to transmit its data is called a helper node or relay node [23].(i)
Cooperative traffic reports: vehicles in the same traffic area, such as in an accident or in a neighborhood, can cooperatively issue a traffic report including awareness messages (CAMs), safety importance, and vehicle heading and transmit a packet to the RSU attached with aMS−SM2 signature. The MS−SM2 signature can help the RSU to check validity of the packet and also reduce the computation cost of RSU.(ii)
RSU-assisted communication: when a source RSU fails to successfully transmit a packet to the targeted destination, it forwards the packet to the next RSU along the path using the backhaul wired connection. The new RSU relays the received packet to the targeted destination. In this scenario, both the source RSU and relayed RSU can jointly sign the packet usingMS−SM2 to convince the target vehicle of the message transmitted, which can also prevent any malicious RSU from sending out frauds without collusion.


## 4.1. Multi-CA Architecture

In vehicular networks, taking C-V2X, for example, certificate authorities usually include organizations for registration, communication authorization, and pseudonym authorization. Specifically, any device that is involved in the network should first require for registration certificate from registration CA and then require for other certificates from different CAs that are needed to send and receive messages in the network.For instance, a vehicle is required to get a certificate from the registration CA using its unique identity before joining the network. It can then require a pseudonym certificate for the anonymous V2V communication and a secure V2I communication certificate from secure communication CA using its registration certificate. The vehicle can also apply multiple registration certificates from different registration CAs. To simplify the authentication process, the distributed CAs can employMS−SM2 in order to jointly generate only one certificate or one registration certificate for the vehicle at the same time, instead of generating certificates one by one.


## 4.2. Cooperative V2I Communication

Cooperative communication in vehicular networks has been leveraged to offer various improvements on spectral efficiency, transmission reliability, and reduced transmission delay. Vehicles can cooperate with each other either directly or through an RSU, and the vehicular node which helps the source node to transmit its data is called a helper node or relay node [23].(i)
Cooperative traffic reports: vehicles in the same traffic area, such as in an accident or in a neighborhood, can cooperatively issue a traffic report including awareness messages (CAMs), safety importance, and vehicle heading and transmit a packet to the RSU attached with aMS−SM2 signature. The MS−SM2 signature can help the RSU to check validity of the packet and also reduce the computation cost of RSU.(ii)
RSU-assisted communication: when a source RSU fails to successfully transmit a packet to the targeted destination, it forwards the packet to the next RSU along the path using the backhaul wired connection. The new RSU relays the received packet to the targeted destination. In this scenario, both the source RSU and relayed RSU can jointly sign the packet usingMS−SM2 to convince the target vehicle of the message transmitted, which can also prevent any malicious RSU from sending out frauds without collusion.


## 5. Conclusions

In this paper, we present a candidate multisignature scheme from the SM2 signature algorithm in the plain public-key model. Compared to a list of individual signatures, the storage volume ofMS−SM2 signature reduces nearly 50% and the computation cost is relatively low. In addition, we specify in detail some potential applications of the MS−SM2 scheme to vehicular networks, especially in the scenario of cooperatively secure communication, with the goal of maximizing performance and compatibility. Because of the high-speed mobility, designing more efficient protocols with fewer communication rounds for vehicular networks is still a challenging research problem.



---

*Source: 7897527-2021-10-27.xml*