CryptoDB
Homomorphic Signatures over Binary Fields: Secure Network Coding with Small Coefficients
Authors: | |
---|---|
Download: | |
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 }