Groth10#

[Gro10]

Product Argument#

Consider three commitments

\[ c=g^{r} \prod_{i \in[n]} g_{i}^{a_{i}} \quad d=g^{s} \prod_{j \in[n]} g_{j(n+1)}^{b_{j}} \quad v=g^{t} \prod_{i \in[n]} g_{i}^{u_{i}} \quad \forall i \in[n]: u_{i}=a_{i} b_{i} \]

Permutation Argument#

Constant Size NIZK Argument for Circuit Satisfiability#

CNARG

NAND-gate circuit \(C\)

GM17#

[GM17]

CY21

Alessandro Chiesa and Eylon Yogev. Subquadratic snargs in the random oracle model. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, 711–741. Cham, 2021. Springer International Publishing. URL: https://link.springer.com/chapter/10.1007/978-3-030-84242-0_25.

Gro10

Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In ASIACRYPT. 2010. URL: https://www.iacr.org/archive/asiacrypt2010/6477323/6477323.pdf.

GM17

Jens Groth and Mary Maller. Snarky signatures: minimal signatures of knowledge from simulation-extractable snarks. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, 581–612. Cham, 2017. Springer International Publishing. URL: https://eprint.iacr.org/2017/540.pdf.

SNARGs in the Random Oracle Model#

ROM-SNARGs

  • [CY21] have constructed a ROM-SNARG of proof length of \(O(\log (t / \varepsilon) \cdot \log t \cdot \log n)\), and hence slightly overcome the “quadratic” barrier.

SNARGs in Other Models#