Dual-Homomorphic Message Authentication Code Scheme for Network Coding-Enabled Wireless Sensor Networks

Abstract

Network coding has shown a considerable improvement in terms of capacity and robustness compared to traditional store-and-forward transmission paradigm. However, since the intermediate nodes in network coding-enabled networks have the ability to change the packets en route, network coding-enabled networks are vulnerable to pollution attacks where a small number of polluted messages can corrupt bunches of legitimate messages. Recently, research effort has been put on schemes for protecting the transmitted messages against data pollution attacks. However, most of them cannot resist tag pollution attacks. This paper presents a new homomorphic MAC-based scheme, called Dual-Homomorphic MAC (Dual-HMAC), for network coding-enabled wireless sensor networks. The proposed scheme makes use of two types of tags (i.e., MACs and D-MACs) to provide resistance against data pollution attacks and partially tag pollution attacks. Furthermore, our proposed scheme presents low communication overhead and low computational complexity compared to other existing schemes.

1. Introduction

Wireless sensor networks (WSNs) have been recently used in a plethora of applications of many different areas, such as surveillance monitoring, environmental monitoring, traffic control, natural disaster prevention, and e-health. Due to their wide range of applications, they have already become so attractive to research community. However, WSNs are characterized by low communication bandwidth and power consumption constraints [1]. Thus, network coding (NC) can be a promising solution for WSNs, since it is a technique that can provide network capacity improvement [2] and lower energy consumption [3].

NC was introduced by Ahlswede et al. [2]. Nowadays, NC has been used in various applications over different networks, such as wireless mesh networks [4], wireless sensor networks [5], and peer-to-peer systems [6]. In contrast to traditional and classical commodity flow, where information is only routed or replicated, information flow can also employ coding operations at intermediate nodes. In [7], random linear network coding (RLNC) was studied as a fully distributed method for performing network coding. Also, in [7], it is mentioned that there is a possibility for each node in the network to select a set of coefficients independently and randomly and use them to make linear combinations of the data symbols.

However, NC is more susceptible to data pollution attack than the traditional store-and-forward approach. If a data pollution attack is not detected at the forwarders, then the sink nodes will not be able to recover the source messages correctly. It is worthwhile to mention that even a small number of polluted messages can infect a large number of downstream nodes because the pollution propagates via recoding. Furthermore, NC-enabled networks are also vulnerable to tag pollution attack, which is a more sophisticated type of pollution attack. In tag pollution attack, the adversary targets at modifying (i.e., polluting) the tags carried by the messages rather than modifying the content of the messages. It is possible for a message with polluted tags to travel multiple hops until it is detected and discarded. Yet, this results in a waste of network bandwidth.

Thus far, several cryptographic schemes such as homomorphic hash functions, signatures, and MACs have been presented to secure network coding against data and tag pollution attacks (e.g., [8, 9]). Furthermore, information-theoretic schemes have been also proposed (e.g., [10, 11]) to detect data pollution attacks. Although information-theoretic schemes are more efficient, in terms of computation, compared to the cryptographic schemes, they can only detect polluted packets at the sink nodes.

Among all the above mentioned proposed schemes, Homomorphic MAC is considered as a low-complexity solution against data pollution [12, 13]. Specifically, a MAC or tag is a small piece of information appended to the end of the message packet. This piece of information is the output of a MAC function taking as inputs the message packet and a secret key. However, this solution is vulnerable to tag pollution attacks.

In this paper, we propose a new homomorphic MAC-based scheme, called Dual-Homomorphic MAC (Dual-HMAC), for NC-enabled WSNs, in order to mitigate both data pollution attacks and partially tag pollution attacks. In our scheme, the source generates multiple MACs and Dual MACs (D-MACs) for each message. Each MAC ensures integrity of the transmitted message and each D-MAC ensures integrity of the MACs. In other words, by appending D-MACs, the proposed scheme mitigates partially tag pollution attacks.

The rest of the paper is outlined as follows. In Section 2, we give an overview of the related work on security schemes against data pollution attacks and tag pollution attacks in NC-enabled networks. In Section 3, the problem statement is discussed. In Section 4, our proposed Dual-HMAC scheme is presented. In Section 5, the security analysis of the proposed scheme takes place. In Section 6, its performance evaluation is given. In Section 7, a comparison among the communication and computation overhead of our work (i.e., Dual-HMAC) and the communication and computation overhead of the related works in [9, 14] is provided. Finally, Section 8 concludes the paper.

2. Related Work

In this section, we present related work on security schemes against pollution attacks in NC-enabled networks. In addition, we present the key distribution mechanisms used by these security schemes.

2.1. Security Schemes against Pollution Attacks in NC-Enabled Networks

Most of the research in the field of pollution attacks in network coding is focused on two types of security schemes: information-theoretic schemes [10, 11] and cryptographic schemes [14, 15].

2.1.1. Cryptographic Schemes

These schemes rely on additional verification information which is added by the sources through cryptographic techniques. This allows intermediate nodes to verify the original messages and filter out the polluted ones. This category includes the homomorphic hashing schemes, the homomorphic signature schemes, and the homomorphic MACs.

(a) Homomorphic Hashing Schemes. Homomorphic hashing schemes are based on a homomorphic hash function which is applied by the source to the messages. These schemes rely also on additional secure communication channels in order to transmit the calculated hash values to the intermediate nodes. A well-known homomorphic hashing scheme is proposed by Krohn et al. in [8] which enables the intermediate nodes to verify on-the-fly. The extension of this work was presented in [16] which is focused on network coding-enabled networks and further reduces the expensive computation cost of hash functions in each intermediate node by enabling cooperation verification.

(b) Homomorphic Signature Schemes. Homomorphic signature schemes were introduced for the first time by Charles et al. in [17] and have been based on Weil pairing over elliptic curves. The homomorphic property of the signatures in these schemes allows nodes to sign any linear combination of the incoming packets without contacting the signing entity. The calculation of signature covers the whole augmented message. In [18], Yu et al. proposed a homomorphic signature function which allows the relay nodes to verify the received messages by generating the signatures without contacting the signing entities. In Yu's scheme, the communication does not need any extra secure communication channel. Their experimental results show that its verification efficiency is improved up to 10 times compared to the other related work (i.e., CJLs scheme [17]). Moreover, in [10], an alternative lightweight scheme is proposed. It is much faster rather than Yu's scheme, but it is not as secure as the first one.

(c) Homomorphic MACs. Homomorphic MACs are based on appending some extra information to the original message. The basic definition of homomorphic MAC is defined by Agrawal and Boneh in [14] which allows the integrity checking of the network coded data. However, this idea is susceptible to tag pollution attacks. Kehdi and Baochun [19] presented a homomorphic MAC scheme to detect pollution attacks based on the subspace properties of random linear network coding, where null keys for verification are used. As a lot of null keys are used in each generation, a high bandwidth overhead can be incurred. The authors in [13] proposed an idea where the source attaches multiple MACs to each packet. This idea can be applied for XOR network coding networks; however it is vulnerable to tag pollution attacks. RIPPLE [20] was proposed to counteract against the tag pollution problem. This work is based on a symmetric key based scheme for network coding authentication. RIPPLE allows a node to efficiently detect corrupted packets and encode only the authenticated (i.e., verified) ones. However, the global synchronization among all nodes is the problem of this scheme. In [9], the authors presented a hybrid-key cryptography approach which could achieve authentication in the presence of both data and tag pollution attacks. To achieve this, a number of tags and a signature are appended to each transmitted message. However, the signature which is necessary for preventing tag pollution is a time consuming process.

2.1.2. Information-Theoretic Schemes

The information-theoretic schemes benefit from the reasonable computation performance in comparing to the cryptographic schemes, but they have two main drawbacks. First of all, they are not able to detect the polluted messages at the intermediate nodes of the network. For example, the work presented in [10], which extends the random network coding, relies on coding redundant information into the original messages allowing only the receivers to detect the polluted messages. Furthermore, the information-theoretic schemes are characterized by the limitation on the number of compromised nodes. These two drawbacks comprise the main motivation to interest to the cryptographic schemes.

2.2. Key Distribution Mechanisms in NC-Enabled Networks

Nowadays, in emerging multicast communication systems (e.g., pay TV and video-conferencing services), the key distribution is a challenging issue. There are various proposed schemes for key distribution in multicast systems. Key distribution models can be categorized in trusted-server schemes [21], public-key schemes, and key predistribution schemes [22]. The trusted-server and public-key schemes are infeasible to be used in WSNs as the sensors have limitations in terms of energy and computing processes. On the other hand, key predistribution schemes are feasible to be used in WSNs. In these schemes, the shared keys are distributed among the nodes of a group in such a way that every node in the group is able to compute individually a common key associated with that group. Two examples of key predistribution schemes are given as follows.

In MacSig which is an efficient subspace authentication scheme for NC and presented in [9], the double-random key distribution has been proposed. This proposed keys distribution model includes two random procedures. First of all, they assign each node with a random set of keys; next, the source node randomly selects a subset of keys from the key pools and uses these keys to generate the MACs. However, it is necessary to attach the indexes of these keys to each packet. Hence, a considerable bandwidth overhead is incurred.

In KEPTE (key predistribution-based tag encoding) scheme, a key distribution model for practical NC has been proposed in [23]. According to this key distribution model, a Key Distribution Center (KDC) is responsible for the distribution of the keys. The KDC allocates N secret vectors at the source node to produce N tags. Moreover, it assigns two secret vectors to each node to check the correctness of its received packets.

3. Problem Statement

In this section, we provide our problem statement through a network coding-enabled WSN model and its corresponding adversary model.

3.1. Network Coding-Enabled WSN Model

We consider a network coding-enabled WSN, as it is depicted in Figure 1, consisting of a source node S, a number of intermediate nodes, and a set of sink nodes. Random linear network coding is exploited in this network. In order to model our network, we define a triple $(G,S,R)$ which consists of the following components:

• (i)

directed multigraph G: we consider a pair of V, E as a directed acyclic graph where V and E are the node sets and edge sets of G, respectively;

(ii)

source node S: in our network model, we have a source S that wants to multicast its messages;

(iii)

non-source node R: we define relay and sink nodes in a set of nodes which is defined as: $R=\left\{\forall x\in V-\{S\}\right\}$ .

Notations section summarizes the main notations used in this paper.

Figure 1

A general multicast network.

Prior to transmission, the source node partitions message packets into generations. Each generation consists of m messages packets denoted as ${\underset{\_}{\mathbf{u}}}_{\mathrm{1}},{\underset{\_}{\mathbf{u}}}_{\mathrm{2}},\dots ,{\underset{\_}{\mathbf{u}}}_m$ . Each packet ${\underset{\_}{\mathbf{u}}}_i$ is represented as a vector of n symbols $\left({\underset{\_}{u}}_{i,\mathrm{1}},{\underset{\_}{u}}_{i,\mathrm{2}},\dots ,{\underset{\_}{u}}_{i,n}\right)$ in the finite field ${\mathbb{F}}_p^n$ . In [24], it is shown that $p={\mathrm{2}}^{\mathrm{8}}$ is usually sufficient for practical use and convenient for computation. Then, the source node generates an augmented packet ${\mathbf{u}}_i$ by prefixing ${\underset{\_}{\mathbf{u}}}_i$ with the ith unit vector of dimension m represented as

$$\begin{array}{cc}& {\mathbf{u}}_i=\left(\stackrel{m}{\overbrace{\underset{i-\mathrm{1}}{\underbrace{\mathrm{0},\dots ,\mathrm{0}}},\mathrm{1,0},\dots ,\mathrm{0}}},{\underset{\_}{u}}_{i,\mathrm{1}},\dots ,{\underset{\_}{u}}_{i,n}\right)\in {\mathbb{F}}_p^{m+n}.\end{array}$$

(1)

After that, the source node transmits these augmented packets to its neighbour nodes. During transmission, an intermediate node buffers its received packets ${\underset{\_}{\mathbf{u}}}_i$ temporarily and creates an outgoing message y as linear combinations of packets ${\mathbf{u}}_{\mathrm{1}},{\mathbf{u}}_{\mathrm{2}},\dots ,{\mathbf{u}}_h$ belonging to the same generation:

$$\begin{array}{cc}& y={\displaystyle \sum }_{i=\mathrm{1}}^h{c}_i{\mathbf{u}}_i,\end{array}$$

(2)

where each $c_i\in {\mathbb{F}}_p$ is a random coefficient chosen by each forwarder. A coded packet y is considered to be valid if it is in the linear subspace spanned by the original augmented packets, denoted as $y\in \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left\{{\mathbf{u}}_{\mathrm{1}},\dots ,{\mathbf{u}}_m\right\}$ . In fact, when y is valid, these linear combination coefficients are the first m symbols of the packet y. Otherwise, y is invalid and it is denoted as $y\notin \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left\{{\mathbf{u}}_{\mathrm{1}},\dots ,{\mathbf{u}}_m\right\}$ , which may be caused by transmission errors or pollution attacks. After transmission, when a sink node has obtained m linearly independent coded packets, it can decode those using Gaussian eliminations, so as to recover the original messages [7].

3.2. Adversary Model

For the above mentioned network coding-enabled model, we consider that the source is always trusted and there is no possibility to forge it, but the intermediate and sink nodes can be compromised. The adversary is able to wiretap all the data packets that are transmitted over a network. The adversary's goal is to achieve pollution attack. There are two types of pollution attack.

Data Pollution Attack. An adversary can inject fake data packets into the network. The objective of data pollution attack is to pass the verification of other innocent nodes and to cause incorrect decoding at the sink node, as well as wasting of bandwidth.

Tag Pollution Attack. An adversary injects a corrupted packet consisting of correct data but modified tags to the network. The objective of tag pollution is to discard the correct data packets due to the corresponding corrupted tags. This results in the waste of bandwidth. A basic scenario of tag pollution attack is presented in Figure 2.

Figure 2

A basic scenario of tag pollution. We consider a scenario which has a packet and 4 tags. We consider a node A as an adversary that pollutes the second tag $t_{\mathrm{2}}$ of the packet. In (a), we see that the next hop, node B, has two sets of keys ( $K_{\mathrm{2}}$ , $K_{\mathrm{3}}$ ) and is able to detect tag pollution. As a result node B discards the packet. In (b), the next hop, node B does not have ( $K_{\mathrm{2}}$ ), so it allows the polluted packet to pass which results in wasted bandwidth; however, the hop, node C is able to detect the polluted packet. In the last scenario shown in (c), we demonstrate the case, where totally wasted bandwidth occurs since none of the nodes holds key $K_{\mathrm{2}}$ .

4. Proposed Scheme: Dual-Homomorphic MAC (Dual-HMAC)

In this section, we present our Dual-HMAC scheme, which mitigates data pollution and partially tags pollution attacks for a network coding-enabled WSN. The Dual-HMAC scheme's outline, the construction and the correctness of the scheme, and the key distribution model are provided in this section.

Our proposed solution is based on the homomorphic MAC solution, defined by Agrawal and Boneh [14], and the MacSig scheme proposed in [9]. Additionally, our proposed scheme makes use of additional MACs, termed as D-MACs, in order to resist data pollution and partially tag pollution attacks. In contrast to the homomorphic MAC solution in [14], our proposed scheme is not susceptible to tag pollution attacks. Particularly, our proposed scheme can achieve resistance for the half of the tags against tag pollution attack with significant low computational complexity compared to the MacSig scheme, which uses a signature scheme characterized by a much considerable computational overhead.

Our scheme consists of three steps, as it is depicted in Figure 3, in order to generate the required MACs and D-MACs. In step 1, it computes a number of MACs (i.e., tags), for each message, according to the keys which are chosen randomly from the first pool of keys. Then, in step 2, it computes a number of D-MACs for the initial MACs, according to the keys which are chosen from the second pool of keys. Finally, in step 3, the computed MACs and D-MACs are appended to the message. More specifically, the main idea of our work is based on the orthogonal subspace property [9].

Figure 3

The basic idea of Dual-HMAC scheme which is related to the padding orthogonality property.

4.1. The Outline of the Dual-HMAC Scheme

In this section, we provide description of the proposed Dual-HMAC scheme with a formal method. This scheme includes four steps: setup, tag generation, verification, and encoding detailed as follows.

4.1.1. Setup

• (a)

Key Distribution Centre (KDC) distributes the following two sets of secrete key vectors to the source node S: ${\mathcal{K}}_S=\left\{{\mathbf{k}}_{\mathrm{1}},{\mathbf{k}}_{\mathrm{2}},\dots ,{\mathbf{k}}_L\right\}$ , ${\mathbf{k}}_l\in {\mathbb{F}}_p^{m+n+\mathrm{1}}$ and ${\mathcal{K}}_S^{\prime }=\left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },{\mathbf{k}}_{\mathrm{2}}^{\prime },\dots ,{\mathbf{k}}_{L^{\prime }}^{\prime }\right\}$ , ${\mathbf{k}}_{l^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+\mathrm{1}}$ . KDC also distributes the following two subsets of secrete vectors to all intermediate nodes and sink nodes: ${\mathcal{K}}_{n_i}=\left\{{\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_R\right\}$ , ${\mathbf{k}}_r\in {\mathbb{F}}_p^{m+n+\mathrm{1}}$ , and ${\mathcal{K}}_{n_i}^{\prime }=\left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },\dots ,{\mathbf{k}}_{R^{\prime }}^{\prime }\right\}$ , ${\mathbf{k}}_{r^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+\mathrm{1}}$ .

(b)

Note that ${\mathcal{K}}_S\cap {\mathcal{K}}_S^{\prime }=⌀$ , ${\mathcal{K}}_{n_i}\subset {\mathcal{K}}_S$ , ${\mathcal{K}}_{n_i}^{\prime }\subset {\mathcal{K}}_S^{\prime }$ , and if $i\ne j$ , then ${\mathcal{K}}_{n_i}\ne {\mathcal{K}}_{n_j}$ and ${\mathcal{K}}_{n_i}^{\prime }\ne {\mathcal{K}}_{n_j}^{\prime }$ .

(c)

Note that the subscriptions l, $l^{\prime }$ , r, and $r^{\prime }$ represent the index of the key, which do not change in different subsets. In other words, if ${\mathbf{k}}_l={\mathbf{k}}_r$ , then $l=r$ ; if ${\mathbf{k}}_{l^{\prime }}={\mathbf{k}}_{r^{\prime }}$ , then $l^{\prime }=r^{\prime }$ .

The detail of probabilistic key distribution algorithm will be described in Section 4.4, as well as how to choose the key set size.

4.1.2. Tag Generation

For every data packet ${\mathbf{u}}_i\in {\mathbb{F}}_p^{m+n}$ , the source uses the $\mathrm{M}\mathrm{A}\mathrm{C}\left({\mathit{k}}_{\mathrm{1}},{\mathit{k}}_{\mathrm{2}},\dots ,{\mathit{k}}_L,{\mathit{u}}_i\right)$ and $\mathrm{D}\text{-}\mathrm{M}\mathrm{A}\mathrm{C}\left({\mathit{k}}_{\mathrm{1}}^{\prime },{\mathit{k}}_{\mathrm{2}}^{\prime },\dots ,{\mathit{k}}_{L^{\prime }}^{\prime },t_{{\mathit{u}}_i,\mathrm{1}},\dots ,t_{{\mathit{u}}_i,L}\right)$ algorithms to generate the $(L+L^{\prime })$ tags.

4.1.3. Verification

When a relay or sink node receives a coded packet $y\in {\mathbb{F}}_p^{m+n}$ with its tags, this node checks the correctness of packet y using the algorithm Verify via its predistributed keys ${\mathcal{K}}_{n_i}$ and ${\mathcal{K}}_{n_i}^{\prime }$ . If the output is 1, then the received coded packet y is considered to be a correct one. Otherwise, this packet is discarded.

4.1.4. Encoding

When an intermediate node receives h encoded packets $u_i\in {\mathbb{F}}_p^{m+n}$ ( $\mathrm{1}\le i\le h$ ), and they all are checked or considered to be correct, a forward coded packet along with new tags is generated using the $\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}\left({\left({\mathbf{u}}_i,t_{{\mathit{u}}_i,\mathrm{1}},\dots ,t_{{\mathit{u}}_i,L},t_{{\mathit{u}}_i,\mathrm{1}}^{\prime },\dots ,t_{{\mathit{u}}_i,L^{\prime }}^{\prime }\right)}_{i=\mathrm{1}}^h,{\left(c_i\right)}_{i=\mathrm{1}}^h\right)$ algorithm with locally randomly generated coefficients $c_i$ .

4.2. The Construction

In this subsection, we provide the construction of the scheme. Particularly, we present the above-mentioned four algorithms, namely, MAC, D-MAC, Combine, and Verify, in detail. The algorithm MAC computes L tags for each data packet ${\mathbf{u}}_i$ , and the algorithm D-MAC computes another $L^{\prime }$ tags for the L tags. Moreover, the algorithm Combine generates new tags for RLNC encoded packet. Furthermore, the algorithm Verify checks the correctness of a data packet with all tags. Details of these four algorithms are described as follows.

4.2.1. $\text{MAC}\mathbf{(}{\mathcal{K}}_{\mathit{S}}\mathbf{,}{\mathit{u}}_{\mathit{i}}\mathbf{)}$

• (i)

Input: ${\mathcal{K}}_S$ consists of L secrete vectors ${\mathbf{k}}_{\mathrm{1}},{\mathbf{k}}_{\mathrm{2}},\dots ,{\mathbf{k}}_L\in {\mathbb{F}}_p^{m+n+\mathrm{1}}$ , and the ith data packet ${\mathbf{u}}_i\in {\mathbb{F}}_p^{m+n}$ as shown in (1).

(ii)

Output: L tags $t_{{\mathbf{u}}_i,\mathrm{1}},t_{{\mathbf{u}}_i,\mathrm{2}},\dots ,t_{{\mathbf{u}}_i,L}\in {\mathbb{F}}_p^{}$ for packet ${\mathbf{u}}_i$ , where

$$\begin{array}{cc}& t_{{\mathbf{u}}_i,l}=-\frac{\left({\sum }_{j=\mathrm{1}}^{m+n}{u}_{i,j}{k}_{l,j}\right)}{k_{l,m+n+\mathrm{1}}}.\end{array}$$

(3)

4.2.2. $\text{D-MAC}\left({\mathcal{K}}_{\mathit{S}}^{\mathbf{\prime }}\mathbf{,}{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}1}\mathbf{,}\dots \mathbf{,}{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}\mathit{L}}\right)$

• (i)

Input: ${\mathcal{K}}_S^{\prime }$ consists of $L^{\prime }$ secrete vectors ${\mathbf{k}}_{\mathrm{1}}^{\prime },{\mathbf{k}}_{\mathrm{2}}^{\prime },\dots ,{\mathbf{k}}_{L^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+\mathrm{1}}$ , and the L tags $t_{{\mathbf{u}}_i,l}\in {\mathbb{F}}_p^{}$ generated in (3) for the packet ${\mathbf{u}}_i$ .

(ii)

Output: $L^{\prime }$ tags $t_{{\mathbf{u}}_i,\mathrm{1}}^{\prime },t_{{\mathbf{u}}_i,\mathrm{2}}^{\prime },\dots ,t_{{\mathbf{u}}_i,L^{\prime }}^{\prime }\in {\mathbb{F}}_p^{}$ for packet ${\mathbf{u}}_i$ , where

$$\begin{array}{cc}& t_{{\mathbf{u}}_i,l^{\prime }}^{\prime }=-\frac{\left({\sum }_{j=\mathrm{1}}^L{t}_{{\mathbf{u}}_i,j}{k}_{l^{\prime },j}^{\prime }\right)}{k_{l^{\prime },L+\mathrm{1}}}.\end{array}$$

(4)

4.2.3. $\text{Combine}\left({\left({\mathit{u}}_{\mathit{i}}\mathbf{,}{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}1},\dots ,{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}\mathit{L}}\mathbf{,}{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}1}^{\mathbf{\prime }},\dots ,{\mathit{t}}_{{\mathit{u}}_{\mathit{i}}\mathbf{,}{\mathit{L}}^{\mathbf{\prime }}}^{\mathbf{\prime }}\right)}_{\mathit{i}\mathbf{=}1}^{\mathit{h}}\mathbf{,}{\left({\mathit{c}}_{\mathit{i}}\right)}_{\mathit{i}\mathbf{=}1}^{\mathit{h}}\right)$

• (i)

Input: h vectors ${\mathbf{u}}_i\in {\mathbb{F}}_p^{m+n}$ ( $\mathrm{1}\le i\le h$ ) as shown in (2), each with $(L+L^{\prime })$ tags $t_{u_i,\mathrm{1}},\dots ,t_{u_i,L},t_{u_i,\mathrm{1}}^{\prime },\dots ,t_{u_i,L^{\prime }}^{\prime }\in {\mathbb{F}}_p^{}$ ( $\mathrm{1}\le i\le h$ ), and h constants $c_{\mathrm{1}},\dots ,c_h\in {\mathbb{F}}_p^{}$ .

(ii)

Output: a coded packet with $(L+L^{\prime })$ tags generated by

$$\begin{array}{l}\left(y,t_{y,\mathrm{1}},\dots ,t_{y,L},t_{y,\mathrm{1}}^{\prime },\dots ,t_{y,L^{\prime }}^{\prime }\right)\\ \hspace{1em}={\displaystyle \sum }_{i=\mathrm{1}}^h{c}_i\left(u_i,t_{u_i,\mathrm{1}},\dots ,t_{u_i,L},t_{u_i,\mathrm{1}}^{\prime },\dots ,t_{u_i,L^{\prime }}^{\prime }\right).\end{array}$$

(5)

4.2.4. $\text{Verify}\left({\mathcal{K}}_{{\mathit{n}}_{\mathit{i}}}\mathbf{,}{\mathcal{K}}_{{\mathit{n}}_{\mathit{i}}}^{\mathbf{\prime }}\mathbf{,}\left(\mathit{y}\mathbf{,}{\mathit{t}}_{\mathit{y}\mathbf{,}1},\dots ,{\mathit{t}}_{\mathit{y}\mathbf{,}\mathit{L}}\mathbf{,}{\mathit{t}}_{\mathit{y}\mathbf{,}1}^{\mathbf{\prime }},\dots ,{\mathit{t}}_{\mathit{y}\mathbf{,}{\mathit{L}}^{\mathbf{\prime }}}^{\mathbf{\prime }}\right)\right)$

• (i)

Input: ${\mathcal{K}}_{n_i}$ consists of secrete vectors ${\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_R\in {\mathbb{F}}_p^{m+n+\mathrm{1}},\left\{{\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_R\right\}\subset \left\{{\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_L\right\}$ and ${\mathcal{K}}_{n_i}^{\prime }$ consists of secrete vectors ${\mathbf{k}}_{\mathrm{1}}^{\prime },\dots ,{\mathbf{k}}_{R^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+\mathrm{1}}$ , $\left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },\dots ,{\mathbf{k}}_{R^{\prime }}^{\prime }\right\}\subset \left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },{\mathbf{k}}_{\mathrm{2}}^{\prime },\dots ,{\mathbf{k}}_{L^{\prime }}^{\prime }\right\}$ , as well as a RLNC encoded packet $y\in {\mathbb{F}}_p^{m+n}$ with $(L+L^{\prime })$ tags $t_{y,\mathrm{1}},\dots ,t_{y,L},t_{y,\mathrm{1}}^{\prime },\dots ,t_{y,L^{\prime }}^{\prime }\in {\mathbb{F}}_p^{}$ .

(ii)

Output: if

$$\begin{array}{cc}& \forall {\mathbf{k}}_r\in \left\{{\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_R\right\},\hspace{1em}{\delta }_r=\left({\displaystyle \sum }_{j=\mathrm{1}}^{m+n}{y}_j{k}_{r,j}\right)+t_{y,r}{k}_{r,m+n+\mathrm{1}}=\mathrm{0},\end{array}$$

(6)

$$\begin{array}{cc}& \forall {\mathbf{k}}_{r^{\prime }}^{\prime }\in \left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },\dots ,{\mathbf{k}}_{R^{\prime }}^{\prime }\right\},\hspace{1em}{\delta }_{r^{\prime }}^{\prime }=\left({\displaystyle \sum }_{j=\mathrm{1}}^L{t}_{y,j}^{}{k^{\prime }}_{r^{\prime },j}\right)+t_{y,r^{\prime }}^{\prime }{k}_{r^{\prime },L+\mathrm{1}}^{\prime }=\mathrm{0}\end{array}$$

(7)

then output 1; otherwise output 0.

4.3. The Correctness of Dual-HMAC

The proposed Dual-HMAC is going to be correct if the Verify algorithm could produce output 1 for the valid data packet and the valid RLNC encoded packet. Rigorously speaking, it should satisfy the following condition:

•  

If $\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}({\mathcal{K}}_{n_i},{\mathcal{K}}_{n_i}^{\prime },({\mathit{u}}_i,\mathrm{M}\mathrm{A}\mathrm{C}({\mathcal{K}}_S,{\mathit{u}}_i)$ , $\mathrm{D}\text{-}\mathrm{M}\mathrm{A}\mathrm{C}({\mathcal{K}}_S^{\prime },{\mathit{u}}_i))$ = $\mathrm{1}$ and

 

If   $\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}({\mathcal{K}}_{n_j},{\mathcal{K}}_{nj}^{\prime },({\mathit{u}}_j,t_{{\mathit{u}}_j,\mathrm{1}},\dots ,t_{{\mathit{u}}_j,L},t_{{\mathit{u}}_j,\mathrm{1}}^{\prime },\dots ,t_{{\mathit{u}}_j,L^{\prime }}^{\prime }))$ = $\mathrm{1}$ , $\forall j=\mathrm{1},\dots ,h$ , then

 

$\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}({\mathcal{K}}_{n_j},{\mathcal{K}}_{n_j}^{\prime }$ , $\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{e}(({\mathit{u}}_j,t_{{\mathit{u}}_j,\mathrm{1}},\dots ,t_{{\mathit{u}}_j,L}$ , $t_{{\mathit{u}}_j,\mathrm{1}}^{\prime },\dots$ , $t_{{\mathit{u}}_j,L^{\prime }}^{\prime }{)}_{j=\mathrm{1}}^h$ , ${\left(c_j\right)}_{j=\mathrm{1}}^h))=\mathrm{1}$ .

Theorem 1.

The first verification is correct.

Proof.

According to the description of “Setup,” since ${\mathcal{K}}_{n_i}\subset {\mathcal{K}}_S$ , $\forall {\mathbf{k}}_r\in {\mathcal{K}}_{n_i}$ , there is a key ${\mathbf{k}}_l={\mathbf{k}}_r$ and $l=r$ . As a result, by letting $y={\mathbf{u}}_i$ , ${\mathbf{k}}_l={\mathbf{k}}_r$ , and substituting $t_{y,r}=t_{{\mathbf{u}}_i,l}$ using (3), it is for sure that (6) ${\delta }_r=\mathrm{0}$ , $\forall {\mathbf{k}}_r\in {\mathcal{K}}_{n_i}$ .

Similarly, since ${\mathcal{K}}_{n_i}^{\prime }\subset {\mathcal{K}}_S^{\prime }$ , $\forall {\mathbf{k}}_{r^{\prime }}^{\prime }\in {\mathcal{K}}_{n_i}^{\prime }$ , there is a key ${\mathbf{k}}_{l^{\prime }}={\mathbf{k}}_{r^{\prime }}$ and $l^{\prime }=r^{\prime }$ . As a result, by letting $y={\mathbf{u}}_i$ , ${\mathbf{k}}_{l^{\prime }}={\mathbf{k}}_{r^{\prime }}$ , and substituting $t_{y,r^{\prime }}^{\prime }=t_{{\mathbf{u}}_i,l^{\prime }}^{\prime }$ using (4), it is for sure that (7) ${\delta }_{r^{\prime }}^{\prime }=\mathrm{0}$ , $\forall {\mathbf{k}}_{r^{\prime }}^{\prime }\in {\mathcal{K}}_{n_i}^{\prime }$ .

As a result, $\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}({\mathcal{K}}_{n_i},{\mathcal{K}}_{n_i}^{\prime },({\mathit{u}}_i,\mathrm{M}\mathrm{A}\mathrm{C}({\mathcal{K}}_S,{\mathit{u}}_i)$ , $\mathrm{D}\text{-}\mathrm{M}\mathrm{A}\mathrm{C}({\mathcal{K}}_S^{\prime },{\mathit{u}}_i))=\mathrm{1}$ .

Theorem 2.

The second verification is correct.

Proof.

According to (3), the tags are created in a way that ${\mathbf{k}}_l$ is orthogonal to the concatenation of ${\mathbf{u}}_i$ and its l tags ${\mathbf{k}}_l\perp ({\mathbf{u}}_i\parallel t_{{\mathbf{u}}_i,l})$ . This relationship is true for all packets in the same generation, which represents as ${\mathbf{k}}_l\perp \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left\{({\mathbf{u}}_i\parallel t_{{\mathbf{u}}_i,l}{)}_{i=\mathrm{1}}^m\right\}$ .

If $\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}\left({\mathcal{K}}_{n_j},{\mathcal{K}}_{nj}^{\prime },\left({\mathit{u}}_j,t_{{\mathit{u}}_j,1},\dots ,t_{{\mathit{u}}_j,L},t_{{\mathit{u}}_j,1}^{\prime },\dots ,t_{{\mathit{u}}_j,L^{\prime }}^{\prime }\right)\right)=1$ , $\forall j=1,\dots ,h$ , then ${\mathbf{k}}_l\perp \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left\{({\mathbf{u}}_j\parallel t_{{\mathbf{u}}_j,l}{)}_{j=\mathrm{1}}^h\right\}$ . Moreover, the algorithm Combine is a linear combination, which does not change the subspace. Hence, $(y\parallel t_{y,l})\in \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left\{({\mathbf{u}}_j\parallel t_{{\mathbf{u}}_j,l}{)}_{j=\mathrm{1}}^h\right\}$ , ${\mathbf{k}}_l\perp (y\parallel t_{y,l})$ , and (6)   ${\delta }_r=\mathrm{0}$ , $\forall {\mathbf{k}}_r\in {\mathcal{K}}_{n_i}$ . Similarly, we could derive ${\delta }_{r^{\prime }}^{\prime }=\mathrm{0}$ , $\forall {\mathbf{k}}_{r^{\prime }}^{\prime }\in {\mathcal{K}}_{n_i}^{\prime }$ . As a result, the output of Verify is 1, and the second condition is also correct.

4.4. Key Distribution Model

In our work, we assume that a set of symmetric keys are distributed to all participant nodes in a secure and authenticated manner through a key distribution scheme. In this section, we provide the model of the key distribution scheme that we have adopted.

A set system is a pair $(X,F)$ , where X is a finite set of elements and F is an ordered set of subsets of X.

Definition  A.

A set system $(X,F)$ is called a c cover-free family (c-CFF) if, for any c sets $A_{\mathrm{1}},A_{\mathrm{2}},\dots ,A_c\in F$ and any other set $B\in F$ , one has

$$\begin{array}{cc}& B\not\subset {\displaystyle \bigcup }_{J=\mathrm{1}}^c{A}_i.\end{array}$$

(8)

Definition  B.

A set system $(X,F)$ is called a $(c,d)$ cover-free family ((c, d)-CFF) if, for any c sets $A_{\mathrm{1}},A_{\mathrm{2}},\dots ,A_c\in F$ and any other set $B\in F$ , one has

$$\begin{array}{cc}& \left|B\setminus {\displaystyle \bigcup }_{J=\mathrm{1}}^c{A}_j\right|>d.\end{array}$$

(9)

We believe that if key assignment is done properly, no coalition of c nodes can fool another node. Our key predistribution scheme considers two key pools which are available at the source node. We use all these two sets for checking the message's integrity. It is shown in [25] that, in order to resist against less than c compromised nodes, the cardinality of the key size at the source must be $(c+\mathrm{1})$ times larger than those key sizes at the relay/sink nodes, which could be expressed as $L\ge (c+\mathrm{1})R$ , and $L^{\prime }\ge (c+\mathrm{1})R^{\prime }$ . More specifically, we claim that, by this model, we can be sure each verifier has some shared keys which can verify the integrity of messages. Our scheme assigns two sets ${\mathcal{K}}_S=\left\{{\mathbf{k}}_{\mathrm{1}},{\mathbf{k}}_{\mathrm{2}},\dots ,{\mathbf{k}}_L\right\}$ , ${\mathbf{k}}_l\in {\mathbb{F}}_p^{m+n+\mathrm{1}}$ , ${\mathcal{K}}_S^{\prime }=\left\{{\mathit{k}}_1^{\prime },{\mathit{k}}_2^{\prime },\dots ,{\mathit{k}}_{L^{\prime }}^{\prime }\right\}$ , ${\mathit{k}}_{l^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+1}$ to a source node where each has $L=L^{\prime }=\left|{\mathcal{K}}_S\right|=\left|{\mathcal{K}}_S^{\prime }\right|=e(c+\mathrm{1})\mathrm{l}\mathrm{n}(\mathrm{1}/q)$ keys. Moreover, we distribute two sets ${\mathcal{K}}_{n_i}=\left\{{\mathbf{k}}_{\mathrm{1}},\dots ,{\mathbf{k}}_R\right\}$ , ${\mathbf{k}}_r\in {\mathbb{F}}_p^{m+n+\mathrm{1}}$ , and ${\mathcal{K}}_{n_i}^{\prime }=\left\{{\mathbf{k}}_{\mathrm{1}}^{\prime },\dots ,{\mathbf{k}}_{R^{\prime }}^{\prime }\right\}$ , ${\mathbf{k}}_{r^{\prime }}^{\prime }\in {\mathbb{F}}_p^{L+\mathrm{1}}$ to each node where each of these sets has $R=R^{\prime }=\left|{\mathcal{K}}_{n_i}\right|=\left|{\mathcal{K}}_{n_i}^{\prime }\right|=e\mathrm{l}\mathrm{n}(\mathrm{1}/\sqrt{q})$ keys. In addition, q is the security parameter and it stands as $q={\left(\mathrm{N}·\left(\begin{array}{c}N\\ c\end{array}\right)\right)}^{-\mathrm{1}}$ , where N is the total number of recipients (usually $q=\mathrm{1}{\mathrm{0}}^{-\mathrm{3}}$ would be sufficient) and c is a fixed number of corrupted users. Every key ${\mathbf{k}}_r$ or ${\mathbf{k}}_{r^{\prime }}^{\prime }$ is included in a set of each verifier with probability of $\mathrm{1}/\mathrm{2}(c+\mathrm{1})$ (for simplicity, we consider the same length for both poll keys).

5. Security Analysis

In this section, we analyse the possibilities of an adversary launching pollution attack successfully. Hence, three possible pollution attack behaviours are analysed, and their security levels are quantified, respectively. We summarize our analysis in Table 1. Finally, the possible knowledge that an adversary can access is analysed.

Table 1

Security analysis.

Adversary behaviour	Adversary behaviour description	Max hops
Data pollution		$$c-\mathrm{1}$$
Tag pollution (MAC)		$$c-\mathrm{1}$$
Dual-tag pollution (D-MAC)		$$N-i$$

A representation of adversary behavior. Max hops shows the maximum hops which the polluted packet can travel through the network. We consider the worst case when the adversary node can have access to all the next $$c-\mathrm{1}$$ nodes keys (say, a chain of c compromised nodes; moreover, $$(N-i)$$ is the maximum number of hops between the adversary and the sink node).

5.1. The Resistance against Pollution Attack

We consider the following three possible pollution attack scenarios.

5.1.1. 1st Pollution Behaviour: Data Pollution Attack

An adversary node intends to make changes in a message. This polluted message can be detected immediately by the next hop, or in a few hops later (maximum $c-\mathrm{1}$ hops later). It means the polluted message should travel some hops to be detected. The worst case happens whenever an adversary can do coalition with the other $c-\mathrm{1}$ compromised nodes.

5.1.2. 2nd Pollution Behaviour: Tag (i.e., MAC) Pollution Attack

An adversary node intends to make changes in the MACs. This attack can be detected immediately by the next hop if he cannot compromise the next hop and get the next hop keys, or in a few hops later (maximum $c-\mathrm{1}$ hops later). It is similar to the 1st pollution behaviour.

5.1.3. 3rd Pollution Behaviour: Dual-Tag (i.e., D-MAC) Pollution Attack

An adversary i which is one of the N legitimate nodes ( $(N-i)$ is the maximum number of hops between the adversary and the sink node) intends to make changes in D-MACs. This attack can be detected by the next hop by the probability of $\mathrm{1}/\mathrm{2}(c+\mathrm{1})$ . The polluted D-MAC can travel some hops, before it is detected, by the probability of ${\left[\mathrm{1}-\mathrm{1}/\mathrm{2}(c+\mathrm{1})\right]}^{N-i}$ (see Theorem 3).

Theorem 3.

The probability that a downstream user receives the same key as ${key}_x$ of user x is not less than ${\left[\mathrm{1}-\mathrm{1}/\mathrm{2}(c+\mathrm{1})\right]}^{N-i}$ .

Proof.

The probability of recovering the same shared key between two nodes is $\mathrm{1}/\mathrm{2}(c+\mathrm{1})$ , so the probability of the ${\mathrm{k}\mathrm{e}\mathrm{y}}_x$ from a user x located in next hop $x+\mathrm{1}$ is $\mathrm{1}/\mathrm{2}(c+\mathrm{1})$ , and this probability would be ${\left(\mathrm{1}/\mathrm{2}(c+\mathrm{1})\right)}^{\mathrm{2}}$ if this key is found in two hops later. In other words, if the total number of hops between an intermediate node and a sink node, named as downstream node, is $(N-i)$ , then the probability that a downstream user receives the same key as ${\mathrm{k}\mathrm{e}\mathrm{y}}_x$ of user x is not less than ${\left[\mathrm{1}-\mathrm{1}/\mathrm{2}(c+\mathrm{1})\right]}^{N-i}$ .

5.2. The Possible Knowledge of an Adversary

As outlined in Section 3.2, we assume the source node is trustworthy and the process of key predistribution is secure. Hence, the secret key sets, ${\mathcal{K}}_S$ and ${\mathcal{K}}_S^{\prime }$ , assigned to the source node are considered secure. However, an adversary can wiretap all the data communication in a network and may compromise several relay or sink nodes. Hence, the adversary can get access to the received packets from the previous hops, the key information distributed to him by the KDC, and the key information stored at the compromised nodes.

6. Performance Evaluation

In this section, communication and computation overhead of the proposed Dual-HMAC scheme are presented.

6.1. Communication Overhead

In our scheme, each source message has $m+n$ codewords and each codeword has $\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}p$ bits. So, the bit-length of a source message is $(m+n)\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}p$ . The L MACs and the $L^{\prime }$ D-MACs are appended to the source message. We consider $\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}p$ symbols for each MAC and D-MAC. By fixing $L+L^{\prime }=l$ , our scheme has the following communication overhead:

$$\begin{array}{cc}& \frac{\left(L+L^{\prime }\right){\log }_{\mathrm{2}}p}{\left(m+n\right){\log }_{\mathrm{2}}p}=\frac{L+L^{\prime }}{m+n}=\frac{l}{m+n}.\end{array}$$

(10)

Hence, the Dual-HMAC scheme's overhead is equal to the scheme presented in [14]. However this scheme is vulnerable to tag pollution. Additionally, the bandwidth overhead between our scheme and the scheme proposed in [9] is given by the following equation:

$$\begin{array}{l}\frac{O_{b_{\mathrm{D}\mathrm{u}\mathrm{a}\mathrm{l}\text{-}\mathrm{H}\mathrm{M}\mathrm{A}\mathrm{C}}}}{O_{b_{\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{S}\mathrm{i}\mathrm{g}}}}=\frac{l/\left(m+n\right)}{\left(l+\mathrm{1}\right)/\left(m+n\right)+\mathrm{32}l/\mathrm{128}\left(m+n\right)}\\ =\frac{\mathrm{1}}{\mathrm{1.25}+\mathrm{1}/l}.\end{array}$$

(11)

Base on (11), the bandwidth overhead comparison between our scheme and the scheme described in [9], for different values of c, is depicted in the graphs included in Figure 4.

Figure 4

The bandwidth overhead comparison. By fixing $\delta =\mathrm{0.1}$ , $n=\mathrm{20}$  m, $\epsilon =\mathrm{0.01}$ [9], we depict three scenarios (1), (2), and (3) and we use $c=\mathrm{1,2},\mathrm{3}$ for each of them, respectively.

6.2. Computation Overhead

Recall that, to append L MACs and $L^{\prime }$ D-MACs, $L(m+n+\mathrm{1})$ and $L^{\prime }(L+\mathrm{1})$ multiplication operations for MACs and D-MACs are needed, respectively. In addition, for verification, we consider that all the relay nodes have shared keys and each node needs to verify the message. So, as shown in (6) and (7), our scheme needs $L(m+n+\mathrm{1})$ multiplications for MACs and $L^{\prime }(L+\mathrm{1})$ multiplications for D-MACs.

7. Discussion

The number of appended tags which is needed in [14] is $l.$ However, the total number of tags (homomorphic MACs and a signature) which is used in [9] is $l+\mathrm{1}+(l\hspace{0.17em}\hspace{0.17em}\mathrm{k}\mathrm{e}\mathrm{y}\hspace{0.17em}\hspace{0.17em}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{s})$ .

Moreover, the works in [9, 14] need to use $l(m+n)$ and $\left(3/\mathrm{2}\right)\left|p\right|(m+l+\mathrm{1})+(m+n+\mathrm{1})l$ multiplications for the verification phase, respectively. Table 2 summarizes the communication and computation overhead of our work (i.e., Dual-HMAC) and the two related works in [9, 14].

Table 2

Communication and computation overhead of Dual-HMAC and the two related works in [14] and [9].

	[14]	MacSig [9]	Dual-HMAC
Type of key	Symmetric	Hybrid	Symmetric
Data pollution	Yes	Yes	Yes
Tag pollution	No	Yes	Yes
Communication overhead	l	$$l+\mathit{1}+\left(l\hspace{0.17em}\hspace{0.17em}\text{key\hspace{0.17em}\hspace{0.17em}indexes}\right)$$	l
Computation overhead	$$l\left(m+n\right)$$	$$\frac{\mathit{3}}{\mathit{2}}\left|p\right|\left(m+l+\mathit{1}\right)+\left(m+n+\mathit{1}\right)l$$	$$\frac{l}{\mathit{2}}\left(m+n+\frac{l}{\mathit{2}}+\mathit{2}\right)$$

To conclude this section, consider the following.

• (i)

Dual-HMAC incurs a relatively low communication overhead which is almost equal to [14]; however, our scheme's overhead, according to (11), saves up to $(\mathrm{1.25}+\mathrm{1}/l)$ in comparing to MacSig approach [9]. This means that our scheme provides at least 25% bandwidth saving.

(ii)

Dual-HMAC not only slightly increases the tag pollution resistance, but also decreases the computation overhead compared to the schemes in [9, 14].

(iii)

Dual-HMAC provides resistance for half of the tags against tag pollution attack. This results in reducing the possibility of tag pollution around 50% compared to the work presented in [14].

(iv)

Dual-HMAC uses symmetric keys, in contrast to MacSig scheme using symmetric and public keys.

8. Conclusion

Network coding-enabled WSNs are susceptible to pollution attack where a small number of polluted messages can corrupt bunches of legitimate messages. This paper has presented a homomorphic MAC-based scheme, called Dual-HMAC, for network coding-enabled WSNs. The proposed scheme makes use of two types of tags to provide resistance against data pollution attacks and partially tag pollution attacks. The partial protection against tag pollution is related to the key predistribution model. Furthermore, our proposed scheme presents low communication overhead and low computational overhead compared to other existing schemes. Finally, as future work, we plan to propose a scheme that will mitigate not only partially tag pollution attacks but also tag pollution attacks.