Huifang YU,Zhewei QI

School of Cyberspace Security,Xi’an University of Posts and Telecommunications,Xi’an 710121,China

?E-mail:yuhuifang@xupt.edu.cn

Abstract:Network coding can save wireless network resources and is very fast in comparison with traditional routing.In real application scenarios,network coding is vulnerable to pollution attacks and forgery attacks.To solve these problems,the certificateless broadcast multi-signature for network coding (NC-CLBMS) method is devised,where each source node user generates a multisignature about the message vector,and the intermediate node linearly combines the received data.NC-CLBMS is a multi-source multi-signature method with anti-pollution and anti-forgery advantages;moreover,it has a fixed signature length and its computation efficiency is very high.NC-CLBMS has extensive application prospects in unmanned aerial vehicle (UAV) communication networks,fifth-generation wireless networks,wireless sensor networks,mobile wireless networks,and Internet of Vehicles.

Key words:Network coding;Certificateless multi-signature;Linear combination;Homomorphic hash function

1 Introduction

Traditional routing technology is unable to satisfy the increasing demand for network communication.Improving network utilization and efficiency with limited network resources has become the key problem in the field of information theory research.

In theory,network coding (Ahlswede et al.,2000) can make actual network transmission reach the maximum capacity.Network coding can improve transmission reliability (Li P et al.,2012;Papailiopoulos et al.,2012),network transmission efficiency (Li ZP et al.,2009),and network robustness (Al-Kofahi and Kamal,2009) because of integrating coding and routing.Traditional routing technology allows only intermediate nodes to save and forward received data.Network coding can use the intermediate nodes to combine and encode the received data packets,and improve the overall network performance.However,network coding also has many security problems.Its unique topology (Xu J et al.,2016) makes it more vulnerable to pollution attacks.Malicious nodes can tamper with or forge data information;if this data is used for encoding with other unpolluted data,the polluted messages will spread to an entire network and cause unnecessary losses.

Scholars have devised some secure network coding schemes to handle security problems,such as elliptic curve encryption for network coding (Wang L et al.,2019) and network coding signature schemes(Peng et al.,2015;Li SH and Mei,2016;Wang HP and Mei,2016;Zhou and Xu,2016;Wang L et al.,2019;Yu and Li,2019,2020;Niu et al.,2020;Xu CD and Wang,2021;Yu and Wang,2021).In the network coding environment,the intermediate nodes combine and encode the information data and send the combination result to downstream nodes.The validity of the traditional signature is destroyed when the intermediate nodes encode the data.

The followings are the characteristics of broadcast multi-signature: (1) the signature length has nothing to do with the number of users;(2) the public key is used to verify the signature;(3) signers sign the messages out of sequence to obtain valid multi-signature;(4) it is impossible to obtain valid multi-signature without all signers working together.Until now,there is no certificateless multi-source broadcast multisignature scheme,because the traditional certificateless broadcast multi-signature cannot be directly used in network coding.The construction of the secure network coding scheme is an open problem.

In this work,we construct a certificateless broadcast multi-signature for network coding (NC-CLBMS)method,in which each source node outputs a final broadcast multi-signature result and the intermediate node linearly combines the data information from different links to transfer the combination result to downstream nodes.NC-CLBMS creates multi-source multi-signatures that are out of sequence and the signature length is fixed.The hash function in this scheme can ensure the homomorphism of the signature process.NC-CLBMS is helpful when multiple users need to sign the same message,and can resist pollution and forgery attacks.

2 Preliminaries

2.1 Notations

Notations and their meanings are described in Table 1.

Table 1 Symbols and their meanings

2.2 Multi-source transmission model

Multi-source network coding (Yu and Gao,2019)can use node computing power to improve network bandwidth utilization.Multi-source nodes are essential in the transmission model as shown in Fig.1.The multi-source network is viewed as an acyclic directed graphG=(M,E),whereEis the edge set andMis the node set.In the multi-source network,the set of source nodes isu={u1,u1,…,um}∈M,and the set of sink nodes isd={d1,d1,…,dm}∈M.

Fig.1 Multi-source transmission network model

Any destination node can receivemlinearly independent(w1,w2,…,wm),wherewi(i=1,2,…,m)are denoted as

Because the matrixXis invertible and of full rank,the original message can be obtained after decoding as follows:

2.3 Bilinear pairing

3 Formation definition

3.1 Algorithm definition

NC-CLBMS is defined by six polynomial time algorithms as follows:

Setup: Input the security parameter 1ρ,and this algorithm outputs the system parameter setμand master keys.

KeyGen: Input (μ,IDi),and this algorithm outputs the user’s public-private pair (Yi,xi),where IDiis the user’s identity.

Extract: Input(μ,IDi,s),and this algorithm outputs the partial private keydiof the user.

MultiSIG: Input(μ,{ID1,ID2,…,IDn},xi,di),and this algorithm outputs a multi-signatureci.

Combine:Input (ci,vi),and this algorithm outputs a combination resultγ.

Verification:Input (μ,ci,vi,γ),and this algorithm outputs a verification result.

3.2 Security model

NC-CLBMS must be unforgeable against the adaptive chosen message attacks (UF-CMAs).The UF-CMA security model relies on Game1 and Game2,whereA1cannot obtain the master key but can change any public key,andA2knows the master key but cannot change any public key.

Finally,A1(A2) wins in Game1 (Game2) if and only if the signature of IDiis valid.Here,A1cannot query a full private key of IDiwhose public key cannot be replaced,and forgery signature is not returned by multi-signature oracle fromA1(A2).

Advantage ofA1(A2) is the probability thatA1(A2)succeeds in Game1(Game2).

Definition 2(Unforgeability) A NC-CLBMS scheme is said to be UF-CMA secure if noA1(resp.A2)can win in Game1(resp.Game2)with a non-negligible advantage.

4 Concrete NC-CLBMS

4.1 Setup

4.2 KeyGen

The user with identity IDirandomly chooses a secret valuexi∈and calculates the public keyYi=xiP.

4.3 Extract

4.4 MultiSIG

4.5 Combine

4.6 Verification

5 Correctness analysis

6 Security analysis

6.1 Anti-forgery attacks

Then,CusesA1to solve the CDH problem as follows:

Probability analysis: Advantageε'of the CDH problem under forgery attacks is equal to the probability of simultaneous occurrence of three events as follows:

E1:Ccannot fail and abort the game.

E2:A1successfully forges a multi-signature and Pr[E2|E1]≥ε.

E3:There exists at least one record of non-target identity in a successful forgery case.

As described in Theorem 1,we can obtain

IfA1can break the UF-CMA-I security of NC-CLBMS with advantageε,Ccan solve the CDH problem with advantageε',where

Theorem 2(Unforgeability-II) If an attackerA2can break the UF-CMA-II security with advantageεin a random oracle model,a challengerCcan solve the CDH problem with advantageε′≥ε/(neqs),whereqsis the query time to secret value oracle.

ProofAssume that the remainingn-1 users are corrupted except IDi,where there arenusers in NCCLBMS and IDi∈{ }ID1,ID2,…,IDn.Cis a challenger to the CDH problem instance (P,aP,bP)∈G1and its aim is to useA2to obtainabP∈G1.Initially,empty listsL0,L1,andL2record various query-answer values fromA2.IDτis the target identity,τ∈{1,2,…,δ},andδis the query time toH0oracle.

CusesA2to successfully solve the CDH problem,and the solution to the CDH problem is as follows:

Probability analysis: Advantageε'of the CDH problem under forgery attacks is equal to the probability of simultaneous occurrence of three events as follows:

E1:Ccannot fail and terminate the game.

E2:A2successfully forges a multi-signature and Pr[E2|E1]≥ε.

E3: There exists at least one record of the nontarget identity in a successful forgery case.

As described in Theorem 2,we can obtain

IfA2can break the UF-CMA-II security of NCCLBMS with advantageε,Ccan solve the CDH problem with advantageε',where

6.2 Anti-pollution attacks

Theorem 3NC-CLBMS can resist the pollution attacks in a multi-source network coding environment.

ProofIn a multi-source multi-signature,there are two kinds of pollution attacks: one is to generate the forged message;the other is to obtain a forged signature based on the combination result intercepted by the attacker.

In the first attack,the attacker pollutes the source node,the intermediate node receives the message to directly forge the message to transfer in the network,and the intermediate node combines the polluted message:w'=However,the attack is invalid because the attacker cannot effectively sign the tainted message without a private key of signer.

Obtaining,ands'from the above equations is equivalent to solving the elliptic curve discrete logarithm(ECDL)problem.

7 Efficiency analysis

In terms of computational complexity,we compare NC-CLBMS with ZX (Zhou and Xu,2016),YG(Yu and Gao,2019),WZZ (Wang L et al.,2019),YL(Yu and Li,2019),and YW (Yu and Wang,2021).The test platform is as follows:

Operating system: Win10,64-bit;CPU: Intel?CoreTMi5-8250U,1.8 GHz;memory:4 GB;operating platform:Matlab2016a.

Table 2 shows each cryptographic operation time.Table 3 shows the signature time and verification time of several schemes.

Table 2 Operation time of cryptographic algorithms

Comparison of the signature time and verification time of several schemes is as follows.The operation time of the hash function is ignored in the analysis.NC-CLBMS,YL,and YW are based on the certificateless cryptosystem,and they can resist the pollution attacks and forgery attacks;ZX,YG,and WZZ are not based on the certificateless cryptosystem and cannot resist the forgery attacks.

As shown in Table 3,there are many exponential operations in signature and verification algorithms of ZX,YG,WZZ,YL,and YW;thus,they result in the consumption of storage resources;NC-CLBMS uses only 2Cpar,but YL uses 3Cpar;in addition,NCCLBMS does not need any modular exponentiation operation.Simulation curves of the signature time are shown in Fig.2.Simulation curves of the verification time are shown in Fig.3.Known from simulation results in Figs.2 and 3,with the increase of the message vector dimension,the growth rate ofNC-CLBMS is lower than those of other schemes.Hence,NC-CLBMS is more efficient than other schemes.

Fig.2 Signature time of NC-CLBMS and other schemes

Fig.3 Verification time of NC-CLBMS and other schemes

Table 3 Comparison of computational efficiency of several schemes

8 Summary

NC-CLBMS has the advantages of anti-pollution and anti-forgery,and its security relies on the hardness of the elliptic curve discrete logarithm and computational Diffie-Hellman problems.

The homomorphic hash function enables the node to ensure that thecsignature and verification processes are correct.NC-CLBMS is different from traditional signatures,which cannot be directly used in network coding.NC-CLBMS avoids the certificate use and key escrow,and its signature length is fixed.NC-CLBMS has strong robustness and low computation complexity,so it is suitable for applications in unmanned aerial vehicle (UAV) communication networks,wireless sensor networks,fifthgeneration wireless networks,Internet of Things,and wireless mesh networks.

Contributors

Huifang YU devised the NC-CLBMS method and analyzed its security.Zhewei QI processed the data and analyzed the efficiency.Huifang YU drafted the paper.Huifang YU and Zhewei QI revised and finalized this paper.

Compliance with ethics guidelines

Huifang YU and Zhewei QI declare that they have no conflict of interest.