International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Homomorphic Signatures over Binary Fields: Secure Network Coding with Small Coefficients

Authors:
Dan Boneh
David Mandell Freeman
Download:
URL: http://eprint.iacr.org/2010/453
Search ePrint
Search Google
Abstract: We propose a new signature scheme that can be used to authenticate data and prevent pollution attacks in networks that use network coding. At its core, our system is a homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals: - It is the first such scheme that authenticates vectors defined over *binary fields*; previous proposals could only authenticate vectors with large or growing coefficients. - It is the first such scheme based on the problem of finding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based cryptosystems. Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems. Our construction gives an example of a cryptographic primitive -- homomorphic signatures over F_2 -- that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete-log type problems.
BibTeX
@misc{eprint-2010-23354,
  title={Homomorphic Signatures over Binary Fields: Secure Network Coding with Small Coefficients},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Lattice-based cryptography, homomorphic signatures, network coding},
  url={http://eprint.iacr.org/2010/453},
  note={ dfreeman@cs.stanford.edu 14842 received 20 Aug 2010},
  author={Dan Boneh and David Mandell Freeman},
  year=2010
}