Leveled Fully Homomorphic Signatures from Standard Lattices
In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature σ[subscript f,y] certif...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2017
|
| Online Access: | http://hdl.handle.net/1721.1/112962 https://orcid.org/0000-0002-2666-0045 |
| _version_ | 1811084860046966784 |
|---|---|
| author | Gorbunov, Sergey Vaikuntanathan, Vinod Wichs, Daniel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gorbunov, Sergey Vaikuntanathan, Vinod Wichs, Daniel |
| author_sort | Gorbunov, Sergey |
| collection | MIT |
| description | In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature σ[subscript f,y] certifying that y is the correct output of the computation f. Anybody can verify the tuple (f, y, σ[subscript f,y]) using Alice's public verification key and become convinced of this fact without having to retrieve the entire underlying data. 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 dataset. 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 datasets. 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 datasets. 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. |
| first_indexed | 2024-09-23T12:58:44Z |
| format | Article |
| id | mit-1721.1/112962 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:58:44Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1129622022-10-01T12:19:32Z Leveled Fully Homomorphic Signatures from Standard Lattices Gorbunov, Sergey Vaikuntanathan, Vinod Wichs, Daniel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gorbunov, Sergey Vaikuntanathan, Vinod In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature σ[subscript f,y] certifying that y is the correct output of the computation f. Anybody can verify the tuple (f, y, σ[subscript f,y]) using Alice's public verification key and become convinced of this fact without having to retrieve the entire underlying data. 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 dataset. 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 datasets. 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 datasets. 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. Microsoft Corporation (PhD Fellowship) Northrop Grumman Cybersecurity Research Consortium United States. Defense Advanced Research Projects Agency (Grant FA8750-11-2-0225) Alfred P. Sloan Foundation (Research Fellowship) National Science Foundation (U.S.) (Frontier Grant CNS-1414119) 2017-12-29T15:09:12Z 2017-12-29T15:09:12Z 2015-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-3536-2 http://hdl.handle.net/1721.1/112962 Gorbunov, Sergey, Vinod Vaikuntanathan, and Daniel Wichs. “Leveled Fully Homomorphic Signatures from Standard Lattices.” Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC ’15 (2015), 14-17 June, 2015, Portland, Oregaon, Association for Computing Machinery, pp. 469-477. https://orcid.org/0000-0002-2666-0045 en_US http://dx.doi.org/10.1145/2746539.2746576 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC '15 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT Web Domain |
| spellingShingle | Gorbunov, Sergey Vaikuntanathan, Vinod Wichs, Daniel Leveled Fully Homomorphic Signatures from Standard Lattices |
| title | Leveled Fully Homomorphic Signatures from Standard Lattices |
| title_full | Leveled Fully Homomorphic Signatures from Standard Lattices |
| title_fullStr | Leveled Fully Homomorphic Signatures from Standard Lattices |
| title_full_unstemmed | Leveled Fully Homomorphic Signatures from Standard Lattices |
| title_short | Leveled Fully Homomorphic Signatures from Standard Lattices |
| title_sort | leveled fully homomorphic signatures from standard lattices |
| url | http://hdl.handle.net/1721.1/112962 https://orcid.org/0000-0002-2666-0045 |
| work_keys_str_mv | AT gorbunovsergey leveledfullyhomomorphicsignaturesfromstandardlattices AT vaikuntanathanvinod leveledfullyhomomorphicsignaturesfromstandardlattices AT wichsdaniel leveledfullyhomomorphicsignaturesfromstandardlattices |