Paper 2018/861
Delegating Computations with (almost) Minimal Time and Space Overhead
Justin Holmgren and Ron D. Rothblum
Abstract
The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space.
Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. FOCS 2018
- Keywords
- Delegation schemesargumentno-signaling proofs
- Contact author(s)
- rothblum @ cs technion ac il
- History
- 2018-09-22: received
- Short URL
- https://ia.cr/2018/861
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/861, author = {Justin Holmgren and Ron D. Rothblum}, title = {Delegating Computations with (almost) Minimal Time and Space Overhead}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/861}, year = {2018}, url = {https://eprint.iacr.org/2018/861} }