SPARKs: Succinct Parallelizable Arguments of Knowledge
Abstract
We introduce the notion of aSuccinct Parallelizable Argument of Knowledge(SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel timeTwith at mostpprocessors:—The prover’s (parallel) running time is\( T + \mathrm{poly}\hspace{-2.0pt}\log (T \cdot p) \). (In other words, the prover’s running time is essentiallyTfor large computation times!)
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 27, 2022
- Source ID
- 10.1145/3549523
Entities
People
- Cody Freitag
- Ilan Komargodski
- Naomi Ephraim
- Rafael Pass
Organizations
- Air Force Office of Scientific Research
- Cornell Tech
- Defense Advanced Research Projects Agency
- Hebrew University of Jerusalem
- Intelligence Advanced Research Projects Activity
- National Science Foundation
- Office of the Director of National Intelligence