Paper 2024/599
Probabilistically Checkable Arguments for all NP
Abstract
A probabilistically checkable argument (PCA) is a computational relaxation of PCPs, where soundness is guaranteed to hold only for false proofs generated by a computationally bounded adversary. The advantage of PCAs is that they are able to overcome the limitations of PCPs. A succinct PCA has a proof length that is polynomial in the witness length (and is independent of the nondeterministic verification time), which is impossible for PCPs, under standard complexity assumptions. Bronfman and Rothblum (ITCS 2022) constructed succinct PCAs for NC that are publiclyverifiable and have constant query complexity under the subexponential hardness of LWE. We construct a publiclyverifiable succinct PCA with constant query complexity for all NP in the adaptive security setting. Our PCA scheme offers several improvements compared to the Bronfman and Rothblum construction: (1) it applies to all problems in NP, (2) it achieves adaptive security, and (3) it can be realized under any of the following assumptions: the polynomial hardness of LWE; $O(1)$LIN on bilinear maps; or subexponential DDH. Moreover, our PCA scheme has a succinct prover, which means that for any 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 complexitypreserving RAM delegation scheme that is used in our PCA construction and may be of independent interest.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published by the IACR in EUROCRYPT 2024
 Keywords
 PCPsuccinct argumentsinstance compressionRAM delegation
 Contact author(s)
 shany bendavid @ biu ac il
 History
 20240525: revised
 20240417: received
 See all versions
 Short URL
 https://ia.cr/2024/599
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/599, author = {Shany BenDavid}, title = {Probabilistically Checkable Arguments for all {NP}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/599}, year = {2024}, url = {https://eprint.iacr.org/2024/599} }