## CryptoDB

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

Authors: Dan Boneh David Mandell Freeman URL: http://eprint.iacr.org/2010/453 Search ePrint Search Google 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
}