Back to search

Cornell University

Leveraging Parallelism in Interactive Proofs

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sirkin, Naomi
Chair dc:contributor.chair
  • Pass, Rafael N.
Committee members dc:contributor.committeemember
  • Shi, Runting
  • Kleinberg, Robert David

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15578871
Dc Identifier Other
ProQuest Submission ID: 13262
ProQuest Publication ID: 29323627

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sirkin, Naomi. Leveraging Parallelism in Interactive Proofs. Doctor of Philosophy thesis, Cornell University, 2022. https://hdl.handle.net/1813/112060