Quadratic Span Programs and Succinct NIZKs without PCPs
The authors introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. Their main motivation is the construction of succinct arguments of NP-statements that are quick to construct and verify. QSPs seem well-suited for this task, perhaps even better than Probabilistically Checkable Proofs (PCPs). In 2010, Groth constructed a NIZK argument in the Common Reference String (CRS) model for Circuit-SAT consisting of only 42 elements in a bilinear group. Interestingly, this argument does not (explicitly) use PCPs. But this scheme has some disadvantages, namely, the CRS size and prover computation are both quadratic in the circuit size.