Welcome to the resource topic for 2024/599
Title:
Probabilistically Checkable Arguments for all NP
Authors: Shany Ben-David
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 non-deterministic verification time), which is impossible for PCPs, under standard complexity assumptions. Bronfman and Rothblum (ITCS 2022) constructed succinct PCAs for NC that are publicly-verifiable and have constant query complexity under the sub-exponential hardness of LWE.
We construct a publicly-verifiable 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 sub-exponential 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 complexity-preserving RAM delegation scheme that is used in our PCA construction and may be of independent interest.
ePrint: https://eprint.iacr.org/2024/599
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .