Paper 2006/025

Signatures for Network Coding

Denis Charles, Kamal Jain, and Kristin Lauter


This paper presents a practical digital signature scheme to be used in conjunction with network coding. Our scheme simultaneously provides authentication and detects malicious nodes that intentionally corrupt content on the network. The homomorphic property of the signatures allows nodes to sign any linear comination of the incoming packets without contacting the signing authority, but it is computationally infeasible for a node to sign a linear combination of the packets without disclosing what linear combination was used in the generation of the packet. Furthermore, we prove that the signature scheme is secure under well known cryptographic assumptions of the hardness of the Discrete-Log problem and the computational co-Diffie-Hellman problem on elliptic curves. Our scheme has a three-fold advantage over schemes based on homomorphic hashing: Firstly, we do not need to securely transmit hash values of the packets that the source transmits; secondly, since our scheme is based on elliptic curves, smaller security parameters suffice and this translates to improved efficiency since the bit lengths involved are smaller; finally, our scheme provides authentication of the data in addition to detecting pollution of packets.

Note: Corrections to references.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Digital signatureselliptic curvesnetwork codingWeil pairing
Contact author(s)
klauter @ microsoft com
2006-02-16: last of 3 revisions
2006-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Denis Charles and Kamal Jain and Kristin Lauter},
      title = {Signatures for Network Coding},
      howpublished = {Cryptology ePrint Archive, Paper 2006/025},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.