Paper 2011/018

Homomorphic Signatures for Polynomial Functions

Dan Boneh and David Mandell Freeman

Abstract

We construct the first homomorphic signature scheme that is capable of evaluating multivariate polynomials on signed data. Given the public key and a signed data set, there is an efficient algorithm to produce a signature on the mean, standard deviation, and other statistics of the signed data. Previous systems for computing on signed data could only handle linear operations. For polynomials of constant degree, the length of a derived signature only depends logarithmically on the size of the data set. Our system uses ideal lattices in a way that is a ``signature analogue'' of Gentry's fully homomorphic encryption. Security is based on hard problems on ideal lattices similar to those in Gentry's system.

Note: An extended abstract of this work will appear in Eurocrypt 2011. This is the full version.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
homomorphic signaturesidealslattices
Contact author(s)
dabo @ cs stanford edu
History
2011-04-05: last of 2 revisions
2011-01-10: received
See all versions
Short URL
https://ia.cr/2011/018
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/018,
      author = {Dan Boneh and David Mandell Freeman},
      title = {Homomorphic Signatures for Polynomial Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/018},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/018}},
      url = {https://eprint.iacr.org/2011/018}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.