# Certificateless Multisignature Scheme Suitable for Network Coding

Authors: Huifang Yu; Zhewei Qi; Danqing Liu; Ke Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Network coding can save the wireless network resources and improve the network throughput by combining the routing with coding. Traditional multisignature from certificateless cryptosystem is not suitable for the network coding environment. In this paper, we propose a certificateless multisignature scheme suitable for network coding (NC-CLMSS) by using the sequential multisignature and homomorphic hash function. NC-CLMSS is based on the CDH and ECDL problems, and its security is detailedly proved in the random oracle (RO) model. In NC-CLMSS, the source node generates a multisignature for the message, and the intermediate node linearly combines the receiving message. NC-CLMSS can resist the pollution and forgery attacks, and it has the fixed signature length and relatively high computation efficiency.


---

## Body

## 1. Introduction

As the network information interaction technology, the network coding [1] has routing and coding functions and allows the router to encode the received data. Network coding has the merits of high transmission efficiency, fast speed, strong robustness, and good stability, but it is vulnerable to the pollution attacks in the data transmission process. In recent years, the researchers have proposed a series of network-coding signature schemes [2–6] to solve the network coding contamination, where the schemes in [4, 5] effectively solved the replay attacks by using the time stamps; the certificateless network-coding homomorphism signature [6] is designed by using the homomorphic hash function; it can resist the replay attacks with forgery attacks at the same time and has lower computational overhead with the communication cost.In real scenario, there are many applications to use the signature technology. With the development of communication technology, the scholars proposed many signature varieties (including multisignature) suitable for various application scenarios, such as medical field [7–10], privacy security [11], vehicle-mounted network [12, 13], multicast network [14, 15], e-government [16], e-commerce [17], and campus management facilities [18]. Multisignature first generates the partial signature of the same message, and then, the signature collector integrates the partial signatures into a signature. In terms of the order of partial signatures, multisignature can be divided into sequential multisignature [19] and broadcast multisignature [20, 21]. Compared with ordinary multisignature, the sequential multisignature has the following characteristics: (1) the signature length has nothing to do with the number of signatures; (2) instead of using the public key of each signer, the group public key can be used to verify the signature; (3) signers sign the messages in a concrete order, otherwise a valid multisignature cannot be obtained; (4) it is not computationally feasible to obtain the valid signatures without the joint operation of all signers. From now on, there is no sequential multisignature suitable for network coding, as described in Figure 1, so we will devise such a scheme to resist the pollution and forgery attacks in wireless networks.Figure 1
Model for sequential multisignature suitable for network coding.


### 1.1. Contributions

For the above reasons, a new certificateless multisignature scheme for the network coding (NC-CLMSS) is devised by combining the certificateless public key with sequential multisignature. In NC-CLMSS, the users at the source node generate the sequential multisignatures for the messages in a fixed order and transfer the signed messages from the router to the intermediate node. Intermediate node performs the linear combination of received information. Meanwhile, the destination node can verify the correctness of the signature without knowing the signer private key. Destination node filters out the contaminated information and forwards the validated data to the next receiving node. NC-CLMSS overcomes the key escrow and certificate management issues; moreover, it can resist the forgery attacks with pollution attacks in the multisource network-coding environment and has relatively better transmission efficiency.


## 1.1. Contributions

For the above reasons, a new certificateless multisignature scheme for the network coding (NC-CLMSS) is devised by combining the certificateless public key with sequential multisignature. In NC-CLMSS, the users at the source node generate the sequential multisignatures for the messages in a fixed order and transfer the signed messages from the router to the intermediate node. Intermediate node performs the linear combination of received information. Meanwhile, the destination node can verify the correctness of the signature without knowing the signer private key. Destination node filters out the contaminated information and forwards the validated data to the next receiving node. NC-CLMSS overcomes the key escrow and certificate management issues; moreover, it can resist the forgery attacks with pollution attacks in the multisource network-coding environment and has relatively better transmission efficiency.


## 2. Preliminaries

### 2.1. Bilinear Pairing

AssumeG1 and G2 are additive and multiplication cyclic groups with the prime order q, respectively. P is a generator of the cyclic group G1. e: G1 × G1⟶G2 is an admissible bilinear pairing if e is a map with the following properties: e (aP, bP) = e (P, P)ab, for any a, b ∈ zq∗, and P ∈ G1; e (P, P) ≠ 1; there exists an efficient algorithm to compute e (P, Q), for any P, Q ∈ G1.Definition 1.
(ECDL problem). Given (P, aP) ∈ G1, for any a ∈ zq∗, the ECDL (elliptic curve discrete logarithm) problem is to calculate a ∈ zq∗.Definition 2.
(CDH problem). Given (P, aP, bP) ∈ G1, for any a, b ∈ zq∗, the CDH (computational Diffie–Hellman) problem is to calculate abP ∈ G1.


### 2.2. Multisource Network Model

Multisource network coding [22] has a set of source nodes. In the multisource model, each encoding message has a uniformly assigned two-dimensional index. Model for multisource transmission network is shown in Figure 2.Figure 2
Model for multisource transmission network.Multisource network coding is regarded as a directed acyclic graphR = (E′, V), where E′ is the set of edges in the network and V is the set of all nodes. U=u1,u2,…,um⊂V is the set of the source nodes and D=d1,d2,…,dk⊂V is the set of the sink nodes; m multicast messages are expressed by v=v1,v2,…,vm; the source nodes’ set U sends v=v1,v2,…,vm to the sink nodes D, where each message vector vi is composed of n elements over finite field F, where vi is written as(1)vi=vi,1,vi,2,…,vi,n∈F,1≤i≤m.Letj be the unique index uniformly assigned to each message, and the same multicast message sent by different source nodes has the same index. Each packet w=w1,w2,…,wl can be sent by arbitrary intermediate node in network, and w is the linear combination of l messages received by this node.


### 2.3. Symbol Descriptions

In Table1, the readers can see the meaning of notations relevant to this article.Table 1
Meaning of the various notations.
NotationsMeaningKGCThe key generation centerρA security parameterηThe public parameter setIDiSome user identityNiUserNi (i ∈ {1, 2, …, n})SThe master secret keysiThe full private key of a userPKiThe full public key of a userDiThe partial private key of a userRiThe partial public key of a userPiThe user public keyPpubThe system public keyHi (i = 0, 1, 2)Hash function (i = 0, 1, 2)σiA signature of the messagevtσMultisignature


## 2.1. Bilinear Pairing

AssumeG1 and G2 are additive and multiplication cyclic groups with the prime order q, respectively. P is a generator of the cyclic group G1. e: G1 × G1⟶G2 is an admissible bilinear pairing if e is a map with the following properties: e (aP, bP) = e (P, P)ab, for any a, b ∈ zq∗, and P ∈ G1; e (P, P) ≠ 1; there exists an efficient algorithm to compute e (P, Q), for any P, Q ∈ G1.Definition 1.
(ECDL problem). Given (P, aP) ∈ G1, for any a ∈ zq∗, the ECDL (elliptic curve discrete logarithm) problem is to calculate a ∈ zq∗.Definition 2.
(CDH problem). Given (P, aP, bP) ∈ G1, for any a, b ∈ zq∗, the CDH (computational Diffie–Hellman) problem is to calculate abP ∈ G1.


## 2.2. Multisource Network Model

Multisource network coding [22] has a set of source nodes. In the multisource model, each encoding message has a uniformly assigned two-dimensional index. Model for multisource transmission network is shown in Figure 2.Figure 2
Model for multisource transmission network.Multisource network coding is regarded as a directed acyclic graphR = (E′, V), where E′ is the set of edges in the network and V is the set of all nodes. U=u1,u2,…,um⊂V is the set of the source nodes and D=d1,d2,…,dk⊂V is the set of the sink nodes; m multicast messages are expressed by v=v1,v2,…,vm; the source nodes’ set U sends v=v1,v2,…,vm to the sink nodes D, where each message vector vi is composed of n elements over finite field F, where vi is written as(1)vi=vi,1,vi,2,…,vi,n∈F,1≤i≤m.Letj be the unique index uniformly assigned to each message, and the same multicast message sent by different source nodes has the same index. Each packet w=w1,w2,…,wl can be sent by arbitrary intermediate node in network, and w is the linear combination of l messages received by this node.


## 2.3. Symbol Descriptions

In Table1, the readers can see the meaning of notations relevant to this article.Table 1
Meaning of the various notations.
NotationsMeaningKGCThe key generation centerρA security parameterηThe public parameter setIDiSome user identityNiUserNi (i ∈ {1, 2, …, n})SThe master secret keysiThe full private key of a userPKiThe full public key of a userDiThe partial private key of a userRiThe partial public key of a userPiThe user public keyPpubThe system public keyHi (i = 0, 1, 2)Hash function (i = 0, 1, 2)σiA signature of the messagevtσMultisignature


## 3. Formal Definition

### 3.1. Algorithm Definition

A NC-CLMSS is defined by six polynomial time algorithms as follows.Setup: input a security parameter ρ and finally output the master key s with a system parameter set μ.Extract: input μ with the user identity IDi and finally output a pair (Ri, Di) of partial public/private keys.KeyGen: input μ with the user identity IDi and finally output a pair (xi, Pi) of public/private keys.Multisignature: input μ, the master key s, the message vt, the private key (Di, xi), and public key (Ri, Pi) and finally output a signature σi.Combination: input the message vector w1,…,wm and finally output a combined signature σ.Verification: input μ, σi, and σ, the public key (Ri, Pi), and the message vt; the verifier outputs a result based on the verification case.


### 3.2. Security Model

A NC-CLMSS must meet the existential unforgeability against the adaptive chosen-message attacks (UF-CMA). For the UF-CMA security model of NC-CLMSS, we think about the game EXP1/EXP2 between a challengerC and a polynomial time adversary A1 or A2.Firstly,OCsetupρ⟶μA1 and OCsetupρ⟶μ,sA2, where A1 is a malicious user who can change any user public key but cannot know the master private key; A2 is a malicious KGC who knows the system master key but cannot change any user public key. After that, A1 or A2 carries out the adaptive queries as follows:(2)OCpartialprivatekeyIDi⟶DiA1A2,OCpublickeyIDi⟶Ri,PiA1A2,OCprivatekeyIDi⟶xiifPiwas not replacedA1,OCprivatekeyIDi⟶xiA2,OCreplacepublickeyIDi⟶Ri′,Pi′A1,OCmultisignaturevt⟶σiA1A2,OCcombinationσi⟶σA1A2,OCverificationσ,σi⟶message or⊥A1A2.Finally,A1/A2 outputs a forged signature σ∗. In the adaptive queries, A1 should not request the full private key of IDs; A2 cannot request the private key of IDs. In addition, σ∗ should not be returned by any multisignature oracle. A1/A2 wins in EXP1/EXP2 if OCverificationσ,σi⟶not⊥A1/A2.Assume Adv (ρ) denotes the adversary advantage in EXP1/EXP2; then, Adv (ρ) is defined as the probability which A1/A2 succeeds in EXP1/EXP2.Definition 3.
A NC-CLMSS is said to be UF-CMA secure if no polynomial time adversaryA1/A2 succeeds in EXP1/EXP2 with a non-negligible advantage.


## 3.1. Algorithm Definition

A NC-CLMSS is defined by six polynomial time algorithms as follows.Setup: input a security parameter ρ and finally output the master key s with a system parameter set μ.Extract: input μ with the user identity IDi and finally output a pair (Ri, Di) of partial public/private keys.KeyGen: input μ with the user identity IDi and finally output a pair (xi, Pi) of public/private keys.Multisignature: input μ, the master key s, the message vt, the private key (Di, xi), and public key (Ri, Pi) and finally output a signature σi.Combination: input the message vector w1,…,wm and finally output a combined signature σ.Verification: input μ, σi, and σ, the public key (Ri, Pi), and the message vt; the verifier outputs a result based on the verification case.


## 3.2. Security Model

A NC-CLMSS must meet the existential unforgeability against the adaptive chosen-message attacks (UF-CMA). For the UF-CMA security model of NC-CLMSS, we think about the game EXP1/EXP2 between a challengerC and a polynomial time adversary A1 or A2.Firstly,OCsetupρ⟶μA1 and OCsetupρ⟶μ,sA2, where A1 is a malicious user who can change any user public key but cannot know the master private key; A2 is a malicious KGC who knows the system master key but cannot change any user public key. After that, A1 or A2 carries out the adaptive queries as follows:(2)OCpartialprivatekeyIDi⟶DiA1A2,OCpublickeyIDi⟶Ri,PiA1A2,OCprivatekeyIDi⟶xiifPiwas not replacedA1,OCprivatekeyIDi⟶xiA2,OCreplacepublickeyIDi⟶Ri′,Pi′A1,OCmultisignaturevt⟶σiA1A2,OCcombinationσi⟶σA1A2,OCverificationσ,σi⟶message or⊥A1A2.Finally,A1/A2 outputs a forged signature σ∗. In the adaptive queries, A1 should not request the full private key of IDs; A2 cannot request the private key of IDs. In addition, σ∗ should not be returned by any multisignature oracle. A1/A2 wins in EXP1/EXP2 if OCverificationσ,σi⟶not⊥A1/A2.Assume Adv (ρ) denotes the adversary advantage in EXP1/EXP2; then, Adv (ρ) is defined as the probability which A1/A2 succeeds in EXP1/EXP2.Definition 3.
A NC-CLMSS is said to be UF-CMA secure if no polynomial time adversaryA1/A2 succeeds in EXP1/EXP2 with a non-negligible advantage.


## 4. NC-CLMSS Instance

### 4.1. Setup

Given a security parameterρ, KGC (key generation center) chooses cyclic groups G1 and G2 with the prime order q, as described in Section 2.1. P is a generator of G1 and e: G1 × G1⟶G2. KGC selects secure hash functions: H0:0,1∗×G1⟶Zq∗, H1:0,1∗⟶Zq∗,H2:0,1∗⟶G1. KGC chooses a master key s ∈ RZq∗ and maintains its secret and then calculates the system public key Ppub = sP. Finally, KGC publishes the system parameter set: μ=G1,G2,q,P,e,Ppub,H0,H1,H2.


### 4.2. Extract

Given the identityIDi of the user Ni and μ, KGC randomly chooses ri ∈ Zq∗ and calculates Ri=riP, hi=H0IDi,Ri, and Di=ri+his, where IDi ∈ {ID1, ID2,…, IDn}, Di is the partial private key of Ni, and Ri is the partial public key of Ni.


### 4.3. KeyGen

Given the identityIDi of the user Ni and μ, this user Ni (i∈{1, 2, …, n}) randomly chooses a secret value xi ∈ Zq∗ and calculates the public key Pi = xiP. Note that IDi ∈ {ID1, ID2,…,IDn}, PKi = (Pi, Ri) is the full public key of Ni, and si = (xi, Di) are the full private key of Ni.


### 4.4. Multisignature

AssumeL = {ID1, ID2,…, IDn} is an identity set of n users and N1⟶N2⟶…⟶Nn denotes the signature sequence of n users. In other words, the user Ni (i ∈ {1, 2, …, n}) signs the message vt with the sequence N1⟶N2⟶…⟶Nn. Firstly, N1 calculates(3)l1=H1ID1,L,P1,R1,vt,T=H2vt,L,Ppub,σ1=SIGN1=l1x1+D1T,where σ1 is the partial signature of the message vt from the user N1. User N1 delivers vt,σ1 to the user N2. After receiving vt,σi−1, the user Ni (i = 2, 3, …, n) calculates(4)lj=H1IDj,L,Pj,Rj,vt,hj=H0IDj,Rj,1≤j≤i−1,T=H2vt,L,Ppub.If the equalityeσi−1,P=eT,∑j=1i−1ljPj+Rj+hjPpub holds, the user Ni calculates(5)li=H1IDi,L,Pi,Ri,vt,1≤i≤n,σi=σi−1+SIGNi=σi−1+lixi+DiT.Then, the signature of the userNn is σn=∑i=1nSIGNi. Finally, σ=σ1,σ2,…,σd and vt are sent to the intermediate code and sink node.


### 4.5. Combination

Given the local coding vectorα=α1,…,αm and global vector β=β1,…,βm, the intermediate node combines the message vector as follows:(6)w=∑i=1mαiwi.Then, the message vectorvt is also denoted as w=∑j=1mβjvj, and the signature corresponding to the message vector w is σ=σ1,σ2,…,σd. Signature process corresponding to w is σj=∑i=1mσi,jαi, where σi,j (1 ≤ i ≤ m, 1 ≤ j ≤ l) represents the j-th element of σi. Finally, the intermediate node outputs the combined signature σ=∏i=1mσiαi.


### 4.6. Verify

After receiving the multisignature and combination signature, the verifier calculatesli=H1IDi,L,Pi,Ri,vt (1 ≤ i ≤ n) and T=H2vt,L,Ppub.If the equalityeσn,P=eT,∑i=1nliPi+Ri+hiPpub holds, the multisignature is valid and invalid otherwise.


## 4.1. Setup

Given a security parameterρ, KGC (key generation center) chooses cyclic groups G1 and G2 with the prime order q, as described in Section 2.1. P is a generator of G1 and e: G1 × G1⟶G2. KGC selects secure hash functions: H0:0,1∗×G1⟶Zq∗, H1:0,1∗⟶Zq∗,H2:0,1∗⟶G1. KGC chooses a master key s ∈ RZq∗ and maintains its secret and then calculates the system public key Ppub = sP. Finally, KGC publishes the system parameter set: μ=G1,G2,q,P,e,Ppub,H0,H1,H2.


## 4.2. Extract

Given the identityIDi of the user Ni and μ, KGC randomly chooses ri ∈ Zq∗ and calculates Ri=riP, hi=H0IDi,Ri, and Di=ri+his, where IDi ∈ {ID1, ID2,…, IDn}, Di is the partial private key of Ni, and Ri is the partial public key of Ni.


## 4.3. KeyGen

Given the identityIDi of the user Ni and μ, this user Ni (i∈{1, 2, …, n}) randomly chooses a secret value xi ∈ Zq∗ and calculates the public key Pi = xiP. Note that IDi ∈ {ID1, ID2,…,IDn}, PKi = (Pi, Ri) is the full public key of Ni, and si = (xi, Di) are the full private key of Ni.


## 4.4. Multisignature

AssumeL = {ID1, ID2,…, IDn} is an identity set of n users and N1⟶N2⟶…⟶Nn denotes the signature sequence of n users. In other words, the user Ni (i ∈ {1, 2, …, n}) signs the message vt with the sequence N1⟶N2⟶…⟶Nn. Firstly, N1 calculates(3)l1=H1ID1,L,P1,R1,vt,T=H2vt,L,Ppub,σ1=SIGN1=l1x1+D1T,where σ1 is the partial signature of the message vt from the user N1. User N1 delivers vt,σ1 to the user N2. After receiving vt,σi−1, the user Ni (i = 2, 3, …, n) calculates(4)lj=H1IDj,L,Pj,Rj,vt,hj=H0IDj,Rj,1≤j≤i−1,T=H2vt,L,Ppub.If the equalityeσi−1,P=eT,∑j=1i−1ljPj+Rj+hjPpub holds, the user Ni calculates(5)li=H1IDi,L,Pi,Ri,vt,1≤i≤n,σi=σi−1+SIGNi=σi−1+lixi+DiT.Then, the signature of the userNn is σn=∑i=1nSIGNi. Finally, σ=σ1,σ2,…,σd and vt are sent to the intermediate code and sink node.


## 4.5. Combination

Given the local coding vectorα=α1,…,αm and global vector β=β1,…,βm, the intermediate node combines the message vector as follows:(6)w=∑i=1mαiwi.Then, the message vectorvt is also denoted as w=∑j=1mβjvj, and the signature corresponding to the message vector w is σ=σ1,σ2,…,σd. Signature process corresponding to w is σj=∑i=1mσi,jαi, where σi,j (1 ≤ i ≤ m, 1 ≤ j ≤ l) represents the j-th element of σi. Finally, the intermediate node outputs the combined signature σ=∏i=1mσiαi.


## 4.6. Verify

After receiving the multisignature and combination signature, the verifier calculatesli=H1IDi,L,Pi,Ri,vt (1 ≤ i ≤ n) and T=H2vt,L,Ppub.If the equalityeσn,P=eT,∑i=1nliPi+Ri+hiPpub holds, the multisignature is valid and invalid otherwise.


## 5. Correctness Analysis

### 5.1. Single Signature Verification

Given the signatureσi of the message vt, then the signature verification process of the user Ni (i ∈ {1, 2, …, n}) is as follows:(7)eσn,P=e∑i=1nlixi+DiT,P=eT,∑i=1nlixiP+DiP=eT,∑i=1nliPi+Ri+hiPpub.


### 5.2. Combination Verification

Given the messagev1,…,vm and global coding vector β=β1,…,βm, w=∑j=1mβjvj is the message vector received by the intermediate node, and σ=σ1,σ2,…,σt is the multisignature corresponding to w. In the verification phase, it is necessary to check the correctness of the following equality:(8)eσn,P=eT,∑i=1nliPi+Ri+hiPpub,where hi = H0 (IDi, Ri). In the multisource network coding, the intermediate nodes combine the messages from different source nodes and form a combination signature. Different source nodes may send the same message. In order to distinguish the possible combination of the same message vector, the global coding vector is expressed as βj=∑k=1dβjuk, where the global coding vector βjuk∈βju1,…,βjud and source node user uk ∈ {u1, u2, …, ud}. Then, the message vector is expressed as w=∑j=1m∑k=1dβjukvj. Hence, the multisignature of message vector w can be expressed as σ=∏j=1m∏k=1dσjukβjuk, and then, the i-th component in the multisignature can be expressed as σi=∏j=1m∏k=1dσj,iukβjuk,1≤i≤n, where σj,iuk is the i-th component of multisignature σjuk. Then, the relevant equality is verified as follows:(9)eσn,P=e∑i=1n∏j=1m∏k=1dliβj⋅xi+Di⋅∏j=1m∏k=1dTβj,P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅xi+Di⋅P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅xi⋅P+Di⋅P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅Pi+ri+hiPpub.From the verification process of single message, we knoweσn,P=eT,∑i=1nliPi+Ri+hiPpub. Then, the verification process is denoted as(10)e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅Pi+Ri+hiPpub=eT,∑i=1nliPi+Ri+hiPpub.


## 5.1. Single Signature Verification

Given the signatureσi of the message vt, then the signature verification process of the user Ni (i ∈ {1, 2, …, n}) is as follows:(7)eσn,P=e∑i=1nlixi+DiT,P=eT,∑i=1nlixiP+DiP=eT,∑i=1nliPi+Ri+hiPpub.


## 5.2. Combination Verification

Given the messagev1,…,vm and global coding vector β=β1,…,βm, w=∑j=1mβjvj is the message vector received by the intermediate node, and σ=σ1,σ2,…,σt is the multisignature corresponding to w. In the verification phase, it is necessary to check the correctness of the following equality:(8)eσn,P=eT,∑i=1nliPi+Ri+hiPpub,where hi = H0 (IDi, Ri). In the multisource network coding, the intermediate nodes combine the messages from different source nodes and form a combination signature. Different source nodes may send the same message. In order to distinguish the possible combination of the same message vector, the global coding vector is expressed as βj=∑k=1dβjuk, where the global coding vector βjuk∈βju1,…,βjud and source node user uk ∈ {u1, u2, …, ud}. Then, the message vector is expressed as w=∑j=1m∑k=1dβjukvj. Hence, the multisignature of message vector w can be expressed as σ=∏j=1m∏k=1dσjukβjuk, and then, the i-th component in the multisignature can be expressed as σi=∏j=1m∏k=1dσj,iukβjuk,1≤i≤n, where σj,iuk is the i-th component of multisignature σjuk. Then, the relevant equality is verified as follows:(9)eσn,P=e∑i=1n∏j=1m∏k=1dliβj⋅xi+Di⋅∏j=1m∏k=1dTβj,P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅xi+Di⋅P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅xi⋅P+Di⋅P=e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅Pi+ri+hiPpub.From the verification process of single message, we knoweσn,P=eT,∑i=1nliPi+Ri+hiPpub. Then, the verification process is denoted as(10)e∏j=1m∏k=1dTβj,∑i=1n∏j=1m∏k=1dliβj⋅Pi+Ri+hiPpub=eT,∑i=1nliPi+Ri+hiPpub.


## 6. Security Analysis

Theorem 1.
In the RO model, if the polynomial time adversaryA1 can break the UF-CMA-I security of NC-CLMSS, a challenge algorithm C can solve the CDH (computational Diffie–Hellman) problem.Proof.
C receives a random instance (P, aP, bP) ∈ G1 of CDH problem, and its aim is to use A1 (the subroutine of C) to calculate abP ∈ G1. C maintains the initially empty lists L0, L1, L2, and L3 to store the query-answer values of several oracles. Firstly, OCsetupρ⟶μA1, where Ppub = aP. Then, A1 adaptively issues the polynomial time queries as follows.H0 queries: A1 issues an H0 query. C outputs hi to A1 if the relevant tuple is in the list L0; otherwise, C returns a random hi ∈ RZq∗ and stores (IDi, Ri, hi) in L0.H1 queries: A1 issues an H1 query. C returns li if a matching tuple is in the list L1; otherwise, C returns li ∈ RZq∗ and stores (IDi, L, Pi, Ri, vt, li) in L1.H2 queries: A1 issues an H2 query. If it is not the θ-th query (θ ∈ {1, 2, …, q0} (q0 is the query times relevant to the H0 oracle) and a matching tuple is in the list L2, C outputs T = lP (l ∈ RZq∗) and stores (vt, li, Ppub, l, T) in L2; otherwise, C returns T = bP and stores (vt, li, Ppub, -, T) in L2.Partial private key queries:A1 requests a partial private key of IDi. If it is not the θ-th query, C chooses ri ∈ RZq∗ to calculate Ri = riP such that Di satisfies DiP = Ri + hiPpub and finally returns Di as the answer and stores (IDi, ri, Ri, Di,-,-) in the list L3; otherwise, C fails and aborts the game.Public key queries:A1 requests a public key of IDi. C calculates Pi = xiP (xi ∈ RZq∗) and finally returns PKi = (Ri, Pi) and updates the list L3 with (IDi, ri, Ri, Di, xi, Pi).Secret value queries:A1 requests a secret value of IDi. C returns xi from L3 if the corresponding public key has not been replaced.Public key replacement: if it is not theθ-th query, the public key of IDi is replaced by A1; otherwise, C fails and aborts the game.Multisignature queries: for a multisignature query of messagevt, C runs the relevant algorithm and returns a result if it is not the θ-th query; otherwise, C signs vt with the sequence N1⟶N2⟶…⟶Nn. Firstly, C calculates for N1 as follows:(11)l1=H1ID1,L,P1,R1,vt,T=H2vt,L,Ppub,σ1=SIGN1=l1x1+D1T,whereσ1 is the partial signature of vt for N1. Then, C calculates for Ni (i ∈ {1, 2, …, n}) relevant to vt,σi−1 as follows:(12)lj=H1IDj,L,Pj,Rj,vt,hj=H0IDj,Rj,1≤j≤i−1,T=H2vt,L,Ppub.Ifeσi−1,P=eT,∑j=1i−1ljPj+Rj+hjPpub holds, C calculates for Ni as follows:(13)li=H1IDi,L,Pi,Ri,vt,1≤i≤n,σi=σi−1+SIGNi=σi−1+lixi+DiT.Finally,C calculates σn=∑i=1nSIGNi and delivers σ=σ1,σ2,…,σd which is sent to A1.Combination queries:A1 requests a combination query. For the local coding vector α=α1,…,αm, global vector β=β1,…,βm, and message vector w1,w2,…,wm, C combines the message vector w=∑i=1mαiwi. Then, the message vector is also denoted as w=∑j=1mβjvj, and the signature process relevant to w is σj=∑i=1mσi,jαi, where σi, j (1 ≤ i ≤ m and 1 ≤ j ≤ l) denotes the j-th element of σi. Finally, C outputs a combined signature σ=∏i=1mσiαi.Verification queries:A1 requests a verification query. C runs the verification algorithm and returns a result if it is not the θ-th query; otherwise, C calculates li=H1IDi,L,Pi,Ri,vt (1 ≤ i ≤ n) and T=H2vt,L,Ppub. If the equality eσn,P=eT,∑i=1nliPi+Ri+hiPpub holds, C returns σ and ⊥ otherwise.
Finally,A1 outputs a forgery signature σ∗. In the adaptive queries, A1 cannot request a full private key of IDi, and σ∗ is not returned by any multisignature oracle. If it is not the θ-th query, C fails and aborts the game; otherwise, C calls the H0, H1, and H2 oracles and then searches the list L3. Finally, C verifies the following equality:(14)eσn∗,P=eT∗,∑i=1nli∗Pi+Ri∗+hi∗Ppub=ebP,∑i=1nli∗Pi∗+Ri∗+∑i=1nhi∗aP=e∑i=1nli∗xi∗bP+ri∗bP+∑i=1nhi∗abP,P.
From the above equality, we can obtain the solution of CDH problem:(15)σn∗=∑i=1nli∗xi∗bP+ribP+∑i=1nhi∗abP,⇒abP=σn∗−∑i=1nli∗xi∗bP+ribP∑i=1nhi∗.


### 6.1. Probability Estimation

Probability thatC succeeds in the above-mentioned game is estimated as follows. Here, it is necessary to think about three events:E1 is the event that C does not abort the gameE2 is the event that A1 successfully forge a signatureE3 is the event that there exists at least one record of nontarget identity in successful forgery caseInE1, there exists one time not querying the target identity, and then, Pr [E1] ≥ 1/(ls + lr), where ls is the times of secret value query and lr is the query times of public key replacement, E2 denotes that A1 wins in the game, then Pr [E2|E1] ≥ ε, and E3 at least occurs once time in n queries, then Pr [E3|E1∧E2] ≥ 1/n. Hence, the success probability that C solves the CDH problem is(16)ε′=PrE1∧E2∧E3=PrE1⋅PrE2|E1PrE3|E1∧E2≥εn⋅ls+lr.Theorem 2.
In the RO model, if the polynomial time adversaryA2 can break the UF-CMA-II security of NC-CLMSS, a challenge algorithm C must be able to solve the CDH problem.Proof.
C receives a random instance (P, aP, bP) ∈ G1 of CDH problem, and its aim is to utilize A2 (the subroutine of C) to determine the value of abP ∈ G1. C maintains the initially empty lists L0, L1, L2, and L3 to save the query-answer values of several oracles. Firstly, OCsetupρ⟶μ,sA2. Then, A2 adaptively performs the polynomial time queries as below:H0 queries: for an H0 query, if (IDi, Ri, hi) is in the list L0, C returns hi; otherwise, C returns hi ∈ RZq∗ and stores (IDi, Ri, hi) in L0.H1 queries: for an H1 query, if the matching tuple is in the list L1, C returns li; otherwise, C returns li ∈ RZq∗ and stores (IDi, L, Pi, Ri, vt, li) in L1.H2 queries: for an H2 query, if it is not the θ-th query (θ ∈ {1, 2, …,q0} (q0 is the query times relevant to H0 oracle) and the relevant tuple is in the list L2, C randomly outputs T = lP ∈ G1 (l ∈ RZq∗) as the answer; after that, C stores (vt, li, Ppub, l, T) in L2, otherwise, C returns T = bP ∈ G1 and stores (vt, li, Ppub,-,T) in L2.Partial private key queries: for a partial private key query for identityIDi. C calculates Ri = riP, Di = ri + his (ri ∈ RZq∗) and returns Di and stores (IDi, ri, Ri, Di, -, -) in the list L3.Public key queries: for a public key query for identityIDi, if it is not the θ-th query, C calculates Pi = xiP (xi ∈ RZq∗) and finally returns PKi = (Ri, Pi) and updates L3 with (IDi, ri, Ri, Di, xi, Pi); otherwise, C returns PKi = (Ri, Pi⟵aP) and updates L3 with (IDi, ri, Ri, Di, -, Pi).Signature queries:A2 issues a multisignature query for message vt. If it is not the θ-th query, C runs the multisignature algorithm to output a result; otherwise, C signs vt with the sequence N1⟶N2⟶…⟶Nn. Firstly, C calculates for N1 as follows:(17)l1=H1ID1,L,P1,R1,vt,T=H2vt,L,Ppub,σ1=SIGN1=l1lP1+D1lP,whereσ1 is the partial signature of vt for N1. Then, C calculates for Ni (i ∈ {1, 2, …, n}) relevant to vt,σi−1 as follows:(18)lj=H1IDj,L,Pj,Rj,vt,hj=H0IDj,Rj,1≤j≤i−1,T=H2vt,L,Ppub.Ifeσi−1,P=eT,∑j=1i−1ljPj+Rj+hjPpub holds, C calculates for Ni as follows: li=H1IDi,L,Pi,Ri,vt, σi=σi−1+SIGNi=σi−1+lilPi+DilP. C calculates σn=∑i=1nSIGNi and returns σ=σ1,σ2,…,σd.Combination queries:A2 issues a combination query. For the local coding vector α=α1,…,αm, global vector β=β1,…,βm and message vector w1,w2,…,wm, C combines the message vector w=∑i=1mαiwi. Then, the message vector is also denoted as w=∑j=1mβjvj, and the signature corresponding to w is σj=∑i=1mσi,jαi, where σi, j (1 ≤ i ≤ m and 1 ≤ j ≤ l) denotes the j-th element of σi. Finally, C outputs a combined signature σ=∏i=1mσiαi.Verification queries: for a verification query,C runs the verification algorithm and returns a result if it is not the θ-th query; otherwise, C calculates li=H1IDi,L,Pi,Ri,vt (1 ≤ i ≤ n) and T=H2vt,L,Ppub. If eσn,P=eT,∑i=1nliPi+Ri+hiPpub holds, C returns σ and ⊥ otherwise.
Finally,A2 outputs a forgery signature σ∗. In queries, A2 cannot query the secret value of IDi, and σ∗ is not returned by signature oracle. If it is not the θ-th query, C fails and aborts the game; otherwise, C calls the H0, H1, and H2 oracles and then searches the list L3 and then verifies as follows:(19)eσn∗,P=eT∗,∑i=1nli∗Pi∗+Ri∗+hi∗Ppub=ebP,∑i=1nli∗Pi∗+Ri∗+hi∗P=e∑i=1nli∗abP+ri∗bP+hi∗sbP,P.
CDH problem solution can be obtained from equation (19):(20)σn∗=∑i=1nli∗abP+ri∗bP+hi∗sbP,⇒abP=σn∗−∑i=1nri∗bP+hi∗sbP∑i=1nli∗.


### 6.2. Probability Analysis

Probability thatC succeeds in the above game is analyzed as follows. Here, we need to think about three events: E1 is the event that C does not abort the game. In E1, there exists one time not querying the target identity, and then, Pr [E1] ≥ 1/ls, where ls is the times of secret value query. E2 is the event that A2 successfully forge a signature. E2 denotes A2 wins in the game, then Pr[E2|E1] ≥ ε. E3 is the event that there exists at least one record of nontarget identity in successful forgery case. E3 at least occurs once time in n queries, then Pr [E3|E1∧E2] ≥ 1/n. Hence, the probability that C solves the CDH problem is(21)ε′=PrE1∧E2∧E3=PrE1⋅PrE2|E1PrE3|E1∧E2≥εn⋅ls.Theorem 3.
Our NC-CLMSS can prevent the pollution attacks in the multisource network coding environment.Proof.
In NC-CLMSS, the signature process takes place at the source node and intermediate node. For the source node, the attacker can capture any node in the network and uses it to launch the attacks; this node sends the polluted information to the next node, but it is equivalent to solving the elliptic curve discrete logarithm (ECDL) problem for the attacker obtaining the signer private key from the public key. For the intermediate nodes, the attacker captures the signature from source node and tries to forge a signature; then, the attacker must own the user private key, and it is also equivalent to solving the ECDL problem.
NC-CLMSS can resist the pollution attacks in the network-coding environment because solving the ECDL problem is computationally infeasible.


## 6.1. Probability Estimation

Probability thatC succeeds in the above-mentioned game is estimated as follows. Here, it is necessary to think about three events:E1 is the event that C does not abort the gameE2 is the event that A1 successfully forge a signatureE3 is the event that there exists at least one record of nontarget identity in successful forgery caseInE1, there exists one time not querying the target identity, and then, Pr [E1] ≥ 1/(ls + lr), where ls is the times of secret value query and lr is the query times of public key replacement, E2 denotes that A1 wins in the game, then Pr [E2|E1] ≥ ε, and E3 at least occurs once time in n queries, then Pr [E3|E1∧E2] ≥ 1/n. Hence, the success probability that C solves the CDH problem is(16)ε′=PrE1∧E2∧E3=PrE1⋅PrE2|E1PrE3|E1∧E2≥εn⋅ls+lr.Theorem 2.
In the RO model, if the polynomial time adversaryA2 can break the UF-CMA-II security of NC-CLMSS, a challenge algorithm C must be able to solve the CDH problem.Proof.
C receives a random instance (P, aP, bP) ∈ G1 of CDH problem, and its aim is to utilize A2 (the subroutine of C) to determine the value of abP ∈ G1. C maintains the initially empty lists L0, L1, L2, and L3 to save the query-answer values of several oracles. Firstly, OCsetupρ⟶μ,sA2. Then, A2 adaptively performs the polynomial time queries as below:H0 queries: for an H0 query, if (IDi, Ri, hi) is in the list L0, C returns hi; otherwise, C returns hi ∈ RZq∗ and stores (IDi, Ri, hi) in L0.H1 queries: for an H1 query, if the matching tuple is in the list L1, C returns li; otherwise, C returns li ∈ RZq∗ and stores (IDi, L, Pi, Ri, vt, li) in L1.H2 queries: for an H2 query, if it is not the θ-th query (θ ∈ {1, 2, …,q0} (q0 is the query times relevant to H0 oracle) and the relevant tuple is in the list L2, C randomly outputs T = lP ∈ G1 (l ∈ RZq∗) as the answer; after that, C stores (vt, li, Ppub, l, T) in L2, otherwise, C returns T = bP ∈ G1 and stores (vt, li, Ppub,-,T) in L2.Partial private key queries: for a partial private key query for identityIDi. C calculates Ri = riP, Di = ri + his (ri ∈ RZq∗) and returns Di and stores (IDi, ri, Ri, Di, -, -) in the list L3.Public key queries: for a public key query for identityIDi, if it is not the θ-th query, C calculates Pi = xiP (xi ∈ RZq∗) and finally returns PKi = (Ri, Pi) and updates L3 with (IDi, ri, Ri, Di, xi, Pi); otherwise, C returns PKi = (Ri, Pi⟵aP) and updates L3 with (IDi, ri, Ri, Di, -, Pi).Signature queries:A2 issues a multisignature query for message vt. If it is not the θ-th query, C runs the multisignature algorithm to output a result; otherwise, C signs vt with the sequence N1⟶N2⟶…⟶Nn. Firstly, C calculates for N1 as follows:(17)l1=H1ID1,L,P1,R1,vt,T=H2vt,L,Ppub,σ1=SIGN1=l1lP1+D1lP,whereσ1 is the partial signature of vt for N1. Then, C calculates for Ni (i ∈ {1, 2, …, n}) relevant to vt,σi−1 as follows:(18)lj=H1IDj,L,Pj,Rj,vt,hj=H0IDj,Rj,1≤j≤i−1,T=H2vt,L,Ppub.Ifeσi−1,P=eT,∑j=1i−1ljPj+Rj+hjPpub holds, C calculates for Ni as follows: li=H1IDi,L,Pi,Ri,vt, σi=σi−1+SIGNi=σi−1+lilPi+DilP. C calculates σn=∑i=1nSIGNi and returns σ=σ1,σ2,…,σd.Combination queries:A2 issues a combination query. For the local coding vector α=α1,…,αm, global vector β=β1,…,βm and message vector w1,w2,…,wm, C combines the message vector w=∑i=1mαiwi. Then, the message vector is also denoted as w=∑j=1mβjvj, and the signature corresponding to w is σj=∑i=1mσi,jαi, where σi, j (1 ≤ i ≤ m and 1 ≤ j ≤ l) denotes the j-th element of σi. Finally, C outputs a combined signature σ=∏i=1mσiαi.Verification queries: for a verification query,C runs the verification algorithm and returns a result if it is not the θ-th query; otherwise, C calculates li=H1IDi,L,Pi,Ri,vt (1 ≤ i ≤ n) and T=H2vt,L,Ppub. If eσn,P=eT,∑i=1nliPi+Ri+hiPpub holds, C returns σ and ⊥ otherwise.
Finally,A2 outputs a forgery signature σ∗. In queries, A2 cannot query the secret value of IDi, and σ∗ is not returned by signature oracle. If it is not the θ-th query, C fails and aborts the game; otherwise, C calls the H0, H1, and H2 oracles and then searches the list L3 and then verifies as follows:(19)eσn∗,P=eT∗,∑i=1nli∗Pi∗+Ri∗+hi∗Ppub=ebP,∑i=1nli∗Pi∗+Ri∗+hi∗P=e∑i=1nli∗abP+ri∗bP+hi∗sbP,P.
CDH problem solution can be obtained from equation (19):(20)σn∗=∑i=1nli∗abP+ri∗bP+hi∗sbP,⇒abP=σn∗−∑i=1nri∗bP+hi∗sbP∑i=1nli∗.


## 6.2. Probability Analysis

Probability thatC succeeds in the above game is analyzed as follows. Here, we need to think about three events: E1 is the event that C does not abort the game. In E1, there exists one time not querying the target identity, and then, Pr [E1] ≥ 1/ls, where ls is the times of secret value query. E2 is the event that A2 successfully forge a signature. E2 denotes A2 wins in the game, then Pr[E2|E1] ≥ ε. E3 is the event that there exists at least one record of nontarget identity in successful forgery case. E3 at least occurs once time in n queries, then Pr [E3|E1∧E2] ≥ 1/n. Hence, the probability that C solves the CDH problem is(21)ε′=PrE1∧E2∧E3=PrE1⋅PrE2|E1PrE3|E1∧E2≥εn⋅ls.Theorem 3.
Our NC-CLMSS can prevent the pollution attacks in the multisource network coding environment.Proof.
In NC-CLMSS, the signature process takes place at the source node and intermediate node. For the source node, the attacker can capture any node in the network and uses it to launch the attacks; this node sends the polluted information to the next node, but it is equivalent to solving the elliptic curve discrete logarithm (ECDL) problem for the attacker obtaining the signer private key from the public key. For the intermediate nodes, the attacker captures the signature from source node and tries to forge a signature; then, the attacker must own the user private key, and it is also equivalent to solving the ECDL problem.
NC-CLMSS can resist the pollution attacks in the network-coding environment because solving the ECDL problem is computationally infeasible.


## 7. Performance Analysis

In this section, the performance comparison is made between NC-CLMSS and existing schemes in [19–21] based on the computational complexity. Schemes in [19–21] cannot resist the pollution attacks; the schemes in [20, 21] are not sequential multisignature. Our NC-CLMSS is a sequential multisignature and can resist pollution attacks. Table 2 describes the time complexity of main cryptography operations. Experimental environment for the performance analysis in this section: the processor is Intel (R) Core (TM) i7-6700HQ CPU @2.60GHz; the system type is the 64-bit operating system. Based on this system, we use C programming language, PBC library, and OpenSSL program to obtain the cryptography operation time, as shown in Table 2.Table 2
The time complexity of cryptographic operations.
Cryptographic operationsOperation time (ms)Time to perform an exponential operation:Cme7.5Time to perform a scalar multiplication:Cmul1.56Time to perform a hash operation:Cmtp17.2Time to perform a bilinear operation:Cpar19.7Table3 describes the computational efficiency of several schemes. From Table 3, the computational complexity of NC-CLMSS is relatively lower than other schemes in [19–21].Table 3
Computational efficiency comparison of several schemes.
ReferencesSignature time (ms)Verification time (ms)Total time (ms)Xu and Wang scheme3nCmtp + 2nCmul + 2nCpar3nCmtp + 2nCpar6nCmtp + 2nCmul + 4nCparNiu et al. scheme(2n + 1) Cmtp + 2nCmul + 2nCpar(2n + 1) Cmtp + 3nCpar2 (2n + 1) Cmtp + 2nCmul + 5nCparTanwar et al. scheme3nCmtp + 4nCmul3nCmtp + 2nCmul6nCmtp + 6nCmulNC-CLMSS(2n + 1) Cmtp + 2nCmul + 2nCpar(2n + 1) Cmtp + 2nCpar2 (2n + 1) Cmtp + 2nCmul + 4nCparSimulation curves of signature time-consuming of comparison schemes are shown in Figure3. Simulation curves of verification time-consuming comparison are shown in Figure 4. Simulation curves of total algorithm time comparison are shown in Figure 5. Assume the number n of signature members is 10, 20, 30, 40, 50, and 60, respectively. Experiment results show the running time of different schemes increases linearly with the increase of the number of signed members. As shown in Figure 3, in the signature phase, the growth rate of NC-CLMSS is relatively slower than other schemes. From Figure 4, the computational efficiency of NC-CLMSS is the highest. In terms of total time in Figure 5, NC-CLMSS takes the least time. Hence, NC-CLMSS is a relatively better cryptography algorithm in several schemes.Figure 3
Comparison of the signature time.Figure 4
Comparison of the verification time.Figure 5
Total time comparison of several schemes.


## 8. Summary

Network encoding cryptography has many merits, but there exists the inevitable problem how to resist the pollution attacks and forgery attacks in the message transmission process. By using the techniques of the certificateless multisignature and multisource network coding cryptosystem, we construct a certificateless multisignature scheme suitable for network coding (NC-CLMSS). Under the ECDL and CDH assumptions, this algorithm is proved to satisfy the UF-CMA security and can resist the pollution attacks; its computational complexity is relatively lower.



---

*Source: 1609873-2021-11-16.xml*