You are looking at a specific version 20140621:045642 of this paper. See the latest version.

Paper 2014/469

Homomorphic Signatures with Efficient Verification for Polynomial Functions

Dario Catalano, Dario Fiore, and Bogdan Warinschi

Abstract

A homomorphic signature scheme for a class of functions $\mathcal{C}$ allows a client to sign and upload elements of some data set $D$ on a server. At any later point, the server can derive a (publicly verifiable) signature that certifies that some $y$ is the result computing some $f\in\mathcal{C}$ on the basic data set $D$. This primitive has been formalized by Boneh and Freeman (Eurocrypt 2011) who also proposed the only known construction for the class of multivariate polynomials of fixed degree $d\geq 1$. In this paper we construct new homomorphic signature schemes for such functions. Our schemes provide the first alternatives to the one of Boneh-Freeman, and improve over their solution in three main aspects. First, our schemes do not rely on random oracles. Second, we obtain security in a stronger fully-adaptive model: while the solution of Boneh-Freeman requires the adversary to query messages in a given data set all at once, our schemes can tolerate adversaries that query one message at a time, in a fully-adaptive way. Third, signature verification is more efficient (in an amortized sense) than computing the function from scratch. The latter property opens the way to using homomorphic signatures for publicly-verifiable computation on outsourced data. Our schemes rely on a new assumption on leveled graded encodings which we show to hold in a generic model.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2014
Keywords
homomorphic signaturesverifiable computation
Contact author(s)
dario fiore @ imdea org
History
2014-06-21: received
Short URL
https://ia.cr/2014/469
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.