International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Signatures for Network Coding

Denis Charles
Kamal Jain
Kristin E. Lauter
Search ePrint
Search Google
Abstract: 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.
  title={Signatures for Network Coding},
  booktitle={IACR Eprint archive},
  keywords={applications / Digital signatures, elliptic curves, network coding, Weil pairing},
  note={ 13195 received 23 Jan 2006, last revised 16 Feb 2006},
  author={Denis Charles and Kamal Jain and Kristin E. Lauter},