# Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures

**Authors:**

*D. Boneh and D. Freeman*

** Abstract: **

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.

_{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. 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 properties.

** Reference:**

In proceedings of PKC'11, LNCS 6571, pp. 1-16.

**Full paper:**
pdf