Probabilistically Checkable Arguments for All NP

A probabilistically checkable argument ( \(\textsf{PCA}\) ) is a computational relaxation of \(\textsf{PCP}\) s, where soundness is guaranteed to hold only for false proofs generated by a computationally bounded adversary. The advantage of \(\textsf{PCA}\) s is that they are able to overcome the limitations of \(\textsf{PCP}\) s. A succinct \(\textsf{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 \(\textsf{PCP}\) s, under standard complexity assumptions. Bronfman and Rothblum (ITCS 2022) constructed succinct \(\textsf{PCA}\) s for \(\textsf{NC}\) that are publicly-verifiable and have constant query complexity under the sub-exponential hardness of \(\textsf{LWE}\) . We construct a publicly-verifiable succinct \(\textsf{PCA}\) with constant query complexity for all \(\textsf{NP}\) in the adaptive security setting. Our \(\textsf{PCA}\) scheme offers several improvements compared to the Bronfman and Rothblum construction: (1) it applies to all problems in \(\textsf{NP}\) , (2) it achieves adaptive security, and (3) it can be realized under any of the following assumptions: the polynomial hardness of \(\textsf{LWE}\) ; O(1)- \(\textsf{LIN}\) ; or sub-exponential \(\textsf{DDH}\) . Moreover, our \(\textsf{PCA}\) scheme has a succinct prover, which means that for any \(\textsf{NP}\) relation that can be verified in time T and space S, the proof can be generated in time \(O_{\lambda ,m}(T\cdot \textrm{polylog}(T))\) and space \(O_{\lambda ,m}(S\cdot \textrm{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 complexity-preserving \(\mathsf {RAM~Delegation}\) scheme that is used in our \(\textsf{PCA}\) construction and may be of independent interest.