# Efficiency of Secure Network Coding Schemes

Elke Franz, Stefan Pfennig, André Fischer

► To cite this version:

Elke Franz, Stefan Pfennig, André Fischer. Efficiency of Secure Network Coding Schemes. 13th International Conference on Communications and Multimedia Security (CMS), Sep 2012, Canterbury, United Kingdom. pp.145-159, 10.1007/978-3-642-32805-3_12. hal-01540886

HAL Id: hal-01540886

https://inria.hal.science/hal-01540886

Submitted on 16 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficiency of Secure Network Coding Schemes

Elke Franz, Stefan Pfennig, and André Fischer

TU Dresden, Faculty of Computer Science
01062 Dresden, Germany
{elke.franz|stefan.pfennig|andre.fischer}@tu-dresden.de

**Abstract.** Network coding is a promising approach for increasing performance of multicast data transmission and reducing energy costs. Of course, it is essential to consider security aspects to ensure a reliable data transmission. Particularly, pollution attacks may have serious impacts in network coding since a single attacker can jam large parts of the network. Therefore, various approaches have been introduced to secure network coding against this type of attack.

However, introducing security increases costs. Even though there are some performance analysis of secure schemes, to our knowledge there are no details whether these schemes are worthwhile to replace routing under the facet of efficiency. Thus, we discuss in this paper parameters to assess the efficiency of secure network coding schemes. Using three network graphs, we evaluate parameters focusing on communication overhead for selected schemes. Our results show that there are still benefits in comparison to routing depending on the network topology.

**Keywords:** network coding, security, efficiency, performance

## 1 Introduction

The concept of network coding was introduced by Ahlswede et al. [1]. It allows for increasing throughput for multicast transmissions and for saving bandwidth. Particularly, it has been shown that the min-cut max-flow capacity can be achieved in the multicast scenario [1]. The key idea of network coding is that intermediate nodes compute algebraic combinations from packets they receive, in contrast to common routing where packets are just forwarded by the nodes. For an overview on the topic, we refer to [6-8, 19].

While network coding is a promising approach for increasing efficiency of data transmission, it is vulnerable to various attacks. Thus, introducing security mechanisms is a necessity. Within this paper, we focus on the question whether such secure network coding schemes still offer benefits in comparison to traditional routing, and which approaches for secure network coding should be preferred depending on the underlying network topology.

Several approaches have been suggested for network coding. The approaches we evaluate in this paper are based on random linear network coding (RLNC), where the nodes randomly and independently select linear network coding coefficients [12]. RLNC allows for implementing a decentralized solution since there is no need for propagating the coefficients to the nodes.
To counteract the vulnerability to attacks, various schemes for secure network coding have been proposed in the literature (e.g., [2, 4, 13–15, 18]). Most of these approaches aim at providing security against pollution attacks which may have severe impacts on network coding: Even one polluted packet influences all computations performed by subsequent nodes, hence, may prevent the successful decoding of many other packets at the recipients.

Usually, introducing security implies additional costs. Security mechanisms may require additional computations, introduce delays, or increase storage requirements. This fact raises the question whether secure network coding schemes can still provide benefits regarding throughput and bandwidth as intended by network coding. These questions not only influence the time needed for transmitting data packets through a network. An increased effort finally increases energy consumption of the network, a topic that is today of growing importance.

There are two contributions in this paper. First, we discuss which parameters are suited for describing the efficiency of secure network coding schemes. To study the influence of the network topology on these parameters, we use three network graphs that allow for varying network parameters. As second contribution, we present first results of the evaluation of selected secure network coding approaches in comparison to RLNC without security and to routing. These first results focus on communication overhead. The network graphs help in clarifying which characteristics of the underlying network increases additional costs. Such results shall help to assess whether secure network coding can provide benefits for a given network topology at all, and which approach should be preferred.

The paper is organized as follows. Section 2 describes shortly the schemes we selected for our evaluations. For a more detailed discussion of secure network coding schemes, we refer to [9]. Section 3 discusses which parameters are suited for evaluating efficiency. The results of our evaluation are presented and discussed in Section 4. Finally, Section 5 concludes and gives an outlook.

# 2 Secure Network Coding

## 2.1 Random Linear Network Coding

The common notation for describing network coding schemes is based on a directed, acyclic graph $G = (V, E)$ consisting of a set of nodes (also called vertices) $V$ and a set of edges $E$. There is a number of sending nodes $S \subset V$, receiving nodes $R \subset V$, and forwarding nodes $F \subset V$. A forwarding node receives $l$ data packets $x_i = (x_{i,1}, x_{i,2}, ..., x_{i,n})$, $i = 1, 2, ..., l$ on its $l$ incoming edges. Each data packet $x_i$ consists of $n$ codewords $x_{i,j} \in \mathbb{F}_q$. The forwarding node randomly selects $l$ coefficients $\alpha_i \in \mathbb{F}_q$ and computes linear combinations

$$x_j = \sum_{i=1}^{l} \alpha_i x_i. \qquad (1)$$

Generally, we assume that it computes different combinations $x_j$ for each outgoing edge. When the receiving nodes got sufficient linear independent packets, they can decode by solving the corresponding equation system.
A practical system for implementing these ideas – Practical Network Coding (PNC) – is introduced in [3]. In our evaluation, we refer to this framework. PNC describes a data format that enables receiving nodes to decode without knowing the randomly selected coefficients. The sender divides the data to be sent into portions $\bar{p}_i \in \mathbb{F}_q^m$ of m codewords each. These native data packets are amended by a global encoding vector $(\beta_{i,1}, \beta_{i,2}, ..., \beta_{i,h}) \in \mathbb{F}_q^h$ that reflects the linear operations. Packets that can be combined during transmission establish a generation $G$. The size of the generation depends on the multicast capacity $h$.

Thus, we can think of a generation as a matrix of data packets. The sending node produces a generation containing the original, uncombined data amended by an $h \times h$ identity matrix that represents the initial global encoding vector:

$$G = \begin{pmatrix} \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_h \end{pmatrix} = \begin{pmatrix} \beta_{1,1} = 1 \cdots \beta_{1,h} = 0 & \bar{p}_{1,1} & \bar{p}_{1,2} \cdots \bar{p}_{1,m} \\ \vdots & \ddots & \vdots \\ \beta_{h,1} = 0 \cdots \beta_{h,h} = 1 & \bar{p}_{h,1} & \bar{p}_{h,2} \cdots \bar{p}_{h,m} \end{pmatrix} \quad (2)$$

The rows of this matrix are the data packets of size $n = h + m$ codewords sent by the source node. During network coding, the data packets are combined as described by Eq. (1). We refer to combined data packets by

$$\mathbf{x}_i = (x_{i,1}, x_{i,2}, ..., x_{i,n}) = (\beta_{i,1}, \beta_{i,2}, ..., \beta_{i,h}, p_{i,1}, p_{i,2}, ..., p_{i,m}). \quad (3)$$

The coefficients of the global encoding vector reflect the linear combinations computed by the forwarding nodes.

Successful decoding requires that the sink nodes receive sufficient linear independent combinations, i.e., the rank of the matrix of received data packets must be $h$. The probability for successful decoding in case of RLNC depends on the field size $q$; it becomes sufficiently high for a field size of at least $q = 2^8$ [12].

## 2.2 Attacker Model

In order to be practically usable, security aspects of network coding need to be considered. Confidentiality, integrity, and availability of the messages (i.e., the original data) have to be ensured even in case of intended attacks. For ensuring confidentiality, the attacker must be prevented from getting to know enough linear independent data packets. For ensuring integrity and availability, a sufficient amount of data packets needs to be available to the recipient so that he can successfully decode the messages. This implies that integrity and availability of these data packets have to be ensured.

Basically, we have to consider passive as well as active attackers. Passive attackers only observe the system (eavesdropping) while active attackers perform specific actions (modification, deletion, or pollution of packets).

Potential threats to network coding are discussed, e.g., in [5, 15]. If no uncoded packets are sent through the network, an eavesdropper with limited access to the links cannot threaten confidentiality [2]. However, we cannot exclude stronger attacks with certainty. Particularly, if an attacker is able to control a node he can observe and modify all data packets passing this node.
Nevertheless, confidentiality of messages is not widely discussed in the lit-
erature since it is mostly addressed at the upper layers of the system [5]. One
example for a scheme protecting the confidentiality of messages is SPOC. In that
approach, the originally chosen coefficients are encrypted and only the recipient
owning the appropriate keys can decrypt the data [17].

The majority of secure network coding schemes, however, considers pollution
attacks that must be addressed at the layer of network coding. Therefore, we
also focus on this type of attack. Pollution attacks concern the integrity of data
packets. Such attacks are notably critical because polluted packets influence the
result of all subsequent combinations computed by forwarding nodes [5]. Finally,
the recipients may not be able to successfully decode the data.

Various approaches for securing network coding against pollution attacks
have been suggested in the literature. An important distinction is the question
when polluted packets can be detected and filtered out. For our evaluation, we
selected approaches that enable forwarding nodes to recognize polluted packets.
Thus, these nodes are able to drop such packets and the influence of pollution
attacks is limited. The selected schemes are introduced in the next section.

## 2.3 Network Coding Schemes Secure against Pollution Attacks

Network coding schemes that enable forwarding nodes to detect polluted packets are mainly based on cryptography. That means, we need some secret information that can be used for verifying the validity of received packets. However, known cryptographic solutions cannot be directly applied to network coding. Digital signatures are usual for verifying both the integrity and the source of a message, but since the data packets are modified by forwarding nodes, common digital signatures become invalid after the first hop. The same applies to cryptographic hashes and symmetric authentication. Additionally, symmetric authentication would require a key exchange between the sender and all forwarders and recipients.

To overcome these problems, homomorphic hashes and homomorphic signa-
tures have been suggested to secure network coding against pollution attacks.
The homomorphic property of these approaches enables forwarding nodes to
compute valid hashes or signatures for combined data packets. Another approach
is the delayed delivery of information necessary to verify the validity of received
data packets. This time asymmetry was introduced in the TESLA protocol [16],
a broadcast authentication protocol with delayed key release.

Generally, schemes based on asymmetric cryptography require more com-
putational effort while TESLA-like schemes increase delay and communication
overhead. However, the actual costs depend on the underlying network graph
and the communication requirements. Hence, the dependence of the additional
costs on parameters describing the network should be known to decide which
approach should be preferred in a concrete communication scenario. Within this
paper, we provide first results for the selected secure network coding schemes
shortly described in the following.
Homomorphic Hashes [11]. The first scheme we selected uses a hash function to enable recognizing polluted packets. The hash function includes exponentiation modulo a prime r of size 1024 bits, thus, the size of the hash values is 1024 bits. The size of the code words is 256 bits.

The sender computes for each native data packet $\bar{p}_i$ a hash value $h(\bar{p}_i)$. Since the hash values are homomorphic, forwarding nodes can verify the validity of data packets $x_i = (\beta_i, p_i)$ by comparing the hash of these data packets to the linear combination of the hashes delivered by the sender:

$$h(p_i) \stackrel{?}{=} h(\bar{p}_1)^{\beta_{i,1}} \cdot h(\bar{p}_2)^{\beta_{i,2}} \cdot \dots \cdot h(\bar{p}_h)^{\beta_{i,h}} \mod r.$$

Hence, the hashes $h(\bar{p}_i)$ must be known to the forwarding nodes. Since the context of the paper is content distribution, the authors assume that the nodes download the hash values when they join the system. For our analysis, we assume that the sender broadcasts the hash values before transmission of the data packets. To ensure authenticity of the hashes, they need to be digitally signed. The structure of the data packets does not need to be changed.

DART [4]. As second scheme, we selected the TESLA-like scheme DART that is based on delayed checksum delivery. The sender periodically computes and disseminates a signed checksum packet consisting of the checksum $chk_s(G)$, a seed $s$, and a timestamp $t$ for the current generation $G$. For computing the checksum, the sender generates a pseudo-random Matrix $H_s$ using the seed $s$ and a publicly known function $f$.

Each node maintains two buffers: verified_set and unverified_set. After receiving a checksum packet, the node first checks its authenticity. If the verification succeeded, the node re-broadcasts the checksum packet to its neighbors and then checks packets in unverified_set it has received before the checksum was generated. To verify the data packets, the node also generates $H_s$ and checks if the product of checksum and global encoding vector equals the product of random matrix and encoded data.

Invalid packets are discarded; successfully checked packets are transferred to verified_set and will be used for computing linear combinations. Since each node needs for verification a new checksum packet, the number of checksum packets the sender has to generate depends on the number of hops to the recipients.

For increasing efficiency, the authors suggest batch verification. Furthermore, to reduce the introduced delays, pipelining is suggested in which several generations are sent and processed concurrently.

Scheme according to Wang [18]. The third scheme we selected for evaluating additional costs utilizes symmetric authentication – homomorphic MACs (Message Authentication Codes) – and time asymmetry for delayed key release. The number of MACs per data packet depends on the number of hops. The MACs are integrated into the data packets.

Verification of the MACs requires knowledge of the corresponding keys. For each generation, the sender computes a chain of seed values that are the basis for computing these keys. The final value of the chain is necessary in order to
check the validity of the seed values; thus, the sender first digitally signs this
value and broadcasts it to the involved nodes. To prevent that an attacker can
compute upcoming seed values, the code word length is increased to 128 bits.

According to the TESLA scheme, the seed values are distributed to the ver-
ifying nodes after the data packets arrived. The nodes check the validity of the
seed values, derive the necessary keys, and, finally, compute and compare the
MACs. Since the MACs are homomorphic, the nodes can compute valid MACs
for the combined packets. Each node has to compute one MAC less than received.

*RSA-based scheme [10]* The last scheme we analyzed uses the homomorphic
property of the simple RSA signature scheme. The sender computes a digital
signature for each data packet using his private signature key *d* and integrates
it into the particular packet.

Each node is able to verify signatures by means of the public test key e.
Due to the homomorphic property, forwarders can compute valid signatures
for combined packets by multiplying the signatures raised to the power of the
local coefficients αᵢ. All operations concerning the signature are done modulo a
composite number N. Hence the size of the signatures is constant, e.g., 1024 bit.

In contrast to schemes above the codewords are arbitrary integers instead
of elements of a finite field. Thus, every $x_{i,j}$ will grow by a certain amount of
bits dependent on the number of hops $k$ and the number of ingoing edges $\ell$, e.g. 10 bits per hop with $\ell = 4$. For optimization of communication overhead, we set $m = 1$, i.e., we have only one large $p_{i,1}$ per packet $x_i$. However, this setting implies higher computational costs. A larger $m$ increases communication overhead while decreasing computational costs.

3 Assumptions for the Analysis

**3.1 Parameters for the Evaluation of the Schemes**

The major concern of our comparison is to answer the question whether secure
network coding schemes can still provide benefits in comparison to traditional
routing. On one hand, we can compare the performance of the secure schemes to
the performance of schemes without security mechanisms. On the other hand,
it is reasonable to evaluate additional costs implied by introducing security. It
is necessary to define suitable parameters reflecting performance and additional
costs. Thereby, we are interested in results that describe the dependence of the
selected parameters on the characteristics of the underlying network so that it
is possible to assess

1. whether secure network coding can offer benefits in comparison to routing for a given data flow, and if this is the case,

2. which approach for secure network coding should be preferred for the given network.

Consequently, we focus on parameters that can be analyzed on a rather
abstract level without knowing technical details of the system components.
Performance is usually described by parameters like throughput or delay. To allow for a theoretical analysis, we evaluate the **number of ticks** (time slices) necessary to deliver the messages to the intended recipients, a parameter that should highly correlate with the real delay and, hence, roughly reflects the throughput within the network. To simplify matters, we assume that each node can receive on all incoming edges and send on all outgoing edges at the same time. Furthermore, we assume that both transmission of a packet via one link and processing of packets by the nodes need one tick. Thus, the results describe the minimum introduced delay.

Various parameters can be evaluated to describe additional costs and, finally, additional energy required for secure data transmission. Describing absolute energy consumption requires detailed knowledge about the system, e.g., about the implementation of various operations or about the energy requirements of the system components. Generally, additional costs can be described by

- additional operations to be performed by the nodes,

- memory overhead, and

- communication overhead.

Additional operations clearly increase energy consumption. Memory overhead also implies additional operations for accessing the memory. Within our evaluations, we did not consider these issues since they strongly depend on technical conditions and we focus on a theoretical analysis that allows answering the general questions given above. Additional operations and memory accesses might influence the time needed by the nodes for processing data. Due to simplicity, we assume that nodes have enough computing power and memory so that neither additional operations nor memory accesses introduce additional delays. Within our evaluation, we focused on *communication overhead* introduced by security mechanisms. Generally, we assumed a predetermined size per packet for all schemes under investigation. IP addresses and other header information are not considered since they are equal for all schemes. We evaluated three parameters describing communication overhead referring to the transmission of a single generation *G*.

As first parameter, we evaluated the **maximum relative payload**. This parameter helps to assess the amount of additional data introduced by secure network coding schemes to allow authentication of data packets – checksums, digital signatures, MACs, etc. This additional data needs to be included within the data packets or has to be sent in extra data packets what reduces the available payload. Thus, the maximum relative payload allows for coarsely estimating how many generations are necessary to transmit a given amount of data. Considering in addition the number of ticks necessary for transmitting one generation allows roughly assessing the delay for transmitting that amount of data. We want to point out that the processing of multiple generations needs to be considered for such an estimation, e.g., applying pipelining as suggested in [4].

However, the actual amount of data packets to be sent by the sending node may be larger since it depends on the underlying network graph. For example,
all nodes involved in data transmission need the authentication information for
checking the validity of received data packets. Thus, data packets containing
authentication information may be sent several times. Hence, we evaluated as
second parameter the **actual relative payload**, a value that reflects the actual
network load initiated by the sending node.

As a third parameter, we determined the **send operations** necessary for
transmitting all the data packets to the recipients. This parameter gives an im-
pression of the overall effort in the whole network while the parameters referring
to the relative payload just considered the applied load for the sending node. In
case of constant packet size the amount of data sent in the whole network for
the transaction is linearly dependent on the number of send operations. Thus,
this parameter should roughly correspond to the overall network load.

**3.2 Network Topology**

The parameters introduced above describe the efficiency of the selected schemes
depending on the underlying network topology. Thus, it seems to be reason-
able to use network topologies for the evaluation that are suitable to study the
influence of relevant network properties. We especially consider the number of
nodes involved in a data transmission and the number of hops to the recipients
as relevant properties. For our evaluation we used the network models depicted
in Fig. 1.

According to the definition in Sect. 2.1, sending nodes $\mathbf{s}_i$ are nodes that only
send data but do not compute linear combinations. Generally, we assume that a
large file should be transmitted, so we introduce a virtual source node $\mathbf{s}$ that has
the task to distribute data to the sending nodes $\mathbf{s}_i$. For the analysis we restrict
our focus on one generation $\mathcal{G}$ whose size depends on the broadcast capacity $h$.
All edges are assumed to be equal and to have unit capacity, so $h$ is determined
by the min-cut of $\mathcal{G}$. Furthermore, we assume that all receiving nodes shall get
all messages contained in one generation. Nodes that have the same distance
from the sending nodes are considered to be on the same level.

Model 1 is intended to study the influence of the number of nodes involved
in transmission. The size of a generation is 2 for this example, thus, the virtual
source node distributes 2 packets alternating to the sending nodes $\mathbf{s}_i$ for $1 \le i \le \ell$
($\ell$ even). Each node has 2 direct connections to nodes on the next level. Thus,
each forwarding node $\mathbf{f}_i$ for $1 \le i \le \ell$ should get 2 different packets.

Model 2 allows for evaluating the impact of the number of hops $k$ to the
recipients. The virtual source node distributes 2 different packets to the sending
nodes $\mathbf{s}_1$ and $\mathbf{s}_2$. Every node can communicate to every node on the next level.
The number of forwarding nodes increases with a growing number of hops $k$.

Model 3 was originally introduced by Fragouli et al. [7] to demonstrate possible benefits of network coding. We analyzed how secure network schemes perform with that graph. In contrast to the scheme introduced in [7], we again assume that all recipients should get all messages to have comparable conditions. The virtual source node sends a total of $\ell$ packets $\mathbf{x}_i$ to the sending nodes $\mathbf{s}_i$ for $1 \le i \le \ell$. Now every receiver $\mathbf{r}_i$ is interested in getting all original messages $\mathbf{p}_i$
<figure><img src="image_2.png" /><figcaption>Fig. 1. Considered network topologies.</figcaption></figure>

for $1 \le i \le l$. There is no direct communication possible between $s_i$ and $r_j$ for $i = j$. The only obvious way is to communicate via the two forwarder nodes $f_1$ and $f_2$, the link between these nodes establishes a kind of bypass.

Furthermore, we have to analyze the probability that the receiver is able to decode all packets. This probability depends on the underlying finite field $\mathbb{F}_q$ and in some cases on the topology of the network. In general the probability is about $(q-1)/q$, which is also true for model 1 and 2. Indeed, it is essential for model 2 that every node sends different packets on its outgoing edges, otherwise the decoding probability decreases with rising $k$. In model 3, only node $f_1$ performs network coding. Hence, it can be assured that all recipients can successfully decode all packets disregarding transmission errors.

# 4 Evaluation and Results

## 4.1 Results of our Theoretical Analysis

As far as possible, we used similar conditions for evaluation of the schemes considering the different network graphs. Thus, we always assumed a packet size of 1.400 byte. Furthermore, we determined the selected parameters for transmission of one generation disregarding the actual payload size. Generations are not relevant for routing, here we assumed that the $h$ data packets should be transmitted to each receiver. We assume the size of a digital signature to be 128 bytes for all schemes. Higher security requirements will imply longer signatures.

The diagrams show results for the selected secure network coding schemes compared to network coding without security (PNC) and to routing. For the latter, we assume that each packet has only one network destination. Hence, a packet has to be sent several times if there are multiple recipients. The results for the network models shown in Fig. 1 are discussed in the following.
Model 1. Since the generation size is constant for model 1, the size of the encoding vector is also constant. Hence, the maximum relative payload is also constant for all schemes (Fig. 2(a)). The maximum relative payload of the Wang scheme further depends on the number of hops since this value determines the number of MACs to be attached, however, the number of hops is also constant for model 1. Since routing does not require to include additional data, it achieves a maximum relative payload of 1.0. PNC implies the introduction of the global encoding vector and therewith a loss of only *h* codewords per packet. Hence, it also achieves a high maximum relative payload of 0.99. Due to the largest field size, Homomorphic Hashes achieve the worst maximum relative payload.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Results for model 1: Transmitting two packets.</figcaption></figure>

The actual relative payload depends on the number of receiving nodes since more data need to be sent (Fig. 2(b)). This parameter reflects the advantages of network coding in comparison to routing. Even if the additional data required by the secure network coding schemes decrease the actual relative payload, the schemes are still better than routing.

The number of ticks until all data packets are transmitted to the recipients is also constant for all schemes (Fig. 2(c)). PNC shows the benefit of network coding, but the RSA-based scheme achieves the same good results here. Schemes that utilize time asymmetry need of course more ticks for the transmission.

The time asymmetry also increases the number of send operations in the whole network since the data necessary for verifying the data packets need to be sent to the nodes involved in transmission (Fig. 2(d)). Schemes without time asymmetry are much better, in the best case, they require less network load than routing.

The diagrams only consider the transmission of a single generation. Given the maximum payload of one generation, it is possible to compute the number
of generations needed for transmitting a given amount of data. For example, the transmission of a file of 1 GB requires sending 357 143 “generations” (i.e., $h = 2$ data packets) for routing, 359 713 (+0.7%) for PNC and DART each, 363 373 (+1.7%) for Homomorphic Hashes, 381 098 (+6.7%) for Wang, and 396 511 (+11%) for RSA.

*Model 2.* The generation size for this model is also constant. Thus, the size of the encoding vector is constant. However, the number of hops increases which also implies that the number of forwarding nodes increases. Hence, the relative payload of schemes that require sending authentication information decreases with an increasing number of hops (Fig. 3(a) and 3(b)). The influence is especially strong for the Wang scheme since the number of MACs depends on the number of hops.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Results for model 2: Transmitting two packets.</figcaption></figure>

The number of ticks equally increases for all schemes without time asymmetry (Fig. 3(c)). Again, the influence is significant for the Wang scheme.

The results for the last parameter are similar except that DART yields the worst results due to the need to broadcast the checksums (Fig. 3(d)).

*Model 3.* In contrast to the other models, the generation size increases for this model. Hence, the maximum relative payload of all network coding schemes at least slightly decreases (Fig. 4(a)). In case of a larger field size, the influence is stronger. Contrary to expectations, the maximum relative payload increases for DART for a small number of nodes. The reason is that the digital signature has a stronger influence on the relative payload if there are only few packets in a generation.
<figure><img src="image_5.png" /><figcaption>Fig. 4. Results for model 3: Transmitting $\ell$ packets.</figcaption></figure>

Model 3 was introduced in the literature to illustrate the potential benefits of network coding. This is especially reflected by the actual relative payload (Fig. 4(b)). Even the secure network coding scheme that yields the worst parameter outperforms routing regarding this parameter. If there is a bottleneck in the network, we can expect that network coding provides advantages.

Due to the bottleneck in this network graph, even the network coding schemes based on time asymmetry outperform routing regarding the number of ticks if there are more than 10 recipients. For Homomorphic Hashes, the number of ticks jumps after a certain increase of the number of recipients. The reason is the necessity to send the hashes of the original data at the beginning. Due to the size of the hashes, there can be at maximum 9 hashes plus signature in a data packet. If the number of packets per generation exceeds this number, an additional data packet needs to be sent.

The same reason causes jumps regarding the number of send operations for Homomorphic Hashes (Fig. 4(d)). The RSA-based scheme does not imply additional send operations in comparison to PNC, thus, it outperforms routing for this model.

## 4.2 Discussion of the Results

Generally, we can summarize two basic results that confirm our assumptions: First, network coding (PNC) outperforms routing in terms of throughput (number of ticks), network load (number of send operations), and actual relative payload. Second, introducing security increases costs – secure network coding schemes yield at best the same results as PNC, but no better results. However, a closer look at the results reveals that secure network coding schemes may be
still better than routing. As example, consider model 3 with 12 recipients. Best
results for the evaluated secure network coding schemes regarding routing are:
actual relative payload 391%-1082%, number of ticks 28.6%-85.7%, and send
operations 58.7% (RSA-based scheme).

For the maximum relative payload, routing always delivers the best results
due to the fact that network coding schemes always require to contain some
additional data. However, this parameter is rather theoretical since it does not
take into account the underlying network topology. Thus, we focus on the other
parameters in this concluding discussion.

Schemes that require including additional data in the data packets decrease the actual relative ratio. This influence is especially strong if the alphabet size needs to be increased, e.g., in the scheme according to Wang [18]. Regarding the number of ticks that represents the delay for transmitting messages and the number of send operations that influences the energy consumption, schemes with no time asymmetry are clearly better. For schemes with time asymmetry, the number of nodes involved in data transmission as well as the number of hops have a significant influence on these parameters.

So far, we got best results for the RSA-based scheme [10] and we expect
that we would get similar results regarding the evaluated parameters for other
schemes that do not utilize time asymmetry. However, we want to point out that
we worked with a setting that reduces the communication overhead (Sect. 2.3).

# 5 Summary and Outlook

Our results show that secure network coding can still provide benefits regarding
communication overhead in comparison to routing. However, we want to point
out that the results presented in this paper are not sufficient to completely assess
the efficiency of secure network coding schemes. Particularly, we solely focused on
parameters describing communication overhead. A comprehensive comparison of
secure network coding schemes regarding their efficiency calls for considering *all*
efficiency parameters sketched in Sect. 3.

Moreover, answering the question whether secure network coding is beneficial
at all and which approach should be preferred requires to analyze the given net-
work and communication requirements. For example, it is necessary to determine
what requires most energy considering the technical conditions of the network
given – more computations, more sending operations, or whatsoever. Enhanc-
ing the evaluations by considering more parameters as well as dependencies on
technical conditions are topics of future work.

Next steps will also include simulation runs. We are currently working on
a network coding simulator based on the NS3 framework<fnref n="1" />. This simulator will
allow to consider various communication scenarios and multiple data flows.

<footnote n="1">¹ http://www.nsnam.org/</footnote>
**Acknowledgement.** This work is supported by the German Research Foundation (DFG) in the Collaborative Research Center 912 "Highly Adaptive Energy-Efficient Computing". We wish to thank Sebastian Clauß, Sabrina Gerbracht, Eduard Jorswieck, Christian Scheunert, Dagmar Schönfeld, and the reviewers for their constructive comments.

## References

1. R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow. *IEEE Trans. on Information Theory*, 46(4):1204–1216, 2000.

2. N. Cai and R. W. Yeung. Secure Network Coding. In *Proc. IEEE Int. Symp. on Information Theory*, 2002.

3. P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In *Proc. Annual Allerton Conference on Communication, Control, and Computing*, 2003.

4. J. Dong, R. Curtmola, and C. Nita-Rotaru. Practical defenses against pollution attacks in intra-flow network coding for wireless mesh networks. In *Proc. WiSec*, 2009.

5. J. Dong, R. Curtmola, and C. Nita-Rotaru. Secure network coding for wireless mesh networks: Threats, challenges, and directions. *Computer Communications*, 32:1790–1801, 2009.

6. C. Fragouli, J.-Y. Le Boudec, and J. Widmer. Network coding: An instant primer. *SIGCOMM Computer Communication Review*, 36:63–68, 2006.

7. C. Fragouli and E. Soljanin. *Network Coding Applications*. Now publishers, 2007.

8. C. Fragouli and E. Soljanin. *Network Coding Fundamentals*. Now publishers, 2007.

9. E. Franz, S. Pfennig, and A. Fischer. Communication overhead of network coding schemes secure against pollution attacks. Technical Report TUD-FI12-07, TU Dresden, May 2012.

10. R. Gennaro, J. Katz, H. Krawczyk, and T. Rabin. Secure network coding over the integers. In *Proc. PKC 2010*, pages 142–160, 2010.

11. C. Gkantsidis and P. R. Rodriguez. Cooperative Security for Network Coding File Distribution. In *Proc. IEEE Int. Conf. on Computer Communications*, 2006.

12. T. Ho, R. Koetter, M. Médard, D. R. Karger, and M. Effros. The benefits of coding over routing in a randomized setting. In *Proc. of the IEEE International Symposium on Information theory*, 2003.

13. T. Ho, B. Leong, R. Koetter, M. Médard, M. Effros, and D. R. Karger. Byzantine Modification Detection in Multicast Networks with Random Network Coding. *IEEE Trans. on Information Theory*, 54(6):2798–2803, 2008.

14. S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Médard. Resilient network coding in the presence of byzantine adversaries. In *in Proc. 26th Annual IEEE Conf. on Computer Commun., INFOCOM*, pages 616–624, 2007.

15. L. Lima, J. P. Vilela, P. F. Oliveira, and J. Barros. Network coding security: Attacks and countermeasures. CoRR, abs/0809.1366, 2008.

16. A. Perrig, R. Canetti, J. D. Tygar, and D. Song. The TESLA broadcast authentication protocol. *RSA CryptoBytes*, 5(2):2–13, Summer/Fall 2002.

17. J. P. Vilela, L. Lima, and J. Barros. Lightweight security for network coding. In *Proc. IEEE Int. Conf. on Communications*, 2008.

18. Y. Wang. Insecure "provably secure network coding" and homomorphic authentication schemes for network coding. IACR Eprint archive, 2010.

19. R. W. Yeung. *Information Theory and Network Coding*. Springer Publishing Company, Incorporated, 2008.