International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

SPARKs: Succinct Parallelizable Arguments of Knowledge

Authors:
Naomi Ephraim , Cornell Tech
Cody Freitag , Cornell Tech
Ilan Komargodski , NTT Research
Rafael Pass , Cornell Tech
Download:
DOI: 10.1007/978-3-030-45721-1_25 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument system with the following three properties for computing and proving a time T (non-deterministic) computation: - The prover's (parallel) running time is T + polylog T. (In other words, the prover's running time is essentially T for large computation times!) - The prover uses at most polylog T processors. - The communication complexity and verifier complexity are both polylog T. While the third property is standard in succinct arguments, the combination of all three is desirable as it gives a way to leverage moderate parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover's parallel running time is not allowed. Our main results are the following, all for non-deterministic polynomial-time RAM computation. We construct (1) an (interactive) SPARK based solely on the existence of collision-resistant hash functions, and (2) a non-interactive SPARK based on any collision-resistant hash function and any SNARK with quasi-linear overhead (as satisfied by recent SNARK constructions).
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30247,
  title={SPARKs: Succinct Parallelizable Arguments of Knowledge},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Succinct arguments;SNARK;verifiable computation;interactive proofs},
  volume={12105},
  doi={10.1007/978-3-030-45721-1_25},
  author={Naomi Ephraim and Cody Freitag and Ilan Komargodski and Rafael Pass},
  year=2020
}