International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Probabilistically Checkable Arguments for all NP

Authors:
Shany Ben-David , Bar-Ilan University
Download:
DOI: 10.1007/978-3-031-58734-4_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: A probabilistically checkable argument ($\mathsf{PCA}$) is a computational relaxation of $\mathsf{PCP}$s, where soundness is guaranteed to hold only for false proofs generated by a computationally bounded adversary. The advantage of $\mathsf{PCA}$s is that they are able to overcome the limitations of $\mathsf{PCP}$s. A \emph{succinct} $\mathsf{PCA}$ has a proof length that is polynomial in the witness length (and is independent of the non-deterministic verification time), which is impossible for $\mathsf{PCP}$s, under standard complexity assumptions. Bronfman and Rothblum (ITCS 2022) constructed succinct $\mathsf{PCA}$s for $\mathsf{NC}$ that are publicly-verifiable and have constant query complexity under the sub-exponential hardness of $\mathsf{LWE}$. We construct a publicly-verifiable succinct $\mathsf{PCA}$ with constant query complexity for all $\mathsf{NP}$ in the adaptive security setting. Our $\mathsf{PCA}$ scheme offers several improvements compared to the Bronfman and Rothblum construction: (1) it applies to all problems in $\mathsf{NP}$, (2) it achieves adaptive security, and (3) it can be realized under any of the following assumptions: the \emph{polynomial} hardness of $\mathsf{LWE}$; $O(1)$-$\mathsf{LIN}$; or sub-exponential $\mathsf{DDH}$. Moreover, our $\mathsf{PCA}$ scheme has a \emph{succinct prover}, which means that for any $\mathsf{NP}$ relation that can be verified in time $T$ and space $S$, the proof can be generated in time $O_{\lambda,m}(T\cdot\mathrm{polylog}(T))$ and space $O_{\lambda,m}(S\cdot\mathrm{polylog}(T))$. Here, ${O}_{\lambda,m}$ accounts for polynomial factors in the security parameter and in the size of the witness. En route, we construct a new \emph{complexity-preserving} $\mathsf{RAM~Delegation}$ scheme that is used in our $\mathsf{PCA}$ construction and may be of independent interest.
BibTeX
@inproceedings{eurocrypt-2024-33920,
  title={Probabilistically Checkable Arguments for all NP},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58734-4_12},
  author={Shany Ben-David},
  year=2024
}