Paper 2014/469

Homomorphic Signatures with Efficient Verification for Polynomial Functions

Dario Catalano, Dario Fiore, and Bogdan Warinschi


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)
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2014
homomorphic signaturesverifiable computation
Contact author(s)
dario fiore @ imdea org
2014-06-21: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.