### Parallelizable Delegation from LWE

##### Abstract

We present the first non-interactive delegation scheme for P with time-tight parallel prover efficiency based on standard hardness assumptions. More precisely, in a time-tight delegation scheme–which we refer to as a SPARG (succinct parallelizable argument)–the prover's parallel running time is t + polylog(t), while using only polylog(t) processors and where t is the length of the computation. (In other words, the proof is computed essentially in parallel with the computation, with only some minimal additive overhead in terms of time). Our main results show the existence of a publicly-verifiable, non-interactive, SPARG for P assuming polynomial hardness of LWE. Our SPARG construction relies on the elegant recent delegation construction of Choudhuri, Jain, and Jin (FOCS'21) and combines it with techniques from Ephraim et al (EuroCrypt'20). We next demonstrate how to make our SPARG time-independent–where the prover and verifier do not need to known the running-time t in advance; as far as we know, this yields the first construction of a time-tight delegation scheme with time-independence based on any hardness assumption. We finally present applications of SPARGs to the constructions of VDFs (Boneh et al, Crypto'18), resulting in the first VDF construction from standard polynomial hardness assumptions (namely LWE and the minimal assumption of a sequentially hard function).

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
succinct argument verifiable delay function delegation scheme
Contact author(s)
cfreitag @ cs cornell edu
rafael @ cs cornell edu
nephraim @ cs cornell edu
History
2022-08-09: approved
See all versions
Short URL
https://ia.cr/2022/1025

CC BY

BibTeX

@misc{cryptoeprint:2022/1025,
author = {Cody Freitag and Rafael Pass and Naomi Sirkin},
title = {Parallelizable Delegation from LWE},
howpublished = {Cryptology ePrint Archive, Paper 2022/1025},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1025}},
url = {https://eprint.iacr.org/2022/1025}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.