Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures
D. Boneh and
We construct a linearly 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.
Our scheme can be used to authenticate linear transformations of signed data,
such as those arising when computing mean and least squares fit or in networks
that use network coding. Our construction gives an example of a cryptographic
primitive -- homomorphic signatures over F2
-- 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
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 formulation of the k-SIS problem adds
to the ``toolbox'' of lattice-based cryptography and may be useful in
constructing other lattice-based cryptosystems.
As a second application of the new k-SIS tool, we construct an ordinary
signature scheme and prove it k-time unforgeable in the standard model
assuming the hardness of the k-SIS problem. Our construction
has shorter public keys than other lattice-based signatures with the same
In proceedings of PKC'11, LNCS 6571, pp. 1-16.