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.

Available format(s)
Category
Public-key cryptography
Publication info
Keywords
homomorphic signaturesverifiable computation
Contact author(s)
dario fiore @ imdea org
History
Short URL
https://ia.cr/2014/469

CC BY

BibTeX

@misc{cryptoeprint:2014/469,
author = {Dario Catalano and Dario Fiore and Bogdan Warinschi},
title = {Homomorphic Signatures with Efficient Verification for Polynomial Functions},
howpublished = {Cryptology ePrint Archive, Paper 2014/469},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/469}},
url = {https://eprint.iacr.org/2014/469}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.