SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK

CRS model · GS08 · security loss: additive: soundness is perfect, and zero knowledge loses at most twice the DDH advantage in each of ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$, for switching the commitment key from binding to hiding

Statement

Under SXDH over a Type-3 pairing group, systems of pairing-product, multi-scalar-multiplication and quadratic equations over the group have non-interactive witness-indistinguishable proofs in the common reference string model, and NIZK proofs for multi-scalar-multiplication and quadratic equations and for pairing-product equations whose target is $1$ (or a product of pairings of public elements). Circuit satisfiability is a system of quadratic equations, so every $\mathbf{NP}$ language has a NIZK proof of size linear in the circuit — GS08.

Sketch

The CRS is a commitment key for group elements and exponents; under SXDH a binding key (extractable, giving soundness) and a hiding key (perfectly hiding, with a simulation trapdoor, giving zero knowledge) are indistinguishable. A proof consists of commitments to the witness plus group elements that make the equation verify once the commitment randomness cancels.

Notes

• GS08 also instantiate the proofs under the subgroup decision assumption and under DLIN — GS08.