CryptoDB
Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | Succinct arguments allow a powerful (yet polynomial-time) prover to convince a weak verifier of the validity of some NP statement using very little communication. A major barrier to the deployment of such proofs is the unwieldy overhead of the prover relative to the complexity of the statement to be proved. In this work, we focus on complexity-preserving arguments where proving a non-deterministic time $t$ and space $s$ RAM computation takes time $\tilde O(t)$ and space $\tilde O(s)$. Currently, all known complexity-preserving arguments either are private-coin, rely on non-standard assumptions, or provide only weak succinctness. In this work, we construct complexity-preserving succinct argument based solely on collision-resistant hash functions, thereby matching the classic succinct argument of Kilian (STOC '92). |
BibTeX
@inproceedings{eurocrypt-2024-33964,
title={Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58737-5_5},
author={Cody Freitag and Omer Paneth and Rafael Pass},
year=2024
}