Title: Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures
Abstract: We propose 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: Our scheme can be used to authenticate linear transformations of signed data, such as those arising when computing mean and Fourier transform or in networks that use network coding. Our construction gives an example of a cryptographic primitive — homomorphic signatures over $\mathbb{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. 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 can be viewed as "removing the random oracle" from the signatures of Gentry, Peikert, and Vaikuntanathan at the expense of only allowing a small number of signatures.