International Association for Cryptologic Research

International Association
for Cryptologic Research


On Black-Box Knowledge-Sound Commit-And-Prove SNARKs

Helger Lipmaa , University of Tartu, Tartu, Estonia
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: Gentry and Wichs proved that adaptively sound SNARGs for hard languages need non-falsifiable assumptions. Lipmaa and Pavlyk claimed Gentry-Wichs is tight by constructing a non-adaptively sound zk-SNARG FANA for NP from falsifiable assumptions. We show that FANA is flawed. We define and construct a fully algebraic $F$-position-binding vector commitment scheme VCF. We construct a concretely efficient commit-and-prove zk-SNARK Punic, a version of FANA with an additional VCF commitment to the witness. Punic satisfies semi-adaptive black-box $G$-knowledge-soundness, a new natural knowledge-soundness notion for commit-and-prove SNARKs. We use a new proof technique to achieve global consistency using a functional somewhere-extractable commitment scheme to extract vector commitment's local proofs.
  title={On Black-Box Knowledge-Sound Commit-And-Prove SNARKs},
  author={Helger Lipmaa},