Let me augment the abstract with a few comments (which are based on reading oarts of the introduction). First, the notion of succinct used here refers to the additive term comes on top of the witness length, which is unavoibdable in the current context (of proofs rather than arguments). Specifically, for a witness relation that is computable by depth $D$ circuits of size $S$ is essentially $m^{2/3}\cdot\poly(D,\log S))$, where $m$ is the length of the witness, which is assumed to be polynomially related to the length of the input. Third, the result holds using the minimal assumption (i.e., the existence of one-way functions); furthermore, it makes black-box use of the one-eway function and achieves negligible soundness error.
A key component in the new protocol is a new construction of a statistically binding polynomial commitment scheme (PCS), which allows a sender to commit to a large polynomial P such that later it can prove the correctness of evaluations (i.e., correctness of claims of the type “P(x) = y”). They contruct a succinct PCS for multilinear polynomials, over any sufficiently large field, in which the communication is only additively larger than the description size of the polynomial.
Zero-knowledge proofs allow to encode a computation so that it can be verified without revealing any additional information beyond its correctness. In this work we focus on proofs that are statistically sound meaning that even an unbounded prover cannot make the verifier accept a false statement, except with negligible probability, and computationally zero-knowledge. The seminal result of Goldreich, Micali and Wigderson (CRYPTO 1986) shows that, assuming the existence of a one-way function, such zero-knowledge proofs exist for all languages in NP.
Some of the early protocols, such as that of GMW, have a large polynomial overhead in communication compared to the original NP witness. A line of works has shown that in many cases this communication overhead can be avoided. Most recently, Athamnah et al. (TCC 2024) constructed zero-knowledge proofs for all bounded-depth NP relations, where the communication complexity is only larger by an additive factor than the original NP witness. The main caveat of their result is that the protocol makes a non-blackbox use of the one-way function.
In this work we show that such succinct zero-knowledge proofs exist for the same class of NP relations, where the protocol makes only a blackbox use of a one-way function. Our protocol achieves a negligible soundness error, in contrast to recent works which can achieve, at best, an inverse polynomial error.
See ECCC TR25-162.