Bilinear pairing + q-DLOG ⇒ zk-SNARK (Groth16 in the AGM)

Algebraic group model · FKL18, Gro16 · security loss: tight

Statement

In the algebraic group model, knowledge soundness of Groth’s preprocessing SNARK for QAP satisfiability over an asymmetric bilinear group reduces tightly to the $(q_1,q_2)$-DLOG assumption in that group, for $q_1,q_2$ polynomial in the size of the QAP — FKL18; the construction is perfectly zero-knowledge, unconditionally — Gro16. It is therefore a zk-SNARK for every algebraic prover if $q$-DLOG holds.

Notes

• Gro16’s own knowledge-soundness proof is in the generic bilinear group model: Bilinear pairing ⇒ zk-SNARK — Gro16.
• A proof is 3 group elements (2 in ${\mathbb{G}}_1$, 1 in ${\mathbb{G}}_2$), verified with one pairing-product equation of 3 pairings, and for $m$ wires and $n$ multiplication gates the CRS has about $m+2n$ elements of ${\mathbb{G}}_1$ and $n$ of ${\mathbb{G}}_2$ — Gro16.