Paper 2009/569

Secure Network Coding Over the Integers

Rosario Gennaro, Jonathan Katz, Hugo Krawczyk, and Tal Rabin


Network coding has received significant attention in the networking community for its potential to increase throughput and improve robustness without any centralized control. Unfortunately, network coding is highly susceptible to ``pollution attacks" in which malicious nodes modify packets in a way that prevents the reconstruction of information at recipients; such attacks cannot be prevented using standard end-to-end cryptographic authentication because network coding requires that intermediate nodes modify data packets in transit. Specialized solutions to the problem have been developed in recent years based on homomorphic hashing and homomorphic signatures. The latter are more bandwidth-efficient but require more computation; in particular, the only known construction uses bilinear maps. We contribute to this area in several ways. We present the first homomorphic signature scheme based solely on the RSA assumption (in the random oracle model), and present a homomorphic hashing scheme based on composite moduli that is computationally more efficient than existing schemes (and which leads to secure network coding signatures based solely on the hardness of factoring in the standard model). Both schemes use shorter public keys than previous schemes. In addition, we show variants of existing schemes that reduce the communication overhead significantly for moderate-size networks, and which improve computational efficiency in some cases quite dramatically (e.g., we achieve a 20-fold speedup in the computation of intermediate nodes). At the core of our techniques is a modified approach to network coding where instead of working in a vector space over a field, we work directly over the integers (with small coefficients).

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Network codinghomomorphic hashinghomomorphic signatures
Contact author(s)
hugo @ ee technion ac il
2009-11-25: received
Short URL
Creative Commons Attribution


      author = {Rosario Gennaro and Jonathan Katz and Hugo Krawczyk and Tal Rabin},
      title = {Secure Network Coding Over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2009/569},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.