[Resource Topic] 2014/469: Homomorphic Signatures with Efficient Verification for Polynomial Functions

Welcome to the resource topic for 2014/469

Homomorphic Signatures with Efficient Verification for Polynomial Functions

Authors: Dario Catalano, Dario Fiore, 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.

ePrint: https://eprint.iacr.org/2014/469

Talk: https://www.youtube.com/watch?v=u-U66Oe6miA

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .