# A Homomorphic Network Coding Signature Scheme for Multiple Sources and its Application in IoT

Authors: Tong Li; Wenbin Chen; Yi Tang; Hongyang Yan
Journal: Security and Communication Networks
 (2018)

---

## Abstract

As a method for increasing throughput and improving reliability of routing, network coding has been widely used in decentralized IoT systems. When files are shared in the system, network coding signature techniques can help authenticate whether a modified packet in files is injected or not. However, in an IoT system, there are often multiple source devices each of which has its own authentication key, where existing single-source network coding signature schemes cannot work. In this paper, we study the problem of designing secure network coding signatures in the network with multiple sources and propose the multisource homomorphic network coding signature. We also give construction and prove its security.


---

## Body

## 1. Introduction

With the rapid development of Internet and communication technologies, the Internet of Things (IoT) has emerged as a leading technology that brings convenience to our daily lives. More and more smart terminals are connected on the Internet, and files, logs, and other real-time contents are shared among these terminals all the times. According to a report of International Data Corporation (IDC), there will be nearly 28 billion installed IoT devices by 2020.Considering the scale of IoT’s expansion, it is very essential to increase its throughput in such a huge decentralized network. When a source device transmits a file to a set of target receivers, an effective way is to split the file intot data packets and send them to its neighbouring nodes by using the network coding technique. In the network coding, each intermediate node linearly combines packets rather than simply storing and forwarding the incoming packets. In other words, an intermediate node that receives a set of packets from its incoming links can modify them and send the modifications to other nodes through its outgoing edges. In some applications, either an ad hoc node or an intermediate device can play a role of an intermediate node. This linear network coding allows receivers to recover the original information with high probability if they collect sufficiently many correct packets. Thus, the throughput for sharing real-time contents in IoT is increased.However, security is one of the most important requirement of IoT systems, and IoT devices often interact with third-party applications. Without authenticate mechanisms, the inherent flaw of linear network coding would be disturbed by invalid packets injected by third-party applications. Intermediate nodes can later use the invalid incoming vectors in its output, which means that the errors are propagated subsequently and data receivers will not obtain the original information. As a result, adversaries could easily initiate a Denial of Service (DoS) attack to prevent the original file from being recovered. The main idea to mitigate attacks is to provide a way to authenticate valid packets, and Catalano et al. [1] proposed an efficient network coding signature scheme as a solution of the authentication problem. By verifying a modified signature of the corresponding modified packet, any device can easily know whether this packet is valid.Unfortunately, in an IoT system, origin data are usually collected from various sources (e.g., sensors) each of which could have its own signature for authentication. It is required that any (intermediate) receiver can perform the combination of incoming packets which are signed by different keys. As a drawback, trivially adopting the existing network coding has to generate signatures are linear in the numbert of the sources, and thus the signatures cannot be directly combined when packets are modified. Motivated by this problem, in this paper, we propose a multisource linearly homomorphic network coding signature scheme. The proposed scheme is extended from our previous work [2] and enables a multilayers routing network rather than a 3-layer one, which can be used to implement authentication for transmitting files in the IoT system.The rest of this paper is organized as follows. Section2 presents some related works. Section 3 overviews some definitions. In Section 4, we describe our multisource linearly homomorphic network coding signature scheme. Section 5 analyzes the correctness and security of the proposed scheme. In Section 6 we summarize the paper.


## 2. Related Works

In the traditional network routing, every node simply receives packets and forwards them to neighbour nodes. A routing method called network coding [3, 4] is proposed and developed for increasing throughput in the network. In the network coding, intermediate nodes combine received data packets and transit them and the data receiver still obtains the original data. This technique can be used in IoT applications and cloud systems for broadcast and transmission [5–19].In the single-source scenario, some schemes were proposed to make sure that there is always a recipient bound to the corresponding for authentication. M. Krohn et al. introduced the homomorphic hash function [20, 21] and extended it to network coding. The linearly homomorphic signature is a more effective authentication for the network coding. Reference [22] proposed the first linearly homomorphic signature scheme. Reference [23–25] found some security flaw and errors, and Yu et al. [26] gave a construction by combining the RSA-based signature with the homomorphic hash function. Reference [27, 28] designed signature schemes for peer-to-peer networks and distributed contents respectively. Reference [29, 30] proposed homomorphic network coding signature schemes based on the bilinear mapping and RSA assumption respectively. In [31], Boneh et al. designed a signature scheme with the property of signing unlimited number of messages. Based on the complexity of lattice problems, [32] introduced the k-SIS problem and constructed a signature scheme over binary fields. For a fine-grain access control, [33, 34] proposed schemes based on the identity-based signature. The schemes above are proven secure in the random oracle model. In the standard model, some homomorphic network coding signature schemes were proposed [1, 34–36]. The security of the scheme in [35] is based on the discrete logarithm assumption. Independent of these works, [37] proposed a method that transforms standard signature schemes to linearly homomorphic signatures in the standard model.However, in a multisource case which is the common scenario in the IoT system, there is still no linearly homomorphic network coding signature scheme. Our goal is to design a multisource linearly homomorphic network coding signature scheme.


## 3. Preliminaries

Then, we show some definitions of the linearly homomorphic network coding signature as follows.Definition 1 (linearly homomorphic network coding signatures adapted from [1]).
A linearly homomorphic network coding signature schemeLS consists of a tuple of probabilistic, polynomial-time algorithms (NetKG,NetSign,NetVer,NetEval) with the following functionality.
NetKG ( 1 λ , m , n ) → ( p k , s k ). Given the security parameter λ and m,n, this algorithm outputs a key pair (sk,pk), where sk is the secret key and pk is the public verification key. Note that m is the dimension of the vector spaces and n+m is an upper bound to the size of the signed vectors.
NetSign ( s k , I d , w ) → σ. The signing algorithm takes a secret key sk, a file identifier Id∈Fp and a vector w∈Fpn+m as input and then outputs a signature σ.
NetVer ( p k , I d , w , σ ) → a c c e p t. Given the public key pk, a file identifier Id, a vector w∈Fpn+m, and a signature σ, the algorithm outputs a bit accept represents accept or reject.NetEval(pk,Id,{(wi,αi,σi)}i=1μ)→σ. Given a public key pk, a file identifier Id, and a set of tuples (wi,αi,σi), this algorithm outputs a new signature σ such that if each σi is a valid signature on vector wi, then σ is a valid signature for w obtained from the linear combination ∑i=1μ‍αiwi.Forcorrectness, it is required that if the key pair (sk,pk) is output by NetKG(1λ,m,n), then(i)
letId∈Fp and w∈Fpn+m; if σ←NetSign(sk,Id,w), thenNetVer(pk,Id,w,σ)=1;(ii)
for allId, any t>0 and all sets of triples {(wi,αi,σi)}i=1μ; ifNetVer(pk,Id,wi,σi)=1 for all i, thenNetVer(pk,Id,∑i=1μ‍αiwi and NetEval(pk,Id,{(wi,αi,σi)}i=1μ))=1.The definition of unforgeability of linearly homomorphic signature is presented as follows.Definition 2 (unforgeability adapted from [32]).
For a linearly homomorphic network coding signature schemeLS=(NetKG, NetSign,NetVer,NetEval), the following game is considered.Setup: The challenger runs NetKG(1λ,m,n) to obtain (sk,pk) and gives pk to A.Queries: Proceeding adaptively, A specifies a sequence of data sets wi. For each i, the challenger chooses Idi uniformly from Fp and gives to A the tag Idi and the signatures σij←NetSign(sk,Idi,wij) for j=1,…,k.Output: A outputs a file identifier Id∗, a message m∗, and a signature σ∗. The adversary wins if NetVer(pk,Id∗,w∗,σ∗)=1, and either (1) Id∗≠Idi for all i or (2) Id∗=Idi for some i but w∗∉span(wi), where span(wi) is the subspace generated by all wi.The advantage ofA is defined to be the probability that A wins the security game. LS is called unforgeable if for any PPT adversary A, the advantage in the game is negligible in λ.Lete:G×G′→GT be a bilinear map, where G,G′ and GT are bilinear groups of prime order p. In [38], Boneh and Boyen introduced the definition of the q-Strong Diffie-Hellman Assumption (q-SDH for short).Definition 3 (q-SDH assumption [38]).
Letk∈N be the security parameter, p>2λ be a prime, and G,G′,GT be bilinear groups of prime order p. Let g be a generator of G and g′ be a generator of G′, respectively. Then we say that the q-SDH Assumption holds in G,G′,GT if for any PPT algorithm A and any q = poly(k), the following probability is negligible in λ:(1)PrAg,gx,gx2,…,gxq,g′,g′x=c,g1/x+c≤neglλ


## 4. The Proposed Scheme

### 4.1. Architecture

Consider an application in practical. A log report of some intelligent terminals is supposed to be jointly published via the linear network coding. To prevent the injection of invalid data packets and make the transmission reliable, each data packet should be suffixed with a valid recipient before forwarding. A network coding signature scheme can help to meet this requirement when all terminal devices have the same key used for signing packets. However, if each device has its own key, a group of signatures cannot be directly combined for the corresponding packets. As a solution for the verification problem, we present this homomorphic network coding signature scheme for multiple sources.An architecture is shown in Figure1. A terminal device can be seen as a source, while the receiver wants to get the log report with a correct recipient. Each entity in the scheme is described as follows:(i)
Source nodes. After some parameters are generated as public information, the ith source node generates its own key pair (pki,ski) for signing and verifying. Each node has a part of the original file, and the part can be seen as a data packet. To obtain a signature σ, the ith node signs its packet that belongs to the file with an identifier Id using ski. Then, it sends the signed tuple (Id,w,σ) on its outgoing edges.(ii)
Intermediate nodes. When an intermediate node receives some packets with the corresponding signatures, it checks whether any one is not valid. Then, it selects μ coefficients for the rest valid packets w1,…,wμ, and combines the packets and their signatures, respectively. Finally, the combined tuple is forwarded on the outgoing edges.(iii)
Receiver. Once the receiver has collected Id file’s packets signed by using all t secret keys, it checks the validity and recovers the original file if the check is passed.Figure 1
Architecture of the proposed scheme.


### 4.2. Scheme Description

In this section, we present our construction of the multisource homomorphic network coding signature scheme. There aret devices as source nodes, any number of intermediate nodes, and several receivers. For simplicity, we assume that each source node holds and forwards a packet of a file. The whole file can be represented as a augmented vector set w={w1,…,wt}, of which the ith packet can be represented as w(i)=(u1(i),…,um(i),v1(i),…,vn(i)). Each packet belongs to a file with the ID Id and some of the packets are encoded together with the same Id.As described above, each source node has its own key pair in the system. For theith source, its private key is used to sign w(i) so that the signed packets can be verified by intermediate nodes which receive the signatures. After receiving several input packets, an intermediate node firstly checks each packet and discards all the packets that cannot pass the check. With a signature σ, the corresponding packet can be verified even though it is linear combinations of vectors originated from different sources. Then, using random or established coefficients, the node makes linear combinations of the remaining data packets and produces a signature for the encoded packet based on the received signatures without accessing the private keys. Briefly, an adversary’s attack is successful if it can generate a forged data packet (Id∗,w∗,σ∗) that makes verification algorithm output 1 using public keys, while either Id∗ is an invalid file ID or Id∗ is valid but w∗ is not in the domain of files.Then, we describe the algorithms of a multisource homomorphic network coding signature scheme based on the signature scheme CFW in [1] as follows:Public System Parameters ( λ ) → p a r a m. Choose a bilinear map e: G×G′→GT, where G,G′,GT are bilinear groups of prime order p>2λ, while g is a generator of G and g′ is a generator of G′. Randomly choose elements h,h1,…,hn,g1,…,gm from G. The algorithm outputs system parameters param=(p,g,g′,h,h1,…,hn,g1,…,gm) as public.NetKG ( i , m , n ) → ( p k i , s k i ). This algorithm is run by each ith source node for setting up its own key pair. The ith source node randomly chooses ai∈Fp to set its private key as ski=ai and public key as ki=Pi=(g′)ai. The algorithm outputs the key pair (pki,ski).NetSign ( s k i , I d , w ( i ) ) → σ. Each ith source node signs its data packet as if in the single-source signature scheme CFW, but their secret key is different. For the packet vector w(i)=(u1(i),…,um(i),v1(i),…,vn(i))∈Fpm+n, the ith source computes its signature as follows:(i)
LetId∈Fp∗ and si∈Fp;(ii)
ComputeXi=(hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id and output its signature σ=(X(1),…,X(i),…,X(t),s), where Xi′=1 for each i′≠i.Note that, for theith source node, the rest packets in w={w(1),…,w(t)} other than w(i) are all set as zero vectors before forwarding.NetEval ( I d , { w j , α j , σ j } j = 1 μ ) → σ. If an intermediate node has received μ valid packet sets wj=(uj,1(i),…,uj,m(i),vj,1(i),…,vj,n(i)) from the same Id, of which signature is σj=(Xj1,…,Xj(t),sj). Each coefficient αj∈Fp is determined by the intermediate node. The combined signature of this node is also a t+1-dimension vector σ=(X(1),…,X(t),s), where s=∑i=1t‍∑j=1μ‍αjsjmodp and each X(i)=∏j=1μ‍(Xj(i))αj. This algorithm outputs the combined signature σ. Then, the modified packet w is forwarded to other nodes along with its signature σ.NetVer ( { p k i } i = 1 t , I d , w , σ ) → a c c e p t. Taking public keys {pki}i=1t, file ID Id, data packet w, and the corresponding signature σ as input, the verification algorithm outputs1, if∏i=1t‍e(Xi,Pi(g′)Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′) and 0, otherwise.


## 4.1. Architecture

Consider an application in practical. A log report of some intelligent terminals is supposed to be jointly published via the linear network coding. To prevent the injection of invalid data packets and make the transmission reliable, each data packet should be suffixed with a valid recipient before forwarding. A network coding signature scheme can help to meet this requirement when all terminal devices have the same key used for signing packets. However, if each device has its own key, a group of signatures cannot be directly combined for the corresponding packets. As a solution for the verification problem, we present this homomorphic network coding signature scheme for multiple sources.An architecture is shown in Figure1. A terminal device can be seen as a source, while the receiver wants to get the log report with a correct recipient. Each entity in the scheme is described as follows:(i)
Source nodes. After some parameters are generated as public information, the ith source node generates its own key pair (pki,ski) for signing and verifying. Each node has a part of the original file, and the part can be seen as a data packet. To obtain a signature σ, the ith node signs its packet that belongs to the file with an identifier Id using ski. Then, it sends the signed tuple (Id,w,σ) on its outgoing edges.(ii)
Intermediate nodes. When an intermediate node receives some packets with the corresponding signatures, it checks whether any one is not valid. Then, it selects μ coefficients for the rest valid packets w1,…,wμ, and combines the packets and their signatures, respectively. Finally, the combined tuple is forwarded on the outgoing edges.(iii)
Receiver. Once the receiver has collected Id file’s packets signed by using all t secret keys, it checks the validity and recovers the original file if the check is passed.Figure 1
Architecture of the proposed scheme.


## 4.2. Scheme Description

In this section, we present our construction of the multisource homomorphic network coding signature scheme. There aret devices as source nodes, any number of intermediate nodes, and several receivers. For simplicity, we assume that each source node holds and forwards a packet of a file. The whole file can be represented as a augmented vector set w={w1,…,wt}, of which the ith packet can be represented as w(i)=(u1(i),…,um(i),v1(i),…,vn(i)). Each packet belongs to a file with the ID Id and some of the packets are encoded together with the same Id.As described above, each source node has its own key pair in the system. For theith source, its private key is used to sign w(i) so that the signed packets can be verified by intermediate nodes which receive the signatures. After receiving several input packets, an intermediate node firstly checks each packet and discards all the packets that cannot pass the check. With a signature σ, the corresponding packet can be verified even though it is linear combinations of vectors originated from different sources. Then, using random or established coefficients, the node makes linear combinations of the remaining data packets and produces a signature for the encoded packet based on the received signatures without accessing the private keys. Briefly, an adversary’s attack is successful if it can generate a forged data packet (Id∗,w∗,σ∗) that makes verification algorithm output 1 using public keys, while either Id∗ is an invalid file ID or Id∗ is valid but w∗ is not in the domain of files.Then, we describe the algorithms of a multisource homomorphic network coding signature scheme based on the signature scheme CFW in [1] as follows:Public System Parameters ( λ ) → p a r a m. Choose a bilinear map e: G×G′→GT, where G,G′,GT are bilinear groups of prime order p>2λ, while g is a generator of G and g′ is a generator of G′. Randomly choose elements h,h1,…,hn,g1,…,gm from G. The algorithm outputs system parameters param=(p,g,g′,h,h1,…,hn,g1,…,gm) as public.NetKG ( i , m , n ) → ( p k i , s k i ). This algorithm is run by each ith source node for setting up its own key pair. The ith source node randomly chooses ai∈Fp to set its private key as ski=ai and public key as ki=Pi=(g′)ai. The algorithm outputs the key pair (pki,ski).NetSign ( s k i , I d , w ( i ) ) → σ. Each ith source node signs its data packet as if in the single-source signature scheme CFW, but their secret key is different. For the packet vector w(i)=(u1(i),…,um(i),v1(i),…,vn(i))∈Fpm+n, the ith source computes its signature as follows:(i)
LetId∈Fp∗ and si∈Fp;(ii)
ComputeXi=(hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id and output its signature σ=(X(1),…,X(i),…,X(t),s), where Xi′=1 for each i′≠i.Note that, for theith source node, the rest packets in w={w(1),…,w(t)} other than w(i) are all set as zero vectors before forwarding.NetEval ( I d , { w j , α j , σ j } j = 1 μ ) → σ. If an intermediate node has received μ valid packet sets wj=(uj,1(i),…,uj,m(i),vj,1(i),…,vj,n(i)) from the same Id, of which signature is σj=(Xj1,…,Xj(t),sj). Each coefficient αj∈Fp is determined by the intermediate node. The combined signature of this node is also a t+1-dimension vector σ=(X(1),…,X(t),s), where s=∑i=1t‍∑j=1μ‍αjsjmodp and each X(i)=∏j=1μ‍(Xj(i))αj. This algorithm outputs the combined signature σ. Then, the modified packet w is forwarded to other nodes along with its signature σ.NetVer ( { p k i } i = 1 t , I d , w , σ ) → a c c e p t. Taking public keys {pki}i=1t, file ID Id, data packet w, and the corresponding signature σ as input, the verification algorithm outputs1, if∏i=1t‍e(Xi,Pi(g′)Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′) and 0, otherwise.


## 5. Analysis

### 5.1. Correctness

According to the definition in Section3, we analyze the correctness of the proposed scheme.Theorem 4.
The proposed multisource homomorphic network coding signature scheme is correct.Proof.
For eachi∈{1,…,t}, the ith original vector is denoted as w(i)=(u1(i),…,um(i),v1(i),…,vn(i))∈Fpm+n. There is ∏i=1t‍e(Xi,Pi(g′)Id)=e(Xi,Pi(g′)Id)=e((hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id,(g′)ai+Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′). Thus, the verification result on a valid original signature σ is 1.
On the other hand, in a modified packet,w=∑j=1μ‍αjwj and s=∑i=1t‍∑j=1μ‍αjsjmodp. There is ∏i=1t‍e(Xi,Pi(g′)Id)=∏i=1t‍e((hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id,(g′)ai+Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′). Thus, The verification result on a combined signature σ is 1.
Therefore, algorithms in the proposed is correct.


### 5.2. Security

Then, we give the proof that the signatures in the scheme is unforgeable according to the definition in Section3.Theorem 5.
The proposed multisource homomorphic network coding signature scheme is secure under theq-SDH assumption.Proof.
If an adversary has a PPT algorithmB∗ which can forge the valid signature for a data packet, B∗ can be used to construct an efficient algorithm B to forge valid signatures the CFW signature scheme.
The public system parameters are chosen as follows:G,G′,GT are bilinear groups of prime order p>2λ and e is a bilinear map: G×G′→GT; g is a generator of G and g′ is a generator of G′; h,h1,…,hn,g1,…,gm are random factors.
The algorithmB∗ takes the public system parameters param, the public keys {pki} a valid identifier Id, and each packet w with its signature as input. According to the received data signed packets (Id, {wj,αj,σj}j=1μ), algorithm B∗ tries to output a forged signed packet (Id∗,{αj∗},w∗,σ∗) which makes verification algorithm output 1. That is, either Id∗≠Id or Id∗=Id and w∗≠∑‍αj∗wj.
Then, based onB∗ algorithm, we construct another PPT algorithm B which can produce a forged signature for packets in the CFW signature scheme.
We assume that the first-source node uses(a,P) as its private and public keys, i.e., sk1=a and pk1=P. Other t-1 source nodes whose private and public keys are generated as follows:(i)
Randomly selectt-1 numbers from Fp: x1,…,xt-1;(ii)
Set the private key of theith source ai=xi-1(a+Id)-Id and its public key Pi=(g′)ai;
Using theNetSign algorithm, each source node outputs its signature.
A forged signature packet(Id∗,{αj∗},w∗,σ∗) for CFW is output, where σ∗=(X(1)∗,…,X(t)∗,s∗) and s∗=∏j=1μ‍αj∗si∗modp.
It is easy to get(2)e∏i=1tXi∗,P·g′Id=eX1∗∏i=2tXi∗αi∗xi-1,P·g′Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗xi-1,P·g′Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,P·g′Idxi-1=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,P·g′Idxi-1=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,g′ai+Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,Pi·g′Id=e∏i=1tXi∗αi∗,Pi·g′Id=ehs∗∏j=1nhjuj∏j=1mgjvj,g′.
Since eitherId∗≠Id, or w∗≠∑‍αj∗wj, the forged signature is valid.
However, the CFW signature scheme is secure under q-SDH assumption. Therefore, the proposed multisource homomorphic network coding signature scheme is secure under theq-SDH assumption.


## 5.1. Correctness

According to the definition in Section3, we analyze the correctness of the proposed scheme.Theorem 4.
The proposed multisource homomorphic network coding signature scheme is correct.Proof.
For eachi∈{1,…,t}, the ith original vector is denoted as w(i)=(u1(i),…,um(i),v1(i),…,vn(i))∈Fpm+n. There is ∏i=1t‍e(Xi,Pi(g′)Id)=e(Xi,Pi(g′)Id)=e((hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id,(g′)ai+Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′). Thus, the verification result on a valid original signature σ is 1.
On the other hand, in a modified packet,w=∑j=1μ‍αjwj and s=∑i=1t‍∑j=1μ‍αjsjmodp. There is ∏i=1t‍e(Xi,Pi(g′)Id)=∏i=1t‍e((hsi∏j=1m‍hjuj∏j=1m‍gjvj)1/ai+Id,(g′)ai+Id)=e(hs∏j=1m‍hjuj∏j=1n‍gjvj,g′). Thus, The verification result on a combined signature σ is 1.
Therefore, algorithms in the proposed is correct.


## 5.2. Security

Then, we give the proof that the signatures in the scheme is unforgeable according to the definition in Section3.Theorem 5.
The proposed multisource homomorphic network coding signature scheme is secure under theq-SDH assumption.Proof.
If an adversary has a PPT algorithmB∗ which can forge the valid signature for a data packet, B∗ can be used to construct an efficient algorithm B to forge valid signatures the CFW signature scheme.
The public system parameters are chosen as follows:G,G′,GT are bilinear groups of prime order p>2λ and e is a bilinear map: G×G′→GT; g is a generator of G and g′ is a generator of G′; h,h1,…,hn,g1,…,gm are random factors.
The algorithmB∗ takes the public system parameters param, the public keys {pki} a valid identifier Id, and each packet w with its signature as input. According to the received data signed packets (Id, {wj,αj,σj}j=1μ), algorithm B∗ tries to output a forged signed packet (Id∗,{αj∗},w∗,σ∗) which makes verification algorithm output 1. That is, either Id∗≠Id or Id∗=Id and w∗≠∑‍αj∗wj.
Then, based onB∗ algorithm, we construct another PPT algorithm B which can produce a forged signature for packets in the CFW signature scheme.
We assume that the first-source node uses(a,P) as its private and public keys, i.e., sk1=a and pk1=P. Other t-1 source nodes whose private and public keys are generated as follows:(i)
Randomly selectt-1 numbers from Fp: x1,…,xt-1;(ii)
Set the private key of theith source ai=xi-1(a+Id)-Id and its public key Pi=(g′)ai;
Using theNetSign algorithm, each source node outputs its signature.
A forged signature packet(Id∗,{αj∗},w∗,σ∗) for CFW is output, where σ∗=(X(1)∗,…,X(t)∗,s∗) and s∗=∏j=1μ‍αj∗si∗modp.
It is easy to get(2)e∏i=1tXi∗,P·g′Id=eX1∗∏i=2tXi∗αi∗xi-1,P·g′Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗xi-1,P·g′Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,P·g′Idxi-1=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,P·g′Idxi-1=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,g′ai+Id=eX1∗α1∗,P·g′Id·e∏i=2tXi∗αi∗,Pi·g′Id=e∏i=1tXi∗αi∗,Pi·g′Id=ehs∗∏j=1nhjuj∏j=1mgjvj,g′.
Since eitherId∗≠Id, or w∗≠∑‍αj∗wj, the forged signature is valid.
However, the CFW signature scheme is secure under q-SDH assumption. Therefore, the proposed multisource homomorphic network coding signature scheme is secure under theq-SDH assumption.


## 6. Conclusion

In this paper, to give a solution for authentication of network coding, we propose the multisource homomorphic network coding signature in the standard model and show that the signature scheme is security underq-SDH assumption holds. The proposed scheme can effectively guarantee the availability in a multisource IoT system.



---

*Source: 9641273-2018-06-14.xml*