SigNCode: A provably secure homomorphic signature scheme for network coding

Network coding allows intermediate nodes to mix data in order to achieve
higher throughput and better reliability. Hence, nodes combine multiple
packets into a single packet before forwarding it. Such scheme needs efficient
authentication and integrity mechanisms in order to prevent pollution
attacks whereby an attacker injects bogus messages into the system instead
of network coded blocks. Such an attack has the potential impact of infecting
all subsequent message exchanges between nodes that received polluted
messages. In this paper, we propose SigNCode, a new integrity mechanism
based on homomorphic operations allowing an on-the-fly verification of the
integrity of a network coded packet and therefore preventing pollution attacks.
Thanks to this new mechanism, any intermediate node is capable of
constructing a correct signature for a linear combination of messages originating
from the source. The proposed mechanism is based on the use of
bilinear pairings and relies on a single communication channel. In order to
evaluate the security of our signature scheme we also developed a new security
definition and a proof model that encompass the extended integrity
notion underlying network coding. This definition and the model help distinguish
some legitimate forgery such as linear combinations of original data
blocks from pure forgery such as injection of bogus data.