International Association
for Cryptologic Research

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.

We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem Ham_alpha (the language of bit vectors with Hamming weight at least alpha), surpassing previously known results for this problem. We demonstrate the usefulness of the one-sided error property in applications: no malicious party can frame an honest prover as cheating by presenting verifier randomness that leads to a rejection. We show proofs of proximity for Ham_alpha with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For n-bit input vectors, highlighting input query complexity, our MA has O(log n) query complexity, the PCP makes O(loglog n) queries, and the IOP makes a single input query. The prover in all of our applications runs in expected quasi-linear time. Additionally, we show that any perfectly complete IP of proximity for Ham_alpha with input query complexity n^{1-epsilon} has proof length Omega(log n). Furthermore, we study PCPs of proximity where the verifier is restricted to making a single input query (SIQ). We show that any SIQ-PCP for Ham_alpha must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length n+o(n). As an application, we provide new methods that transform PCPs (and IOPs) for arbitrary languages with nonzero completeness error into PCPs (and IOPs) that exhibit perfect completeness. These transformations achieve parameters previously unattained.

A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate P is exactly n. We define security by modeling vPIR as an ideal functionality and following the real-ideal paradigm. Starting from a standard PIR scheme, we construct a vPIR scheme for any database property that can be verified by a machine that reads the database once and maintains a bounded size state between rows. We also construct vPIR with public verification based on LWE or on DLIN. The main technical hurdle is to demonstrate a simulator that extracts a long input from an adversary that sends a single short message. Our vPIR constructions are based on the notion of batch argument for NP. As contribution of independent interest, we show that batch arguments are equivalent to quasi-arguments---a relaxation of SNARKs which is known to imply succinct argument for various sub-classes of NP.