## Cryptology ePrint Archive: Report 2010/453

**Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures**

*Dan Boneh and David Mandell Freeman*

**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:

- 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.

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.

**Category / Keywords: **public-key cryptography / Lattice-based cryptography, homomorphic signatures, k-time signatures

**Publication Info: **An extended abstract of this paper will appear in PKC 2011.

**Date: **received 20 Aug 2010, last revised 9 May 2011

**Contact author: **dfreeman at cs stanford edu

**Available format(s): **PDF | BibTeX Citation

**Note: **New version with many updates.

**Version: **20110509:221952 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]