Paper 2011/696

Efficient Network Coding Signatures in the Standard Model

Dario Catalano, Dario Fiore, and Bogdan Warinschi


Network Coding is a routing technique where each node may actively modify the received packets before transmitting them. While this departure from passive networks improves throughput and resilience to packet loss it renders transmission susceptible to {\em pollution attacks} where nodes can misbehave and change in a malicious way the messages transmitted. Nodes cannot use standard signature schemes to authenticate the modified packets: this would require knowledge of the original sender's signing key. Network coding signature schemes offer a cryptographic solution to this problem. Very roughly, such signatures allow signing vector spaces (or rather bases of such spaces). Furthermore, these signatures are homomorphic: given signatures on a set of vectors it is possible to create signatures for any linear combination of these vectors. Designing such schemes is a difficult task, and the few existent constructions either rely on random oracles or are rather inefficient. In this paper we introduce two new network coding signature schemes. Both of our schemes are provably secure in the standard model, rely on standard assumptions, {\em and} are in the same efficiency class with previous solutions based on random oracles.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Full version of the paper appeared in the proceedings of PKC 2012
digital signaturesnetwork coding
Contact author(s)
fiore @ cs nyu edu
2012-03-14: revised
2011-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Catalano and Dario Fiore and Bogdan Warinschi},
      title = {Efficient Network Coding Signatures in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2011/696},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.