Paper 2022/1025

Parallelizable Delegation from LWE

Cody Freitag, Cornell Tech
Rafael Pass, Cornell Tech, Tel-Aviv University
Naomi Sirkin, Cornell Tech

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)
Publication info
succinct argument verifiable delay function delegation scheme
Contact author(s)
cfreitag @ cs cornell edu
rafael @ cs cornell edu
nephraim @ cs cornell edu
2022-08-09: approved
2022-08-08: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.