An Efficient Scheme for Securing XOR Network Coding against Pollution Attacks

Network coding is promising to maximize throughput in various networking systems. Compared to normal network coding operated over large finite fields, XOR network coding has gained an increasing number of applications for its simplicity, especially in wireless networks. However, both types of network coding systems are vulnerable to pollution attacks in which the compromised forwarders inject polluted messages into the systems. Existing solutions to pollution attacks can protect only the normal network coding, but none of them is able to secure XOR network coding. In this paper, we propose an efficient scheme for securing XOR network coding against pollution attacks. Our scheme exploits probabilistic key pre-distribution and message authentication codes (MACs). In our scheme, the source appends multiple MACs to each message, where each MAC can authenticate only a part of the message and the parts authenticated by different MACs are overlapped. Thus, multiple forwarders can collaboratively verify different parts of messages using the MACs with their own shared keys. By carefully controlling the overlapping between the parts authenticated by different MACs, our scheme can filter polluted messages in a few hops with a high probability. To the best of our knowledge, this is the first solution to pollution attacks for XOR network coding. Experimental results show that it is 200 to 1000 times faster than existing ones, hence, it is particularly suitable for resource-constrained wireless networks.