# Signing a Linear Subspace: Signature Schemes for Network Coding

**Authors:**

*D. Boneh, D. Freeman, J. Katz, and B. Waters*

** Abstract: **

Network coding offers increased throughput and improved robustness
to random faults in completely decentralized networks.
In contrast to traditional routing schemes, however, network coding
requires intermediate nodes to modify data packets en route;
for this reason, standard signature schemes are inapplicable and it
is a challenge to provide resilience to tampering by malicious
nodes.
Here, we propose two signature schemes that can be used in
conjunction with network coding to prevent malicious modification of
data. In particular, our schemes can be viewed as signing linear
subspaces in the sense that a signature on *V*
authenticates exactly those vectors in *V*.
Our first scheme is homomorphic and has better performance,
with both public key size and per-packet overhead being constant.
Our second scheme does not rely on random oracles and uses weaker assumptions.
We also prove a lower bound on the length of signatures for
linear subspaces showing that both of our schemes are essentially optimal in
this regard.

** Reference:**

In proceedings of PKC 2009, LNCS 5443, pp. 68-87.

**Full paper:**
pdf