DLOG ⇒ Succinct arguments for NP (Bootle et al.)

Fully-black-box reduction · CRS model · BCCGP16

Statement

If DLOG is hard in prime-order groups, arithmetic circuit satisfiability has a public-coin zero-knowledge interactive argument with $O(\log N)$ rounds and $O(\log N)$ group and field elements of communication for circuits with $N$ fan-in-2 gates, in which prover and verifier computation is linear in $N$; its public parameters are uniformly random group elements, the generators of a Pedersen multicommitment — BCCGP16. Its core is a zero-knowledge argument of knowledge of openings of two Pedersen multicommitments satisfying an inner-product relation, with logarithmic communication and interaction and linear computation for prover and verifier — BCCGP16.

Notes

• Fiat–Shamir leaves the verifier’s running time unchanged, so the non-interactive argument it gives in the random-oracle model has logarithmic proofs and a linear-time verifier — standard.
• Bulletproofs shorten the inner-product argument, giving range proofs of $2{\log }_{2}n+9$ group and field elements for $n$-bit ranges, aggregation of $m$ range proofs at an additive $O(\log m)$ group elements, and logarithmic-size proofs for general arithmetic circuits, from DLOG with no trusted setup and linear-time verification — BBB+18.
• BCCGP16 also give a commitment to a polynomial with verifiable evaluation at any point, which gives an optimized version of Groth’s constant-round argument with square-root communication — BCCGP16. Committing to the coefficient vector with a Pedersen multicommitment and proving evaluations with the inner-product argument gives a transparent polynomial commitment scheme with logarithmic openings: DLOG ⇒ PCS — BCMS20.