Cryptology ePrint Archive: Report 2006/025

Signatures for Network Coding

Denis Charles and Kamal Jain and Kristin Lauter

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.

Category / Keywords: applications / Digital signatures, elliptic curves, network coding, Weil pairing

Date: received 23 Jan 2006, last revised 16 Feb 2006

Contact author: klauter at microsoft com

Available format(s): PDF | BibTeX Citation

Note: Corrections to references.

Version: 20060216:224328 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]