International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Signing a Linear Subspace: Signature Schemes for Network Coding

Authors:
Dan Boneh
David Freeman
Jonathan Katz
Brent Waters
Download:
URL: http://eprint.iacr.org/2008/316
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-18132,
  title={Signing a Linear Subspace: Signature Schemes for Network Coding},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography/signature schemes, network coding, pairing-based cryptography},
  url={http://eprint.iacr.org/2008/316},
  note={To appear in PKC 2009 jkatz@cs.umd.edu 14236 received 31 Jul 2008, last revised 23 Dec 2008},
  author={Dan Boneh and David Freeman and Jonathan Katz and Brent Waters},
  year=2008
}