In this work, we construct the first (leveled) fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data. Only the maximal depth $d$ of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices and satisfies full (adaptive) security. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a data-set. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different data-sets. The complexity of verifying a signature for a computation $f$ is at least as large as that of computing $f$, but can be amortized when verifying the same computation over many different data-sets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation.
These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree.
As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures. We construct HTDFs by relying on the techniques developed by Gentry et al. (CRYPTO '13) and Boneh et al. (EUROCRYPT '14) in the contexts of fully homomorphic and attribute-based encryptions.Category / Keywords: foundations / Homomorphic Signatures, Lattices, Outsourcing Computation Date: received 22 Oct 2014, last revised 7 Nov 2014 Contact author: sergeyg at mit edu Available format(s): PDF | BibTeX Citation Note: This is a merged version of Eprint 2014/463 and 2014/451, with additional results. Version: 20141107:164321 (All versions of this report) Short URL: ia.cr/2014/897 Discussion forum: Show discussion | Start new discussion