Welcome to the resource topic for 2014/451
Title:
Leveled Fully Homomorphic Signatures from Standard Lattices
Authors: Daniel Wichs
Abstract:In a homomorphic signature scheme, a user Alice signs some large data x using her secret signing key and stores the signed data on a server. The server can then run some computation y=g(x) on the signed data and homomorphically produce a short signature \sigma. Anybody can verify the signature using Alice’s public verification key and become convinced that y is the correct output of the computation g over Alice’s data, without needing to have the underlying data itself. In this work, we construct the first leveled fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data, where only the maximal depth d of the circuit needs to be fixed a priori. The size of the evaluated signature grows polynomially in d, but is otherwise independent of the circuit size or the data size. Our solutions are based on the hardness of the small integer solution (SIS) problem, which is in turn implied by the worst-case hardness of problems in standard lattices. We get a scheme in the standard model, albeit with large public parameters whose size must exceed the total size of all signed data. In the random-oracle model, we get a scheme with short public parameters. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature scheme due to Boneh and Freeman (Eurocrypt '11). As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF). We show to how construct homomorphic signatures using HTDFs as a black box. We construct HTDFs based on the SIS problem by relying on a recent technique developed by Boneh et al. (Eurocrypt '14) in the context of attribute based encryption.
ePrint: https://eprint.iacr.org/2014/451
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 .