Leveraging Parallelism in Interactive Proofs

Other Titles


Interactive proof systems enable one party (the prover) to convince another (the verifier) of the validity of some computational statement, and ensure that the verifier will be convinced if and only if the statement is true. Since their introduction, interactive proofs have become one of the most fundamental concepts in theoretical computer science, and have led to breakthrough results across complexity theory and modern cryptography. In recent years, there has been immense interest in succinct proof systems, which enable the verifier to certify computations much faster than computing them. However, the efficiency of these proof systems, specifically the time required to generate a proof, remains a major bottleneck between theory and practice. In this thesis, we approach this challenge through the lens of parallelism. We first consider whether the aforementioned bottleneck can be overcome by leveraging access to parallel processors.In existing proof systems, the time to generate a proof scales at least polylogarithmically with the complexity of the statement being proven–that is, proving correctness of a T-time computation requires time T * polylog(T). In this thesis, we introduce a new paradigm for proof systems in which the prover uses only polylog(T) processors to both compute and prove a T-time computation in time T + polylog(T)–that is, near-optimal parallel time allowing only a small additive overhead. We call such a system a SPARK, or a SPARG when proving only deterministic computations, and show the following: - Constant-round SPARKs for NP from collision-resistant hash functions. - Non-interactive SPARKs for NP from collision-resistant hash functions and succinct non-interactive arguments of knowledge. - Non-interactive SPARGs for P from LWE. Finally, we focus on proof systems for a specific task–that of efficiently verifying that a "long" computation was done correctly. This is captured by the notion of a Verifiable Delay Function (VDF). We obtain the first construction of a VDF in the plain model that relies only on the minimal assumption of a sequential function, along with standard assumptions, by showing that SPARGs for P imply VDFs. In the latter part of this thesis, we introduce a new type of VDF that is more amenable to distributed settings, called a Continuous VDF, and give a construction in the random oracle model based on the repeated squaring assumption. As an additional contribution, we show that the hardness of computing Nash equilibria can be based on the existence of Continuous VDFs.

Journal / Series

Volume & Issue


368 pages


Date Issued




interactive proof; succinct argument; verifiable delay function


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Pass, Rafael N.

Committee Co-Chair

Committee Member

Shi, Runting
Kleinberg, Robert David

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Attribution 4.0 International


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record